cp's OEIS Frontend

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

%I A034883 #34 Feb 16 2025 08:32:37
%S A034883 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 A034883 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 A034883 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 A034883 Maximum length of Euclidean algorithm starting with n and any nonnegative i<n.
%C A034883 Apart from initial term, same as A071647. - _Franklin T. Adams-Watters_, Nov 14 2006
%C A034883 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 A034883 Largest term in n-th row of A051010. - _Reinhard Zumkeller_, Jun 27 2013
%C A034883 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 A034883 T. D. Noe, <a href="/A034883/b034883.txt">Table of n, a(n) for n=1..1000</a>
%H A034883 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EuclideanAlgorithm.html">Euclidean Algorithm</a>
%t A034883 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 A034883 (Haskell)
%o A034883 a034883 = maximum . a051010_row  -- _Reinhard Zumkeller_, Jun 27 2013
%o A034883 (Python)
%o A034883 def euclid_steps(a,b):
%o A034883     step_count = 0
%o A034883     while(b != 0):
%o A034883         a , b = b , a % b
%o A034883         step_count += 1
%o A034883     return step_count
%o A034883 for n in range(1,1001):
%o A034883     l = 0
%o A034883     for i in range(n): l = max(l,euclid_steps(n,i))
%o A034883     print(str(n)+" "+str(l)) # _Ely Golden_, May 18 2020
%K A034883 easy,nonn
%O A034883 1,3
%A A034883 _Erich Friedman_