Hipoteza Beala ma nagrodę w wysokości miliona dolarów, jeśli ją udowodnisz / obalisz.

Stwierdza, że ​​jeśli A, B, C, x, y i z są dodatnimi liczbami całkowitymi o x, y, z> 2, wówczas A, B i C mają wspólny czynnik pierwszy.

Wyzwanie polega na napisaniu programu, który szuka przeciwnego przykładu, aby to obalić!

Zasady

• Napisz program szukający przeciwnego przykładu Hipotezy Beala
• Możesz przeprowadzić wyczerpujące wyszukiwanie (tzn. Wszystkie możliwe kombinacje liczb pasujące do tego formularza) lub użyć optymalizacji (np. A i B są symetryczne).
• Musisz użyć liczb całkowitych o dowolnej dokładności.

Notatki

• To konkurs popularności, bądź kreatywny!
• Prędkość nie jest konieczna, ale sprawia, że ​​jest bardziej interesująca. Optymalizować!
• Interesuje mnie również najkrótszy kod. Otrzymasz ode mnie +1!
• Uruchomię zwycięski program na superkomputerze, do którego mam dostęp!
• Ta hipoteza jest uważana za prawdę, ale to nie znaczy, że nie możemy spróbować!
• Peter Norvig z Google również próbował tego problemu. Możesz skorzystać z jego strony jako wskazówek. Ma krótki program w języku Python, którego możesz użyć jako przykładu.
• Jakiś inny facet (który również pracuje w Google) znacznie poprawił podejście Norviga, jego stronę (z kodem źródłowym) można znaleźć tutaj .
• Moje SO pytanie związane z tym sprzed dwóch lat może być również pomocne: Fin wszystkie A ^ x w danym zakresie .

Jestem żałośnie leniwy (zamierzona gra słów), ale dlaczego nie ... wydaje się, że spełnia zasady.

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"

Spowoduje to wydrukowanie ¹ wszystkich kombinacji, które spełniają właściwość kontrprzykładu. Użyłem pakietu control-monad-omega do przekątnej ℕ ⁶ ... można uznać za oszukiwanie w bibliotece. Ale widząc, jak ktoś później opublikuje odpowiedź APL, w której wszystkie te rzeczy są wbudowane w język (czy nie?), Nie mówię o tym zbyt wiele ...

Oczywiście program jest zbyt powolny (wyczerpanie naiwne i listy połączone jako struktura danych), aby można było oczekiwać, że przyniesie kontrprzykład, ale sam Haskell może faktycznie osiągnąć przyzwoitą wydajność.

¹ Ponieważ drukuje krotki w formacie listy, tj. W jednym wierszu, musisz wyłączyć buforowanie terminala, inaczej nie zobaczysz, kiedy pojawi się wynik. Możesz też zastąpić printgo mapM_ print, aby po każdym wyniku był nowy wiersz, opróżnianie terminalu buforowanego liniowo.

Aby przetestować program, zmień each[3..]na each[2..], a następnie otrzymasz po prostu wszystkie krotki pitagorejskie niebędące koprami.

C #, bez pętli

OK, przejrzałem kilka z tych linków, ale szczerze mówiąc, były trochę nudne. Nie jestem zainteresowany optymalizacją tego z tabelami skrótów i tak dalej. Dlaczego powinienem? Masz cholernego superkomputera!

Do diabła, nawet nie chcę zawracać sobie głowy pętlami! To rozwiązanie będzie zgodne z zasadą braku pętli .

Pamiętaj, że kod, który zamierzam napisać, nie jest dobrym kodem lub rodzajem kodu, który napisałbym w prawdziwym życiu (na wypadek, gdyby przyszli pracodawcy to przeczytali). Ten kod podkreśla zwięzłość i umiejętność pracy w narracji oraz deasfasuje właściwe konwencje, rytuały, pętle i tak dalej.

Aby zademonstrować, o czym mówię, zaczniemy od szokującej klasy z polami publicznymi do przechowywania argumentów równania:

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

OK, zaczniemy od tego, co jest prawdopodobnie najtrudniejszym wyzwaniem. Musimy znaleźć sposób na permutację poprzez każdą kombinację tych operandów. Istnieją niewątpliwie sposoby, aby to zrobić bardziej efektywnie niż sprawdzanie każdej permutacji, ale nie mogę się martwić, aby je rozgryźć. A dlaczego mam? Mamy cholernego superkomputera!

Oto algorytm, który wymyśliłem. Jest niewiarygodnie nieefektywny i ciągle przegląda te same operandy, ale kogo to obchodzi? Superkomputer!

• Traktuj sześć operandów jako liczbę podstawową 2 i przenikaj przez każdą kombinację.
• Traktuj sześć operandów jako liczbę podstawową 3 i przenikaj przez każdą kombinację.
• Traktuj sześć operandów jako liczbę podstawową 4 i przenikaj przez każdą kombinację.
• (...)

Jak to wszystko zrobić bez pętli? Łatwo! Wystarczy zaimplementować IEnumerablei powiązane, IEnumeratoraby wypompować permutacje. Później użyjemy LINQ do zapytania.

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

Teraz jesteśmy w biznesie! Wszystko, co musimy zrobić, to wymienić przykład BealOperandGeneratori znaleźć kontrprzykład Hipotezi Beala.

Naszym kolejnym dużym problemem jest to, że nie ma wbudowanego sposobu na podniesienie BigIntegerpotęgi do BigInteger. Istnieje BigInteger.Pow(BigInteger value, int exponent)i BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), ale nie ma metody na podniesienie BigIntegerdo potęgi innej BigIntegermodulo nieskończoności.

Co za błyszczący gwóźdź problemu! Wygląda na to, że został rozwiązany za pomocą naszego IEnumerable/ IEnumeratormłota!

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

Teraz mamy metodę rozszerzenia Pow, którą można wywołać na a BigInteger, i przyjmuje BigIntegerwykładnik wykładniczy i brak modułu.

OK, cofnijmy się. Jak możemy stwierdzić, czy konkretny BealOperandsjest kontrprzykładem hipotezy Beala? Cóż, dwie rzeczy muszą być prawdą:

• Operandy, po podłączeniu do tej formuły u góry strony, muszą tworzyć prawdziwe równanie.
• A, B i C NIE mogą mieć wspólnego czynnika podstawowego (tzn. Ich GCD wynosi 1).

Mamy to, czego potrzebujemy, aby sprawdzić pierwszy warunek. I okazuje się, że drugi warunek jest o wiele łatwiejszy do sprawdzenia niż się wydaje. BigIntegerzapewnia cudowną GreatestCommonDivisormetodę, która pozwala nam wygodnie ominąć cały koszmar próbowania wdrożenia tego bez pętli.

Jesteśmy więc gotowi napisać metodę, aby sprawdzić, czy a BealOperandsjest kontrprzykładem. Tutaj idzie...

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

I wreszcie możemy połączyć to wszystko za pomocą tej dość sprytnej Mainmetody:

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

Nie ma kontrprzykładów z C ^ Z <= 1,0E27.

Od lutego 2019 sprawdzam C ^ Z <= 1.0E29 przy założeniu, że wykładnik „X” i / lub „Y” musi wynosić> = 5.

Obecna wersja tego programu („X” i / lub „Y”> = 5) zajmuje mniej niż 1 sekundę na AMD 2920X, aby znaleźć wszystkie rozwiązania dla C ^ Z <= 1.0E15. (Ale wszystkie gcd (A, B, C) mają> = 2)

Szczegóły na stronie http://www.durangobill.com/BealsConjecture.html

Mogę zmodyfikować bieżący kod (używa „C” i OpenMP) poza te limity, ale będę potrzebował więcej niż 128 GB pamięci RAM, aby go uruchomić. (Pomogłyby również setki procesorów. Tysiące procesorów byłyby jeszcze lepsze.) (Jeśli masz bezpłatny dostęp do czegoś takiego, skontaktuj się ze mną.)

Mój adres e-mail znajduje się na stronie głównej http://www.durangobill.com

Zakończyła się druga wersja programu wyszukiwania Beala. Wyniki są następujące:

1) Nie ma kontrprzykładów z $C^Z < 10^{26}$. Pełna lista wszystkich ogólnych rozwiązań$A^X + B^Y = C^Z$ z co najmniej jednym wykładnikiem $(X,Y) >= 4$można zobaczyć na: http://www.durangobill.com/BealXgt3e27.txt

2) Jeśli założysz, że co najmniej jeden z wykładników $(X,Y)$ musi być $>= 5$, nie ma żadnych kontrprzykładów z $C^Z < 10^{28}$. Pełna lista wszystkich ogólnych rozwiązań$A^X + B^Y = C^Z$ z co najmniej jednym wykładnikiem $(X,Y) >= 5$i C ^ Z <1.0E29 można zobaczyć na stronie : http://www.durangobill.com/BealXgt4e29.txt

Szczegóły: http://www.durangobill.com/BealsConjecture.html

Następne dwa pytania to: 1) Czy superkomputer może przedłużyć wyszukiwanie? 2) Jeśli superkomputer mógłby przedłużyć wyszukiwanie, czy byłoby to praktyczne?

1) Aby rozszerzyć jedno z powyższych wyszukiwań do 1.0E30, wymagane będzie 300 GB pamięci RAM na rdzeń, chyba że rdzenie mogą współdzielić 300 GB. Dla każdego kolejnego dodatkowego przyrostowego wzrostu mocy wykładniczej powyżej 1,0E30 ilość wymaganej pamięci RAM wzrasta co najmniej 2,2 razy.

2) Ilość mocy obliczeniowej potrzebnej do każdego dalszego przyrostowego wykładnika do i powyżej 1,0E30 zwielokrotnia łączny czas procesora przez około 3,8. Wyszukiwanie do wersji 1.0E29 trwało 2 tygodnie przy użyciu 12 rdzeni. Czas superkomputera nie jest na ogół „darmowy” i istnieje bardzo małe prawdopodobieństwo, że istnieją jakieś kontrprzykłady.

Jako przewodnik po wydajności kodu na durangobill.com/BealE29code.txt, każdy z 12 rdzeni uśredniał 220 milionów iteracji pętli na sekundę dla pętli wewnętrznej. (Średnia dotyczy 2-tygodniowego biegu.) (Zwiększenie pamięci RAM powyżej tego, co mam, zwiększyłoby tę średnią prędkość nawet dwukrotnie).

Pozwolę Austinowi odpowiedzieć 1) i 2), ponieważ ma on dostęp do superkomputera, a ja nie. (Jeśli przypadkowo zdarzy się, że zarówno 1), jak i 2) są „gotowe”, mogę dostarczyć kod „C” z zastrzeżeniem, że nie znam instrukcji wielowątkowych dla dużych klastrów superkomputerowych.)

Musiałem umieścić to w 2 komentarzach, aby dopasować.

Główne tablice są przydzielane w następujący sposób:

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

(Będziesz potrzebował 128 GB pamięci RAM dla tych tablic)

z:

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

„Baza” faktycznie potrzebuje 33 bitów ( cbrt(1.0E29)) - dodatkowy bit jest wypełniony „Mocą” (która potrzebuje tylko 7 bitów).

Tablice działają podobnie do tabeli skrótów. Ponieważ jednak są one sortowane według PRIME1 i używane tylko jako tabele przeglądowe, nie potrzebujesz połączonych list, aby uzyskać do nich dostęp. Wynikiem jest zatem bardzo szybkie liniowe wyszukiwanie czasu, aby sprawdzić, czy próba A ^ X + B ^ Y = jakiekolwiek C ^ Z.

Zatem instrukcje w najbardziej wewnętrznej pętli mają tylko dwie pętle głębokości.

Instrukcje „Pragma” kontrolują liczbę używanych wielordzeniowych rdzeni (w tym przypadku 12) - wszystkie mogą uzyskać dostęp do pojedynczej kopii tablic.

Oto „główny” kod (w „C”) (Mam nadzieję, że komentarze pasują do opublikowanej długości wiersza. Jeśli nie, skopiuj je i wklej kod w dokumencie, który ma dłuższą długość wiersza).