Finding largest viable step size, simple

Question

I have a set of rational numbers $t_0, t_1, t_2, \dots ,t_n$ in strictly ascending order $t_i < t_j$ where $i < j$.

My goal is to find the largest possible step size $\Delta t \in \mathbb Q$ such that for all $k$ there's a $c_k \in \mathbb N$ such that $t_0+c_k\Delta t = t_k$

For instance, if $t_0 = 0, t_1 = 1, t_2 = 2.5$ then the maximum step size is $\Delta t = 0.5$

Must $c_k$ be an integer? If so, for some lists of real numbers there is no such step, for example for the real numbers $0,1,\sqrt2.$ — David K, Dec 15 '19 at 12:17
My mistake - $t_i$ and $\Delta t$ are rational. $c_k$ must be integer. — Oria Gruber, Dec 15 '19 at 12:23

score 0 · Accepted Answer · answered Dec 15 '19 at 12:55

You can apply the Euclidean Algorithm to find the greatest common divisor (GCD) of $t_1 - t_0$ and $t_2 - t_0.$ Say the result is $\Delta t_1.$ Then apply the algorithm again to find the GCD of $\Delta t_1$ and $t_3 - t_0.$ Take the result of that, call it $\Delta t_2$, then find the GCD of $\Delta t_2$ and $t_4 - t_0.$ Continue in this way until every $t_k - t_0$ has been treated.

There is also a way to apply something like Euclid's algorithm to all the differences $t_k - t_0$ in parallel, but I don't have any reason to think it's more efficient than the method above.

Finding largest viable step size, simple

1 Answers1