Numerical test of abc hypothesis (yes, the one)

Hi, Habr.

On Geektimes Habr there were already several articles about the abc-hypothesis (for example, in 2013 and in 2018 ). The story itself about a theorem that cannot be proven for many years, and then cannot be checked for as many years, certainly deserves at least a feature film. But in the shadow of this wonderful story, the theorem itself is considered too superficially, although it is no less interesting. Even by the fact that the abc hypothesis is one of the few unsolved problems of modern science, the task of which can be understood even by a fifth-grader. If this hypothesis is indeed true, then the proof of other important theorems easily follows from it, for example, the proof of Fermat's theorem .

Without claiming Mochizuki’s laurels, I also decided to try and decided to check with the computer how much the equality promised in the hypothesis was fulfilled. Actually, why not? Modern processors are not only to play games - why not use a computer in its basic (compute) purpose ...
')
Who cares what happened, please under the cat.

Formulation of the problem

Start over. What is the theorem about? As Wikipedia says (the wording in the English version is slightly more understandable), for mutually simple (without common divisors) numbers a, b and c, such that a + b = c, for any ε> 0 there is a limited number of triples a + b = c, such that:



The function rad is called a radical , and denotes the product of prime factors of a number. For example, rad (16) = rad (2 * 2 * 2 * 2) = 2, rad (17) = 17 (17 is a prime number), rad (18) = rad (2 * 3 * 3) = 2 * 3 = 6, rad (1,000,000) = rad (2 ^ 6 ⋅ 5 ^ 6) = 2 * 5 = 10.

Actually, the essence of the theorem is that the number of such triples is quite small. For example, if we take at random ε = 0.2 and equality 100 + 27 = 127: rad (100) = rad (2 * 2 * 5 * 5) = 10, rad (27) = rad (3 * 3 * 3) = 3, rad (127) = 127, rad (a * b * c) = rad (a) * rad (b) * rad (s) = 3810, 3810 ^ 1.2 is clearly greater than 127, the inequality is not satisfied. But there are exceptions, for example, for equality 49 + 576 = 625, the condition of the theorem is fulfilled (those who wish can check it themselves).

The next key moment for us is of these equalities, according to the theorem, a limited number. Those. This means that you can just try them all on your computer. In the end, this gives us the Nobel Prize is quite an interesting programming problem.

So let's get started.

Source

The first version was written in Python, and although this language is too slow for such calculations, writing code on it is easy and simple, which is convenient for prototyping.

Getting the radical : decompose the number into prime factors, then remove the repetitions, converting the array into a set. Then just get the product of all the elements.

def prime_factors(n): factors = [] # Print the number of two's that divide n while n % 2 == 0: factors.append(int(2)) n = n / 2 # n must be odd at this point so a skip of 2 ( i = i + 2) can be used for i in range(3, int(math.sqrt(n)) + 1, 2): # while i divides n , print i ad divide n while n % i == 0: factors.append(int(i)) n = n / i # Condition if n is a prime number greater than 2 if n > 2: factors.append(int(n)) return set(factors) def rad(n): result = 1 for num in prime_factors(n): result *= num return result 

Mutually simple numbers : decompose numbers into factors, and just check the intersection of sets.

 def not_mutual_primes(a,b,c): fa, fb, fc = prime_factors(a), prime_factors(b), prime_factors(c) return len(fa.intersection(fb)) == 0 and len(fa.intersection(fc)) == 0 and len(fb.intersection(fc)) == 0 

Check : we use already created functions, everything is simple.

 def check(a,b,c): S = 1.2 # Eps=0.2 if c > (rad(a)*rad(b)*rad(c))**S and not_mutual_primes(a, b, c): print("{} + {} = {} - PASSED".format(a, b, c)) else: print("{} + {} = {} - FAILED".format(a, b, c)) check(10, 17, 27) check(49, 576, 625) 

Those interested can experiment on their own by copying the above code into any online Python editor. Of course, the code works as expectedly slowly, and going through all the triples to at least a million would be too long. Below is a optimized version under the spoiler, it is recommended to use it.

The final version was rewritten in C ++ using multi-threading and some optimization (working on C with intersection of sets would be too hardcore, although probably faster). The source code is under the spoiler, it can be compiled in the free g ++ compiler, the code works under Windows, OSX and even on Raspberry Pi.


For those who are too lazy to install the C ++ compiler, a slightly optimized Python version is shown, which can be run in any online editor (I used https://repl.it/languages/python ).

results

There are really very few a, b, c tracks.

Some results are shown below:
N = 10 : 1 “troika”, execution time <0.001c
1 + 8 = 9

N = 100 : 2 "triples", execution time <0.001c
1 + 8 = 9
1 + 80 = 81

N = 1000 : 8 "triples", execution time <0.01c
1 + 8 = 9
1 + 80 = 81
1 + 242 = 243
1 + 288 = 289
1 + 512 = 513
3 + 125 = 128
13 + 243 = 256
49 + 576 = 625

N = 10000 : 23 "troika", runtime 2s


N = 100000 : 53 "triples", run time 50c


With N = 1,000,000, we have only 102 “triples”, the full list is given under the spoiler.


Alas, the program still works slowly, I didn’t wait for the results for N = 10,000,000, the calculation time is more than an hour (maybe I was wrong somewhere with the optimization of the algorithm, and it can be done better).

More interesting to see the results graphically:



In principle, it is quite obvious that the dependence of the number of possible triples on N grows noticeably slower than N itself, and it is quite likely that the result will converge to some specific number for each ε. By the way, as ε increases, the number of “triples” significantly decreases, for example, when ε = 0.4, we have only 2 equalities for N <100000 (1 + 4374 = 4375 and 343 + 59049 = 59392). So in general, it seems that the theorem is indeed satisfied (well, and probably it has already been tested on computers more powerful, and it is possible that all this has long been considered).

Those interested can experiment on their own, if anyone has results for numbers 10,000,000 or more, I’m happy to add them to the article. Of course, it would be interesting to “calculate” until the moment when the set of “triples” stops growing completely, but it can take a really long time, the speed of calculation seems to depend on N as N * N (and maybe N ^ 3), and the process very long. But nevertheless, amazing nearby, and those who wish may well join the search.

Edit: as suggested in the comments, the table with the results already exists in Wikipedia - in the range N up to 10 ^ 18 the number of "triples" is still growing, so the "end" of the set has not yet been found. The more interesting - the intrigue is still preserved.