I recently read about
Goodstein sequences for the first time, and was interested in writing a J verb that can generate a sequence.
Goodstein sequences are defined here:
definition
A Goodstein sequence is defined in terms of
hereditary representations of numbers.
An example of hereditary representation of 100 using base 2.
100=26+25+22=222+2+222+1+22.
Let the hereditary representation of
n using base
2 be
G0(n), i.e. the start of the sequence.
Then
G1(n) uses the hereditary representation of
n base 2, but exchanges 3 for 2 in all places in this representation. Finally, we minus 1.
We can continue, so in general,
Gm+1(n)=Hm+1(Gm)−1
where
Ha(x) is the base
a hereditary representation of
x.
For example:
G0(100)=100=26+25+22=222+2+222+1+22.
G1(100)=333+3+333+1+33−1=228767924549636.
G2(100)=34860300617850752458892464995335199931446351133540222782081259753676586478191222...
G3(100)=59814694315693446387155462718734091954899936833389952752466750303416092596593874...
This sequence grows explosively fast for most values of
n. Interestingly,
Goodstein's Theorem states that it will always terminate at 0 eventually. For all positive values of
n. Even though it is futile to attempt computing a Goodstein sequence for most values of
n, as the numbers involved become unmanageable very quickly, it is still interesting and worthwhile writing a verb to do such a thing.
Here is one implementation in J:
goodstein=: 4 : 0"0 0
if. y <: 0 do. 0 return.
elseif. y = x do. x+1 return.
end.
s=. I. (x:x) (|.@:((>:@:>.@:^. # [) #: ])) x:y
+/ (x+1) ^ (x: x) goodstein s
)
G=: <:@:goodstein`]@.(0&=@:])
NB. generates sequence
genSeq=: 3 : 0"1
'base val its'=. y
c=. 0
vals=. val
whilst. its > c=. c+1 do.
val=. base G val
vals=. vals,val
base=. base+1
if. val = 0 do. break.end.
end.
vals
)
There are three verbs here,
goodstein, G, genSeq.
goodstein is a recursive dyadic verb which calculates the hereditary representation of the right argument, with base the left argument, and then exchanges occurences of the base by
base+1. The reason for the recursion is that for each exponent of the base in the hereditary representation sum, we also need to calculate a hereditary representation.
G merely subtracts one from the return value of
goodstein.FInally,
genSeq, is used to simply generate a sequence. It takes three arguments; the start base (which should be 2); the starting value; the number of iterations to calculate.
Example:
will return 100 228767924549636 34860300617850752458892464995...