Skip to content

Instantly share code, notes, and snippets.

@littleredcomputer
Created January 29, 2015 05:25
Show Gist options
  • Save littleredcomputer/b53954fd82badaa52317 to your computer and use it in GitHub Desktop.
Save littleredcomputer/b53954fd82badaa52317 to your computer and use it in GitHub Desktop.
(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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment