A051012 - OEIS

A051012

Denominator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0 <= m < n.

%I #17 Apr 22 2022 05:31:39

%S 1,2,1,1,5,6,7,4,9,10,11,3,13,14,15,8,17,18,19,5,21,2,23,4,25,26,9,7,

%T 29,30,31,16,11,34,35,9,37,38,13,4,41,42,43,1,15,46,47,8,49,50,51,13,

%U 53,54,55,28,19,58,59,15,61,62,63,32,65,6,67,17,69,70,71,36,73,74,75

%N Denominator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0 <= m < n.

%H Reinhard Zumkeller, <a href="/A051012/b051012.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EuclideanAlgorithm.html">Euclidean Algorithm</a>.

%t t[m_, n_] := For[r[-1]=m; r[0]=n; k=1, True, k++, r[k] = Mod[r[k-2], r[k-1]]; If[r[k] == 0, Return[k-1]]]; a[n_] := Denominator[Sum[t[m, n], {m, 0, n}]/n]; Array[a, 100] (* _Amiram Eldar_, Apr 22 2022 after _Jean-François Alcover_ at A051010 *)

%o (Haskell)

%o import Data.Ratio ((%), denominator)

%o a051012 n = denominator $ (sum $ a051010_row n) % n

%o -- _Reinhard Zumkeller_, Jun 27 2013

%Y Cf. A034883, A051010, A051011 (numerators).

%K nonn,frac

%O 1,2

%A _Eric W. Weisstein_