A271977 -id:A271977 - cp's OEIS frontend

A056193 Goodstein sequence starting with 4: to calculate a(n+1), write a(n) in the hereditary representation in base n+2, then bump the base to n+3, then subtract 1.

4, 26, 41, 60, 83, 109, 139, 173, 211, 253, 299, 348, 401, 458, 519, 584, 653, 726, 803, 884, 969, 1058, 1151, 1222, 1295, 1370, 1447, 1526, 1607, 1690, 1775, 1862, 1951, 2042, 2135, 2230, 2327, 2426, 2527, 2630, 2735, 2842, 2951, 3062, 3175, 3290, 3407

Offset: 0

Henry Bottomley, Aug 02 2000

Goodstein's theorem shows that such a sequence converges to zero for any starting value [e.g. if a(0)=1 then a(1)=0; if a(0)=2 then a(3)=0; and if a(0)=3 then a(5)=0]. With a(0)=4 we have a(3*2^(3*2^27 + 27) - 3)=0, which is well beyond the 10^(10^8)-th term.
The second half of such sequences is declining and the previous quarter is stable.
The resulting sequence 0,1,3,5,3*2^402653211 - 3, ... (see Comments in A056041) grows too rapidly to have its own entry.

			a(0) = 4 = 2^2,
a(1) = 3^3 - 1 = 26 = 2*3^2 + 2*3 + 2,
a(2) = 2*4^2 + 2*4 + 2 - 1 = 41 = 2*4^2 + 2*4 + 1,
a(3) = 2*5^2 + 2*5 + 1 - 1 = 60 = 2*5^2 + 2*5,
a(4) = 2*6^2 + 2*6 - 1 = 83 = 2*6^2 + 6 + 5,
a(5) = 2*7^2 + 7 + 5 - 1 = 109 etc.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (final 2 terms from Nicholas Matteo)
R. L. Goodstein, On the Restricted Ordinal Theorem, The Journal of Symbolic Logic, Vol. 9, No. 2 (1944), 33-41.
Eric Weisstein's World of Mathematics, Goodstein Sequence.
Wikipedia, Goodstein's Theorem
Reinhard Zumkeller, Haskell programs for Goodstein sequences

Cf. A056041, A056004, A057650, A059934, A059935, A059936, A271977.

Cf. A215409, A266204, A271554, A222117, A059933, A211378.

Haskell
```
See Zumkeller link
```

lista(nn) = {print1(a = 4, ", "); for (n=2, nn, pd = Pol(digits(a, n)); q = sum(k=0, poldegree(pd), if (c=polcoeff(pd, k), c*x^subst(Pol(digits(k, n)), x, n+1), 0)); a = subst(q, x, n+1) - 1; print1(a, ", "););} \\ Michel Marcus, Feb 22 2016

Edited by N. J. A. Sloane, Mar 06 2006

Offset changed to 0 by Nicholas Matteo, Sep 04 2019

A215409 The Goodstein sequence G_n(3).

Original entry on oeis.org

3, 3, 3, 2, 1, 0

Offset: 0

Jonathan Sondow, Aug 10 2012

G_0(m) = m. To get the 2nd term, write m in hereditary base 2 notation (see links), change all the 2s to 3s, and then subtract 1 from the result. To get the 3rd term, write the 2nd term in hereditary base 3 notation, change all 3s to 4s, and subtract 1 again. Continue until the result is zero (by Goodstein's Theorem), when the sequence terminates.

Decimal expansion of 33321/100000. - Natan Arie Consigli, Jan 23 2015

			a(0) = 3 = 2^1 + 1;
a(1) = 3^1 + 1 - 1 = 3^1 = 3;
a(2) = 4^1 - 1 = 3;
a(3) = 3 - 1 = 2;
a(4) = 2 - 1 = 1;
a(5) = 1 - 1 = 0.

R. L. Goodstein, On the Restricted Ordinal Theorem, J. Symb. Logic 9, 33-41, 1944.
Eric Weisstein's World of Mathematics, Hereditary Representation
Eric Weisstein's World of Mathematics, Goodstein Sequence
Eric Weisstein's World of Mathematics, Goodstein's Theorem
Wikipedia, Hereditary base-n notation
Wikipedia, Goodstein sequence
Wikipedia, Goodstein's Theorem
Reinhard Zumkeller, Haskell programs for Goodstein sequences

Cf. A056004, A057650, A059934, A059935, A059936, A271977.

Cf. A056041, A056193, A266204, A271554, A222117, A059933, A211378.

Haskell
```
-- See Link
```

PadRight[CoefficientList[Series[3 + 3 x + 3 x^2 + 2 x^3 + x^4, {x, 0, 4}], x], 6] (* Michael De Vlieger, Dec 12 2017 *)

B(n, b)=sum(i=1, #n=digits(n, b), n[i]*(b+1)^if(#nIain Fox, Dec 13 2017

first(n) = my(res = vector(n)); res[1] = res[2] = res[3] = 3; res[4] = 2; res[5] = 1; res; \\ Iain Fox, Dec 12 2017

first(n) = Vec(3 + 3*x + 3*x^2 + 2*x^3 + x^4 + O(x^n)) \\ Iain Fox, Dec 12 2017

a(n) = floor(2 - (4/Pi)*atan(n-3)) \\ Iain Fox, Dec 12 2017

a(0) = a(1) = a(2) = 3; a(3) = 2; a(4) = 1; a(n) = 0, n > 4;
From Iain Fox, Dec 12 2017: (Start)
G.f.: 3 + 3*x + 3*x^2 + 2*x^3 + x^4.
E.g.f.: 3 + 3*x + (3/2)*x^2 + (1/3)*x^3 + (1/24)*x^4.
a(n) = floor(2 - (4/Pi)*arctan(n-3)), n >= 0.
(End)

Corrected by Natan Arie Consigli, Jan 23 2015

A056041 Value for which b(a(n))=0 when b(2)=n and b(k+1) is calculated by writing b(k) in base k, reading this as being written in base k+1 and then subtracting 1.

Original entry on oeis.org

2, 3, 5, 7, 23, 63, 383, 2047

Offset: 0

Henry Bottomley, Aug 04 2000

a(8)=3*2^(3*2^27+27)-1 which is more than 10^(10^8) and equal to the final base of the Goodstein sequence starting with g(2)=4; indeed, apart from the initial term, the sequence starting with b(2)=8 is identical to the Goodstein sequence starting with g(2)=4. The initial terms of a(n) [2, 3, 5 and 7] are equal to the initial terms of the equivalent final bases of Goodstein sequences starting at the same points. a(9)=2^(2^(2^70+70)+2^70+70)-1 which is more than 10^(10^(10^20)).
It appears that if n is even then a(n) is one less than three times a power of two, while if n is odd then a(n) is one less than a power of two.
Comment from John Tromp, Dec 02 2004: The sequence 2,3,5,7,3*2^402653211 - 1, ... gives the final base of the Goodstein sequence starting with n. This is an example of a very rapidly growing function that is total (i.e. defined on any input), although this fact is not provable in first-order Peano Arithmetic. See the links for definitions. This grows even faster than the Friedman sequence described in the Comments to A014221.
In fact there are two related sequences: (i) The Goodstein function l(n) = number of steps for the Goodstein sequence to reach 0 when started with initial term n >= 0: 0, 1, 3, 5, 3*2^402653211 - 3, ...; and (ii) the same sequence + 2: 2, 3, 5, 7, 3*2^402653211 - 1, ..., which is the final base reached. Both grow too rapidly to have their own entries in the database.
Related to the hereditary base sequences - see cross-reference lines.
This sequence gives the final base of the weak Goodstein sequence starting with n; compare A266203, the length of the weak Goodstein sequence. a(n) = A266203(n) + 2.

			a(3)=7 because starting with b(2)=3=11 base 2, we get b(3)=11-1 base 3=10 base 3=3, b(4)=10-1 base 4=3, b(5)=3-1 base 5=2, b(6)=2-1 base 6=1 and b(7)=1-1 base 7=0.

R. L. Goodstein, On the Restricted Ordinal Theorem, J. Symb. Logic 9, 33-41, 1944.
L. Kirby, and J. Paris, Accessible independence results for Peano arithmetic, Bull. London Mathematical Society, 14 (1982), 285-293.
J. Tromp, Programming Pearls
Eric Weisstein's World of Mathematics, Goodstein Sequence
Wikipedia, Goodstein's theorem

Cf. A266202, A268687, A268689, A268688.
Equals A266203 + 2.
Weak Goodstein sequences: A267647, A267648, A271987, A271988, A271989, A271990, A271991, A137411, A271992, A265034.
Steps of strong Goodstein sequences: A056004, A057650, A059934, A059935, A059936, A271977.
Strong Goodstein sequences: A215409, A056193, A266204, A222117, A059933.
Woodall numbers: A003261.

A271978 G_7(n), where G is the Goodstein function defined in A266201.

Original entry on oeis.org

0, 173, 2454, 332147, 37665879, 774841151, 1162263921, 1937434592, 2749609302, 3486784574, 3486786855, 3487116548, 3524450280

Offset: 3

Natan Arie Consigli, Apr 30 2016

nonn

a(16) is too big to include - see b-file. a(17) = 9.221...*10^2347, a(18) = 2.509...*10^316952. - Pontus von Brömssen, Sep 25 2020

			Find G_7(7):
G_1(7) = B_2(7)-1= B[2](2^2+2+1)-1 = 3^3+3+1-1 = 30;
G_2(7) = B_3(G_1(7))-1 = B[3](3^3+3)-1 =  4^4+4-1 = 259;
G_3(7) = B_4(G_2(7))-1 = 5^5+3-1 = 3127;
G_4(7) = B_5(G_3(7))-1 = 6^6+2-1 = 46657;
G_5(7) = B_6(G_4(7))-1 = 7^7+1-1 = 823543;
G_6(7) = B_7(G_5(7))-1 = 8^8-1 = 16777215;
G_7(7) = B_8(G_6(7))-1 = 7*9^7+7*9^6+7*9^5+7*9^4+7*9^3+7*9^2+7*9+7-1 = 37665879.

Pontus von Brömssen, Table of n, a(n) for n = 3..16
Wikipedia, Goodstein's theorem

Cf. A056004: G_1(n); A057650: G_2(n); A059934: G_3(n); A059935: G_4(n); A059936: G_5(n); A271977: G_6(n); this sequence: G_7(n); A271979: G_8(n); A271985: G_9(n); A271986: G_10(n); A266201: G_n(n).

from sympy.ntheory.factor_ import digits
def bump(n,b):
  s=digits(n,b)[1:]
  l=len(s)
  return sum(s[i]*(b+1)**bump(l-i-1,b) for i in range(l) if s[i])
def A271978(n):
  if n==3: return 0
  for i in range(2,9):
    n=bump(n,i)-1
  return n # Pontus von Brömssen, Sep 25 2020

a(9) corrected by Pontus von Brömssen, Sep 25 2020

A271979 G_8(n), where G is the Goodstein function defined in A266201.

Original entry on oeis.org

0, 211, 3325, 555551, 77777775, 20000000211, 30000003325, 50000555551, 70077777775, 100000000211, 100000003325, 100000555551, 100077777775

Offset: 3

Natan Arie Consigli, Apr 30 2016

nonn

At least half of the digits of every term (except a(14)) are the same.
Let n > 0:
a(4n) mod 100 = 211;
a(4n+1) mod 1000 = 3325;
a(4n+2) mod 1000000 = 555551;
a(4n+3) mod 100000000 = 77777775;
Proof for a(4n):
If x is divisible by 4 its hereditary representation in base 2 has all summands divisible by 4 and it cannot have the summands 1 and 2.
If we calculate G_1(x) we would end with:
G_1(x) = B_2(x)-1.
Clearly, B_2(x) = 3^a + 3^b + ... is divisible by 3^3 = 27 and that would mean that the representation of B_2(x)-1 would be B_2(x)-1 = X_3 + 2*3^2+2*3+2.
From now on, let X_n be a sum of powers of n (greater than the right term).
We finish proving the statement by calculating G_8(x):
G_2(x) = B_3(X_3 +2*3^2+2*3+2)-1 = X_4 + 2*4^2+2*4+2-1;
G_3(x) = B_4(X_4 +2*4^2+2*4-1)-1 = X_5 + 2*5^2+2*5+1-1;
G_4(x) = B_5(X_5 +2*5^2+2*5)-1 = X_6 + 2*6^2+2*6-1;
G_5(x) = B_6(X_6 +2*6^2+6+5)-1 = X_7 + 2*7^2+7+5-1;
G_6(x) = B_7(X_7 +2*7^2+7+4)-1 = X_8 + 2*8^2+8+4-1;
G_7(x) = B_8(X_8 +2*8^2+8+3)-1 = X_9 + 2*9^2+9+3-1;
G_8(x) = B_9(X_9 +2*9^2+9+2)-1 = X_10 + 2*10^2+10+2-1 = X_10 + 211;
So finally G_8(x) mod 100 = 211.
The other cases can be proved using the same reasoning.
a(17) = 3.3330...*10^3333, a(18) = 5.555550...*10^555555. - Pontus von Brömssen, Sep 25 2020

			Calculate G_8(5):
G_1(5) = B_2(5)-1 = B_2(2^2+1)-1 = 27;
G_2(5) = B_3(3^3)-1 = 4^4-1 = 255;
G_3(5) = B_4(3*4^3 + 3*4^2 + 3*4 + 3)-1 = 3*5^3 + 3*5^2 + 3*5 + 3-1 = 467;
G_4(5) = B_5(3*5^3 + 3*5^2 + 3*5 + 2)-1 = 3*6^3 + 3*6^2 + 3*6 + 2-1 = 775;
G_5(5) = B_6(3*6^3 + 3*6^2 + 3*6 + 1)-1 = 3*7^3 + 3*7^2 + 3*7 + 1-1 = 1197;
G_6(5) = B_7(3*7^3 + 3*7^2 + 3*7)-1 = 3*8^3 + 3*8^2 + 3*8-1 = 1751;
G_7(5) = B_8(3*8^3 + 3*8^2 + 2*8 + 7)-1 = 3*9^3 + 3*9^2 + 2*9 + 7-1 = 2454;
G_8(5) = B_9(3*9^3 + 3*9^2 + 2*9 + 6)-1 = 3*10^3 + 3*10^2 + 2*10 + 6-1 = 3325.

Pontus von Brömssen, Table of n, a(n) for n = 3..16
Wikipedia, Goodstein's theorem

Cf. A056004: G_1(n); A057650: G_2(n); A059934: G_3(n); A059935: G_4(n); A059936: G_5(n); A271977: G_6(n); A271978: G_7(n); this sequence: G_8(n); A271985: G_9(n); A271986: G_10(n); A266201: G_n(n).

from sympy.ntheory.factor_ import digits
def bump(n,b):
  s=digits(n,b)[1:]
  l=len(s)
  return sum(s[i]*(b+1)**bump(l-i-1,b) for i in range(l) if s[i])
def A271979(n):
  if n==3: return 0
  for i in range(2,10):
    n=bump(n,i)-1
  return n # Pontus von Brömssen, Sep 25 2020

Incorrect program and terms removed by Pontus von Brömssen, Sep 25 2020

A271985 G_9(n), where G is the Goodstein function defined in A266201.

Original entry on oeis.org

0, 253, 4382, 885775, 150051213, 570623341475, 855935016215, 1426559238830, 1997331745490, 3138428376974, 3138428381103, 3138429262496, 3138578427934

Offset: 3

Natan Arie Consigli, Apr 30 2016

nonn

a(17) = 2.066...*10^4574. - Pontus von Brömssen, Sep 25 2020

			Compute G_9(10):
G_1(10)= B_2(10)-1 = B_2(2^(2+1)+2)-1 = 3^(3+1)+3-1 = 83;
G_2(10) = B_3(3^(3+1)+2)-1 = 4^(4+1)+2-1 = 1025;
G_3(10) = B_4(4^(4+1)+1)-1 = 5^(5+1)+1-1 = 15625;
G_4(10) = B_5(5*5^(5+1))-1 = 6^(6+1)-1= 279935;
G_5(10) = B_6(5*6^6+5*6^5+5*6^4+5*6^3+5*6^2+5*6+5)-1 = 5*7^7+5*7^5+5*7^4+5*7^3+5*7^2+5*7+5-1 = 4215754;
G_6(10) = B_7(5*7^7+5*7^5+5*7^4+5*7^3+5*7^2+5*7+4)-1 = 5*8^8+5*8^5+5*8^4+5*8^3+5*8^2+5*8+4-1 = 84073323;
G_7(10) = B_8(5*8^8+5*8^5+5*8^4+5*8^3+5*8^2+5*8+3)-1 = 5*9^9+5*9^5+5*9^4+5*9^3+5*9^2+5*9+3-1 = 1937434592;
G_8(10) = B_9(5*9^9+5*9^5+5*9^4+5*9^3+5*9^2+5*9+2)-1 = 5*10^10+5*10^5+5*10^4+5*10^3+5*10^2+5*10+2-1 = 50000555551;
G_9(10) = B_10(5*10^10+5*10^5+5*10^4+5*10^3+5*10^2+5*10+1)-1 = 5*11^11+5*11^5+5*11^4+5*11^3+5*11^2+5*11+1-1 = 1426559238830.

Pontus von Brömssen, Table of n, a(n) for n = 3..16
Wikipedia, Goodstein's theorem

Cf. A056004: G_1(n); A057650: G_2(n); A059934: G_3(n); A059935: G_4(n); A059936: G_5(n); A271977: G_6(n); A271978: G_7(n); A271979: G_8(n); this sequence: G_9(n); A271986: G_10(n); A266201: G_n(n).

from sympy.ntheory.factor_ import digits
def bump(n,b):
  s=digits(n,b)[1:]
  l=len(s)
  return sum(s[i]*(b+1)**bump(l-i-1,b) for i in range(l) if s[i])
def A271985(n):
  if n==3: return 0
  for i in range(2,11):
    n=bump(n,i)-1
  return n # Pontus von Brömssen, Sep 25 2020

Incorrect program and terms removed by Pontus von Brömssen, Sep 25 2020

A271986 G_10(n), where G is the Goodstein function defined in A266201.

Original entry on oeis.org

0, 299, 5643, 1357259, 273624711, 17832200896811, 26748301350411, 44580503598539, 62412976762503, 106993205379371, 106993205384715, 106993206736331, 106993479003783

Offset: 3

Natan Arie Consigli, May 01 2016

nonn

a(17) = 1.926...*10^6103. - Pontus von Brömssen, Sep 25 2020

Pontus von Brömssen, Table of n, a(n) for n = 3..16
Wikipedia, Goodstein's theorem

Cf. A056004: G_1(n); A057650: G_2(n); A059934: G_3(n); A059935: G_4(n); A059936: G_5(n); A271977: G_6(n); A271978: G_7(n); A271979: G_8(n); A271985: G_9(n); this sequence: G_10(n); A266201: G_n(n).

from sympy.ntheory.factor_ import digits
def bump(n,b):
  s=digits(n,b)[1:]
  l=len(s)
  return sum(s[i]*(b+1)**bump(l-i-1,b) for i in range(l) if s[i])
def A271986(n):
  if n==3: return 0
  for i in range(2,12):
    n=bump(n,i)-1
  return n # Pontus von Brömssen, Sep 25 2020

Incorrect program and terms removed by Pontus von Brömssen, Sep 25 2020

A296441 Array A(n, k) = G_k(n) where G_k(n) is the k-th term of the Goodstein sequence of n, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 0, 2, 0, 0, 2, 3, 0, 0, 1, 3, 4, 0, 0, 0, 3, 26, 5, 0, 0, 0, 2, 41, 27, 6, 0, 0, 0, 1, 60, 255, 29, 7, 0, 0, 0, 0, 83, 467, 257, 30, 8, 0, 0, 0, 0, 109, 775, 3125, 259, 80, 9, 0, 0, 0, 0, 139, 1197, 46655, 3127, 553, 81, 10, 0, 0, 0, 0, 173, 1751, 98039, 46657, 6310, 1023, 83, 11

Offset: 0

Iain Fox, Dec 12 2017

G_0(n) = n. To get to the second term in the row, convert n to hereditary base 2 representation (see links), replace each 2 with a 3, and subtract 1. For the third term, convert the second term (G_1(n)) into hereditary base 3 notation, replace each 3 with a 4, and subtract one. This pattern continues until the sequence converges to 0, which, by Goodstein's Theorem, occurs for all n.

			| n\k |  0   1    2     3      4      5       6       7       8       9  ...
|-----|------------------------------------------------------------------------
|  0  |  0,  0,   0,    0,     0,     0,      0,      0,      0,      0, ...
|  1  |  1,  0,   0,    0,     0,     0,      0,      0,      0,      0, ...
|  2  |  2,  2,   1,    0,     0,     0,      0,      0,      0,      0, ...
|  3  |  3,  3,   3,    2,     1,     0,      0,      0,      0,      0, ...
|  4  |  4, 26,  41,   60,    83,   109,    139,    173,    211,    253, ...
|  5  |  5, 27, 255,  467,   775,  1197,   1751,   2454,   3325,   4382, ...
|  6  |  6, 29, 257, 3125, 46655, 98039, 187243, 332147, 555551, 885775, ...
| ... |

Iain Fox, Antidiagonals n = 0..20 of array, flattened
Eric Weisstein's World of Mathematics, Hereditary Representation
Eric Weisstein's World of Mathematics, Goodstein Sequence
Eric Weisstein's World of Mathematics, Goodstein's Theorem
Wikipedia, Hereditary base-n notation
Wikipedia, Goodstein sequence
Wikipedia, Goodstein's Theorem

n-th row: A000004 (n=0), A000007 (n=1), A215409 (n=3), A056193 (n=4), A266204 (n=5), A266205 (n=6), A271554 (n=7), A271555 (n=8), A271556 (n=9), A271557 (n=10), A271558 (n=11), A271559 (n=12), A271560 (n=13), A271561 (n=14), A222117 (n=15), A059933 (n=16), A271562 (n=17), A271975 (n=18) A211378 (n=19), A271976 (n=20).
k-th column: A001477 (k=0), A056004 (k=1), A057650 (k=2), A059934 (k=3), A059935 (k=4), A059936 (k=5), A271977 (k=6), A271978 (k=7), A271979 (k=8), A271985 (k=9), A271986 (k=10).
G_n(n) = A266201(n) (main diagonal of array).

B(n, b)=sum(i=1, #n=digits(n, b), n[i]*(b+1)^if(#n

cp's OEIS Frontend

A056193 Goodstein sequence starting with 4: to calculate a(n+1), write a(n) in the hereditary representation in base n+2, then bump the base to n+3, then subtract 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Extensions

A215409 The Goodstein sequence G_n(3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A056041 Value for which b(a(n))=0 when b(2)=n and b(k+1) is calculated by writing b(k) in base k, reading this as being written in base k+1 and then subtracting 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A271978 G_7(n), where G is the Goodstein function defined in A266201.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A271979 G_8(n), where G is the Goodstein function defined in A266201.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A271985 G_9(n), where G is the Goodstein function defined in A266201.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A271986 G_10(n), where G is the Goodstein function defined in A266201.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python