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.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations

**Engineering**: From Lowly Paper Clips to Towering Suspension Bridges