pell.clj

(ns cf
  (:require [clojure.math.numeric-tower :as nt]))

(defn- step [x-2 x-1 [a & as]]
  (when a
    (let [x (+ (* a x-1) x-2)]
      (cons x (lazy-seq (step x-1 x as))))))

(defn convergents [as]
  (let [c (fn c [[h & hs] [k & ks]]
            (when (and h k)
              (cons (/ h k) (lazy-seq (c hs ks)))))]
    (c (step 0 1 as) (step 1 0 as))))

(defn cf-sqrt [n]
  (let [[a0 r0] (nt/exact-integer-sqrt n)]
    (if (zero? r0)
      (list a0)
      (loop [m 0 d 1 a a0 r []]
        (if (= a (* 2 a0))
          (cons a0 (cycle r))
          (let [m' (- (* d a) m)
                d' (/ (- n (* m' m')) d)
                a' (nt/floor (/ (+ a0 m') d'))]
            (recur m' d' a' (conj r a'))))))))

(defn pell-solution [n]
  (let [solution? (fn [r]
                    (let [r? (ratio? r)
                          x (if r? (numerator r) r)
                          y (if r? (denominator r) 1)]
                      (= 1 (- (* x x) (* n y y)))))]
    (->> n cf-sqrt convergents (filter solution?) first)))

(-> 29 pell-solution println)