|
Reachability of inequalities from Lame's theorem
I. D. Kan Moscow Aviation Institute (National Research University)
Abstract:
In this paper, the following result is proved. The number of steps in Euclid's algorithm for two natural arguments, the smaller of which has $v$ digital digits in the decimal system, does not exceed the integer part of the fraction \linebreak $(v+ \lg ({\sqrt{5}}/ {\Phi}))/ \lg \Phi$, where $\Phi=(1+\sqrt{5})/2$, and this estimate is achieved for every natural $v$. It is also proved that partial or asymptotic reachability is valid for the other two known upper bounds on the length of the Euclid algorithm.
Key words:
Lame's theorem, Euclid's algorithm.
Received: 05.11.2023 Accepted: 24.05.2024
Citation:
I. D. Kan, “Reachability of inequalities from Lame's theorem”, Dal'nevost. Mat. Zh., 24:1 (2024), 45–54
Linking options:
https://www.mathnet.ru/eng/dvmg530 https://www.mathnet.ru/eng/dvmg/v24/i1/p45
|
Statistics & downloads: |
Abstract page: | 56 | Full-text PDF : | 38 | References: | 14 |
|