Geodesic
The average length of reduced regular continued fractions
Sbornik. Mathematics, Tome 200 (2009) no. 8, pp. 1181-1214 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $l(a/b)$ be the number of steps of the by-excess Euclidean algorithm applied to the numbers $a$ and $b$. In this paper we obtain a three-term asymptotic formula for the expectation of the random value $l(a/b)$, when $1\le a\le b\le R$ and $R\to\infty$. Bibliography: 11 titles.
Keywords: Euclidean algorithm, division by-excess, average length, continued fraction. 
@article{SM_2009_200_8_a4,
     author = {E. N. Zhabitskaya},
     title = {The average length of reduced regular continued fractions},
     journal = {Sbornik. Mathematics},
     pages = {1181--1214},
     year = {2009},
     volume = {200},
     number = {8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2009_200_8_a4/}
}
TY  - JOUR
AU  - E. N. Zhabitskaya
TI  - The average length of reduced regular continued fractions
JO  - Sbornik. Mathematics
PY  - 2009
SP  - 1181
EP  - 1214
VL  - 200
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/SM_2009_200_8_a4/
LA  - en
ID  - SM_2009_200_8_a4
ER  - 
%0 Journal Article
%A E. N. Zhabitskaya
%T The average length of reduced regular continued fractions
%J Sbornik. Mathematics
%D 2009
%P 1181-1214
%V 200
%N 8
%U http://geodesic.mathdoc.fr/item/SM_2009_200_8_a4/
%G en
%F SM_2009_200_8_a4
E. N. Zhabitskaya. The average length of reduced regular continued fractions. Sbornik. Mathematics, Tome 200 (2009) no. 8, pp. 1181-1214. http://geodesic.mathdoc.fr/item/SM_2009_200_8_a4/

[1] O. Perron, Die Lehre von den Kettenbrüchen. Band I. Elementare Kettenbrüche, Teuber, Stuttgart, 1954 | MR | Zbl

[2] Yu. Yu. Finkel'shtein, “Klein polygons and reduced regular continued fractions”, Russian Math. Surveys, 48:3 (1993), 198–200 | DOI | MR | Zbl

[3] H. Heilbronn, “On the average length of a class of finite continued fractions”, Number theory and analysis (papers in honor of E. Landau), Plenum, New York, 1968, 87–96 | MR | Zbl

[4] J. W. Porter, “On a theorem of Heilbronn”, Matematika, 22:1 (1975), 20–28 | MR | Zbl

[5] B. Vallée, “A unifying framework for the analysis of a class of Euclidean algorithms”, LATIN 2000: Theoretical informatics (Punta del Este, Uruguay, 2000), Lecture Notes in Comput. Sci., 1776, Springer-Verlag, Berlin, 343–354 | DOI | MR | Zbl

[6] A. V. Ustinov, “Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm”, Russian Math. Surveys, 72:5 (2008), 1023–1059 | DOI | MR | Zbl

[7] B. Vallée, “Dynamical analysis of a class of Euclidean algorithms”, Theoret. Comput. Sci., 297:1–3 (2003), 447–486 | DOI | MR | Zbl

[8] A. Karatsuba, Basic analytic number theory, Springer-Verlag, Berlin, 1993 | MR | MR | Zbl | Zbl

[9] A. Ya. Khinchin, Izbrannye trudy po teorii chisel, MTsNMO, M., 2006 | MR

[10] A. C. Yao, D. E. Knuth, “Analysis of the subtractive algorithm for greatest common divisors”, Proc. Nat. Acad. Sci. U.S.A., 72:12 (1975), 4720–4722 | DOI | MR | Zbl

[11] A. I. Galochkin, Yu. V. Nesterenko, A. B. Shidlovskii, Vvedenie v teoriyu chisel, Izd-vo MGU, M., 1984 | MR | Zbl