This article is cited in 12 papers

Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm

A. V. Ustinov

Institute for Applied Mathematics, Khabarovsk Division, Far-Eastern Branch of the Russian Academy of Sciences

Abstract: We prove asymptotic formulae with two significant terms for the expectation and variance of the random variable $s(c/d)$ when the variables $c$ and $d$ range over the set $1\leq c\leq d\leq R$ and $R\to\infty$, where $s(c,d)=s(c/d)$ is the number of steps in the Euclidean algorithm applied to the numbers $c$ and $d$.

UDC: 511.335+511.336

MSC: 11K50, 11A55

Received: 27.03.2007

DOI: 10.4213/im2640

 English version: Izvestiya: Mathematics, 2008, 72:5, 1023–1059

Bibliographic databases:

• 
• 
• 
• 
• 
• 
•