A Conjectura de Beal tem um prêmio de um milhão de dólares, se você provar / não provar.

Ele afirma que, onde A, B, C, x, ye z são números inteiros positivos com x, y, z> 2, então A, B e C têm um fator primo comum.

O desafio é escrever um programa que procure um exemplo contrário para refutar isso!

Regras

• Escreva um programa procurando um exemplo contrário da conjectura de Beal
• Você pode realizar uma pesquisa exaustiva (ou seja, todas as combinações possíveis de números que se encaixam neste formulário) ou usar algumas otimizações (por exemplo, A e B são simétricas).
• Você deve usar números inteiros de precisão arbitrária.

Notas

• Este é um concurso de popularidade, seja criativo!
• A velocidade não é necessária, mas a torna mais interessante. Optimize!
• Também estou interessado em ver o código mais curto também. Você receberá um +1 de mim!
• Vou executar o programa vencedor em um supercomputador ao qual tenho acesso!
• Essa conjectura é considerada verdadeira, mas isso não significa que não podemos tentar!
• Peter Norvig, do Google, também tentou esse problema. Você pode usar a página dele como orientação. Ele tem um pequeno programa Python que você pode usar como exemplo.
• Outro cara (que também trabalha no Google) melhorou bastante a abordagem de Norvig; sua página (com código fonte) pode ser encontrada aqui .
• Minha pergunta de SO relacionada a isso de dois anos atrás também pode ser útil: Encontre todos os A ^ x em um determinado intervalo .

Estou sendo pateticamente preguiçoso (trocadilhos), mas por que não ... parece cumprir as regras.

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"

Isso imprime ¹ todas as combinações que atendem à propriedade de contra-exemplo. Eu usei o pacote control-monad-omega para diagonalizar ℕ ⁶ ... pode ser considerado trapaça na biblioteca. Mas, como alguém mais tarde postará uma resposta da APL, onde todas essas coisas estão embutidas na linguagem (ou não é?), Eu não dou muito valor a isso ...

Obviamente, o programa é muito lento (exaustão ingênua e listas vinculadas como estrutura de dados) para que se possa realmente gerar um contra-exemplo, mas o próprio Haskell pode realmente obter um desempenho decente.

¹ Como imprime as tuplas no formato de lista, ou seja, em uma linha, você precisa desativar o buffer do terminal ou não verá quando um resultado chega. Como alternativa, você pode substituir printpor mapM_ printpara obter uma nova linha após cada resultado, liberando um terminal com buffer de linha.

Para testar o programa, mude each[3..]para each[2..], então você simplesmente obterá todas as tuplas pitagóricas não coprime como resultado.

C #, sem loops

OK, eu passei por alguns desses links, mas para ser sincero, eles eram um pouco chatos. Não estou interessado em otimizar o inferno com tabelas de hash e outros enfeites. Por que eu preciso? Você tem um maldito supercomputador!

Inferno, eu nem quero me preocupar com loops! Esta solução seguirá a regra de no-loops .

Observe que o código que estou prestes a escrever não é um código bom ou o tipo de código que eu escreveria na vida real (caso algum empregador em potencial leia isso). Esse código enfatiza a brevidade e a capacidade de trabalhar em uma narrativa e enfatiza as convenções, rituais e loops adequados e assim por diante.

Para demonstrar do que estou falando, começaremos com uma classe chocante com campos públicos para armazenar os operandos da equação:

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

OK, começaremos com o que provavelmente é o desafio mais difícil. Precisamos descobrir uma maneira de permutar todas as combinações desses operandos. Sem dúvida, existem maneiras de fazê-lo com mais eficiência do que verificar todas as permutações, mas não posso me incomodar em descobri-las. E por que eu deveria? Temos um maldito supercomputador!

Aqui está o algoritmo que eu criei. É incrivelmente ineficiente e repassa repetidamente os mesmos operandos, mas quem se importa? Supercomputador!

• Trate os seis operandos como um número de base 2 e permeie todas as combinações.
• Trate os seis operandos como um número base-3 e permeie todas as combinações.
• Trate os seis operandos como um número base-4 e permeie todas as combinações.
• (...)

Como fazer tudo isso sem loops? Fácil! Basta implementar um IEnumerablee associado IEnumeratorpara bombear as permutações. Mais tarde, usaremos o LINQ para consultá-lo.

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

Agora estamos no negócio! Tudo o que precisamos fazer é enumerar uma instância BealOperandGeneratore encontrar um contra-exemplo da conjectura de Beal.

Nosso próximo grande problema é que não parece haver uma maneira embutida de elevar BigIntegera à potência de a BigInteger. Existe BigInteger.Pow(BigInteger value, int exponent), e BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus), mas não existe, um método para elevar um BigInteger, ao poder de outro BigInteger, módulo infinito.

Que prego brilhante de problema! Parece que foi feito para ser resolvido com o nosso 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;
    }
}

Agora temos um método de extensão Pow, que pode ser chamado em a BigInteger, e leva umBigInteger expoente e nenhum módulo.

OK, vamos voltar. Como podemos saber se um particular BealOperandsé um contra-exemplo da conjectura de Beal? Bem, duas coisas precisam ser verdadeiras:

• Os operandos, quando conectados a essa fórmula na parte superior da página, devem formar uma equação verdadeira.
• A, B e C NÃO devem ter um fator primo comum (ou seja, seu MDC é 1).

Temos o que precisamos para verificar a primeira condição. E acontece que a segunda condição é muito mais fácil de verificar do que parece. BigIntegerfornece um GreatestCommonDivisormétodo adorável , que permite evitar convenientemente todo o pesadelo de tentar implementá-lo sem loops.

Portanto, estamos prontos para escrever um método para verificar se a BealOperandsé um contra-exemplo. Aqui vai ...

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

E, finalmente, podemos reunir tudo com esse Mainmétodo bastante liso :

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

Não há contra-exemplos com C ^ Z <= 1.0E27.

A partir de fevereiro de 2019, estou conferindo C ^ Z <= 1.0E29 na suposição de que o expoente "X" e / ou "Y" deve ser> = 5.

A versão atual deste programa ("X" e / ou "Y"> = 5) leva menos de 1 segundo em um AMD 2920X para encontrar todas as soluções em C ^ Z <= 1.0E15. (Mas todos os MDC (A, B, C) são> = 2)

Detalhes em http://www.durangobill.com/BealsConjecture.html

Posso modificar o código atual (usa "C" e OpenMP) além desses limites, mas precisarei de mais de 128 GB de RAM para executá-lo. (Centenas de CPUs também ajudariam. Milhares de CPUs seriam ainda melhores.) (Se você tiver acesso gratuito a algo assim, entre em contato comigo.)

Meu endereço de e-mail está na minha home page em http://www.durangobill.com

A segunda variação do programa de busca do Beal terminou. Os resultados são:

$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$ e C ^ Z <1.0E29 pode ser vista em: http: //www.durangobill .com / BealXgt4e29.txt

Detalhes em: http://www.durangobill.com/BealsConjecture.html

As próximas duas perguntas são: 1) Um supercomputador pode estender a pesquisa? 2) Se um supercomputador pudesse estender a pesquisa, seria prático?

1) Para estender uma das pesquisas acima para 1.0E30, seriam necessários 300 GB de RAM por núcleo, a menos que os núcleos possam compartilhar os 300 GB. Para cada aumento adicional adicional na potência exponencial além de 1.0E30, a quantidade de RAM necessária aumenta em um fator de pelo menos 2,2.

2) A quantidade de energia de processamento necessária para cada aumento adicional do expoente para além de 1.0E30 multiplica o tempo combinado da CPU em cerca de 3,8. A pesquisa para 1.0E29 levou 2 semanas usando 12 núcleos. O tempo do supercomputador geralmente não é "gratuito" e há muito pouca possibilidade de haver contra-exemplos.

Como um guia para a eficiência do código em durangobill.com/BealE29code.txt, cada um dos 12 núcleos teve em média 220 milhões de iterações de loop por segundo para o loop interno. (A média é para a execução de duas semanas.) (Um aumento na memória RAM além do que eu tenho aumentaria essa velocidade média em até um fator de 2.)

Vou deixar Austin responder 1) e 2), já que ele tem acesso a um supercomputador e eu não. (Se por acaso remoto, tanto 1 quanto 2) forem "válidos", posso fornecer o código "C" com a ressalva de que não conheço as instruções de vários threads para grandes agrupamentos de supercomputadores.)

Tinha que colocar isso em 2 comentários para ajustá-lo.

As principais matrizes são alocadas da seguinte maneira:

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

(Você precisará de 128 GB de RAM para essas matrizes)

com:

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

"Base" na verdade precisa de 33 bits (cbrt(1.0E29) ) - o bit extra é empacotado em “Power” (que precisa apenas de 7 bits).

As matrizes funcionam de maneira semelhante a uma tabela de hash. No entanto, como eles são classificados por PRIME1 e usados ​​apenas como tabelas de consulta, você não precisa das listas vinculadas para acessá-los. O resultado é, portanto, uma pesquisa de tempo linear muito rápida para ver se uma tentativa A ^ X + B ^ Y = qualquer C ^ Z.

Assim, as declarações no loop mais interno têm apenas dois loops de profundidade.

As instruções "Pragma" controlam o número de núcleos de multiprocessamento usados ​​(neste caso, 12) - todos podem acessar a cópia única das matrizes.

Aqui está o código “principal” (em “C”) (espero que os comentários correspondam ao comprimento da linha postada. Caso contrário, copie-os e cole o código em algum documento que tenha um comprimento de linha mais longo.)