|
%I #33 Jun 17 2020 05:40:00
%S 0,1,2,2,3,2,3,4,3,3,4,4,5,4,4,4,4,5,5,4,6,4,5,4,5,5,5,5,6,6,6,5,5,7,
%T 5,5,6,5,6,6,6,6,6,6,6,6,7,6,7,7,6,6,6,5,8,6,6,6,6,7,6,6,6,7,7,7,7,7,
%U 7,6,7,6,7,7,7,8,6,6,8,8,8,7,7,6,7,7,7,7,9,6,7,7,7,7,7,6,8,7,7,7
%N Maximum length of Euclidean algorithm starting with n and any nonnegative i<n.
%C Apart from initial term, same as A071647. - _Franklin T. Adams-Watters_, Nov 14 2006
%C Records occur when n is a Fibonacci number. For n>1, the smallest i such that the algorithm requires a(n) steps is A084242(n). The maximum number of steps a(n) is greater than k for n > A188224(k). - _T. D. Noe_, Mar 24 2011
%C Largest term in n-th row of A051010. - _Reinhard Zumkeller_, Jun 27 2013
%C a(n)+1 is the length of the longest possible continued fraction expansion (in standard form) of any rational number with denominator n. - _Ely Golden_, May 18 2020
%H T. D. Noe, <a href="/A034883/b034883.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 GCDSteps[n1_, n2_] := Module[{a = n1, b = n2, cnt = 0}, While[b > 0, cnt++; {a, b} = {Min[a, b], Mod[Max[a, b], Min[a, b]]}]; cnt]; Table[Max @@ Table[GCDSteps[n, i], {i, 0, n - 1}], {n, 100}] (* _T. D. Noe_, Mar 24 2011 *)
%o (Haskell)
%o a034883 = maximum . a051010_row -- _Reinhard Zumkeller_, Jun 27 2013
%o (Python)
%o def euclid_steps(a,b):
%o step_count = 0
%o while(b != 0):
%o a , b = b , a % b
%o step_count += 1
%o return step_count
%o for n in range(1,1001):
%o l = 0
%o for i in range(n): l = max(l,euclid_steps(n,i))
%o print(str(n)+" "+str(l)) # _Ely Golden_, May 18 2020
%K easy,nonn
%O 1,3
%A _Erich Friedman_
|
