Asymptotic behaviour of the first moment of the number of steps in the by-excess and by-deficiency Euclidean algorithms. (English. Russian original) Zbl 1292.11139

Sb. Math. 203, No. 2, 288-305 (2012); translation from Mat. Sb. 203, No. 2, 143-160 (2012).
For \(a/b\in(0,1]\) denote by \(s(a/b)\) the length of the standard continued fraction expansion \[ \frac{a}{b}=\frac{1}{a_1+{\atop\ddots\,\displaystyle{+\frac{1}{a_s}}}}, \] and let \(l(a/b)\) be a length of reduced regular continued fraction \[ \frac{a}{b}=1-\frac{1}{b_1-{\atop\ddots\,\displaystyle{-\frac{1}{b_l}}}}\qquad(b_1, \ldots, b_l\geq 2). \] It was known (see [A. V. Ustinov, Izv. Math. 72, No. 5, 1023–1059 (2008); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 72, No. 5, 189–224 (2008; Zbl 1211.11009)]; [E. N. Zhabitskaya, Math. Notes 89, No. 3, 450–454 (2011); translation from Mat. Zametki 89, No. 3, 472–472 (2011; Zbl 1306.11010)]) that average lengths \[ E^+(R)=\frac{2}{[R]([R]+1)}\sum\limits_{b\leq R}\sum\limits_{a\leq b}s\left(\frac{a}{b}\right),\qquad E^-(R)=\frac{2}{[R]([R]+1)}\sum\limits_{b\leq R}\sum\limits_{a\leq b}l\left(\frac{a}{b}\right) \] satisfy asymptotic formulae \[ E^+(R)=c_1^+\log R+c_0^++O(\omega^+(R)),\qquad E^-(R)=c_2^+\log^2 R+c_1^+\log R+c_0^++O(\omega^-(R)) \] with some explicit constants \(c_i^\pm\) and the error terms \[ \omega^\pm(R)=O(R^{-1}\log^5R). \] The author proves sharper estimates \[ \omega^+(R)=O(R^{-1}\log^3R),\tag{1} \]
\[ \omega^-(R)=O(R^{-1}\log^3R). \tag{2} \] It is interesting that the proof of the estimate (2) uses some ideas from Selberg’s elementary proof of the prime number theorem.
Estimates (1) and (2) are nearly optimal, although \(\Omega\)-theorems for \(\omega^\pm(R)\) are not known. According to numerical experiments performed by the author, the error terms \(\omega^\pm(R)\) should satisfy the estimates \[ \omega^+(R)=O(R^{-1}\log R),\qquad \omega^-(R)=O(R^{-1}\log^2 R). \]


11Y16 Number-theoretic algorithms; complexity
11A55 Continued fractions
11K50 Metric theory of continued fractions
Full Text: DOI