cantor.clj

(ns scratch.cantor)

(defn next-coord [[x y]]
  (cond
   ;; on the top row
   (zero? x)
   (if (zero? (mod y 2))
     [x (inc y)]
     [(inc x) (dec y)])
   ;; on the left column
   (zero? y)
   (if (zero? (mod x 2))
     [(dec x) (inc y)]
     [(inc x) y])
   ;; going up
   (zero? (mod (+ x y) 2))
   [(dec x) (inc y)]
   ;; otherwise, going down
   :default
   [(inc x) (dec y)]))

(defn coord-to-ratio [[x y]]
  (clojure.lang.Ratio. (bigint (inc x)) (bigint (inc y))))

(defn irreducible? [[x y]]
  (let [ratio (coord-to-ratio [x y])]
    (= (.numerator ratio) (inc x))))

(defn cantor-seq []
  (->> [0 0]
       (iterate next-cantor-coord)
       (filter irreducible?)
       (map coord-to-ratio)))

;;scratch.cantor> (take 100 (cantor-seq))
;;(1/1 1/2 2/1 3/1 2/2 1/3 1/4 2/3 3/2 4/1 5/1 4/2 3/3 2/4 1/5 1/6 2/5
;; 3/4 4/3 5/2 6/1 7/1 6/2 5/3 4/4 3/5 2/6 1/7 1/8 2/7 3/6 4/5 5/4 6/3
;; 7/2 8/1 9/1 8/2 7/3 6/4 5/5 4/6 3/7 2/8 1/9 1/10 2/9 3/8 4/7 5/6
;; 6/5 7/4 8/3 9/2 10/1 11/1 10/2 9/3 8/4 7/5 6/6 5/7 4/8 3/9 2/10
;; 1/11 1/12 2/11 3/10 4/9 5/8 6/7 7/6 8/5 9/4 10/3 11/2 12/1 13/1
;; 12/2 11/3 10/4 9/5 8/6 7/7 6/8 5/9 4/10 3/11 2/12 1/13 1/14 2/13
;; 3/12 4/11 5/10 6/9 7/8 8/7 9/6)