login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. Adams-Watters, 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 n-th 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 13:24 EDT 2021. Contains 348049 sequences. (Running on oeis4.)