Beal's Conjecture hat einen Millionen-Dollar-Preis, wenn Sie es beweisen / widerlegen.

Es heißt, wenn A, B, C, x, y und z positive ganze Zahlen mit x, y, z> 2 sind, dann haben A, B und C einen gemeinsamen Primfaktor.

Die Herausforderung besteht darin, ein Programm zu schreiben, das nach einem Gegenbeispiel sucht, um dies zu widerlegen!

Regeln

• Schreiben Sie ein Programm, das nach einem Gegenbeispiel für Beals Vermutung sucht
• Sie können eine umfassende Suche durchführen (dh alle möglichen Zahlenkombinationen, die zu dieser Form passen) oder einige Optimierungen verwenden (z. B. sind A und B symmetrisch).
• Sie müssen Ganzzahlen mit beliebiger Genauigkeit verwenden.

Anmerkungen

• Dies ist ein Beliebtheitswettbewerb, sei kreativ!
• Geschwindigkeit ist nicht notwendig, macht es aber interessanter. Optimieren!
• Ich bin auch daran interessiert, den kürzesten Code zu sehen. Du bekommst eine +1 von mir!
• Ich starte das Gewinnerprogramm auf einem Supercomputer, auf den ich Zugriff habe!
• Diese Vermutung wird als wahr angesehen, aber das heißt nicht, dass wir es nicht versuchen können!
• Peter Norvig von Google hat dieses Problem ebenfalls versucht. Sie können seine Seite als Anleitung verwenden. Er hat ein kurzes Python-Programm, das Sie als Beispiel verwenden können.
• Ein anderer Typ (der zufällig auch bei Google arbeitet) hat Norvigs Ansatz stark verbessert. Seine Seite (mit Quellcode) finden Sie hier .
• Meine SO-Frage dazu vor zwei Jahren könnte ebenfalls hilfreich sein: Fin all A ^ x in einem bestimmten Bereich .

Ich bin pathetisch faul (Wortspiel beabsichtigt), aber warum nicht ... scheint die Regeln zu erfüllen.

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"

Dies gibt ¹ alle Kombinationen aus, die die Gegenbeispieleigenschaft erfüllen. Ich habe das Control-Monad-Omega-Paket zum Diagonalisieren von ising ^{6 verwendet} . Aber da jemand später eine APL-Antwort posten wird, in der all dieses Zeug in die Sprache eingebaut ist (oder nicht?), Gebe ich nicht zu viel darüber ab ...

Natürlich ist das Programm viel zu langsam (naive Erschöpfung und verknüpfte Listen als Datenstruktur), um tatsächlich ein Gegenbeispiel zu liefern, aber Haskell selbst kann tatsächlich eine anständige Leistung erzielen.

¹ Da die Tupel in Listenformat druckt, das heißt in einer Zeile, müssen Sie Ihre Terminals Pufferung ausgeschaltet oder Sie werden nicht sehen , wenn ein Ergebnis kommt. Alternativ können Sie ersetzen printmit , mapM_ printso dass Sie eine neue Zeile nach jedem Ergebnis erhalten, Leeren eines leitungsgepufferten Terminals.

Wenn Sie das Programm testen möchten, wechseln Sie each[3..]zu. each[2..]Als Ergebnis erhalten Sie einfach alle nicht koprimen pythagoreischen Tupel.

C #, keine Schleifen

OK, ich habe ein paar dieser Links überflogen, aber um ehrlich zu sein, sie waren ein bisschen langweilig. Ich bin nicht daran interessiert, das Ganze mit Hash-Tabellen und so weiter zu optimieren. Warum sollte ich brauchen? Du hast einen verdammten Supercomputer!

Verdammt, ich möchte mich nicht einmal mit Schleifen beschäftigen! Diese Lösung folgt der No-Loops-Regel .

Bitte beachten Sie, dass der Code, den ich gerade schreibe, kein guter Code ist oder die Art von Code, die ich im wirklichen Leben schreibe (falls potenzielle Arbeitgeber dies zufällig lesen). Dieser Code betont die Kürze und die Fähigkeit, in einer Erzählung zu arbeiten, und betont die richtigen Konventionen und Rituale und Schleifen und so weiter.

Um zu demonstrieren, wovon ich spreche, beginnen wir mit einer schockierenden Klasse mit öffentlichen Feldern, um die Operanden der Gleichung zu speichern:

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

OK, wir beginnen mit der wahrscheinlich schwierigsten Herausforderung. Wir müssen einen Weg finden, durch jede Kombination dieser Operanden zu permutieren. Es gibt zweifellos Möglichkeiten, dies effizienter zu tun, als jede Permutation zu überprüfen, aber ich kann mich nicht darum kümmern, sie herauszufinden. Und warum sollte ich Wir haben einen verdammten Supercomputer!

Hier ist der Algorithmus, den ich mir ausgedacht habe. Es ist unglaublich ineffizient und geht immer wieder dieselben Operanden durch, aber wen interessiert das? Supercomputer!

• Behandle die sechs Operanden als Zahl zur Basis 2 und permutiere durch jede Kombination.
• Behandle die sechs Operanden als Zahl zur Basis 3 und permutiere durch jede Kombination.
• Behandle die sechs Operanden als eine Zahl zur Basis 4 und permutiere durch jede Kombination.
• (...)

Wie geht das alles ohne Schleifen? Einfach! Implementieren Sie einfach ein IEnumerableund das zugehörige IEnumerator, um die Permutationen abzupumpen. Später werden wir LINQ verwenden, um es abzufragen.

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() { }
}

Jetzt sind wir im Geschäft! Alles, was wir tun müssen, ist eine Instanz von aufzählen BealOperandGeneratorund ein Gegenbeispiel von Beals Vermutung zu finden.

Unser nächstes großes Problem ist, dass es keinen eingebauten Weg zu geben scheint, um a BigIntegerzur Macht von a zu erheben BigInteger. Es gibt BigInteger.Pow(BigInteger value, int exponent), BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus)aber keine Methode, um eine Modulo-Unendlichkeit BigIntegerzur Macht einer anderen zu erheben BigInteger.

Was für ein glänzender Nagel für ein Problem! Es sieht aus wie es gemacht wurde mit unserem zu lösenden IEnumerable/ IEnumeratorHammer!

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;
    }
}

Jetzt haben wir eine Erweiterungsmethode Pow, die für a aufgerufen werden BigIntegerkann und einen BigIntegerExponenten und keinen Modul annimmt .

OK, lass uns zurücktreten. Wie können wir feststellen, ob ein bestimmtes BealOperandsObjekt ein Gegenbeispiel für Beals Vermutung ist? Nun, zwei Dinge müssen stimmen:

• Wenn die Operanden oben auf der Seite in diese Formel eingefügt werden, müssen sie eine wahre Gleichung bilden.
• A, B und C dürfen KEINEN gemeinsamen Primfaktor haben (dh ihr GCD ist 1).

Wir haben das, was wir brauchen, um die erste Bedingung zu überprüfen. Und es stellt sich heraus, dass die zweite Bedingung viel einfacher zu überprüfen ist als es sich anhört. BigIntegerbietet eine schöne GreatestCommonDivisorMethode, mit der wir den ganzen Albtraum, dies ohne Schleifen umzusetzen, bequem umgehen können.

Wir sind also bereit, eine Methode zu schreiben, um zu überprüfen, ob a BealOperandsein Gegenbeispiel ist. Hier geht...

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;
    }
}

Und schließlich können wir alles mit dieser ziemlich raffinierten MainMethode zusammenbringen:

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

Es gibt keine Gegenbeispiele mit C ^ Z <= 1.0E27.

Ab Februar 2019 überprüfe ich C ^ Z <= 1.0E29 unter der Annahme, dass entweder der Exponent "X" und / oder "Y"> = 5 sein muss.

Die aktuelle Version dieses Programms („X“ und / oder „Y“> = 5) benötigt auf einem AMD 2920X weniger als 1 Sekunde, um alle Lösungen für C ^ Z <= 1.0E15 zu finden. (Aber alle gcd (A, B, C) sind> = 2)

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

Ich kann den aktuellen Code (verwendet "C" und OpenMP) über diese Grenzen hinaus ändern, benötige jedoch mehr als 128 GB RAM, um ihn auszuführen. (Hunderte von CPUs würden auch helfen. Tausende von CPUs wären noch besser.) (Wenn Sie freien Zugang zu so etwas haben, kontaktieren Sie mich bitte.)

Meine E-Mail-Adresse befindet sich auf meiner Homepage unter http://www.durangobill.com

Die zweite Variante des Beal-Suchprogramms ist beendet. Die Ergebnisse sind:

$C^Z < 10^{26}$$A^X + B^Y = C^Z$$(X,Y) >= 4$

$(X,Y)$$>= 5$$C^Z < 10^{28}$$A^X + B^Y = C^Z$$(X,Y) >= 5$

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

Die nächsten beiden Fragen lauten: 1) Kann ein Supercomputer die Suche ausweiten? 2) Wenn ein Supercomputer die Suche erweitern könnte, wäre es praktisch?

1) Um eine der oben genannten Suchvorgänge auf 1.0E30 zu erweitern, sind 300 GB RAM pro Kern erforderlich, es sei denn, Kerne können die 300 GB gemeinsam nutzen. Für jede weitere inkrementelle Erhöhung der Exponentialleistung über 1,0E30 hinaus erhöht sich die Menge des erforderlichen Arbeitsspeichers um einen Faktor von mindestens 2,2.

2) Die Menge an Rechenleistung, die für jede weitere inkrementelle Erhöhung des Exponenten auf und über 1,0E30 benötigt wird, multipliziert die kombinierte CPU-Zeit mit etwa 3,8. Die Suche nach 1.0E29 dauerte mit 12 Kernen 2 Wochen. Die Supercomputer-Zeit ist im Allgemeinen nicht "frei", und es gibt kaum Aussichten, dass es Gegenbeispiele gibt.

Als Anhaltspunkt für die Effizienz des Codes unter durangobill.com/BealE29code.txt betrug jeder der 12 Kerne für die innere Schleife durchschnittlich 220 Millionen Schleifeniterationen pro Sekunde. (Der Durchschnitt gilt für die Dauer von zwei Wochen.) (Eine Erhöhung des RAM-Speichers über den von mir angegebenen Wert hinaus würde diese Durchschnittsgeschwindigkeit um den Faktor 2 erhöhen.)

Ich lasse Austin 1) und 2) beantworten, da er Zugang zu einem Supercomputer hat und ich nicht. (Wenn zufällig 1) und 2) ein "go" sind, kann ich den "C" -Code mit der Einschränkung angeben, dass ich mit Multithread-Anweisungen für große Supercomputer-Cluster nicht vertraut bin.)

Musste dies in 2 Kommentare setzen, um es zu passen.

Die Hauptfelder sind wie folgt zugeordnet:

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

(Für diese Arrays benötigen Sie 128 GB RAM.)

mit:

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

"Base" benötigt tatsächlich 33 Bits ( cbrt(1.0E29)) - das zusätzliche Bit wird in "Power" (das nur 7 Bits benötigt) gestopft.

Die Arrays funktionieren ähnlich wie eine Hash-Tabelle. Da sie jedoch nach PRIME1 sortiert sind und nur als Nachschlagetabellen verwendet werden, benötigen Sie die verknüpften Listen nicht, um darauf zuzugreifen. Das Ergebnis ist somit eine sehr schnelle lineare Zeitsuche, um festzustellen, ob ein Versuch A ^ X + B ^ Y = irgendein C ^ Z ist.

Somit sind Anweisungen in der innersten Schleife nur zwei Schleifen tief.

"Pragma" -Anweisungen steuern die Anzahl der verwendeten Mehrprozessorkerne (in diesem Fall 12) - alle können auf die einzelne Kopie der Arrays zugreifen.

Hier ist der "Haupt" -Code (in "C") (Ich hoffe, die Kommentare passen zur angegebenen Zeilenlänge. Wenn nicht, kopieren Sie sie heraus und fügen Sie den Code in ein Dokument mit einer längeren Zeilenlänge ein.)