|
|
A034883
|
|
Maximum length of Euclidean algorithm starting with n and any nonnegative i<n.
|
|
10
|
|
|
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
|
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
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
|
|
|
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)
(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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|