COMPUTING SCIENCE

# Calculemus!

Celebrating 25 years of celebrating computation

# ABCs

My third example is another pursuit of shy, elusive mathematical objects. It concerns the simple equation
*
a
*
+
*
b
*
=
*
c
*
, where
*
a
*
,
*
b
*
and
*
c
*
are positive integers that have no divisors in common (other than 1); for example, the equation 4+5=9 qualifies under this condition.

Now for some number theory. Multiply the three numbers
*
a, b
*
and
*
c
*
, then find all the prime factors of the product. From the list of factors, cast out any duplicates, so that each prime appears just once. The product of the unique primes is called the radical of
*
abc
*
, or
*
rad
*
(
*
abc
*
). For the triple {4, 5, 9}, the product is 4×5×9=180, and the factor list is 2, 2, 3, 3, 5. Removing the duplicated 2s and 3s leaves the unique factor list 2, 3, 5, so that
*
rad
*
(180)=30.

In this example,
*
c
*
is less than
*
rad
*
(
*
abc
*
). Can it ever happen than
*
c
*
is greater than
*
rad
*
(
*
abc
*
)? Yes: The triple {5, 27, 32} has the product 5×27×32=4,320, for which the unique primes are again 2, 3 and 5. Thus
*
c
*
=32 is greater than
*
rad
*
(4,320)=30. Triples where
*
c
*
exceeds
*
rad
*
(
*
abc
*
) are called
*
abc
*
-hits. As with MSTD sets, there are infinitely many of them, and yet they are rare. Among all
*
abc
*
triples with
*
c
*
≤10,000, there are just 120
*
abc
*
-hits.

If
*
c
*
can be greater than
*
rad
*
(
*
abc
*
), how much greater? It's been shown that c can exceed
*
rad
*
(
*
abc
*
) plus any constant or
*
rad
*
(
*
abc
*
) multiplied by any constant. How about
*
rad
*
(
*
abc
*
) raised to some power greater than 1? A conjecture formulated by Joseph Oesterlé of the University of Paris and David W. Masser of the University of Basel claims there are only finitely many exceptional cases where
*
c
*
>
*
rad
*
(
*
abc
*
)
^{
1+ε
}
, for any ε no matter how small. The conjecture has made the search for
*
abc
*
-hits more than an idle recreation. If the conjecture could be proved, there would consequences in number theory, such as a much simpler proof of Fermat's Last Theorem.

In a program to search for
*
abc
*
-hits the one sticky point is factoring the product
*
abc
*
. Factoring integers is a notorious unclassified problem in computer science, with no efficient algorithm known but also no proof that the task is hard. If you want to get serious about the search, you need to give some thought to factoring algorithms—or else latch on to code written by someone else who has done that thinking. On the other hand, for merely getting a sense of what
*
abc
*
-hits look like and where they're found, the simplest factoring method—trial division—works quite well.

Searchers for
*
abc
*
-hits can also join ABC@home (
www.abcathome.com
), a distributed computing project.

**IN THIS SECTION**

EMAIL TO A FRIEND :

# Comments

You don't mention Axiom, though it is a powerful and accessible calculation tool, and can be adapted and developed.

posted by John Spencer

August 12, 2008 @ 1:36 PM

Dear Mr Hayes,
Wolfram now sells Mathematica Home Edition for about $ 300. I have recently started using it (while learning the language) and I am quite pleased.
I very much enjoy your columns and r...

posted by Marc Weinberger

June 10, 2009 @ 1:30 PM

**Of Possible Interest**

**Letters to the Editors**: Getting Personal

**Letters to the Editors**: Global Changes

**Letters to the Editors**: Powerful Questions