On the average number of steps in the Euclidean algorithm
From MaRDI portal
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)].
Recommendations
- A Simple Estimate for the Number of Steps in the Euclidean Algorithm
- On the asymptotic analysis of the Euclidean algorithm
- The number of steps in the Euclidean algorithm
- Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
- The mean number of steps in the Euclidean algorithm with odd partial quotients
Cited in
(9)- The mean number of steps in the Euclidean algorithm with least absolute value remainders
- On crepant resolutions of 2-parameter series of Gorenstein cyclic quotient singularities
- Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm
- A Simple Estimate for the Number of Steps in the Euclidean Algorithm
- The number of steps in the Euclidean algorithm
- Bias in the number of steps in the Euclidean algorithm and a conjecture of Ito on Dedekind sums
- Reachability of inequalities from Lame's theorem
- The number of steps in the Euclidean algorithm over complex quadratic fields
- On the asymptotic analysis of the Euclidean algorithm
This page was built for publication: On the average number of steps in the Euclidean algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1172658)
