Level-k Goodstein Sequences
r.e.s.
integer, using operations up to an arbitrary level in
the Ackermann hierarchy +, *, ^, ^^, ^^^, ..., and
Goodstein sequences are defined (as Goodstein himself
introduced them) at *all* finite levels -- although
only level-3 Goodstein sequences (using +,*,^) are
typically ever mentioned.
The growth rate of the level-3 Goodstein function of
argument n -- given by the number of positive terms
in the Goodstein sequence that starts with base 2 and
initial term n -- is said to be that of F_epsilon in
the Wainer hierarchy.
Question:
---------
At what ordinal in the Wainer hierarchy is the growth
rate of a level-k Goodstein function (k = 2 or k > 3)?
Or how else might these growth rates be characterised?
Note for k = 1:
----------------
It's mildly interesting that the level-1 Goodstein
function, g_1(n), for Goodstein sequences that start
with base a >= 2 and initial term n >= 0, has the
following closed-form:
g_1(n) = 2^floor(n/a)*(a + n%a + 1) - 3.
Furthermore, all Goodstein functions (at all levels)
range over the values of this function g_1. (!)
(The value of the base, say B_1(n), at which the
Goodstein sequence first hits 0 may be a more natural
parameter; for example, with a = 2 we get
B_1(n) = 2^floor(n/2)*(3 + n%2) - 1
corresponding to sequence <2,3,5,7,11,15,23,31,47,...>
cf. A052955 at www.research.att.com/~njas/sequences/)
----------------
The remainder of this posting summarises Goodstein's
representations of an integer and Goodstein sequences ...
The hierarchy of operations +, *, ^, ^^, ^^^, ...
with the usual standard recursive definition, will be
conveniently written as indexed operators:
[1]=+, [2]=*, [3]=^, [4]=^^, [5]=^^^, ...
By convention, excessive parentheses are avoided by
giving higher-level operators higher precedence in the
order of evaluation; e.g., b[1]x[2]y = b+(x*y),
b[2]x[1]y = (b*x)+y, etc.)
Goodstein's level-k base-b representation of integer n,
is the expression defined recursively as follows,
with n >= 0, k >= 1, b >= 2:
R(n)
= n (0 <= n <= b-1)
= b [k] R(x_k) [k-1] R(x_(k-1)) ... [1] R(x_1) (n >= b)
where x_1,...,x_k are the largest integers satisfying
b [k] x_k [k-1] x_(k-1) ... [j] x_j <= n (1<= j <= k).
Thus,
level-1 representations have form b+X,
with X also of this form;
level-2 representations have form b*X+Y,
with X,Y also of this form;
level-3 representations have form b^X*Y+Z,
with X,Y,Z also of this form;
level-4 representations have form b^^X^Y*Z+T,
with X,Y,Z,T also of this form;
etc.
By convention, representations are abbreviated by omitting
any instances of +0, *1, ^1, ^^1, etc.; for example,
the level-3 base-2 representation of the number 6 is
2^(2^1*1+0)*1+(2^1*1+0), which abbreviates to 2^2+2.
Examples:
Base-2 representations of 266 at levels 1,2,3,4,5:
level 1: R(266) = 2+2+...+2 (with 133 2's)
level 2: R(266) = 2*(2*(2*(2*2*2*2*2+1))+1)
level 3: R(266) = 2^2^(2+1)+2^(2+1)+2
level 4: R(266) = 2^^(2+1)^2+2^^2*2+2
level 5: R(266) = 2^^^2^^2+2^^^2*2+2.
Definition -- Level-k Goodstein Sequences
-----------------------------------------
The level-k Goodstein sequence, starting with base a >= 2
and value n >= 0 is the sequence of integers G(b)(b >= a)
defined by the following recursion:
G(a) = n
G(b+1) = Bump_b( G(b) ) - 1 if G(b) > 0
= 0 otherwise
where Bump_b(G(b)) is the value that results from changing
every instance of b to b+1 in the level-k base-b
representation of G(b). NB: Unlike Goodstein, we are using
the base itself to index the sequence <G(a), G(a+1), ...>,
and the notation G(b) supresses the dependence on level k,
initial base a, and initial value n = G(a).
For convenience, we speak of the sequence as "terminating"
at the least base B such that G(B) = 0, and refer to B as
the "final base". It can be shown that all Goodstein
sequences terminate.
Examples
--------
Level-1 Goodstein sequence starting with base 2, value 4:
base b term G(b)
------ -----------------------------------------------
2 4 = 2+2
3 3+3 - 1 = 3+2
4 4+2 - 1 = 4+1
5 5+1 - 1 = 5
6 5
7 4
8 3
9 2
10 1
11 0
B = final base = 2^2*3-1 = 11.
Level-2 Goodstein sequence starting with base 2, value 4:
base b term G(b)
------ -----------------------------------------------
2 4 = 2*2
3 3*3 - 1 = 3*2+2
4 4*2+2 - 1 = 4*2+1
5 5+2+1 - 1 = 5*2
6 6*2 - 1 = 6+5
7 7+5 - 1 = 7+4
8 8+4 - 1 = 8+3
9 9+3 - 1 = 9+2
10 10+2 -1 = 10+1
11 11+1 - 1 = 11
12 12 - 1 = 11
13 10
... ...
23 0
B = final base = 2^3*3-1 = 23.
Level-3 Goodstein sequence starting with base 2, value 4:
base b term G(b)
------ -----------------------------------------------
2 4 = 2^2
3 3^3 - 1 = 3^2*2+3*2+2
4 4^2*2+4*2+2 - 1 = 4^2*2+4*2+1
... ...
23 23^2*2
...
j j^2 (j = 2^27*3 - 1)
...
B 0
B = final base = 2^402653211*3 - 1.
Level-4 Goodstein sequence starting with base 2, value 4:
base b term G(b)
------ -----------------------------------------------
2 4 = 2^^2
3 3^^3 - 1 =
3^^2^(3*2+2)*(3^2*2 + 3*2 + 2)
+ 3^^2^(3*2+1)*(3^2*2 + 3*2 + 2)
+ 3^^2^(3*2 )*(3^2*2 + 3*2 + 2)
+ 3^^2^(3 +2)*(3^2*2 + 3*2 + 2)
+ 3^^2^(3 +1)*(3^2*2 + 3*2 + 2)
+ 3^^2^(3 )*(3^2*2 + 3*2 + 2)
+ 3^^2^(2 )*(3^2*2 + 3*2 + 2)
+ 3^^2^(1 )*(3^2*2 + 3*2 + 2)
+ 3^2*2 + 3*2 + 2
4 etc.
... ...
B 0
B = final base = 2^(?)*3-1.
--r.e.s.
r.e.s.
> Goodstein's level-k base-b representation of integer n,
> is the expression defined recursively as follows,
> with n >= 0, k >= 1, b >= 2:
>
> R(n)
> = n (0 <= n <= b-1)
> = b [k] R(x_k) [k-1] R(x_(k-1)) ... [1] R(x_1) (n >= b)
>
> where x_1,...,x_k are the largest integers satisfying
> b [k] x_k [k-1] x_(k-1) ... [j] x_j <= n (1 <= j <= k).
>
> Thus,
> level-1 representations have form b+X,
> with X also of this form[, or is a digit];
> level-2 representations have form b*X+Y,
> with X,Y also of this form[, or is a digit];
> level-3 representations have form b^X*Y+Z,
> with X,Y,Z also of this form[, or is a digit];
> level-4 representations have form b^^X^Y*Z+T,
> with X,Y,Z,T also of this form[, or is a digit];
> etc.
I'd inadvertently omitted the part 'or is a digit'.
In these hereditary base-b representations, a digit
is an integer in the set {0,1,...,b-1} (as usual).
( For the purpose of representing arbitrary ordinals,
Goodstein also introduced more general forms in which
"digits" are not restricted to {0,1,...,b-1}, such
that the "value" of a representation need not equal
the integer it represents. (!) )
I'd neglected to cite the primary source ...
Goodstein, R. L.,
"Transfinite Ordinals in Recursive Number Theory"
J. Symb. Logic 12, 123-129, 1947.
> By convention, representations are abbreviated by omitting
> any instances of +0, *1, ^1, ^^1, etc.; for example,
> the level-3 base-2 representation of the number 6 is
> 2^(2^1*1+0)*1+(2^1*1+0), which abbreviates to 2^2+2.
>
> Examples:
> Base-2 representations of 266 at levels 1,2,3,4,5:
> level 1: R(266) = 2+2+...+2 (with 133 2's)
> level 2: R(266) = 2*(2*(2*(2*2*2*2*2+1))+1)
> level 3: R(266) = 2^2^(2+1)+2^(2+1)+2
> level 4: R(266) = 2^^(2+1)^2+2^^2*2+2
> level 5: R(266) = 2^^^2^^2+2^^^2*2+2.
BTW, although the convention improves economy of notation,
it somewhat disguises the *positional* role played by the
digits, which is similar to that in non-hereditary base-b
representations.
--r.e.s.