|
%I #54 Jun 19 2021 04:00:17
%S 0,0,1,2,83,1197,187243,37665879,20000000211,855935016215,
%T 44580503598539,2120126221988686,155568095557812625,
%U 6568408355712901455,295147905179358418247,14063084452070776884879
%N Goodstein numbers: a(n) = G_n(n), where G is the Goodstein function.
%C 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.
%C For example, the hereditary representation of 132132 in base-2 is:
%C 132132 = 2^17 + 2^10 + 2^5 + 2^2
%C = 2^(2^4 + 1) + 2^(2^3 + 2) + 2^(2^2 + 1) + 2^2
%C = 2^(2^(2^2) + 1) + 2^(2^(2+1) + 2) + 2^(2^2 + 1) + 2^2.
%C Define B_k(n) to be the function that substitutes k+1 for all the bases of the base-k hereditary representation of n.
%C 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.
%C (Sometimes B_k(n) is referred to as n "bumped" from base k.)
%C 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.
%C 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.)
%C Named after the English mathematician Reuben Louis Goodstein (1912-1985). - _Amiram Eldar_, Jun 19 2021
%H R. L. Goodstein, <a href="https://www.jstor.org/stable/2268019">On the Restricted Ordinal Theorem</a>, J. Symb. Logic, Vol. 9, No. 2 (1944), pp. 33-41; <a href="http://pageperso.lif.univ-mrs.fr/~luigi.santocanale/TERGoodstein/Goodstein1944.pdf">alternative link</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GoodsteinSequence.html">Goodstein sequences</a>.
%e Compute a(5) = G_5(5):
%e G_0(5) = 5;
%e G_1(5) = B_2(G_0(5))-1 = B_2(2^2+1)-1 = (3^3+1)-1 = 27 = 3^3;
%e 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;
%e G_3(5) = B_4(G_2(5))-1 = B_4(3*4^3+3*4^2+3*4+3)-1 = 467;
%e G_4(5) = B_5(G_3(5))-1 = B_5(3*5^3+3*5^2+3*5+2)-1 = 775;
%e G_5(5) = B_6(G_4(5))-1 = B_6(3*6^3+3*6^2+3*6+1)-1 = 1197.
%o (PARI) (B(n,b)=sum(i=1,#n=digits(n,b),n[i]*(b+1)^if(#n<b+i,#n-i,B(#n-i,b)))); A266201(n)=for(k=1,n,n=B(n,k+1)-1);n \\ _M. F. Hasler_, Feb 12 2017
%Y 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).
%Y 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;
%Y Bumping Sequences: A222112: B_2(n);
%Y Other sequences: A222113.
%K nonn
%O 0,4
%A _Natan Arie Consigli_, Jan 22 2016
%E Edited by _M. F. Hasler_, Feb 12 2017
%E Incorrect a(16) deleted (the correct value is ~ 2.77*10^861) by _M. F. Hasler_, Feb 19 2017
| 