On the average number of steps in the Euclidean algorithm
type: Item
instance of: scholarly article
title: On the average number of steps in the Euclidean algorithm
zbMATH Open document ID: 0502.10002
author: Hans Kilian
published in: Elemente der Mathematik
publication date: 1983-01-01T00:00:00Z
full work available at URL: https://eudml.org/doc/141302
review text: 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)].
reviewed by: Fritz Schweiger
Mathematics Subject Classification ID: 11A55
zbMATH DE Number: 3790506
zbMATH Keywords: asymptotic result
zbMATH Keywords: length of Euclidean algorithm
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 3790506