project euler 64

pe_64.clj

;; Problem 64  : 2011/11/25
;; "Elapsed time: 755.433163 msecs"

;; (sqrt X)+M
;; -----------
;;      N

(defn int-floor [n]
  (Math/round (Math/floor n)))

(defn inverse-rationalize [X M N]
  (let [new-N (/ (- X (* M M)) N)
	new-M (- M)]
    [new-M new-N]))
  
(defn make-proper [X M N]
  (let [numerator (+ (Math/sqrt X) M)
	a (int-floor (/ numerator N))
	new-M (- M (* a N))]
    [a new-M]))
	
;; not used
(defn get-continued-fraction-list
  "Get continued fraction list of Sqrt X"
  ([X] (get-continued-fraction-list X 0 1))
  ([X M N]
     (let [[a prop-M] (make-proper X M N)
	   [new-M new-N] (inverse-rationalize X prop-M N)]
       (lazy-seq
	(cons a
	      (get-continued-fraction-list X new-M new-N))))))


(defn get-continued-fraction-args
  "Get continued fraction parms of Sqrt X"
  ([X] (get-continued-fraction-args X 0 1))
  ([X M N]
     (let [[a prop-M] (make-proper X M N)
	   [new-M new-N] (inverse-rationalize X prop-M N)]
       (lazy-seq
	(cons [new-M new-N]
	      (get-continued-fraction-args X new-M new-N))))))

(defn count-continued-flaction-loop [X]
  (let [continued-flaction-args (drop 1 (get-continued-fraction-args X))
	key (first continued-flaction-args)]
    (loop [n 1
	   cfa (next continued-flaction-args)]
      (if (= (first cfa) key)
	n
	(recur (inc n) (next cfa))))))

(defn pe-64 [n]
  (count
   (filter odd?
	   (map count-continued-flaction-loop
		(filter (complement square?) (range 1 (inc n)))))))