

A034883


Maximum length of Euclidean algorithm starting with n and any 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


LINKS

T. D. Noe, Table of n, a(n) for n=1..1000
Eric W. Weisstein, MathWorld: 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


CROSSREFS

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


KEYWORD

easy,nonn,changed


AUTHOR

Erich Friedman


STATUS

approved



