What is the maximum recursion depth reached by this program?

Henry Rich On 4/11/2018 4:05 PM, Jose Mario Quintana wrote:

You might like to look also at Arie Groeneveld's message, [Jprogramming] Crash calculating large hyper operations http://www.jsoftware.com/pipermail/programming/2015-November/043351.html Unfortunately, running on the latest stable release, JVERSION Engine: j806/j64nonavx/windows Release: commercial/2017-11-06T10:01:33 Library: 8.06.09 Qt IDE: 1.6.2/5.6.3 Platform: Win 64 Installer: J806 install InstallPath: j:/program files/j Contact: www.jsoftware.com the following, S=: 1 :0 : if. 0= y do. 0 else. 'q r'=. (0,m) #: y ( r *(1+m) ^ (0 (m S) x)) + (1+x) m S q end. ) G=: (>:@[ $: _1+ 4 : '0 (x S)y')`[@.(0=]) 2 G"0 i.4 now produces a crash ("J has stopped working") instead of, 2 3 5 7 As far as I can see, the code should run on J804 but I do not know if it runs on J805 (or on the latest and greatest j807). Anyway, in theory, 2 G"0 i.5 should include the additional number, _1 + 3 * 2 ^ 402653211x in practice, of course, it cannot (even trying to execute the sentence _1 + 3 * 2 ^ 402653211x produces a limit error). On Wed, Apr 11, 2018 at 9:15 AM, 'Jon Hough' via Programming < programm...@jsoftware.com> 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 134078079299425970995740249982 058461274793658205923933777235614437217640300735469768018742 98166903427690031858186486050853753882811946569946433649006084099 191101259794547752035640455970396459919808104899009433713951 27892465205302426158030... -------------------------------------------- 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---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm

--- This email has been checked for viruses by AVG. http://www.avg.com ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm