Goodstein's theorem: https://en.wikipedia.org/wiki/Goodstein%27s_theorem
This states that every Goodstein sequence eventually terminates at 0.
The wikipedia page defines Goodstein sequences in terms of Hereditary base-n
notation
one such sequence is 4,26,41,60...
Copying verbatim from wikipedia:
==============
The Goodstein sequence G(m) of a number m is a sequence of natural numbers. The
first element in the sequence G(m) is m itself. To get the second, G(m)(2),
write m in hereditary base-2 notation, change all the 2s to 3s, and then
subtract 1 from the result. In general, the (n + 1)-st term G(m)(n + 1) of the
Goodstein sequence of m is as follows:
Take the hereditary base-n + 1 representation of G(m)(n).
Replace each occurrence of the base-n + 1 with n + 2.
Subtract one. (Note that the next term depends both on the previous term and on
the index n.)
Continue until the result is zero, at which point the sequence terminates.
===============
The sequences take an impossibly long time to terminate for most inputs, so
there is no use writing a verb that iterates until convergance. This is my verb
that will calculate the first N elements of the sequence,
starting with a given base and val. the base should start at 2, to conform to
the above definition.
goodstein=: 3 : 0
'base val its'=. y
vals=. ''
c=: 0
whilst.its> c=: c+1 do.
if. val = 0 do. vals return.
else.
t=: ((1+ >.base^.val)#base) #: val
if. base < # t do.
if. 0 < base { |.t do.
tr=: 0 (base}) |.t
if. (base+1) < # tr do.
ts=: (1+(base+1){tr) ((x+1)}) tr
ts=: |.ts
else.
ts=: tr,1
ts=: |.ts
end.
else. ts=: t end.
else.
ts=: t
end.
val=. <:(base+1) #. ts
vals=. vals,val
base=. base+1
end.
end.
vals
)
NB. example
goodstein 2 4 9
26 41 60 83 109 139 173 211 253 NB. continues to very large numbers.
goodstein 2 3 5
3 3 2 1 0 NB. terminates after 6 iterations
Is was hoping the goodstein verb could be defined tacitly, but my verb is
clearly a bit of a mess. Just for fun, any elegant solutions?
Thanks,
Jon
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
