Lazy Sequences that "Look Ahead" for Project Euler Problem 14

Question

I'm trying to solve Project Euler Problem 14 in a lazy way. Unfortunately, I may be trying to do the impossible: create a lazy sequence that is both lazy, yet also somehow 'looks ahead' for values it hasn't computed yet.

The non-lazy version I wrote to test correctness was:

(defn chain-length [num]
  (loop [len 1
         n  num]
(cond
  (= n 1) len 
  (odd? n) (recur (inc len) (+ 1 (* 3 n)))
  true     (recur (inc len) (/ n 2)))))

Which works, but is really slow. Of course I could memoize that:

(def memoized-chain
   (memoize
     (fn [n]
       (cond
        (= n 1) 1 
         (odd? n) (+ 1 (memoized-chain (+ 1 (* 3 n))))
         true     (+ 1 (memoized-chain (/ n 2)))))))

However, what I really wanted to do was scratch my itch for understanding the limits of lazy sequences, and write a function like this:

(def lazy-chain
     (letfn [(chain [n] (lazy-seq
                         (cons (if (odd? n)
                                 (+ 1 (nth lazy-chain (dec (+ 1 (* 3 n)))))
                                 (+ 1 (nth lazy-chain (dec (/ n 2)))))
                               (chain (+ n 1)))))]
       (chain 1)))

Pulling elements from this will cause a stack overflow for n>2, which is understandable if you think about why it needs to look 'into the future' at n=3 to know the value of the tenth element in the lazy list because (+ 1 (* 3 n)) = 10.

Since lazy lists have much less overhead than memoization, I would like to know if this kind of thing is possible somehow via even more delayed evaluation or queuing?

Answer 1

A seq "looking into the future"

An example of a funky seq looking into the future might look like this:

(def funky-seq
     (let [substrate (atom ())]
       (letfn [(funk [n] (delay (if (odd? n) n @(nth @substrate (inc n)))))]
         (reset! substrate (map funk (range))))
       (map deref @substrate)))

user> (take 10 funky-seq)
(1 1 3 3 5 5 7 7 9 9)

(A cookie to whoever makes this simpler without breaking it. :-))

Of course if determining the value of an element might involve looking at a "future" element which itself depends on a further element which calls for the computation of a still more distant element..., the catastrophe cannot be helped.

Euler 14

The fundamental problem with the scheme of "looking into the future" the code from the question attempts to employ aside, this approach doesn't really solve the problem, because, if you decide to start from 1 and go upwards, you need to take branching into account: a 10 in a Collatz chain might be arrived at through the application of either rule (the n / 2 rule applied to 20 or the 3n + 1 rule starting from 3). Also, if you wish to build your chains upward, you should reverse the rules and either multiply by 2 or subtract 1 and divide by 3 (applying, at each step, that rule which produces an integer -- or possibly both if both do).

Of course you could build a tree, rather than a lazy list, but that wouldn't look anything like the code sketch in the question and I'd expect you to end up ultimately memoizing the thing.

The above is to be qualified with the remark that you might have a conjecture as to which "chain building rule" is likely to generate the longest chain starting from 1 while having the final entry stay below the given limit. If that is the case, you should probably prove it correct and then implement it directly (through loop / recur starting at 1); without a proof, you can't really claim to have solved the problem.