La Conjetura de Beal tiene un premio de un millón de dólares si lo demuestra / refuta.

Establece que si donde A, B, C, x, y y z son enteros positivos con x, y, z> 2, entonces A, B y C tienen un factor primo común.

¡El desafío es escribir un programa que busque un contraejemplo para refutar esto!

Reglas

• Escriba un programa buscando un contraejemplo de la conjetura de Beal
• Puede realizar una búsqueda exhaustiva (es decir, todas las combinaciones posibles de números que se ajusten a este formulario) o utilizar algunas optimizaciones (por ejemplo, A y B son simétricas).
• Debe usar enteros de precisión arbitraria.

Notas

• Este es un concurso de popularidad, ¡sé creativo!
• La velocidad no es necesaria, pero la hace más interesante. ¡Optimizar!
• También estoy interesado en ver el código más corto también. ¡Recibirás un +1 de mi parte!
• ¡Ejecutaré el programa ganador en una supercomputadora a la que tenga acceso!
• Esta conjetura se considera cierta, ¡pero eso no significa que no podamos intentarlo!
• Peter Norvig de Google también ha intentado este problema. Puede usar su página como guía. Tiene un programa corto de Python que puedes usar como ejemplo.
• Otro tipo (que también trabaja en Google) ha mejorado mucho el enfoque de Norvig, su página (con código fuente) se puede encontrar aquí .
• Mi pregunta SO relacionada con esto de hace dos años también puede ser útil: encontrar todas las A ^ x en un rango determinado .

Estoy siendo patéticamente perezoso (juego de palabras), pero por qué no ... parece cumplir con las reglas.

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"

Esto imprime ¹ todas las combinaciones que cumplen la propiedad de contraejemplo. He utilizado el control de la mónada-omega paquete de diagonalización ℕ ⁶ ... podría considerarse biblioteca-trampa. Pero viendo que alguien más tarde publicará una respuesta APL donde todo esto está integrado en el lenguaje (¿o no?), No doy demasiado al respecto ...

Por supuesto, el programa es demasiado lento (agotamiento ingenuo y listas vinculadas como estructura de datos) como para esperar un rendimiento de contraejemplo, pero el propio Haskell puede lograr un rendimiento decente.

¹ Como imprime las tuplas en formato de lista, es decir, en una sola línea, es necesario cambiar sus de terminales amortiguar apagado o no se verán cuando un resultado entra en acción. Como alternativa, se puede reemplazar printcon mapM_ printlo que obtener una nueva línea después de cada resultado, enjuagar un terminal con buffer de línea.

Para probar el programa, cambie each[3..]a each[2..], luego simplemente obtendrá todas las tuplas de Pitágoras no coprimas como resultado.

C #, sin bucles

OK, hojeé un par de esos enlaces, pero para ser honesto, fueron un poco aburridos. No estoy interesado en optimizarlo con tablas hash y demás. ¿Por qué debería necesitarlo? ¡Tienes una maldita supercomputadora!

Demonios, ¡ni siquiera quiero molestarme con los bucles! Esta solución seguirá la regla de no-loops .

Tenga en cuenta que el código que estoy a punto de escribir no es un buen código, o el tipo de código que escribiría en la vida real (en caso de que algún posible empleador lea esto). Este código enfatiza la brevedad y la capacidad de trabajar en una narrativa, y enfatiza las convenciones y rituales y bucles apropiados, etc.

Para demostrar de lo que estoy hablando, comenzaremos con una clase impactante con campos públicos para almacenar los operandos de la ecuación:

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

Bien, comenzaremos con lo que probablemente sea el desafío más difícil. Necesitamos encontrar una manera de permutar a través de cada combinación de esos operandos. Indudablemente, hay formas de hacerlo de manera más eficiente que verificar cada permutación, pero no puedo molestarme en descubrirlas. ¿Y por qué debería hacerlo? ¡Tenemos una maldita supercomputadora!

Aquí está el algoritmo que se me ocurrió. Es increíblemente ineficiente, y repasa los mismos operandos una y otra vez, pero ¿a quién le importa? ¡Supercomputadora!

• Trate los seis operandos como un número de base 2 y permute a través de cada combinación.
• Trate los seis operandos como un número de base 3 y permute a través de cada combinación.
• Trate los seis operandos como un número de base 4 y permute a través de cada combinación.
• (...)

¿Cómo hacer todo esto sin bucles? ¡Fácil! Simplemente implemente un IEnumerabley asociado IEnumeratorpara bombear las permutaciones. Más tarde, usaremos LINQ para consultarlo.

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

Ahora estamos en el negocio! Todo lo que necesitamos hacer es enumerar una instancia de BealOperandGeneratory encontrar un contraejemplo de la Conjetura de Beal.

Nuestro siguiente gran problema es que no parece haber una forma integrada de elevar BigIntegera la potencia de a BigInteger. Hay BigInteger.Pow(BigInteger value, int exponent), y BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), pero ningún método para elevar a BigInteger, al poder de otro BigInteger, módulo infinito.

¡Qué brillante clavo de problema! ¡Parece que fue hecho para ser resuelto con nuestro IEnumerable/ IEnumeratormartillo!

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

Ahora tenemos un método de extensión Pow, que se puede llamar en a BigInteger, y toma un BigIntegerexponente y ningún módulo.

OK, retrocedamos. ¿Cómo podemos saber si un particular BealOperandses un contraejemplo de la Conjetura de Beal? Bueno, dos cosas deben ser ciertas:

• Los operandos, cuando se conectan a esa fórmula en la parte superior de la página, deben formar una ecuación verdadera.
• A, B y C NO deben tener un factor primo común (es decir, su MCD es 1).

Tenemos lo que necesitamos para verificar la primera condición. Y resulta que la segunda condición es mucho más fácil de verificar de lo que parece. BigIntegerproporciona un GreatestCommonDivisormétodo encantador , que nos permite evitar convenientemente toda la pesadilla de tratar de implementar eso sin bucles.

Así que estamos listos para escribir un método para verificar si a BealOperandses un contraejemplo. Aquí va...

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

Y finalmente podemos unirlo todo con este Mainmétodo bastante hábil :

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

No hay contraejemplos con C ^ Z <= 1.0E27.

A partir de febrero de 2019, estoy revisando a C ^ Z <= 1.0E29 asumiendo que el exponente "X" y / o "Y" debe ser> = 5.

La versión actual de este programa ("X" y / o "Y"> = 5) tarda menos de 1 segundo en un AMD 2920X para encontrar todas las soluciones a C ^ Z <= 1.0E15. (Pero todos los mcd (A, B, C) son> = 2)

Detalles en http://www.durangobill.com/BealsConjecture.html

Puedo modificar el código actual (utiliza "C" y OpenMP) más allá de estos límites, pero necesitaré más de 128 GB de RAM para ejecutarlo. (Cientos de CPU también ayudarían. Miles de CPU serían aún mejores). (Si tiene acceso gratuito a algo como esto, contácteme).

Mi dirección de correo electrónico está en mi página de inicio en http://www.durangobill.com

La segunda variación del programa de búsqueda de Beal ha finalizado. Los resultados son:

$C^Z < 10^{26}$$A^X + B^Y = C^Z$$(X,Y) >= 4$ http://www.durangobill.com/BealXgt3e27.txt

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

Detalles en: http://www.durangobill.com/BealsConjecture.html

Las siguientes dos preguntas son: 1) ¿Puede una supercomputadora extender la búsqueda? 2) Si una supercomputadora pudiera extender la búsqueda, ¿sería práctico?

1) Para extender cualquiera de las búsquedas anteriores a 1.0E30, se requerirían 300 GB de RAM por núcleo a menos que los núcleos puedan compartir los 300 GB. Por cada aumento incremental adicional adicional en la potencia exponencial más allá de 1.0E30, la cantidad de RAM requerida aumenta en un factor de al menos 2.2.

2) La cantidad de potencia de procesamiento necesaria para cada aumento incremental adicional en el exponente hasta 1.0E30 y más multiplica el tiempo de CPU combinado por aproximadamente 3.8. La búsqueda a 1.0E29 tomó 2 semanas usando 12 núcleos. El tiempo de la supercomputadora no es generalmente "libre", y hay muy pocas posibilidades de que haya contraejemplos.

Como guía para la eficiencia del código en durangobill.com/BealE29code.txt, cada uno de los 12 núcleos promedió 220 millones de iteraciones de bucle por segundo para el bucle interno. (El promedio es para la ejecución de 2 semanas). (Un aumento en la memoria RAM más allá de lo que tengo aumentaría esta velocidad promedio hasta un factor de 2).

Dejaré que Austin responda 1) y 2) ya que él tiene acceso a una supercomputadora y yo no. (Si por casualidad remota, tanto 1) como 2) son "ir", puedo proporcionar el código "C" con la advertencia de que no estoy familiarizado con las instrucciones de subprocesos múltiples para grandes grupos de supercomputadoras).

Tuve que poner esto en 2 comentarios para que encaje.

Las principales matrices se asignan de la siguiente manera:

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

(Necesitará 128 GB de RAM para estas matrices)

con:

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

"Base" en realidad necesita 33 bits ( cbrt(1.0E29)): el bit adicional se rellena en "Potencia" (que solo necesita 7 bits).

Las matrices funcionan de manera similar a una tabla hash. Sin embargo, dado que están ordenados por PRIME1 y solo se usan como tablas de búsqueda, no necesita las listas vinculadas para acceder a ellas. El resultado es, por lo tanto, una búsqueda lineal de tiempo muy rápida para ver si una prueba A ^ X + B ^ Y = cualquier C ^ Z.

Por lo tanto, las declaraciones en el bucle más interno tienen solo dos bucles de profundidad.

Las declaraciones "Pragma" controlan la cantidad de núcleos de procesamiento múltiple que se utilizan (en este caso 12); todos pueden acceder a la copia única de las matrices.

Aquí está el código "principal" (en "C") (Espero que los comentarios se ajusten a la longitud de la línea publicada. Si no, cópielos y pegue el código en algún documento que tenga una longitud de línea más larga).