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 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

      Identifiers