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?
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).
You solved my second question. Thank you!
Auto comment: topic has been updated by Zaoly (previous revision, new revision, compare).
Auto comment: topic has been updated by Zaoly (previous revision, new revision, compare).
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$$$.
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.
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))
sir it's easy to see it's minimum.
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.