Find Any Integer Pair That Needs Exactly K Euclidean Divisions to Make One of Them Zero

Правка en1, от Zaoly, 2023-12-19 06:30:58

Assume two integers $$$a$$$ and $$$b$$$ ($$$a > b$$$) 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 the number of Euclidean divisions needed to make $$$b$$$ equal $$$0$$$ as $$$k$$$.

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?

Теги euclidean algorithm, division, constructive

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Zaoly 2023-12-19 07:18:27 14
en3 Английский Zaoly 2023-12-19 07:07:44 10 Tiny change: 'and $b$ ($a > b$) that fo' -> 'and $b$ ($1 \le b < a$) that fo'
en2 Английский Zaoly 2023-12-19 07:06:04 12
en1 Английский Zaoly 2023-12-19 06:30:58 964 Initial revision (published)