The algorithm

What is the abc conjecture | Open and solved problems | Consequences | The algorithm

When searching for abc triples, you'll want a fast method for finding them, and you'll want to be sure you find all triples. It is not possible to find all triples, because there are infinitely many. Her we will describe the algorithm used by BOINC to find all abc triples with a, b and c less than a (large) number N

An abc triple is a triple with the radical less than c. Instead of calculating the radical of a triple, we can also define the radical of one number. We simply multiply all distinct prime factors in the factorisation of this number. As a, b and c are relatively prime, the radical of an abc triple is equal to the radical of a × b × c.

What is the radical of 28? Your answer:
Your answer is correct!Your answer is incorrect.The correct answer is: 14

To find all triples, we first need to know how to find all numbers less than N with a certain radical. Suppose we want to find all numbers less than N with radical 2. A number can only have radical 2 if its only prime factor is 2. This means only powers of 2 have radical 2. To find all powers of 2 less than N, we only need to keep multiplying 2 with 2 until we get a number greater than N. If we think about this we see this is not just the case for 2. If we want to find all numbers less than N with radical p, where p is a prime number, we need to keep multiplying p with itself until the number exceeds N. This is a very fast process. The only thing you need to do is multiply by p until the number exceeds N. For N=100000, a modern computer needs less time than 1 second.

But what happens when we want to find numbers with a radical that is not a prime? Suppose you want to find numbers with radical 6. A number with radical 6 may only have prime factors 2 and 3. If we want to find all numbers with radical 6 we start with 6. Now we will multiply with 2 again, until we have a number larger than N. Now we multiply all the numbers we found with 3, and check which numbers are still less than N. We keep multiplying the numbers we get with 3, until they exceed N. These numbers must be of the form 2^k × 3^m where k and m are positive integers. First we found all numbers of the form 2^k × 3, and removed the ones greater than N. Then we found all numbers 2^k × 3², and removed the ones greater than N. And so on.

Now we'll see what happens with other radicals. The radical of a number can be found by multiplying the distinct prime factors of the number. Therefore, a radical cannot have one prime factor twice. This means 6 can be a radical, as this is 2 × 3, but 4 can't for 4 = 2 × 2, so it's not a product of distinct primes.

Which of the numbers 22, 45, 60 is a radical? Your answer:
Your answer is correct!Your answer is incorrect.The correct answer is: 22

Suppose you have a number which is a product of distinct primes. This number can be a radical. To find all numbers less than N with this radical, we do the same as before. We start with the product of all prime factors, which is the number itself. Now we multiply by the smallest prime factor, as long as the number we get is less than N. Now we take the second prime factor and keep multplying the numbers with this prime factor. We keep doing this with all prime factors in this radical. You need to check more often to see if the number exceeds N, but the process is still fairly fast.

We just saw which numbers can be a radical. These are all numbers where every prime factor in it, is in it only once. This means that every number not divisible by the square of a prime number is a radical. Now we would like to find all possible radicals less than a specific number N. But first we'll need to know how to find all primes less than N.

The sieve of Erathostenes

We'll find all primes less than N by using a method discovered by the Greek mathematician Erathostenes about 240 years A.D. The method works like this: You write down all numbers between 2 and N. The reason we start with 2 is because 1 is not a prime. Now you keep repeating two steps.

Highlight the first number you have not crossed out.
Cross out all multiples of the number you just highlighted.

The first number is 2 so you highlight 2, and cross out 4, 6, 8, 10, 12 etc. Now you highlight the next number you have not crossed out. This is 3. Now you cross out all multiples of 3. Continue doing this until all numbers are either crossed out or highlighted. All highlighted numbers are prime, as they are not divisible by a smaller prime. If they were you would have crossed them out.

The sieve of Erathostenes

We can find all radicals in a slightly different way.

Check if the first number is a prime. If it isn't continue to the next number.
If the number is prime, cross out all multiples of the square of this prime.

All numbers which are not crossed out can be a radical, since you crossed out all numbers which are a multiple of a square.

We need some more information before we can find all abc triples with c less than N. For this we have a look at an arbitrary abc triple. Suppose a, b and c < N are an abc triple. We look at the radicals of a, b and c. We call the number with the smallest radical x, the number with the middle radical y, and the number with the largest radical is called z. This means r(x) < r(y) < r(z). So we sort a, b and c on radical. We know x, y and z are relatively prime as a, b and c are relatively prime. So r(x) × r(y) × r(z) = r(xyz). Of course we also know r(xyz) = r(abc), as x, y and z are the same numbers as a, b and c, only ordered differently. Because a, b and c are an abc triple we know the radical of abc is less than c, so it's also less than N. We know that r(y)² is less than r(y) × r(z) as r(y) <r(z). We also know r(x) ≥ 1, so r(y)² < r(x)r(y)r(z) = r(xyz). So r(y)² < N, so r(y) < √N. Now we can calculate all possible values for r(y), as we have already seen how we can find all radicals below a specific number.

Now we have found a maximum for r(y). We can also find such a maximum for r(x). Because r(y)² < r(y)r(z), r(x)r(y)² < r(x)r(y)r(z), which is less than N. This means r(x) is less than N/r(y)².

The above is true for all abc triples. So now we can find all abc triples with a, b and c less than N. We do this in 6 steps:

We find all radicals less than √N. These radicals are all possible radicals for y.
We find all numbers with this radical, less than N. These are the possible numbers for y.
For each radical found for y, we find all radicals for x. These consist of the radicals less than N/r(y)².
For each radical found for x, we find all possible values less than N with this radical. These are the possible values for x for a certain value for r(y).
With these steps we found all values for y and the associated values for x. Now we need to find a z, so the numbers form an abc triple. Z could be the c of the triple, so x+y=z. X or y could also be the c, so x-y=z or y-x=z, so the absolute value of x-y has to be equal to z. So the final steps are:
Find for every pair x, y the two associated z values.
Find the radical of z and check whether x, y and z are an abc triple.

With these steps we find every abc triple with a, b and c less than N. We saw the first 4 steps don't take much time, and the fifth step is only adding and subtracting. The first five steps take relatively little time. With these five steps a lot of triples are eliminated, and only a small selection of possible abc triples remains. We need to check lot less possible abc triples than with most algorithms. This saves a lot of time, and it's what makes the algorithm fast. In the final step the factorization of z has to be found. For large z's this can take a lot of time. This is a step which needs to be done in every algorithm, so this doesn't make our algorithm any slower than other algorithms.