zbMATH — the first resource for mathematics

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).$

MSC:
 11Y16 Number-theoretic algorithms; complexity 11A55 Continued fractions 11K50 Metric theory of continued fractions
Citations:
Zbl 1211.11009; Zbl 1306.11010
Full Text: