A222112 -id:A222112 - cp's OEIS frontend

A266201 Goodstein numbers: a(n) = G_n(n), where G is the Goodstein function.

0, 0, 1, 2, 83, 1197, 187243, 37665879, 20000000211, 855935016215, 44580503598539, 2120126221988686, 155568095557812625, 6568408355712901455, 295147905179358418247, 14063084452070776884879

Offset: 0

Natan Arie Consigli, Jan 22 2016

nonn

To write an integer n in base-k hereditary representation, write n in ordinary base-k representation, and then do the same recursively for all exponents which are greater than k.
For example, the hereditary representation of 132132 in base-2 is:
132132 = 2^17 + 2^10 + 2^5 + 2^2
= 2^(2^4 + 1) + 2^(2^3 + 2) + 2^(2^2 + 1) + 2^2
= 2^(2^(2^2) + 1) + 2^(2^(2+1) + 2) + 2^(2^2 + 1) + 2^2.
Define B_k(n) to be the function that substitutes k+1 for all the bases of the base-k hereditary representation of n.
E.g., B_2(101) = B_2(2^(2^2 + 2) + 2^(2^2 + 1) + 2^2 + 1) = 3^(3^3 + 3) + 3^(3^3 + 1) + 3^3 + 1 = 228767924549638.
(Sometimes B_k(n) is referred to as n "bumped" from base k.)
The Goodstein function is defined as: G_k(n) = B_{k+1}(G_{k-1}(n)) - 1 with G_0(n) = n, i.e., iteration of bumping the number to the next larger base and subtracting one; see example section for instances.
Goodstein's theorem says that for any nonnegative n, the sequence G_k(n) eventually stabilizes and then decreases by 1 in each step until it reaches 0. (The subsequent values of G_k(n) < 0 are not part of the sequence.)
Named after the English mathematician Reuben Louis Goodstein (1912-1985). - Amiram Eldar, Jun 19 2021

			Compute a(5) = G_5(5):
G_0(5) = 5;
G_1(5) = B_2(G_0(5))-1 = B_2(2^2+1)-1 = (3^3+1)-1 = 27 = 3^3;
G_2(5) = B_3(G_1(5))-1 = B_3(3^3)-1 = 4^4-1 = 255 = 3*4^3+3*4^2+3*4+3;
G_3(5) = B_4(G_2(5))-1 = B_4(3*4^3+3*4^2+3*4+3)-1 = 467;
G_4(5) = B_5(G_3(5))-1 = B_5(3*5^3+3*5^2+3*5+2)-1 = 775;
G_5(5) = B_6(G_4(5))-1 = B_6(3*6^3+3*6^2+3*6+1)-1 = 1197.

R. L. Goodstein, On the Restricted Ordinal Theorem, J. Symb. Logic, Vol. 9, No. 2 (1944), pp. 33-41; alternative link.
Eric Weisstein's World of Mathematics, Goodstein sequences.

Cf. Goodstein sequences: A056004: G_1(n); A057650: G_2(n); A059934: G_3(n); A059935: G_4(n); A059936: G_5(n); A215409: G_n(3); A056193: G_n(4); A266204: G_n(5); A266205: G_n(6); A222117: G_n(15); A059933: G_n(16); A211378: G_n(19).
Weak Goodstein sequences: A137411: g_n(11); A265034: g_n(266); A266202: g_n(n); A266203: a(n) = k such that g_k(n)=0;
Bumping Sequences: A222112: B_2(n);
Other sequences: A222113.

(B(n,b)=sum(i=1,#n=digits(n,b),n[i]*(b+1)^if(#nA266201(n)=for(k=1,n,n=B(n,k+1)-1);n \\ M. F. Hasler, Feb 12 2017

Edited by M. F. Hasler, Feb 12 2017

Incorrect a(16) deleted (the correct value is ~ 2.77*10^861) by M. F. Hasler, Feb 19 2017

A056004 Initial step in Goodstein sequences: write n in hereditary representation base 2, bump to base 3, then subtract 1.

Original entry on oeis.org

0, 2, 3, 26, 27, 29, 30, 80, 81, 83, 84, 107, 108, 110, 111, 7625597484986, 7625597484987, 7625597484989, 7625597484990, 7625597485013, 7625597485014, 7625597485016, 7625597485017, 7625597485067, 7625597485068, 7625597485070, 7625597485071, 7625597485094

Offset: 1

Henry Bottomley, Aug 04 2000

nonn

To write an integer n in base-k hereditary representation, write n in ordinary base-k representation, and then do the same recursively for all exponents which are greater than k: e.g., 2^18 = 2^(2^4 + 2) = 2^(2^(2^2) + 2). "Bump to base 3" means to replace all the 2's in that representation by 3. - M. F. Hasler, Feb 19 2017

			a(18)=7625597484989 since 18=2^(2^2)+2^1 which when bumped from 2 to 3 becomes 3^(3^3)+3^1=76255974849890 and when 1 is subtracted gives 7625597484989.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
A. E. Caicedo, Goodstein's function, Revista Colombiana de Matemáticas 41 (2007), 381-391.
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.
Eric Weisstein's World of Mathematics, Hereditary Representation.
Eric Weisstein's World of Mathematics, Goodstein Sequence.
Wikipedia, Goodstein's Theorem
Reinhard Zumkeller, Haskell programs for Goodstein sequences

Using G_k to denote the k-th step, this is the first in the following list: A056004: G_1(n), A057650: G_2(n), A059934: G_3(n), A059935: G_4(n), A059936: G_5(n); A266201: G_n(n); A056041.
Cf. A215409: G_n(3), A056193: G_n(4), A266204: G_n(5), A266205: G_n(6), A222117: G_n(15), A059933: G_n(16), A211378: G_n(19).
See A222112 for an alternate version.

Haskell
```
-- See Link
```

A056004(n)=sum(i=1,#n=binary(n),if(n[i],3^if(#n-i<2,#n-i,A056004(#n-i)+1)))-1 \\ See A266201 for more general code. - M. F. Hasler, Feb 19 2017

Edited by M. F. Hasler, Feb 19 2017

A265034 Weak Goodstein sequence beginning with 266.

Original entry on oeis.org

266, 6590, 65601, 390750, 1679831, 5765085, 16777579, 43047173, 100000551, 214359541, 429982475, 815731628, 1475790101, 2562891818, 4294968647, 6975758960, 11019962273, 16983564926, 25600002083, 37822861652, 54875876045, 78310988018, 110075317151, 152587893847

Offset: 0

N. J. A. Sloane, Dec 09 2015, following a suggestion from Alexander R. Povolotsky

nonn

Chai Wah Wu, Table of n, a(n) for n = 0..10000
Antoine Nectoux, Goodstein Sequences: The Power of a Detour via Infinity, Klein Project Blog, 2015.

For other Goodstein sequences see A014221, A056004, A056041, A056193, A057650, A059933, A059934, A059935, A059936, A137411, A211378, A215409, A222112, A222113, A222117.

More terms from Chai Wah Wu, Dec 09 2015

A222113 Goodstein sequence starting with a(1) = 16: to calculate a(n) for n>1, subtract 1 from a(n-1) and write the result in the hereditary representation base n, then bump the base to n+1.

Original entry on oeis.org

16, 112, 1284, 18753, 326594, 6588345, 150994944, 3524450281, 100077777776, 3138578427935, 106993479003784, 3937376861542205, 155568096352467864, 6568408356994335931, 295147905181357143920, 14063084452070776884880, 708235345355342213988446

Offset: 1

Reinhard Zumkeller, Feb 13 2013

Compare to A222117: the underlying variants to define Goodstein sequences are equivalent.

			a(1) - 1 = 15 = 2^3 + 2^2 + 2^1 + 2^0 = 2^(2^1+1) + 2^2 + 2^1 + 2^0
-> a(2) = 3^(3^1+1) + 3^3 + 3^1 + 3^0 = 112;
a(2) - 1 = 111 = 3^(3^1+1) + 3^3 + 3^1
-> a(3) = 4^(4^1+1) + 4^4 + 4^1 = 1284;
a(3) - 1 = 1283 = 4^(4^1+1) + 4^4 + 3*4^0
-> a(4) = 5^(5^1+1) + 5^5 + 3*5^0 = 18753;
a(4) - 1 = 18752 = 5^(5^1+1) + 5^5 + 2*5^0
-> a(5) = 6^(6^1+1) + 6^6 + 2*6^0 = 326594;
a(5) - 1 = 326593 = 6^(6^1+1) + 6^6 + 6^0
-> a(6)  = 7^(7^1+1) + 7^7 + 7^0 = 6588345.

Helmut Schwichtenberg and Stanley S. Wainer, Proofs and Computations, Cambridge University Press, 2012; 4.4.1, page 148ff.

Reinhard Zumkeller, Table of n, a(n) for n = 1..250
R. L. Goodstein, On the Restricted Ordinal Theorem, The Journal of Symbolic Logic, Vol. 9, No. 2, Jun., 1944.
Wikipedia, Goodstein's Theorem
Reinhard Zumkeller, Haskell programs for Goodstein sequences

Cf. A222112.

Haskell
```
-- See Link
```

A342707 T(n, k) is the result of replacing 2's by k's in the hereditary base-2 expansion of n; square array T(n, k) read by antidiagonals upwards, n, k >= 0.

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 2, 1, 3, 3, 1, 0, 1, 2, 4, 4, 4, 1, 0, 2, 2, 5, 27, 5, 5, 1, 0, 0, 3, 6, 28, 256, 6, 6, 1, 0, 1, 1, 7, 30, 257, 3125, 7, 7, 1, 0, 0, 2, 8, 31, 260, 3126, 46656, 8, 8, 1, 0, 1, 2, 9, 81, 261, 3130, 46657, 823543, 9, 9, 1, 0

Offset: 0

Rémy Sigrist, Jun 04 2021

			Array T(n, k) begins:
  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  1   1   1     1      1       1        1          1           1
    2|  0  1   2   3     4      5       6        7          8           9
    3|  1  2   3   4     5      6       7        8          9          10
    4|  1  1   4  27   256   3125   46656   823543   16777216   387420489
    5|  2  2   5  28   257   3126   46657   823544   16777217   387420490
    6|  1  2   6  30   260   3130   46662   823550   16777224   387420498
    7|  2  3   7  31   261   3131   46663   823551   16777225   387420499
    8|  0  1   8  81  1024  15625  279936  5764801  134217728  3486784401
    9|  1  2   9  82  1025  15626  279937  5764802  134217729  3486784402
   10|  0  2  10  84  1028  15630  279942  5764808  134217736  3486784410

Wikipedia, Hereditary base-n notation

See A341907 for a similar sequence.

Cf. A000120, A000312, A002488, A014566, A066068, A066279, A222112, A343255, A345021.

T(n,k) = { my (v=0, e); while (n, n-=2^e=valuation(n,2); v+=k^T(e,k)); v }

T(n, n) = A343255(n).
T(n, 0) = A345021(n).
T(n, 1) = A000120(n).
T(n, 2) = n.
T(n, 3) = A222112(n-1).
T(0, k) = 0.
T(1, k) = 1.
T(2, k) = k.
T(3, k) = k + 1.
T(4, k) = k^k = A000312(k).
T(5, k) = k^k + 1 = A014566(k).
T(6, k) = k^k + k = A066068(k).
T(7, k) = k^k + k + 1 = A066279(k).
T(16, k) = k^k^k = A002488(k).
T(m + n, k) = T(m, k) + T(n, k) when m AND n = 0 (where AND denotes the bitwise AND operator).

A273004 Sum of coefficients in the hereditary representation of n in base 2.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 5, 6, 4, 5, 6, 7, 7, 8, 9, 10, 4, 5, 6, 7, 7, 8, 9, 10, 8, 9, 10, 11, 11, 12, 13, 14, 5, 6, 7, 8, 8, 9, 10, 11, 9, 10, 11, 12, 12, 13, 14, 15, 9, 10, 11, 12, 12, 13, 14, 15, 13, 14, 15, 16, 16, 17, 18, 19, 6, 7, 8, 9, 9, 10, 11, 12, 10, 11, 12, 13, 13, 14, 15, 16, 10, 11, 12, 13, 13, 14, 15, 16, 14, 15, 16, 17, 17, 18, 19, 20, 11, 12, 13, 14, 14

Offset: 0

M. F. Hasler, May 12 2016

The hereditary representation of a number n in base b is a [possibly empty] sum (possibly represented as a list) of monomials of the form m*b^e (possibly represented as a list [m,e] or as a single number m if e = 0) with coefficients 0 < m < b, and the (strictly increasing) exponents e > 0 recursively again expressed in the same form. Thus 0 = [], 1 = 1*b^0 = [1], b = 1*b^1 = [[1, [1]]] etc.

			266 = 1*2^1 + 1*2^(1+1*2^1) + 1*2^(1*2^(1+1*2^1)) which can be represented as [[1, [1]], [1, [1, [1, [1]]]], [1, [[1, [1, [1, [1]]]]]]], and there are 11 "1"s, therefore a(266) = 11.

Andrei Zabolotskii, Table of n, a(n) for n = 0..8191
Eric Weisstein's World of Mathematics, Hereditary Representation.

Cf. A056004, A222112, A273005 (base 10 analog), A033922, A361838.

a[n_] := a[n] = Total[1 + a /@ Log2[DeleteCases[NumberExpand[n, 2], 0]]]; (* Vladimir Reshetnikov, Dec 21 2023 *)

(hr(n,b=2)=if(1<#n=digits(n,b),my(v=if(n[#n],[n[#n]],[]));forstep(i=#n-1,1,-1,n[i]&&v=concat(v,[[n[i],hr(#n-i,b)]]));v,n));(cc(v)=if(type(v)=="t_VEC",sum(i=1,#v,cc(v[i])),v)); a(n)=cc(hr(n))

def A273004(n):
  s=format(n,'b')[::-1]
  return sum(1+A273004(i) for i in range(len(s)) if s[i]=='1') # Pontus von Brömssen, Sep 17 2020

If n = Sum_{j=1..k} 2^e_j where 0 <= e_1 < ... < e_k, then a(n) = k + Sum_{j=1..k} a(e_j). - Pontus von Brömssen, Sep 17 2020

a(n) = A033922(n) + A361838(floor(n/2)) for n > 1. - Andrei Zabolotskii, Aug 24 2025

A273005 Sum of coefficients in the hereditary representation of n in base 10.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3

Offset: 0

M. F. Hasler, May 12 2016

			266 = 6 + 6*10^1 + 2*10^2 which can be represented as [6, [6, [1]], [2, [2]]], therefore a(266) = 6 + 6 + 1 + 2 + 2 = 17.

Eric Weisstein's World of Mathematics, Hereditary Representation.

Cf. A273004, A056004, A222112.

(hr(n,b=10)=if(1<#n=digits(n,b),my(v=if(n[#n],[n[#n]],[]));forstep(i=#n-1,1,-1,n[i]&&v=concat(v,[[n[i],hr(#n-i,b)]]));v,n));(cc(v)=if(type(v)=="t_VEC",sum(i=1,#v,cc(v[i])),v)); a(n)=cc(hr(n,10))

def A273005(n):
  s=str(n)[::-1]
  return sum(int(s[i])+A273005(i) for i in range(len(s)) if s[i]!='0') # Pontus von Brömssen, Sep 17 2020

If n = Sum_{j=1..k} d_j*10^(e_j) where 0 <= e_1 < ... < e_k and 1 <= d_j <= 9, then a(n) = Sum_{j=1..k} (d_j + a(e_j)). - Pontus von Brömssen, Sep 17 2020

cp's OEIS Frontend

A266201 Goodstein numbers: a(n) = G_n(n), where G is the Goodstein function.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A056004 Initial step in Goodstein sequences: write n in hereditary representation base 2, bump to base 3, then subtract 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

PARI

Extensions

A265034 Weak Goodstein sequence beginning with 266.

Views

Author

Keywords

Links

Crossrefs

Extensions

A222113 Goodstein sequence starting with a(1) = 16: to calculate a(n) for n>1, subtract 1 from a(n-1) and write the result in the hereditary representation base n, then bump the base to n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

A342707 T(n, k) is the result of replacing 2's by k's in the hereditary base-2 expansion of n; square array T(n, k) read by antidiagonals upwards, n, k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A273004 Sum of coefficients in the hereditary representation of n in base 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A273005 Sum of coefficients in the hereditary representation of n in base 10.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Formula