A051010 -id:A051010 - cp's OEIS frontend

A130130 a(0)=0, a(1)=1, a(n)=2 for n >= 2.

0, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Offset: 0

Paul Curtz, Aug 01 2007

a(n) is also total number of positive integers below 10^(n+1) requiring 9 positive cubes in their representation as sum of cubes (cf. Dickson, 1939).
A061439(n) + A181375(n) + A181377(n) + A181379(n) + A181381(n) + A181400(n) + A181402(n) + A181404(n) + a(n) = A002283(n).
a(n) = number of obvious divisors of n. The obvious divisors of n are the numbers 1 and n. - Jaroslav Krizek, Mar 02 2009
Number of colors needed to paint n adjacent segments on a line. - Jaume Oliver Lafont, Mar 20 2009
a(n) = ceiling(n-th nonprimes/n) = ceiling(A018252(n)/A000027(n)) for n >= 1. Numerators of (A018252(n)/A000027(n)) in A171529(n), denominators of (A018252(n)/A000027(n)) in A171530(n). a(n) = A171624(n) + 1 for n >= 5. - Jaroslav Krizek, Dec 13 2009
a(n) is also the continued fraction for sqrt(1/2). - Enrique Pérez Herrero, Jul 12 2010
For n >= 1, a(n) = minimal number of divisors of any n-digit number. See A066150 for maximal number of divisors of any n-digit number. - Jaroslav Krizek, Jul 18 2010
Central terms in the triangle A051010. - Reinhard Zumkeller, Jun 27 2013
Decimal expansion of 11/900. - Elmo R. Oliveira, May 05 2024

Leonard Eugene Dickson, All integers except 23 and 239 are sums of eight cubes, Bulletin of the American Mathematical Society 45 (1939), p. 588-591.
Eric Weisstein's World of Mathematics, Waring's Problem.
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A000005, A000027, A002283, A018252, A051010, A061439, A066150, A070824, A158411, A171529, A171530, A171624, A181375, A181377, A181379, A181381, A181400, A181402, A181404.

a130130 = min 2
a130130_list = 0 : 1 : repeat 2  -- Reinhard Zumkeller, Jun 27 2013

A130130[0]:=0; A130130[1]:=1; A130130[n_]:=2; (* Enrique Pérez Herrero, Jul 12 2010 *)
A130130[n_]:=ContinuedFraction[Sqrt[1/2],n+1][[n+1]] (* Enrique Pérez Herrero, Jul 12 2010 *)
Join[{0, 1},LinearRecurrence[{1},{2},96]] (* Ray Chandler, Sep 23 2015 *)
PadRight[{0,1},120,{2}] (* Harvey P. Dale, Sep 15 2022 *)

a(n)=min(n,2) \\ Charles R Greathouse IV, Jun 01 2011

G.f.: x*(1+x)/(1-x) = x*(1-x^2)/(1-x)^2. - Jaume Oliver Lafont, Mar 20 2009
a(n) = A000005(n) - A070824(n) for n >= 1.
E.g.f.: 2*exp(x) - x - 2. - Stefano Spezia, May 19 2024

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

Original entry on oeis.org

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

A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 2, 1, 1, 2, 2, 3, 3, 2, 1, 1, 1, 3, 1, 4, 2, 2, 1, 1, 2, 1, 2, 3, 2, 3, 2, 1, 1, 1, 2, 2, 1, 3, 3, 2, 2, 1, 1, 2, 3, 3, 2, 3, 4, 4, 3, 2, 1, 1, 1, 1, 1, 3, 1, 4, 2, 2, 2, 2, 1, 1, 2, 2, 2, 4, 2, 3, 5, 3, 3, 3, 2, 1, 1, 1, 3, 2, 3, 2, 1, 3, 4, 3, 4, 2, 2, 1

Offset: 1

Philippe Deléham, Jun 09 2005

Consequence of theorem of Gabriel Lamé (1844): the first value of m in this triangle is T(F(m+2), F(m+1)) where F(n) = A000045(n); example: the first 5 is T(F(7), F(6)) = T(13, 8).
From Bernard Schott, May 01 2022: (Start)
Theorem of Gabriel Lamé (1844): The number of divisions necessary to find the greatest common divisor of two natural numbers n > k by means of the Euclidean algorithm is never greater than five times the number of digits of the smaller number k (see link).
This upper bound 5*length(k) is the best possible; the smallest pairs (n, k) for which T(n, k) = 5 * length(k) when length(k) = 1, 2 or 3 are respectively  (F(7), F(6)), (F(12), F(11)) and (F(17), F(16)) where F(n) = A000045(n). This upper bound is not attained when length(k) >= 4. (End)

			13 = 5*2 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,5) = 4.
Triangle begins:
  1
  1 1
  1 2 1
  1 1 2 1
  1 2 3 2 1
  1 1 1 2 2 1
  1 2 2 3 3 2 1
  1 1 3 1 4 2 2 1
  1 2 1 2 3 2 3 2 1
  1 1 2 2 1 3 3 2 2 1
  1 2 3 3 2 3 4 4 3 2 1
  1 1 1 1 3 1 4 2 2 2 2 1
  1 2 2 2 4 2 3 5 3 3 3 2 1
  1 1 3 2 3 2 1 3 4 3 4 2 2 1
  1 2 1 3 1 2 2 3 3 2 4 2 3 2 1
  1 1 2 1 2 3 3 1 4 4 3 2 3 2 2 1
  1 2 3 2 3 3 3 2 3 4 4 4 3 4 3 2 1
  ..............................
Smallest examples with T(n, k) = 5 * length(k) (Theorem of Gabriel Lamé):
13 = 8*1 + 5, 8 = 5*1 + 3, 5 = 3*1 + 2, 3 = 2*1 + 1, 2 = 2*1 + 0 = so that T(13,8) = 5 = 5 * length(8).
144 = 89*1 + 55, 89 = 55*1 + 34, 55 = 34*1 + 21, 34 = 21*1 + 13, 21 = 13*1 + 8, then 5 steps already seen in the previous example, so that T(144,89) = 10 = 5 * length(89).
1597 = 987*1 + 610, 987 = 610*1 + 377, 610 = 377*1 + 233, 377 = 233*1 + 144, 233 = 144*1 + 89, then 10 steps already seen in the previous examples, so that T(1597,987) = 15 = 5 * length(987).

Ross Honsberger, Mathematical Gems II, Dolciani Mathematical Expositions No. 2, Mathematical Association of America, 1976, Chapter 7, A Theorem of Gabriel Lamé, pp. 54-57.
Wacław Sierpiński, Elementary Theory of Numbers, Theorem 12 (Lamé) p. 21, Warsaw, 1964.

Peter Kagey, Table of n, a(n) for n = 1..10000
Gabriel Lamé, Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers, Comptes rendus de l'Académie des sciences XIX, 1844, pages 867-870.
Wikipedia, Euclidean algorithm.
Wikipedia, Gabriel Lamé.

Cf. A000045, A001622, A002390, A034883, A049816, A051010, A055642.

F:= proc(n,k) option remember;
   if n mod k = 0 then 1
   else 1 + procname(k, n mod k)
   fi
end proc:
seq(seq(F(n,k),k=1..n), n=1..15); # Robert Israel, Feb 16 2016

T[n_, k_] := T[n, k] = If[Divisible[n, k], 1, 1 + T[k, Mod[n, k]]];
Table[T[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Apr 12 2019, after Robert Israel *)

T(n, k) = if ((n % k) == 0, 1, 1 + T(k, n % k)); \\ Michel Marcus, May 02 2022

T(n, k) = A049816(n, k) + 1.
From Robert Israel, Feb 16 2016: (Start)
T(n, k) = 1 if n == 0 (mod k), otherwise T(n, k) = 1 + T(k, (n mod k)).
G.f. G(x,y) of triangle satisfies G(x,y) = x*y/((1-x)*(1-x*y)) - Sum_{k>=1} (x^2*y)^k/(1-x^k) + Sum_{k>=1} G(x^k*y,x). (End)
From Bernard Schott, Apr 29 2022: (Start)
T(F(m+2), F(m+1)) = m where F(n) = A000045(n) (first comment).
T(n, k) <= 5 * length(k) where length(k) = A055642(k).
T(n, k) <= 1 + floor(log(k)/log(phi)) where log(phi) = A002390; the least numbers for which equality stands are when k and n are consecutive Fibonacci numbers. (End)

A049826 a(n) = T(n,n) + T(n+1,n) + ... + T(2n-1,n) = sum over a period of n-th column of array T given by A049816.

Original entry on oeis.org

0, 1, 3, 4, 8, 7, 13, 14, 16, 17, 27, 20, 32, 31, 31, 34, 46, 41, 55, 44, 50, 55, 73, 54, 68, 73, 75, 72, 96, 71, 101, 90, 96, 105, 101, 92, 124, 119, 123, 110, 146, 113, 155, 132, 132, 151, 177, 138, 164, 161, 169, 164, 204, 167, 183, 166, 192, 201, 231, 176

Offset: 1

Clark Kimberling

nonn

a(n) = sum of terms in row n of A051010.

Alois P. Heinz, Table of n, a(n) for n = 1..10000 (first 1000 terms from T. D. Noe)

Cf. A049816, A051010.

A051011 Numerator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0<=m

Original entry on oeis.org

0, 1, 1, 1, 8, 7, 13, 7, 16, 17, 27, 5, 32, 31, 31, 17, 46, 41, 55, 11, 50, 5, 73, 9, 68, 73, 25, 18, 96, 71, 101, 45, 32, 105, 101, 23, 124, 119, 41, 11, 146, 113, 155, 3, 44, 151, 177, 23, 164, 161, 169, 41, 204, 167, 183, 83, 64, 201, 231, 44, 240, 223, 209, 109

Offset: 1

Eric W. Weisstein

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

Cf. A034883, A051010, A051012 (denominators).

import Data.Ratio ((%), numerator)
a051011 n = numerator $ (sum $ a051010_row n) % n
-- Reinhard Zumkeller, Jun 27 2013

t[m_, n_] := For[r[-1]=m; r[0]=n; k=1, True, k++, r[k] = Mod[r[k-2], r[k-1]]; If[r[k] == 0, Return[k-1]]]; a[n_] := Numerator[Sum[t[m, n], {m, 0, n}]/n]; Array[a, 100] (* Amiram Eldar, Apr 22 2022 after Jean-François Alcover at A051010 *)

A051012 Denominator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0 <= m < n.

Original entry on oeis.org

1, 2, 1, 1, 5, 6, 7, 4, 9, 10, 11, 3, 13, 14, 15, 8, 17, 18, 19, 5, 21, 2, 23, 4, 25, 26, 9, 7, 29, 30, 31, 16, 11, 34, 35, 9, 37, 38, 13, 4, 41, 42, 43, 1, 15, 46, 47, 8, 49, 50, 51, 13, 53, 54, 55, 28, 19, 58, 59, 15, 61, 62, 63, 32, 65, 6, 67, 17, 69, 70, 71, 36, 73, 74, 75

Offset: 1

Eric W. Weisstein

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

Cf. A034883, A051010, A051011 (numerators).

import Data.Ratio ((%), denominator)
a051012 n = denominator $ (sum $ a051010_row n) % n
-- Reinhard Zumkeller, Jun 27 2013

t[m_, n_] := For[r[-1]=m; r[0]=n; k=1, True, k++, r[k] = Mod[r[k-2], r[k-1]]; If[r[k] == 0, Return[k-1]]]; a[n_] := Denominator[Sum[t[m, n], {m, 0, n}]/n]; Array[a, 100] (* Amiram Eldar, Apr 22 2022 after Jean-François Alcover at A051010 *)

A278744 Number of steps (modular reductions) in calculating the GCD of n-th consecutive primes p(n) and p(n+1) by the Euclidean algorithm.

Original entry on oeis.org

1, 2, 2, 3, 2, 2, 2, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 2, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2, 2, 5, 5, 3, 2, 2, 3, 2, 2, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 2, 5, 2, 4, 2, 2, 3, 3, 2, 2, 3, 3, 5, 2, 2, 3, 2, 2, 2, 2, 3, 3, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 2, 2, 2, 4, 3, 3, 2

Offset: 1

Adnan Baysal, Nov 27 2016

If x(0)>x(1) are integers, the Euclidean algorithm (or Euclid's algorithm) calculates the GCD of x(0) and x(1) by the recursive formula x(i+2) = x(i) mod x(i+1). This recursion terminates when x(t) = 0 for some t. Then x(t-1) is the GCD. Since the p(n) and p(n+1) are distinct primes, their GCD is 1, and there corresponding x(t-1) = 1. a(n) is the number of modular reductions, i.e., t-2.

Records are a(1) = 1 from gcd(2,3), a(2) = 2 from gcd(3,5), a(4) = 3 from gcd(7, 11), a(46) = 5 from gcd(199,211), a(221) = 6 from gcd(1381,1399), a(757) = 7 from gcd(5749,5779), a(5518) = 8 from gcd(54217,54251), a(65106) = 9 from gcd(815729, 815809), a(1293698) = 10 from gcd(20388583m 20388727), a(3997147) = 11 from gcd(67816457, 67816601). - Charles R Greathouse IV, Nov 28 2016

			For n=5, x(0) = p(6) = 13, x(1) = p(5) = 11. Then x(0) mod x(1) = x(2) = 2, hence x(1) mod x(2) = x(3) = 1. Since there are two modular reductions, a(5) = 2.

Cf. A051010, A072030, A188224, A034883, A267178.

ctgcd(m,n)=my(s); while(n!=1, [m,n]=[n,m%n]; s++); s
a(n,p=prime(n),q=nextprime(p+1))=ctgcd(p,q-p)+1 \\ Charles R Greathouse IV, Nov 28 2016

A = []
q = 1
for i in range(100):
   q = next_prime(q)
   p = next_prime(q)
   ctr = 0
   while q!=1:
       r = p%q
       p = q
       q = r
       ctr += 1
   A.append(ctr)
print A

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

A279047 Number k of modular reductions at which the recurrence relation x(i+1) = x(0) mod x(i) terminates with x(k) = 1, where x(0) = prime(n+1), x(1) = prime(n).

Original entry on oeis.org

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

Offset: 1

Adnan Baysal, Dec 04 2016

nonn

x(i) is a strictly decreasing sequence of nonnegative integers by definition of modular reduction. So at some point x(t) = 0. Let j be the previous positive value, i.e., x(t-1) = j. Then as x(0) mod j = prime(n+1) mod j = x(t) = 0, j|prime(n+1). Since j < prime(n+1), j = 1.

			For n=4, x(0) = p(5) = 11, x(1) = p(4) = 7. 11 mod 7 = 4 ==> 11 mod 4 = 3 ==> 11 mod 3 = 2 ==> 11 mod 2 = 1. Since there are four modular reductions, a(4) = 4.

Cf. A051010, A072030, A278744.

A = []
q = 1
for i in range(100):
    q = next_prime(q)
    p = next_prime(q)
    r = p%q
    ctr = 1
    while r!=1:
        r = p%r
        ctr += 1
    A.append(ctr)
print(A)

A365262 Numbers k which never require the maximum number of steps for the Euclidean algorithm to compute gcd(k,m) for any m > k.

Original entry on oeis.org

54, 78, 96, 135, 150, 156, 164, 182, 252, 304, 336, 442, 480, 483, 525, 532, 558, 570, 582, 640, 645, 675, 740, 744, 780, 912, 918, 922, 924, 1012, 1046, 1132, 1155, 1164, 1170, 1206, 1218, 1320, 1422, 1424, 1450, 1452, 1456, 1488, 1496, 1536, 1548, 1568, 1594

Offset: 1

John Metcalf, Aug 29 2023

nonn

			k = 54 is a term as the number of steps required to compute the Euclidean algorithm gcd(k, m) is smaller than A034883(m) for all m > k.
k = 27 is not a term as the number of steps required to compute the Euclidean algorithm gcd(k, m) is equal to A034883(m) for m = 35 (steps = 5), 44 (steps = 6) and 46 (steps = 6).

Cf. A034883, A051010, A364405.

def gcdsteps(k, m)
  k.zero? ? 0 : 1 + gcdsteps(m % k, k)
end
flags = [nil, *1..5000]
(1..flags.length).each do |m|
  scores = []
  (1..m).each do |k|
    scores << [gcdsteps(k, m), k]
  end
  scores.sort_by! { |n| n[0] }
  scores.select { |n| n[0] == scores.last[0] }.each do |n|
    flags[n[1]] = nil
  end
end
print flags[1..flags.length / 2].compact

cp's OEIS Frontend

A130130 a(0)=0, a(1)=1, a(n)=2 for n >= 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Programs

Haskell

Mathematica

Python

A107435 Triangle T(n,k), 1<=k<=n, read by rows: T(n,k) = length of Euclidean algorithm starting with n and k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A049826 a(n) = T(n,n) + T(n+1,n) + ... + T(2n-1,n) = sum over a period of n-th column of array T given by A049816.

Views

Author

Keywords

Comments

Links

Crossrefs

A051011 Numerator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0<=m

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

A051012 Denominator of average of number of steps in Euclidean algorithm for all gcd(m,n) with 0 <= m < n.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Mathematica

A278744 Number of steps (modular reductions) in calculating the GCD of n-th consecutive primes p(n) and p(n+1) by the Euclidean algorithm.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Sage

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