A Simple Estimate for the Number of Steps in the Euclidean Algorithm (Q5612612)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3335209
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A Simple Estimate for the Number of Steps in the Euclidean Algorithm |
scientific article; zbMATH DE number 3335209 |
Statements
A Simple Estimate for the Number of Steps in the Euclidean Algorithm (English)
0 references
1971
0 references
0.8927937746047974
0 references
0.8386254906654358
0 references
For any pair of integers \(0<u\le v\) we define \(L(u,v)\) to be the number of steps required in the Euclidean algorithm to calculate the greatest common denominator. Consider the values of \(L(u,v)\) when \(0 <u\le v\le x\). It is a classical result that \(L(u,v) \le 2.1(\log x+1)\); the worst cases are when \(u\) and \(u\) are consecutive Fibonacci numbers. The author recently proved (using results from metric number theory) that for each \(\varepsilon>0\) the inequality \[ \vert L(u,v) - (12\pi^{-2} \log 2) \log x\vert < (\log x)^{1/2+ \varepsilon} \] holds for almost all pairs \(u,v\) as \(x\to\infty\) [the author, J. Number Theory 2, 414--422 (1970; Zbl 0206.33502)]. The present note shows how to prove a weaker (but qualitatively correct) result in a few lines. Specifically it is shown that the proportion of pairs \(u,v\) which fail to satisfy \[ \tfrac12 \log x \le L(u,v) \le 2.1(\log x+ 1)\] tends to 0 as ''fast'' as \(x^{-1/100}\).
0 references