My first answer was actually comletely wrong, and only works for the simplest
cases. This is a more robust and correct solution
Advertising
goodstein=: 4 : 0"0 0
if. y = x do.
x+1 return.
elseif. y = 0 do.
0 return.
end.
s=. I. x (|.@:((>:@:>.@:^. # [) #: ])) y
d=. (x+1) ^ (x:x) goodstein x: s
+/d
)
G=: <:@:goodstein
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
end.
vals
)
genSeq 2 4 10
4 26 41 60 83 109 139 173 211 253 299
genSeq 2 19 3
19 7625597484990
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
19110125979454775203564045597039645991980810489900943371395127892465205302426158030...
--------------------------------------------
On Wed, 4/11/18, 'Jon Hough' via Programming <programm...@jsoftware.com> wrote:
Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
To: "Programming Forum" <programm...@jsoftware.com>
Date: Wednesday, April 11, 2018, 5:14 PM
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm