On the average number of steps in the Euclidean algorithm (Q1172658)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the average number of steps in the Euclidean algorithm |
scientific article; zbMATH DE number 3790506
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the average number of steps in the Euclidean algorithm |
scientific article; zbMATH DE number 3790506 |
Statements
On the average number of steps in the Euclidean algorithm (English)
0 references
1983
0 references
For two natural numbers \(a,b\) satisfying \(1\leq a,b\leq N\) denote by \(T(a,b)\) the length of the Euclidean algorithm. Let \(T(N)=N^{-2}\sum_{a,b} T(a,b)\), then the author proves \[ T(N)=12\pi^{-2}(\log 2)(\log N)+O\left((\log N)^{\frac 12+\varepsilon}\right). \] A sharper estimate was given by \textit{G. Lochs} [Monatsh. Math. 65, 27--52 (1961; Zbl 0097.03602)].
0 references
asymptotic result
0 references
length of Euclidean algorithm
0 references
