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>