Hi,
This is my tacit version. Not claiming speed (or anything in the way of code
legibility for that matter). The important verb is hbi, hereditary base-x
incrementation of y used in creating the Goodstein sequence.
My gs verb uses a starting base of 2, and gss starts with base x:
hbi=: ([ (] +/ . * >:@[ ^ [ $: i.@-@#@]) #.^:_1)`]@.(0 = ])"0
gs=: , >:@# <:@hbi {:
gss=: ] , (+ <:@#) <:@hbi {:@]
gs^:(0~:{:)^:10 ] 3x
3 3 3 2 1 0
gs^:(0~:{:)^:10 ] 4x
4 26 41 60 83 109 139 173 211 253 299
gs^:(0~:{:)^:3 ] 19x
19 7625597484990
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084099
191101259794547752035640455...
3 gss^:(0~:{:@])^:10 ] 3x
3 3 2 1 0
Sorry if I didn’t explain my code, kind of short on time. I’m pretty sure it
works though!
Cheers,
Louis
> On 11 Apr 2018, at 15:15, 'Jon Hough' via Programming
> <[email protected]> wrote:
>
> My first answer was actually comletely wrong, and only works for the simplest
> cases. This is a more robust and correct solution
>
> 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 <[email protected]>
> wrote:
>
> Subject: [Jprogramming] Goodstein Sequences and Hereditary base-n notation
> To: "Programming Forum" <[email protected]>
> 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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
