On analogues of Heilbronn's theorem (Q2150617)

A detailed analysis of the Euclidean algorithm leads to various problems concerning the statistical properties of finite continued fractions. If the input data of the algorithm are positive integers \(c\) and \(d\), \(c < d\), then the number of divisions performed, which coincides with the number \(h(c/d)\) of partial quotients in the continued fraction \(c/d = [0; t_1, \ldots, t_h]\). Heilbronn was the first who studied the average behaviour of \(h(c/d)\). In [Abh. Zahlentheorie Anal., 87--96 (1968; Zbl 0212.06503)] he proved the asymptotic formula \[\dfrac{1}{\varphi(d)}\sum\limits_{\substack{1\le c\le d\\ (c,d)=1}}s(c/d)= \dfrac{2\log 2}{\zeta(2)}\log d+O(\log^4\log d).\] The key idea was to reduce this value to the number of solutions of equation \(xx'+yy'=d\), where \(x>y\), \(x'>y'\), \((x,y)=1\) and \((x',y')=1\). In the present paper the author studies modifications of Euclidean algorithm proposed in [\textit{J. Sorenson}, ``The k-ary gcd algorithm'', Technical Report CS-TR-90-979. Madison, WI: University of Wisconsin (1990)]. For each modification he reduces the average number of steps to some complicated system of equations.