Lets take Beal's $1,000,000

Question

Beal's Conjecture has a million dollar prize if you prove/disprove it.

It states that if where A, B, C, x, y, and z are positive integers with x, y, z > 2, then A, B, and C have a common prime factor.

The challenge is to write a program that searches for a counter example to disprove this!

Rules

• Write a program searching for a counter example of Beal's Conjecture
• You can perform an exhaustive search (i.e., all possible combinations of numbers that fit this form) or use some optimizations (e.g., A and B are symmetrical).
• You must use arbitrary-precision integers.

Notes

• This is a popularity contest, be creative!
• Speed isn't necessary, but makes it more interesting. Optimize!
• I am also interested in seeing the shortest code too. You will get a +1 from me!
• I'll run the winning program on a supercomputer that I have access to!
• This conjecture is considered to be true, but that doesn't mean we can't try!
• Peter Norvig of Google has attempted this problem too. You may use his page as guidance. He has a short Python program you can use as an example.
• Some other guy (who also happens to work at Google) has greatly improved on Norvig's approach, his page (with source code) can be found here.
• My SO question related to this from two years ago may also be helpful: Fin all A^x in a given range.

Answer 1

I'm being pathetically lazy (pun intended), but why not... seems to fulfill the rules.

Haskell, 204

import Control.Monad
import Control.Monad.Omega
main=print.filter(\[(a,x),(b,y),(c,z)] 
 ->and$(a^x+b^y==c^z):zipWith(((>1).).gcd)[a,b,c][b,c,a])
 .runOmega$mapM(\_->liftM2(,)(each[1..])$each[3..])"123"

This prints¹ all combinations which fulfill the counterexample property. I used the control-monad-omega package for diagonalising ℕ⁶... might be considered library-cheating. But seeing as someone will later post an APL answer where all this stuff is built into the language (or isn't it?), I don't give too much about it...

Of course, the program is way too slow (naïve exhaustion, and linked-lists as data structure) to be expectable of actually yielding a counterexample, but Haskell itself can actually achieve decent performance.

---

¹Since it prints the tuples in list format, i.e. in one line, you need to switch your terminal's buffering off or you won't see when a result comes in. Alternatively, you can replace print with mapM_ print so you get a newline after each result, flushing a line-buffered terminal.

To test the program, change each[3..] to each[2..], then you'll simply get all non-coprime pythagorean tuples as result.

Answer 2

C#, no loops

OK, I skimmed a couple of those links, but to be honest they were a bit boring. I'm not interested in optimizing the hell out of it with hash tables and whatnot. Why should I need to? You've got a goddamn supercomputer!

Hell, I don't even want to bother with loops! This solution will follow the no-loops rule.

Please note that the code I'm about to write is not good code, or the kind of code I'd write in real life (in case any prospective employers happen to read this). This code emphasises brevity and the ability to work in a narrative, and deemphasises the proper conventions and rituals and loops and so on.

To demonstrate what I'm talking about, we'll start with a shocking class with public fields to store the operands of the equation:

class BealOperands
{
    public BigInteger A, B, C, x, y, z;
}

OK, we'll start with what is probably the hardest challenge. We need to figure out a way to permute through every combination of those operands. There are undoubtedly ways to do it more efficiently than checking every permutation, but I can't be bothered figuring them out. And why should I? We've got a goddamn supercomputer!

Here's the algorithm I came up with. It's incredibly inefficient, and goes over the same operands over and over again, but who cares? Supercomputer!

• Treat the six operands as a base-2 number, and permute through every combination.
• Treat the six operands as a base-3 number, and permute through every combination.
• Treat the six operands as a base-4 number, and permute through every combination.
• (...)

How to do all this without loops? Easy! Just implement an IEnumerable and associated IEnumerator to pump out the permutations. Later, we'll use LINQ to query it.

class BealOperandGenerator : IEnumerable<BealOperands>
{
    // Implementation of IEnumerable<> and IEnumerable -- basically boilerplate to get to BealOperandGeneratorEnumerator.
    public IEnumerator<BealOperands> GetEnumerator() { return new BealOperandGeneratorEnumerator(); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BealOperandGeneratorEnumerator : IEnumerator<BealOperands>
{
    public BealOperandGeneratorEnumerator() { Reset(); }

    private BealOperands operands;
    private BigInteger @base;

    public void Reset()
    {
        // A is set to 0, which is "before" its minimum value, because IEnumerators are supposed to
        // point to their first element *after* the first call to MoveNext().
        // All other operands are set to their minimum values.
        operands = new BealOperands { A = 0, B = 1, C = 1, x = 3, y = 3, z = 3 };
        @base = 2;
    }

    public BealOperands Current
    {
        get 
        {
            // We need to return a copy, since we'll be manipulating our internal one.
            return new BealOperands { 
                A = operands.A, B = operands.B, C = operands.C, 
                x = operands.x, y = operands.y, z = operands.z };
        }
    }

    public bool MoveNext()
    {
        // Increment the lowest "digit" and "carry" as necessary.
        operands.A++;
        if (operands.A - 1 >= @base)
        {
            operands.A = 1; operands.B++;
            if (operands.B - 1 >= @base)
            {
                operands.B = 1; operands.C++;
                if (operands.C - 1 >= @base)
                {
                    operands.C = 1; operands.x++;
                    if (operands.x - 3 >= @base)
                    {
                        operands.x = 3; operands.y++;
                        if (operands.y - 3 >= @base)
                        {
                            operands.y = 3; operands.z++;
                            if (operands.z - 3 >= @base)
                            {
                                operands.z = 3; @base++;
                            }
                        }
                    }
                }
            }
        }
        // There will always be more elements in this sequence.
        return true;
    }

    // More boilerplate
    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

Now we're in business! All we need to do is enumerate an instance of BealOperandGenerator and find a counterexample of Beal's Conjecture.

Our next big problem is that there doesn't seem to be a built-in way to raise a BigInteger to the power of a BigInteger. There's BigInteger.Pow(BigInteger value, int exponent), and BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), but no method to raise a BigInteger, to the power of another BigInteger, modulo infinity.

What a shiny nail of a problem! It looks like it was made to be solved with our IEnumerable/IEnumerator hammer!

class BigIntegerPowerEnumerable : IEnumerable<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerable(BigInteger @base, BigInteger exponent) { this.@base = @base; this.exponent = exponent; } 
    BigInteger @base, exponent;

    public IEnumerator<Tuple<BigInteger, BigInteger>> GetEnumerator() { return new BigIntegerPowerEnumerator(@base, exponent); }
    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { return GetEnumerator(); }
}

class BigIntegerPowerEnumerator : IEnumerator<Tuple<BigInteger, BigInteger>>
{
    public BigIntegerPowerEnumerator(BigInteger @base, BigInteger exponent) 
    {
        originalBase = @base; 
        originalExponent = exponent;
        Reset(); 
    }

    BigInteger originalBase, currentBase, originalExponent, currentExponent;
    bool finished;

    public void Reset()
    {
        // IEnumerable.Reset() is a silly method. You're required to implement it when you implement IEnumerable,
        // but it isn't used by foreach or LINQ or anything. If you want to re-enumerate the enumerable, just get
        // a brand new enumerator.
        // In this case it gets in the way. The only reason I'm storing the original values is so I can implement 
        // this useless method properly. I supposed I could just throw a NotImplementedException or something, 
        // but it's done now.
        currentBase = originalBase;
        currentExponent = originalExponent;
        finished = false;
    }

    public bool MoveNext()
    {
        if (finished) return false;

        if (currentExponent <= Int32.MaxValue)
        {
            currentBase = BigInteger.Pow(currentBase, (Int32)currentExponent);
            currentExponent = 1;
            finished = true;
        }
        else
        {
            currentBase = BigInteger.Pow(currentBase, Int32.MaxValue);
            currentExponent -= Int32.MaxValue;
        }
        return true;
    }

    public Tuple<BigInteger, BigInteger> Current
    {
        get { return new Tuple<BigInteger, BigInteger>(currentBase, currentExponent); }
    }

    object System.Collections.IEnumerator.Current { get { return Current; } }
    public void Dispose() { }
}

static class BigIntegerPowExtension
{
    public static BigInteger Pow(this BigInteger @base, BigInteger exponent)
    {
        return new BigIntegerPowerEnumerable(@base, exponent).Last().Item1;
    }
}

Now we've got an extension method Pow, that can be called on a BigInteger, and takes a BigInteger exponent and no modulus.

OK, let's step back. How can we tell if a particular BealOperands is a counterexample of Beal's Conjecture? Well, two things need to be true:

• The operands, when plugged into that formula up at the top of the page, must form a true equation.
• A, B, and C must NOT have a common prime factor (i.e. their GCD is 1).

We've got what we need to check the first condition. And it turns out the second condition is a lot easier to check than it sounds. BigInteger provides a lovely GreatestCommonDivisor method, which allows us to conveniently sidestep the whole nightmare of trying to implement that without loops.

So we're ready to write a method to check if a BealOperands is a counterexample. Here goes...

static class BealOperandsExtensions
{
    public static bool IsBealsConjectureCounterExample(this BealOperands o)
    {
        // If the equation isn't even true, we don't have a counter example unfortunately
        if (o.A.Pow(o.x) + o.B.Pow(o.y) != o.C.Pow(o.z))
        {
            return false;
        }

        // We have a counterexample if A, B and C are coprime
        return BigInteger.GreatestCommonDivisor(o.A, o.B) == 1 &&
               BigInteger.GreatestCommonDivisor(o.A, o.C) == 1 &&
               BigInteger.GreatestCommonDivisor(o.B, o.C) == 1;
    }
}

And finally we can bring it all together with this rather slick Main method:

static class Program
{
    static void Main()
    {
        var bealOperandGenerator = new BealOperandGenerator();
        if (bealOperandGenerator.Any(o => o.IsBealsConjectureCounterExample()))
        {
            Console.WriteLine("IN YOUR FACE, BEAL!");
        }
    }
}

Answer 3

There are no counterexamples with C^Z <= 1.0E27.

As of Feb. 2019 I’m checking out to C^Z <= 1.0E29 on the assumption that either the “X” and/or “Y” exponent must be >= 5.

Current version of this program (“X” and/or “Y” >= 5) takes less than 1 second on an AMD 2920X to find all solutions out to C^Z <= 1.0E15. (But all of the gcd(A,B,C) are >= 2)

Details at http://www.durangobill.com/BealsConjecture.html

I can modify the current code (Uses “C” and OpenMP) out beyond these limits but will need more than 128GB of RAM to run it. (Hundreds of CPUs would also help. Thousands of CPUs would be even better.) (If you have free access to something like this, please contact me.)

My email address is on my home page at http://www.durangobill.com

Answer 4

The 2nd variation of the Beal’s search program has finished. The results are:

1) There are no counterexamples with \$C^Z < 10^{26}\$. A complete list of all general solutions to \$A^X + B^Y = C^Z\$ with at least one of the exponents \$(X,Y) >= 4\$ can be seen at: http://www.durangobill.com/BealXgt3e27.txt

2) If you assume that at least of of the exponents \$(X,Y)\$ must be \$>= 5\$, there are no counterexamples with \$C^Z < 10^{28}\$. A complete list of all general solutions to \$A^X + B^Y = C^Z\$ with at least one of the exponents \$(X,Y) >= 5\$ and C^Z < 1.0E29 can be seen at: http://www.durangobill.com/BealXgt4e29.txt

Details at: http://www.durangobill.com/BealsConjecture.html

The next two questions are:: 1) Can a supercomputer extend the search? 2) If a supercomputer could extend the search, would it be practical?

1) To extend either of the above searches to 1.0E30, 300GB of RAM would be required per core unless cores can share the 300GB. For each additional further incremental increase in the exponential power beyond 1.0E30, the amount of required RAM increases by a factor of at least 2.2.

2) The amount of processing power needed for each further incremental increase in the exponent to and beyond 1.0E30 multiplies the combined CPU time by about 3.8. The search to 1.0E29 took 2 weeks using 12 cores. Supercomputer time is not generally “free”, and there is very little prospect that there are any counterexamples.

As a guide to the efficiency of the code at durangobill.com/BealE29code.txt, each of the 12 cores averaged 220 million loop iterations per second for the inner loop. (Average is for the 2-week run.) (An increase in RAM memory beyond what I have would increase this average speed by up to a factor of 2.)

I’ll let Austin answer 1) and 2) since he has access to a supercomputer and I don’t. (If by any remote chance that both 1) and 2) are a "go", I can supply the "C" code with the caveat that I'm not familiar with multi-thread instructions for large supercomputer clusters.)

Answer 5

Had to put this in 2 comments to get it to fit.

The major arrays are allocated as follows:

SortHeads = calloc(PRIME1+1, 8);
X2YmodPrime1 = calloc(ARRAYSIZE+1, 4);
X2YmodPrime2 = calloc(ARRAYSIZE+1, 4);
Base = calloc(ARRAYSIZE+1, 4);
Power = malloc(ARRAYSIZE+1);

(You will need 128GB of RAM for these arrays)

with:

#define PRIME1 2147483647LLU
#define PRIME2 2147483629LLU
#define ARRAYSIZE 4700000000LL

“Base” actually needs 33 bits (cbrt(1.0E29)) - the extra bit is stuffed in “Power” (which only needs 7 bits.)

The arrays operate similar to a hash table. However, since they are sorted by PRIME1 and only used as look-up tables, you don’t need the linked lists to access them. The result is thus a very fast linear time lookup to see if a trial A^X + B^Y = any C^Z.

Thus statements in the innermost loop are only two loops deep.

“Pragma” statements control the number of multi processing cores that are used (in this case 12) - all can access the single copy of the arrays.

Here’s the “main” code (in “C”) (Hope the comments fit the posted line length. If not, copy them out and paste the code in some document that has a longer line length.)