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
