euler14.clj

; Problem 14
;
; The following iterative sequence is defined for the set of positive integers:
;
; n -> n/2 (n is even)
; n -> 3n + 1 (n is odd)
;
; Using the rule above and starting with 13, we generate the following sequence:
;
; 13  40  20  10  5  16  8  4  2  1
;
; It can be seen that this sequence (starting at 13 and finishing at 1) contains
; 10 terms. Although it has not been proved yet (Collatz Problem), it is thought
; that all starting numbers finish at 1.
; 
; Which starting number, under one million, produces the longest chain?
;
 
(defn hotpo-count [x]
  (if (pos? x)
    (loop [n x cnt 0]
    (cond (= n 1)
	  (inc cnt)
	  (even? n)
	  (let [nn (/ n 2)]
	    (recur nn (inc cnt)))
	  :else
	  (let [nn (inc (* n 3))]
	    (recur nn (inc cnt)))))))
 
(defn longest-hotpo-below [limit]
  (loop [x (max 1 (/ limit 2)) maxx 0 len 0]
    (if (= x limit) 
      maxx
      (let [cnt (hotpo-count x)]
	(if (> cnt len)
	  (recur (inc x) x cnt)
	  (recur (inc x) maxx len))))))
 
(def answer (longest-hotpo-below 1000000))
; => 837799 (525 steps)