;; sbcl commonlisp
;;下面研究康托尔配对函数

(defun f (z)
  (let ((i (realpart z))
        (j (imagpart z)))
    (+ (* 1/2
          (+ i j)
          (+ i j 1))
       j)))


;; 通过递归实现的反函数
(defun reverse-f (n)
  (cond
    ((= n 0) #C(0 0))
    ((= n 1) #C(1 0))
    (t (let ((y-- (reverse-f (1- n))))
         (cond ((= 0 (realpart y--))
                (+ 1
                   (* #C(0 -1)
                      y--)))
               (t (+ #C(-1 1)
                     y--)))))))

(reverse-f 0);;should=0 0
(reverse-f 1);;should=1 0
(reverse-f 2);;should=0 1
(reverse-f 3);;should=2 0
(mapcar #'reverse-f '(1 2 3 4 5 6 7 8 9 10 11 12 13 14) )


;; 但是如何解丢番图方程(1/2)(x+y)(x+y+1)+y=n还是没有什么头绪。



(defun iter (x0 f n)
  (if (= n 0)
      x0
      (iter (funcall f x0) f (- n 1))))


(defun reverse-f (n)
  (iter #C(0 0)
        #'(lambda (z)
            (cond
              ((= z #C(0 0))
               #C(1 0))
              ((= 0 (realpart z))
               (+ 1
                  (* #C(0 -1)
                     z)))
              (t (+ #C(-1 1)
                    z))))
        n))


(defun S (n) (* 1/2 n (1+ n)))
(defun S^r (n)
  (multiple-value-bind (f r)
      (floor (* 1/2 (+ -1 (sqrt (1+ (* 8 n))))))
    f))
(defun reverse-f (n)
  (let* ((m (S^r n))
         (Y (- n (S (S^r n))))
         (X (- m Y)))
    (format t "n=~a~% m=~a~% ~a==(S (S^r n))~% y=~a~% x=~a~%" n m (S (S^r n)) y x)
    (cons X Y)
    )
  )

(mapcar #'reverse-f '(33333333333333333) )
(floor (+ 1 3/22222222222222222222222222222222222222222222222222222))