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

Reply via email to