; abc conjecture

(define sort #f)
(define merge #f)
(let ()
  (define dosort
    (lambda (pred? ls n)
      (if (= n 1)
          (list (car ls))
          (let ((i (quotient n 2)))
            (domerge pred?
                     (dosort pred? ls i)
                     (dosort pred? (list-tail ls i) (- n i)))))))
  (define domerge
    (lambda (pred? l1 l2)
      (cond
        ((null? l1) l2)
        ((null? l2) l1)
        ((pred? (car l2) (car l1))
         (cons (car l2) (domerge pred? l1 (cdr l2))))
        (else (cons (car l1) (domerge pred? (cdr l1) l2))))))
  (set! sort
    (lambda (pred? l)
      (if (null? l) l (dosort pred? l (length l)))))
  (set! merge
    (lambda (pred? l1 l2)
      (domerge pred? l1 l2))))

(define (rad n)
  (define (uniq x xs)
    (if (null? xs) (list x)
      (if (= (car xs) x) xs
        (cons x xs))))
  (let twos ((n n) (fs (list)))
    (if (even? n) (twos (/ n 2) (uniq 2 fs))
      (if (= n 1) 2
        (let odds ((n n) (f 3) (fs fs))
          (cond ((< n (* f f))
                  (apply * (uniq n fs)))
                ((zero? (modulo n f))
                  (odds (/ n f) f (uniq f fs)))
                (else (odds n (+ f 2) fs))))))))

(define (q a b c)
  (if (and (= (gcd a b) 1)
           (= (gcd b c) 1)
           (= (gcd c a) 1))
      (/ (log c) (log (rad (* a b c))))
      (error 'q "must be coprime")))

(define (abc limit)
  (define (q a b c)
    (/ (log c) (log (rad (* a b c)))))
  (define (f a b)
    (let* ((c (+ a b)) (qabc (q a b c)))
      (if (< limit c) (list)
        (append (if (< qabc 1) (list)
                  (list (list qabc b a c)))
                (f (- (* 2 a) b) a)
                (f (+ (* 2 a) b) a)
                (f (+ a (* 2 b)) b)))))
  (sort (lambda (xs ys) (< (car ys) (car xs)))
    (append (f 2 1) (f 3 1))))

(for-each
  (lambda (trip)
    (display trip)
    (newline))
  (abc 100))

(1.292030029884618 1 80 81)
(1.226294385530917 1 8 9)
(1.1757189916348774 32 49 81)
(1.1126941404922133 1 63 64)
(1.0412424573518235 1 48 49)
(1.018975235452531 5 27 32)