COMPUTING SCIENCE
Calculemus!
Celebrating 25 years of celebrating computation
Brian Hayes
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.
» Post Comment