## ABC Conjecture

### September 18, 2012

Our `rad`

function combines factorization by trial division with a `uniq`

auxiliary function that only adds a factor if it is distinct:

`(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))))))))

The `q`

function is simple:

`(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")))

To find all the (*a*,*b*,*c*) triples less than a limit, we can either consider all possible pairs of *a* and *b*, testing each for coprimality, or use a clever method to generate coprime pairs directly, eliminating the need for a test. We’ll be clever. If you start with the two pairs (2,1) and (3,1), then form two infinite ternary trees starting from each (*m*,*n*), each child of the form (2*m*−*n*,*m*), (2*m*+*n*,*m*) and (*m*+2*n*,*n*) forms a new coprime pair; the two trees thus formed are complete and distinct. We return the (*a*,*b*,*c*) triples sorted by descending *q*:

`(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))))

There are 31 triples *q*>1 with *c* less than a thousand:

`> (abc 1000)`

((1.4265653296335432 3 125 128)

(1.3175706029138485 1 512 513)

(1.311101219926227 1 242 243)

(1.292030029884618 1 80 81)

(1.2727904629543532 13 243 256)

(1.226294385530917 1 8 9)

(1.2251805398372944 1 288 289)

(1.2039689893561185 49 576 625)

(1.198754152359422 169 343 512)

(1.1757189916348774 32 49 81)

(1.1366732909394883 25 704 729)

(1.1126941404922133 1 63 64)

(1.1084359145429683 32 343 375)

(1.1048460623308174 104 625 729)

(1.0921945706283556 1 675 676)

(1.0917548251330267 100 243 343)

(1.0790468171894105 1 624 625)

(1.0458626417646626 1 728 729)

(1.0456203807611666 5 507 512)

(1.0412424573518235 1 48 49)

(1.0370424407259895 81 175 256)

(1.0344309549548174 343 625 968)

(1.0326159011595437 81 544 625)

(1.0326070471078377 7 243 250)

(1.0288287974277142 2 243 245)

(1.027195810121916 4 121 125)

(1.0251241218312794 27 512 539)

(1.018975235452531 5 27 32)

(1.0129028397298183 1 224 225)

(1.0084113092374762 200 529 729)

(1.004797211020379 1 960 961))

You can run the program at http://programmingpraxis.codepad.org/fmbvssfd.

Pages: 1 2

A python version. I left out code for gcd and prime factors

Haskell version of the suggested solution. Uses primes and factorization algorithm taken from the haskellwiki

[…] make a long story shorter, there was a challenge on Programming Praxis that intrigued me, which was to write code that given a upper bound on c would generate a list of […]

A Java solution:

I went with quick and easy, using Racket’s excellent

`for*/list`

macro to generate the final step. Interestingly, although it just brute forces the problem rather than the “smarter” solution posted here, it actually runs about 20% faster on the n=1000 case than the code posted here (on the same machine and the same environment). Not entirely sure why, although I am curious if anyone has any thoughts.In any case, you can see my version on my blog.

This algorithm is still to slow to solve http://projecteuler.net/problem=127