

A034883


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


9



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

Apart from initial term, same as A071647.  Franklin T. AdamsWatters, Nov 14 2006
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
Largest term in nth row of A051010.  Reinhard Zumkeller, Jun 27 2013
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


LINKS

T. D. Noe, Table of n, a(n) for n=1..1000
Eric Weisstein's World of Mathematics, Euclidean Algorithm


MATHEMATICA

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 *)


PROG

(Haskell)
a034883 = maximum . a051010_row  Reinhard Zumkeller, Jun 27 2013
(Python)
def euclid_steps(a, b):
step_count = 0
while(b != 0):
a , b = b , a % b
step_count += 1
return step_count
for n in range(1, 1001):
l = 0
for i in range(n): l = max(l, euclid_steps(n, i))
print(str(n)+" "+str(l)) # Ely Golden, May 18 2020


CROSSREFS

Sequence in context: A238943 A070081 A071647 * A338643 A051125 A321126
Adjacent sequences: A034880 A034881 A034882 * A034884 A034885 A034886


KEYWORD

easy,nonn


AUTHOR

Erich Friedman


STATUS

approved



