Hi Neil,<div><br></div><div>Thanks for the educational code.  I had to remove the error line in your code as there are more than one number &lt; 1000000 with the same collatz length... in fact it happens right away:</div><div>
<br></div><div><div>&gt; (define ht (make-hash (list &#39;(1 . 1))))</div><div>&gt; (collatz-length ht 999999)</div><div>259</div><div>&gt; (collatz-length ht 999998)</div><div>259</div><div><br></div><div>-Joe</div><div>
<br></div><br><div class="gmail_quote">On Mon, Apr 2, 2012 at 9:40 PM, Neil Van Dyke <span dir="ltr">&lt;<a href="mailto:neil@neilvandyke.org">neil@neilvandyke.org</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Joe Gilray wrote at 04/03/2012 12:00 AM:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
*The bad news*: it still feels a little clunky.  It has a lot of imperative statements and the memoization in the hash table feels too much like a side-effect to me.<br>
<br>
Any more help?<br>
</blockquote>
<br>
Here&#39;s an implementation without mutations.  It&#39;s simple brute-force with memoization (I&#39;m not aware of an algorithmic or numeric shortcut).<br>
<br>
Note that it uses immutable hashes functionally, passing &quot;memo&quot; hashes into and out of every place that we would want to update the memoization.<br>
<br>
Note also that I originally had &quot;answer-n-list&quot; to record multiple &quot;n&quot; having the same term-count, but then I added the &quot;error&quot; form to verify that this algorithm never has more than one &quot;n&quot; in &quot;answer-n-list&quot;.<br>

<br>
#lang racket/base<br>
<br>
(define (f n)<br>
  (if (even? n)<br>
      (/ n 2)<br>
      (+ 1 (* 3 n))))<br>
<br>
(define (get-terms-count memo n)<br>
  ;; Note: We don&#39;t have to detect cycles, at least not for max-n 999,999<br>
  (cond ((hash-ref memo n #f) =&gt; (lambda (n-steps)<br>
                                   (values memo n-steps)))<br>
        (else (let*-values (((next-n)            (f n))<br>
                            ((memo next-n-steps) (get-terms-count memo next-n))<br>
                            ((n-steps)           (+ 1 next-n-steps)))<br>
                (values (hash-set memo n n-steps)<br>
                        n-steps)))))<br>
<br>
(define (euler-14 (max-n (- #e1e6 1)))<br>
  (let loop ((answer-n-list      &#39;(1))<br>
             (answer-terms-count 1)<br>
             (n                  max-n)<br>
             (memo               #hash((1 . 1))))<br>
    (if (= 1 n)<br>
        (values answer-n-list answer-terms-count)<br>
        (let-values (((memo n-terms-count) (get-terms-count memo n)))<br>
          (cond ((&lt; n-terms-count answer-terms-count)<br>
                 (loop answer-n-list<br>
                       answer-terms-count<br>
                       (- n 1)<br>
                       memo))<br>
                ((&gt; n-terms-count answer-terms-count)<br>
                 (loop (cons n &#39;())<br>
                       n-terms-count<br>
                       (- n 1)<br>
                       memo))<br>
                (else ; (= n-terms-count answer-terms-count)<br>
                 (error &#39;euler-14 &quot;seems to be unreachable for max-n 999,999&quot;)<br>
                 (loop (cons n answer-n-list)<br>
                       answer-terms-count<br>
                       (- n 1)<br>
                       memo)))))))<br>
<br>
(euler-14)<div class="HOEnZb"><div class="h5"><br>
<br>
Neil V.<br>
<br>
-- <br>
<a href="http://www.neilvandyke.org/" target="_blank">http://www.neilvandyke.org/</a><br>
____________________<br>
 Racket Users list:<br>
 <a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/<u></u>users</a><br>
</div></div></blockquote></div><br></div>