Zaoly's blog

By Zaoly, history, 8 months ago,

Assume two integers $a$ and $b$ ($1 \le b < a$) that form an ordered integer pair $(a, b)$. We can perform a Euclidean division on it, which will make it $(b, a \bmod b)$. If we keep performing this division, then $b$ will eventually be $0$. We define $k$ as the number of Euclidean divisions needed to make $b$ equal $0$.

Example: $(19, 8)$ → $(8, 3)$ → $(3, 2)$ → $(2, 1)$ → $(1, 0)$. We perform $4$ divisions until $b$ equals $0$, so $k = 4$.

With the value of $k$ specified ($1 \le k \le 10^9$), how to find any ordered integer pair $(a, b)$ ($1 \le b < a \le 10^{18}$) that needs exactly $k$ Euclidean division to make $b$ equal $0$? If there does not exist such a pair, report it.

I am also curious about one question: it is all known that the Euclidean algorithm is fast, but the speed of the algorithm is determined by $k$, so may $k$ be infinitely large?

• +5

 » 8 months ago, # | ← Rev. 2 →   0 As shown in this Stack Overflow post about time complexity of Euclid's Algorithm, it's logarithmitic time. Since a and b are at most 10^18, K will be very small and can easily fit in a short (dtype).
•  » » 8 months ago, # ^ |   0 You solved my second question. Thank you!
 » 8 months ago, # |   0 Auto comment: topic has been updated by Zaoly (previous revision, new revision, compare).
 » 8 months ago, # |   0 Auto comment: topic has been updated by Zaoly (previous revision, new revision, compare).
 » 8 months ago, # | ← Rev. 2 →   +1 Consider using consecutive fibonacci numbers for a and b. Note that if we take $a=2, b=1$, it terminates in one step. For $a=3, b=2$ it terminates in 2 steps.Let us define $f_{1}=1, f_{2}=2, f_{k+1}=f_{k}+f_{k-1} \space (\text{for} \space k\ge 2)$In general, take $a=f_{k+1}=f_{k}+f_{k-1}, b=f_{k}$. In the next step we get $a=f_{k}, b=f_{k-1}$. It's easy to see by induction that this will terminate in $k$ steps.Since the sequence of fibonacci numbers is infinite, we can solve this problem for arbitrarily large $k$.
•  » » 8 months ago, # ^ |   0 There is no doubt that the constructing method through Fibonacci sequence is correct, but this method does not guarantee a pair where $a$ and $b$ do not exceed $\boldsymbol {10^{18}}$ (when $k = 86$, then $a = 1\,100\,087\,778\,366\,101\,931$, which exceeds $10^{18}$), which forces us to find the minimal solution. By my brute force, in most conditions, this is indeed the minimal result. I wonder how to prove it.
•  » » » 8 months ago, # ^ |   0 maybe the solution by SebastianMestre gives the minimal solution (start by taking (2,1) and we generate the minimal next pair from (2,1) -> (3,2) and continuing the same from (3,2))
•  » » » 8 months ago, # ^ |   0 sir it's easy to see it's minimum.
 » 8 months ago, # |   0 Another way to prove that K is tiny is that a mod b makes b at most half of a when a >= b. Splitting in half means it's logarithmic.