login
Maximum length of Euclidean algorithm starting with n and any nonnegative i<n.
10

%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_