Project Euler 66

chakravala.clj

(defn natural? 
  "Returns true if n is a natural number (greater than zero, and with no 
  fractional component), else false."
  [n] 
  (and (> n 0) (zero? (rem n 1))))

(defn nth-sgonal  
  "For a given s-gonal number P(s,n) = x, returns n (n is a natural number if
  x is a term of the given s-gonal sequence)."
  ^double [^long x ^long s]
  { :pre ((and pos? x) (< 2 s)) } 
  (/ 
    (- (+ (Math/sqrt (+ (- (* 8 s x) (* 16 x)) (* (- 4 s) (- 4 s)))) s) 4) 
    (- (* 2 s) 4)))

(defn sgonal? 
  "Returns true if x is a term of the s-gonal sequence, else false."
  [^long x ^long s]
  { :pre ((and pos? x) (< 2 s)) } 
  (natural? (nth-sgonal x s)))

(defn integers-larger-than
  "Returns an infinite sequence of integers larger than n."
  [n]
  (range (inc n) Double/POSITIVE_INFINITY))

(defn integers-smaller-than
  "Returns an infinite sequence of integers smaller than n."
  [n]
  (range (dec n) Double/NEGATIVE_INFINITY -1))

(defn chakravala 
  "Returns a vector with the coefficients [a,b] to solve Pell's equation 
  (a^2 - nb^2 = 1) for the given n using the Chakravala method."
  [n]
  { :pre [(pos? n) (not (sgonal? n 4)) ]}
  (let [sqrtn (first (exact-integer-sqrt n)) 
    find-initial (fn [n] [sqrtn 1 (- (*' sqrtn sqrtn) n)])
    find-optimal-m (fn [[a b k] n] 
      (let [pm (interleave (integers-smaller-than (inc sqrtn)) (integers-larger-than sqrtn))
        candidates (take 2 (filter #(zero? (rem (+' a (*' b %)) k)) pm))
        c1 (first candidates)
        c2 (second candidates)]
        (if (< (abs (- (*' c1 c1) n)) (abs (- (*' c2 c2) n))) c1 c2)))
    step (fn [[a b k] n m] (let [k' (abs k)] 
      [(/ (+' (*' a m) (*' n b)) k') (/ (+' a (*' b m)) k') (/ (- (*' m m) n) k)]))]

    (subvec (loop [abk (find-initial n)]
      (cond
        (= (abk 2) 1) abk ;; k = 1
        :else (recur (step abk n (find-optimal-m abk n))))) 0 2)))

euler-66.clj

(defn euler-66 [] (ffirst (sort 
  #(compare (second %2) (second %1)) 
    (into [] (for [x (remove #(sgonal? % 4) (range 1 1001))] 
      [x (first (chakravala x))])))))