×

Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm. (English. Russian original) Zbl 1211.11009

Izv. Math. 72, No. 5, 1023-1059 (2008); translation from Izv. Ross. Akad. Nauk, Ser. Mat. 72, No. 5, 189-224 (2008).
Let \([0;t_1;t_2;\dots t_s]\) be the continued fraction of length \(s=s(c/d)\) for rational number \(c/d\) with \(1\leq c <d\). In addition, let \(s(1)=0\). The quantity \(s(c/d)\) coincides with the number of steps in the Euclidean algorithm applied to the numbers \(c\) and \(d\). For real \(R\geq 2\) denote \[ \text{E}(R)=\frac{2}{[R]([R]+1)}\sum\limits_{d\leq R}\sum\limits_{c\leq d}s\left(\frac{c}{d}\right),\;\text{ D}(R)=\frac{2}{[R]([R]+1)}\sum\limits_{d\leq R}\sum\limits_{c\leq d}\left(s\left(\frac{c}{d}\right)-\text{E}(R)\right)^2. \] The asymptotic formulas for the quantities \(\text{E}(R)\) and \( \text{ D}(R) \) are obtained in the case when \(R\rightarrow\infty\).

MSC:

11A55 Continued fractions
11K65 Arithmetic functions in probabilistic number theory
11N37 Asymptotic results on arithmetic functions
PDFBibTeX XMLCite
Full Text: DOI