A084242 -id:A084242 - cp's OEIS frontend

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

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

Offset: 1

Erich Friedman

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

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

a034883 = maximum . a051010_row  -- Reinhard Zumkeller, Jun 27 2013

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

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

A036543 a(n) = T(3,n), array T given by A048471.

Original entry on oeis.org

1, 9, 33, 105, 321, 969, 2913, 8745, 26241, 78729, 236193, 708585, 2125761, 6377289, 19131873, 57395625, 172186881, 516560649, 1549681953, 4649045865, 13947137601, 41841412809, 125524238433, 376572715305, 1129718145921

Offset: 0

Clark Kimberling

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-3).

n-th difference of a(n), a(n-1), ..., a(0) is 2^(n+2) for n=1, 2, 3, ...

Cf. A146541 (inv. bin. transf.)

[4*3^n-3: n in [0..30]]; // Vincenzo Librandi, Nov 11 2011

4*3^Range[0,25]-3 (* or *) LinearRecurrence[{4,-3},{1,9},25] (* Harvey P. Dale, Aug 16 2011 *)

vector(30, n, n--; 4*3^n-3) \\ G. C. Greubel, Nov 23 2018

[4*3^n-3 for n in range(30)] # G. C. Greubel, Nov 23 2018

Binomial transform of A084242. Second binomial transform of periodic sequence A010688. - Paul Barry, May 23 2003
From Paul Barry, May 23 2003: (Start)
a(n) = 4*3^n - 3;
G.f.: (1+5*x)/((1-x)*(1-3*x));
E.g.f.: 4*exp(3*x) - 3*exp(x). (End)
a(n) = 4*a(n-1) - 3*a(n-2); a(0)=1, a(1)=9. - Harvey P. Dale, Aug 16 2011
a(n) = 3*a(n-1) + 6. - Vincenzo Librandi, Nov 11 2011
a(n) = A171498(n) - 2. - Philippe Deléham, Apr 13 2013

A089642 Numbers m such that there is a single k, 1 <= k <= m, such that the number of elements in the continued fraction for m/k is maximum.

Original entry on oeis.org

1, 3, 4, 5, 8, 12, 13, 15, 21, 30, 34, 39, 40, 42, 48, 55, 56, 65, 72, 74, 80, 89, 102, 110, 130, 144, 168, 170, 176, 180, 185, 193, 194, 208, 233, 272, 275, 288, 297, 299, 312, 336, 340, 377, 400, 445, 456, 468, 517, 546, 550, 610, 638, 699, 715, 720, 754, 777

Offset: 1

Benoit Cloitre, Jan 01 2004

nonn

Except for 2, all Fibonacci numbers are in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..250

Cf. A000045, A084242.

q[n_] := Count[len = Length[ContinuedFraction[n/#]] & /@ Range[n], Max[len]] == 1; Select[Range[1000], q] (* Amiram Eldar, Jun 14 2022 *)

for(n=1,330,if(sum(s=1,n,if(length(contfrac(n/s))-vecmax(vector(n,i,length(contfrac(n/i)))),0,1))==1,print1(n,",")))

More terms from Jinyuan Wang, Apr 06 2020

A122700 Numbers k such that the length of the continued fraction for (k/m) is maximized for a unique m (1 < m < k).

Original entry on oeis.org

2, 3, 4, 5, 8, 12, 13, 15, 21, 30, 34, 39, 40, 42, 48, 55, 56, 65, 72, 74, 80, 89, 102, 110, 130, 144, 168, 170, 176, 180, 185, 193, 194, 208, 233, 272, 275, 288, 297, 299, 312, 336, 340, 377, 400, 445, 456, 468, 517, 546, 550, 610, 638, 699, 715, 720, 754, 777

Offset: 1

Benoit Cloitre, Oct 25 2006

nonn

Sequence contains all the Fibonacci numbers greater than 1 (A020695).

			5/2 = [2, 2], 5/3 = [1, 1, 2], 5/4 = [1, 4]; thus the continued fraction for 5/m is maximized at the unique value m=3, and 5 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..500

Cf. A020695, A084242.

Cf. A089642. - R. J. Mathar, Aug 02 2008

cfQ[v_] := Count[v, Max[v]] == 1; q[n_] := cfQ[Length[ContinuedFraction[#/n]] & /@ Range[2, n - 1]]; Join[{2}, Select[Range[3, 1000], q]](* Amiram Eldar, Jun 25 2022 *)

A364405 Numbers k such that k is never the smallest number which requires the maximum number of steps for the Euclidean algorithm for computing gcd(k,m) for any m > k.

Original entry on oeis.org

12, 16, 20, 24, 38, 46, 48, 50, 54, 56, 66, 70, 78, 81, 84, 88, 91, 96, 98, 99, 100, 104, 116, 122, 126, 130, 132, 135, 138, 141, 148, 150, 155, 156, 161, 162, 164, 166, 168, 176, 180, 182, 193, 196, 200, 201, 204, 205, 210, 212, 214, 218, 220, 228, 232, 234, 236

Offset: 1

John Metcalf, Jul 22 2023

nonn

Positive numbers not in A084242.

Cf. A084242, A051010.

def gcdsteps(k, m)
  k.zero? ? 0 : 1 + gcdsteps(m % k, k)
end
flags = [nil, *1..2000]
(1..flags.length).each do |m|
  scores = []
  (1..m).each do |k|
    scores << [gcdsteps(k, m), k]
  end
  flags[scores.sort_by { |n| -n[0] }.first[1]] = nil
end
puts flags[1..flags.length / 2].compact

A089636 Least k, 1 <= k <= 2^n, such that the continued fraction for 2^n/k contains the maximum number of elements.

Original entry on oeis.org

1, 3, 5, 9, 23, 39, 79, 158, 281, 741, 1145, 2297, 4495, 10111, 20223, 40446, 80983, 162009, 323369, 646271, 1216723, 2592211, 5184422, 9733109, 20739329, 41467565, 81559503, 163649289, 311481083, 662667007, 1325334527, 2628708543, 5308871023, 9627863373

Offset: 1

Benoit Cloitre, Jan 01 2004

nonn

From Jon E. Schoenfield, Nov 05 2014: (Start)
Several terms are close to 2^n / phi, where phi = (1 + sqrt(5))/2 = 1.6180339... (see A001622); e.g., 2^22/a(22) = 4194304/2592211 = 1.6180411... .
When a ratio r of two integers is expressed as a continued fraction, it cannot have a relatively large number of elements (i.e., relative to other fractions whose numerators and denominators are very roughly the same size as the numerator and denominator of r, respectively) if any of the elements of the continued fraction are large, so the elements of the continued fractions for 2^n / a(n) tend to consist only of small numbers, mostly ones; e.g., 131072/80983 = cf[1; 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 5, 1, 1, 3] (20 elements, consisting of 17 ones, 2 threes, and 1 five).
For n = 1..34, the maximum number of elements is 1, 2, 4, 4, 5, 7, 9, 9, 10, 12, 12, 14, 15, 17, 19, 19, 20, 22, 22, 24, 26, 27, 27, 29, 30, 32, 33, 34, 35, 37, 39, 39, 41, 41.
If a(n) is even, then a(n) = 2*a(n-1), so 2^n/a(n) reduces to 2^(n-1)/a(n-1), and the maximum number of elements is the same at n as it is at n-1. Up to n=34, a(n) is even only at n = 8, 16, and 23. (End)

			From _Jon E. Schoenfield_, Nov 05 2014: (Start)
The continued fractions for 2^3/k for k = 1..2^3 are
8/1 = 8 (1 element)
8/2 = 4 (1 element)
8/3 = 2 + 1/(1 + 1/2) = cf[2;1,2] (3 elements)
8/4 = 2 (1 element)
8/5 = 1 + 1/(1 + 1/(1 + 1/2)) = cf[1;1,1,2] (4 elements)
8/6 = 4/3 = 1 + 1/3 = cf[1;3] (2 elements)
8/7 = 1 + 1/7 = cf[1;7] (2 elements)
8/8 = 1 (1 element)
so the first (and, in this case, only) value of k at which the maximum number of elements (i.e., 4) occurs is k=5; thus, a(3)=5. (End)

Cf. A084242.

a(n) = A084242(2^n).

More terms from Jon E. Schoenfield, Nov 05 2014

A089641 Number of k, 1<=k<=n, such that the number of elements in the continued fraction for n/k is maximum.

Original entry on oeis.org

1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 2, 1, 2, 4, 2, 2, 3, 1, 4, 2, 5, 3, 3, 2, 2, 2, 1, 2, 2, 4, 1, 2, 4, 2, 4, 1, 1, 4, 1, 2, 2, 3, 2, 2, 1, 2, 2, 4, 2, 4, 8, 1, 1, 5, 2, 4, 2, 8, 6, 5, 2, 1, 2, 2, 3, 2, 3, 4, 1, 3, 1, 2, 2, 7, 5, 2, 1, 2, 2, 2, 8, 2, 2, 4, 2, 1, 5, 2, 4, 4, 4, 2, 6, 2, 8, 2, 6, 6, 1, 2, 2, 2

Offset: 1

Benoit Cloitre, Jan 01 2004

nonn

Cf. A084242.

a(n)=sum(s=1,n,if(length(contfrac(n/s))-vecmax(vector(n,i,length(contfrac(n/i)))),0,1))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Programs

Haskell

Mathematica

Python

A036543 a(n) = T(3,n), array T given by A048471.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A089642 Numbers m such that there is a single k, 1 <= k <= m, such that the number of elements in the continued fraction for m/k is maximum.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A122700 Numbers k such that the length of the continued fraction for (k/m) is maximized for a unique m (1 < m < k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A364405 Numbers k such that k is never the smallest number which requires the maximum number of steps for the Euclidean algorithm for computing gcd(k,m) for any m > k.

Views

Author

Keywords

Comments

Crossrefs

Programs

Ruby

A089636 Least k, 1 <= k <= 2^n, such that the continued fraction for 2^n/k contains the maximum number of elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A089641 Number of k, 1<=k<=n, such that the number of elements in the continued fraction for n/k is maximum.

Views

Author

Keywords

Crossrefs

Programs

PARI