La conjecture de Beal a un prix d'un million de dollars si vous le prouvez / réfutez.

Il indique que si où A, B, C, x, y et z sont des entiers positifs avec x, y, z> 2, alors A, B et C ont un facteur premier commun.

Le défi est d'écrire un programme qui recherche un exemple de compteur pour réfuter cela!

Règles

• Écrire un programme à la recherche d'un contre-exemple de la conjecture de Beal
• Vous pouvez effectuer une recherche exhaustive (c'est-à-dire toutes les combinaisons possibles de nombres qui correspondent à ce formulaire) ou utiliser certaines optimisations (par exemple, A et B sont symétriques).
• Vous devez utiliser des entiers de précision arbitraire.

Remarques

• Il s'agit d'un concours de popularité, soyez créatif!
• La vitesse n'est pas nécessaire, mais la rend plus intéressante. Optimiser!
• Je suis également intéressé à voir le code le plus court aussi. Vous obtiendrez un +1 de ma part!
• Je vais exécuter le programme gagnant sur un supercalculateur auquel j'ai accès!
• Cette conjecture est considérée comme vraie, mais cela ne signifie pas que nous ne pouvons pas essayer!
• Peter Norvig de Google a également tenté de résoudre ce problème. Vous pouvez utiliser sa page comme guide. Il a un petit programme Python que vous pouvez utiliser comme exemple.
• Un autre gars (qui travaille également chez Google) a considérablement amélioré l'approche de Norvig, sa page (avec le code source) peut être trouvée ici .
• Ma question SO liée à cela il y a deux ans peut également être utile: Fin tout A ^ x dans une plage donnée .

Je suis pathétiquement paresseux (jeu de mots), mais pourquoi pas ... semble respecter les règles.

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"

Ceci imprime ¹ toutes les combinaisons qui remplissent la propriété de contre-exemple. J'ai utilisé le package control-monad-omega pour diagonaliser ℕ ⁶ ... pourrait être considéré comme une fraude de bibliothèque. Mais vu que quelqu'un postera plus tard une réponse APL où tout cela est intégré dans la langue (ou n'est-ce pas?), Je n'en donne pas trop ...

Bien sûr, le programme est beaucoup trop lent (épuisement naïf et listes de liens comme structure de données) pour être susceptible de produire un contre-exemple, mais Haskell lui-même peut réellement atteindre des performances décentes.

¹ Puisqu'il imprime les tuples sous forme de liste, c'est-à-dire sur une ligne, vous devez désactiver la mise en mémoire tampon de votre terminal ou vous ne verrez pas quand un résultat entrera. Vous pouvez également le remplacer printpar mapM_ printpour obtenir une nouvelle ligne après chaque résultat, rinçage d'un terminal à ligne tampon.

Pour tester le programme, passez each[3..]à each[2..], vous obtiendrez alors simplement tous les tuples pythagoriciens non coprimes.

C #, pas de boucles

OK, j'ai survolé quelques-uns de ces liens, mais pour être honnête, ils étaient un peu ennuyeux. Je ne suis pas intéressé à optimiser l'enfer avec des tables de hachage et ainsi de suite. Pourquoi devrais-je en avoir besoin? Vous avez un putain de supercalculateur!

Enfer, je ne veux même pas m'embêter avec des boucles! Cette solution suivra la règle no-loops .

Veuillez noter que le code que je suis sur le point d'écrire n'est pas un bon code, ou le type de code que j'écrirais dans la vraie vie (au cas où des employeurs potentiels liraient cela). Ce code met l'accent sur la brièveté et la capacité de travailler dans un récit, et met l'accent sur les conventions et les rituels et boucles appropriés, etc.

Pour démontrer de quoi je parle, nous allons commencer par une classe choquante avec des champs publics pour stocker les opérandes de l'équation:

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

OK, nous allons commencer par ce qui est probablement le défi le plus difficile. Nous devons trouver un moyen de permuter à travers chaque combinaison de ces opérandes. Il existe sans aucun doute des moyens de le faire plus efficacement que de vérifier chaque permutation, mais je ne peux pas être dérangé de les découvrir. Et pourquoi devrais-je? Nous avons un putain de supercalculateur!

Voici l'algorithme que j'ai trouvé. C'est incroyablement inefficace et répète encore et encore les mêmes opérandes, mais qui s'en soucie? Supercalculateur!

• Traitez les six opérandes comme un nombre en base 2 et permutez à travers chaque combinaison.
• Traitez les six opérandes comme un nombre en base 3 et permutez à travers chaque combinaison.
• Traitez les six opérandes comme un nombre en base 4 et permutez à travers chaque combinaison.
• (...)

Comment faire tout cela sans boucles? Facile! Il suffit de mettre en œuvre un IEnumerableet associé IEnumeratorpour pomper les permutations. Plus tard, nous utiliserons LINQ pour l'interroger.

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

Maintenant, nous sommes en affaires! Tout ce que nous devons faire est d'énumérer une instance de BealOperandGeneratoret de trouver un contre-exemple de la conjecture de Beal.

Notre prochain gros problème est qu'il ne semble pas y avoir de moyen intégré d'élever a BigIntegerau pouvoir de a BigInteger. Il y a BigInteger.Pow(BigInteger value, int exponent)et BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), mais pas de méthode pour élever un BigInteger, à la puissance d'un autre BigInteger, l'infini modulo.

Quel clou brillant d'un problème! On dirait qu'il a été fait pour être résolu avec notre 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;
    }
}

Nous avons maintenant une méthode d'extension Pow, qui peut être appelée sur un BigInteger, et prend un BigIntegerexposant et aucun module.

OK, reculons. Comment savoir si un particulier BealOperandsest un contre-exemple de la conjecture de Beal? Eh bien, deux choses doivent être vraies:

• Les opérandes, lorsqu'ils sont connectés à cette formule en haut de la page, doivent former une véritable équation.
• A, B et C ne doivent PAS avoir un facteur premier commun (c'est-à-dire que leur GCD est 1).

Nous avons ce dont nous avons besoin pour vérifier la première condition. Et il s'avère que la deuxième condition est beaucoup plus facile à vérifier qu'il n'y paraît. BigIntegerfournit une belle GreatestCommonDivisorméthode, qui nous permet de contourner commodément tout le cauchemar d'essayer de l'implémenter sans boucles.

Nous sommes donc prêts à écrire une méthode pour vérifier si a BealOperandsest un contre-exemple. Voici...

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

Et enfin, nous pouvons tout rassembler avec cette Mainméthode plutôt simple:

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

Il n'y a pas de contre-exemples avec C ^ Z <= 1.0E27.

Depuis février 2019, je passe à C ^ Z <= 1.0E29 en supposant que l'exposant «X» et / ou «Y» doit être> = 5.

La version actuelle de ce programme («X» et / ou «Y»> = 5) prend moins d'une seconde sur un AMD 2920X pour trouver toutes les solutions jusqu'à C ^ Z <= 1.0E15. (Mais tous les pgcd (A, B, C) sont> = 2)

Détails sur http://www.durangobill.com/BealsConjecture.html

Je peux modifier le code actuel (utilise «C» et OpenMP) au-delà de ces limites mais j'ai besoin de plus de 128 Go de RAM pour l'exécuter. (Des centaines de processeurs seraient également utiles. Des milliers de processeurs seraient encore meilleurs.) (Si vous avez un accès gratuit à quelque chose comme ça, veuillez me contacter.)

Mon adresse e-mail est sur ma page d'accueil à http://www.durangobill.com

La deuxième variante du programme de recherche de Beal est terminée. Les résultats sont:

$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$

Détails sur: http://www.durangobill.com/BealsConjecture.html

Les deux questions suivantes sont: 1) Un superordinateur peut-il étendre la recherche? 2) Si un supercalculateur pouvait étendre la recherche, serait-ce pratique?

1) Pour étendre l'une des recherches ci-dessus à 1.0E30, 300 Go de RAM seraient nécessaires par cœur, à moins que les cœurs ne puissent partager les 300 Go. Pour chaque augmentation supplémentaire supplémentaire de la puissance exponentielle au-delà de 1.0E30, la quantité de RAM requise augmente d'un facteur d'au moins 2,2.

2) La quantité de puissance de traitement nécessaire pour chaque augmentation incrémentielle supplémentaire de l'exposant jusqu'à 1,0E30 et au-delà multiplie le temps CPU combiné d'environ 3,8. La recherche à 1.0E29 a pris 2 semaines en utilisant 12 cœurs. Le temps de supercalculateur n'est généralement pas «gratuit» et il y a très peu de chances qu'il y ait des contre-exemples.

Pour guider l'efficacité du code sur durangobill.com/BealE29code.txt, chacun des 12 cœurs a en moyenne 220 millions d'itérations de boucle par seconde pour la boucle interne. (La moyenne est pour la course de 2 semaines.) (Une augmentation de la mémoire RAM au-delà de ce que j'aurais augmenterait cette vitesse moyenne jusqu'à un facteur de 2.)

Je vais laisser Austin répondre 1) et 2) car il a accès à un supercalculateur et moi non. (Si par hasard, à la fois 1) et 2) sont un "go", je peux fournir le code "C" avec la mise en garde que je ne connais pas les instructions multi-thread pour les grands clusters de superordinateurs.)

J'ai dû mettre cela en 2 commentaires pour l'adapter.

Les tableaux principaux sont répartis comme suit:

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

(Vous aurez besoin de 128 Go de RAM pour ces baies)

avec:

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

"Base" a en fait besoin de 33 bits (cbrt(1.0E29) ) - le bit supplémentaire est bourré dans "Power" (qui n'a besoin que de 7 bits.)

Les tableaux fonctionnent de manière similaire à une table de hachage. Cependant, étant donné qu'ils sont triés par PRIME1 et uniquement utilisés comme tables de recherche, vous n'avez pas besoin des listes liées pour y accéder. Le résultat est donc une recherche de temps linéaire très rapide pour voir si un essai A ^ X + B ^ Y = tout C ^ Z.

Ainsi, les instructions dans la boucle la plus intérieure ne sont profondes que de deux boucles.

Les instructions «Pragma» contrôlent le nombre de cœurs de traitement multiples utilisés (dans ce cas, 12) - tous peuvent accéder à la copie unique des tableaux.

Voici le code «principal» (en «C») (j'espère que les commentaires correspondent à la longueur de la ligne publiée. Sinon, copiez-les et collez le code dans un document qui a une longueur de ligne plus longue.)