http://www.jsoftware.com/jwiki/Essays/Collatz%20Conjecture
On Thu, Sep 11, 2014 at 11:16 PM, Neill Robson <[email protected]> wrote: > I've been working on various Project Euler problems in J, and I seem to > always get stuck whenever a problem requires excessive/lengthy recursion. > In particular, I've been working on problem number 14, which asks what > starting value (under 1 million) produces the longest Collatz sequence. > > Now, I started out writing some silly procedural code, mostly to get a > handle on what I was trying to do. Don't bother deciphering it too > carefully: > > PE14=: 3 : 0 > > NB. length is a list of 1 followed by <:y zeroes > > length=: $. multmask~ <: y > > usedNums=: 1 > > for_i. i. &. <: y do. > > collatz=: 1 $ i > > while. -. usedNums e.~ {: collatz do. > > collatz=: collatz , nextColl {: collatz > > end. > > indices=: <: }: collatz > > oldLength=: length {~ <: {: collatz > > newLengths=: |. >: oldLength + i. # indices > > mask=: indices < # length > > indices=: mask # indices > > newLengths=: mask # newLengths > > length=: (newLengths) indices} length > > usedNums=: usedNums , >: indices > > end. > > >: (i. >./) length > > ) > > It basically keeps track of how long each Collatz sequence is, and whenever > a new one is generated, it adds the existing length value to however many > new numbers are added to the front end. > > Anyway, that was too slow, and then the adverb M. was recommended to me. > That led me to this new verb: > > PE14=: >: @ $: @ (-: ` (>: @ (3&*)) @. (2&|)) ` 1: @. (1&=) M."0 > > One would have to pass in >: i. y to this one and find the largest length > from that list. > > It works, but it seems to take just as long as my procedural verb to > complete. By the time any significantly large ceiling is specified, the J > terminal crashes. I have a feeling that, although slightly more terse, this > new verb is no better than the previous one. > > Is there any other method in J to make recursion more efficient? How might > I make the J terminal more tolerant to extended periods of computation? Am > I thinking about this problem in an incorrect manner? > > Thank you for taking the time to respond to this! > > -- > -Neill > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
