Beal’s Conjecture

Beal’s conjecture states that

If m, n, r ≥ 3 and x, y, z are integers, and xm + yn = zr then x, y and z share a common factor.

Several years ago, Peter Norvig wrote a computer program to search for counterexamples. Norvig’s program was written in Python and run on a 400 MHz processor. I have access to a recent 64-bit AMD CPU with lots of RAM, so I decided to update his program and see how far I could push the threshhold.

My approach is essentially the same as his. First, I choose an upper bound on the bases (max_base) and the exponents (max_pow). In this case, I used max_base = max_pow = 1000. With a simple enumeration, this would give 103*6 = 1018 combinations, far too many for a current computer to handle. Furthermore, the numbers involved could be as large as 10001000=103000. That’s a googol raised to the 30th power, and far larger than the native word size of any computer. In general, the running time is O(max_base3 * max_pow3).

Using a hash table

The key insight is to precompute all possible values of zr and store them in a hash table. The keys in this hash table are the various values of zr and the values are the pair (r, z).

Then, for each lefthand side of the equation, xm + yn, it suffices to look the value up in the hash table. If it’s there, we use the z value to check the common factor condition and determine whether we’ve got a real counterexample. These checks take constant time, so that it’s only necessary to enumerate all the x, y, m and n values.

At the cost of O(max_base*max_pow) storage and some initialization cost, we can check each xm + yn in constant time. Thus the total compelxity of the program has been reduced to O(max_base2 * max_pow2), in our case about 1012, which is a manageable number for a modern computer.

Working with reasonably-sized integers

This analysis assumed that we could compare integers in constant time, but with numbers as large as 103000, this is certainly not the case. To deal with this problem, I followed up on one of Norvig’s suggestions and used modular arithmetic. Rather than verifying that xm + yn = zr, I instead verified that xm + yn = zr (mod N). If this is true, then we may or may not have a counterexample. But if it’s not, then we definitely don’t. The number of false positives depends on the choice of the modulus N. Larger values will yield fewer false positives, as will prime numbers. What we lose in accuracy, we gain in speed. Working modulo N, we never have to consider numbers larger than N.

There’s no point in doing this unless the resulting numbers will fit into a machine word, so the largest reasonable choice on a 64-bit machine is N=264. I tried this, but it had a rather high false positive rate compared to primes, so I went with the primes. To do arithmetic modulo a prime p quickly on a computer, numbers as large as p2 must fit in a machine word. According to The Prime Pages, the largest primes less than 232 are p1 = 232-5 and p2 = 232-17. If xm + yn = zr (mod p1) and xm + yn = zr (mod p2), then (x,m,y,n,z,r) is a candidate, and we need to pull out the big guns (arbitrary precision arithmetic) to determine whether it constitutes an actual counterexample.

How effective is this filtering process? Fantastically so. With max_base=200 and max_pow=100, I got this sequence of candidates:

Stage Candidates Percent
All combinations 115,555,328 100%
Candidate (mod p1) 545 0.0005%
Candidate (mod p2) 0 0.0%
Counterexamples 0 0.0%

The big guns never even had to be pulled out! The first filter cut out roughly 199,999 out of every 200,000 possibilities, and the second one took care of the rest. More filters would make the existence of a genuine candidate even less likely.

Constant factor optimizations

There were a few more optimizations to make before I had a finished program. First, from the symmetry of the equation, we can assume that x < y. This eliminates 50% of the computation. Furthermore, there’s no point in considering (x, y) pairs that wouldn’t violate Beal’s conjecture, namely those for which gcd(x, y) > 1. Given any two integers, there is roughly a 6/π2 chance that they are relatively prime to one another (see the math forum for a demonstration of this remarkable fact). Hence these steps have cut out another 2*(1-6/π2) = 80% of the candidates.

The final step before running the search was to construct an optimized hash table to hold the 32-bit integers that we’ve used. I found a workable hash function designed by Thomas Wang, and wrote a lightweight interface around it. There was minimal overhead, since I had no need to include values in the hash table, only keys. With the above hash function, I averaged about 1.5 keys in each nonempty bucket.

The results

My program ran about ten times faster than Norvig’s original Python program on the same hardware, and vastly faster than on his 400Mhz Pentium. For max_base = max_pow = 1000, my program completed the search in just shy of 17 hours. I forgot to include a tally of how many candidates made it past the first prime filter but not the second, so that data is missing from this table.

Stage Candidates Percent
All combinations 301,980,444,768 100%
Candidates (mod p1, p2) 15,683 0.00000519%
Counterexamples 0 0.0%

Sadly, still no counterexamples, and no $100,000. In the future, I may extend the search in other directions. (to fill in more cells in Norvig’s table) But now, it can be succinctly said that Beal’s conjecture is true for all variables up to 1,000.

Correctness

Why should anyone believe my results? For one, you can have the source code and inspect it yourself. To compile, just run “make”. Running the program is a bit more complex, since it involves an executable as well as Norvig’s Python script. For this example, I used

./bealhash3 -v 1000 1000 | python beal.py 1000 1000 | tee 1000x1000.dat

For that matter, you can also inspect 1000×1000.dat, which contains a full list of the candidates produced in my run. If the bealhash program is run with a “-g” flag, then it omits the gcd(x,y)==1 test. This causes causes the Python script to print out legitimate solutions to the Beal equation. I ran Norvig’s original Python script with max_base=200, max_pow=100 and got 809 such solutions. I then added my filter in front of it and got the exact same set of solutions, all 809 of them. This is the main reason I believe in the correctness of my code.

Note that this program MUST BE RUN ON A 64-BIT MACHINE. Otherwise, overflow will produce weirdness and most likely incorrectness.

Future ideas

Virtually all of the execution time of the program is spent doing hash table lookups, so any further optimization would have to improve this. A perfect hash might help here, but I’m not particularly familiar with the theory of perfect hash functions.

Rather than searching over all variables less than a certain bound, I think it would make sense to consider only exponents that are either prime or a power of two. Arguments analogous to those for Fermat’s Last Theorem can be applied here. My program does a decent amount of duplicated computation due to the fact that 23 = 42, etc.

As is often the case, a mathematical proof relating to Beal’s Conjecture could cut down the search space dramatically. For example, one of the first steps taken towards proving FLT was Fermat’s proof when the exponent was four. This eliminated all multiples of four from consideration. Something akin to that would be very helpful here.

29 Comments »

  1. danvk.org » Beal’s Conjecture said,

    May 24, 2007 at 9:49 pm

    [...] put a link to last summer’s work on Beal’s Conjecture over on the right-hand side of the site. A quick [...]

  2. jeet said,

    June 16, 2010 at 9:18 pm

    Hi,
    Why are the number of candidates less for a N = large prime as opposed to N= large number? Also I need to cite your work. Can you provide me with required information?

  3. Greg R said,

    September 7, 2010 at 7:50 pm

    “… due to the fact that 23 = 42, etc.”

    Or 24 = 42, even. ;-) (Unless your statement was mod 2, 4 or 8, I guess.)

  4. Greg R said,

    September 7, 2010 at 7:51 pm

    Doh…so much for my SUP tags.

    In any case, I think you meant that 2^4 = 4^2.

  5. Delu V. said,

    September 20, 2010 at 1:28 am

    Hi,
    I have the proof you need,a paradox in fact.The manuscript has been submitted.As is usual you would have to maintain discretion on the paper till after the journal has peer- reviewed and published it.It is available immediately on an email request if you could do me a simple request.
    Nice day.
    Regards,
    Delu

  6. Arnie Dris said,

    October 31, 2010 at 6:53 am

    Hi Delu, Hi Greg,

    Any news on the submitted proof?

  7. Nicola said,

    September 5, 2012 at 6:07 am

    How to make the source code an app? I tried py2exe, but it didn’t work

  8. anil said,

    October 27, 2012 at 1:51 am

    sir i just want to know what we have find just numbers plz tell me

  9. Stephen Wynn said,

    June 3, 2013 at 12:18 am

    My generalisation of Beal’s conjecture applies to many more equations.

  10. Stephen Wynn said,

    June 3, 2013 at 12:20 am

    My generalisation of Beal,s conjecture applies to many more equationss.

  11. Solve a math puzzle, win $1 million « Xenophilia (True Strange Stuff) said,

    June 6, 2013 at 7:27 am

    [...] http://www.danvk.org/wp/beals-conjecture [...]

  12. Don Blazys said,

    August 22, 2013 at 9:53 pm

    My proof, which you can find here:

    http://scienceasia.asia/index.php?journal=ama&page=article&op=view&path%5B%5D=32

    shows that the properties of logarithms require that Beal’s conjecture be true. In other words, there can be no “counter example” to Beal’s conjecture because the properties of logarithms disallow it.

  13. михаил said,

    October 25, 2013 at 7:43 am

    http://www.mathematica.su the beal conjecture m a eremin

  14. михаил said,

    November 13, 2013 at 2:59 am

    теорема№1:уравнение била не имеет решений в целых числах если а в с не имеют общих делителей. теорема№ 2 уравнение била не может выполнятся во взаимно простых числах. эти теоремы будут скоро опубликованы

  15. михаил said,

    November 13, 2013 at 3:03 am

    если а в с не имеют общих делителей к теореме№1

  16. михаил said,

    November 13, 2013 at 3:05 am

    если а в с не имеют общих делителей к теореме№1 контрпример к гипотезе била не возможен

  17. Chris said,

    November 19, 2013 at 7:30 pm

    Can you post the source code of it? I don’t want to compile it, I just want to inspect it.

  18. Chris said,

    November 19, 2013 at 7:37 pm

    Or at least can you post more of your theroy behind it, like how you generated the bases and powers, stuff like that?

  19. михаил said,

    November 20, 2013 at 8:29 pm

    смотри сайт еремина михаила андреевича на двух языках идет заполнение сайта.

  20. михаил said,

    January 10, 2014 at 1:47 am

    criteria of resolvability of the eguation in integers /beal conjeiture.

  21. михаил said,

    January 10, 2014 at 1:49 am

    beal conjecture

  22. михаил said,

    January 12, 2014 at 9:57 am

    the impossibility of a counterexample the beal conjecture

  23. Dr Raj said,

    March 28, 2014 at 8:21 am

    It is futile to search for a counter example.
    Please do checkout a proof at
    http://unsolvedproblems.org/S38.pdf

  24. fwjmath said,

    April 5, 2014 at 12:07 pm

    Maybe a highly composite number or a highly abundant number as P1 would be better. It can cut running time off by 30% in my implementation. An experimental code is in https://github.com/fwjmath/beal-optimize.

  25. михаил said,

    April 9, 2014 at 10:27 pm

    Книга М А Еремин”Гипотеза Била” г Москва.2014г.Книга М А Еремин”Что может новый метод решения уравнений Еремина(проблема разрешимости диофантовых уравнений с различными показателями степени)” г Арзамас .2013г.

  26. marouane rhafli said,

    May 8, 2014 at 8:36 am

    hi,
    this an amazing conjecture , I have developped a prime finding algorithm and observed the link to the beal’s conjecture , I proved that this conjecture is true an gave the equation that shows the common prime factor , you can see my demonstrations on
    http://vixra.org/abs/1405.0195

  27. михаил said,

    May 16, 2014 at 9:38 pm

    Теория решения уравнения A^x+B^y=C^z в целых числах:Гипотеза Била. г МОСКВА.издательство URSS.(НОВОЕ НАЗВАНИЕ КНИГИ М А ЕРЕМИН”ГИПОТЕЗА БИЛА” Г .МОСКВА 2014г)

  28. михаил said,

    May 23, 2014 at 2:13 am

    ISBN 978-5-9710-1173-6

  29. михаил said,

    July 14, 2014 at 9:28 pm

    ISBN 978-5 -9927-0082-4

Leave a Comment