OFFSET
0,1
COMMENTS
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.
LINKS
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
EXAMPLE
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.
PROG
Concerning the sequence 2, 3, 5, 7, 3*2^402653211 - 1, ... mentioned above, John Tromp write: In Haskell, the sequence is the infinite list
main=mapM_(print.g 2)[0..] where
g b 0=b; g b n=g c(s 0 n-1)where s _ 0=0; s e n=mod n b*c^s 0 e+s(e+1)(div n b); c=b+1
In Ruby, f(n) is defined by
def s(b, e, n)n==0?0:n%b*(b+1)**s(b, 0, e)+s(b, e+1, n/b)end
def g(b, n)n==0?b:g(b+1, s(b, 0, n)-1)end
def f(n)g(2, n)end
CROSSREFS
KEYWORD
base,nonn,changed
AUTHOR
Henry Bottomley, Aug 04 2000
STATUS
approved