problema de Goldbach.O problema de Goldbach é a afirmação de que qualquer número par, começando com 4, pode ser representado como a soma de dois primos. Ou seja, 6 = 3 + 3; 8 = 5 + 3 ... Pelo que entendi, a solução para o problema é a prova ou refutação dessa afirmação.
A primeira coisa que precisamos fazer é implementar um método para verificar se um número é primo. Um primo é um número divisível apenas por ele mesmo e por um.
public static bool IsPrimeNumber(ulong n)
{
var result = true;
if (n > 1)
{
for (ulong i = 2; i < n; i++)
{
if (n % i == 0)
{
result = false;
break;
}
}
}
else
{
result = false;
}
return result;
}
Agora precisamos obter uma coleção de todos os números primos até ulong.MaxValue = 18446744073709551615 (2 ^ 64-1)
public static IEnumerable<ulong> GetAllPrimeNumbers(ulong maxNumber)
{
List<ulong> primeNumbers = new List<ulong>();
for (ulong i=0; i < maxNumber; i++ )
{
if (IsPrimeNumber(i))
{
primeNumbers.Add(i);
}
}
return primeNumbers;
}
A intuição sugere que levará muito tempo para calculá-los, então vamos reduzir seu número para 300.000
static void Main(string[] args)
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
IEnumerable<ulong> primeNumbers = GetAllPrimeNumbers();
checkGoldbach(primeNumbers);
stopwatch.Stop();
Console.WriteLine(" " + stopwatch.Elapsed.TotalSeconds + " ");
foreach(var number in primeNumbers)
{
Console.Write(number + " ");
}
Console.ReadKey();
}
Então, eu queria encontrar todos os números primos até 2 ^ 64 (parecia-me que algumas horas de cálculos seriam suficientes para mim).
Após dois minutos de execução do programa, decidi colocar um ponto de interrupção e verificar qual número está sendo verificado quanto à simplicidade:
411780 iterações após dois minutos de cálculos. Decidi otimizar um pouco o método para verificar a simplicidade de um número, já que não há necessidade de continuar iterando depois da metade do número.
Assim, o número de iterações necessárias para verificar a simplicidade é reduzido pela metade. Pareceu-me que em 2 minutos o número de iterações deveria dobrar
Mas aqui também eu estava errado. A produtividade aumentou não 100%, mas 22%. Como eu entendi mais tarde, isso se deve ao fato de que metade dos cheques, como antes, são eliminados pela divisão por 2, um terço de todos os números não eliminados pela divisão por 2 são eliminados pela divisão por 3, etc. Dos 500.154 testes de simplicidade, 4.1549 primos foram encontrados. Ou seja, o for iteration
for (ulong i = 2; i <= n/2; i++)
{
if (n % i == 0)
{
result = false;
break;
}
}
executado até o fim (sem interrupção) apenas 41.549 vezes. Em outros casos, foi interrompido antes ...
500154 e não perto de 2 ^ 64, você precisa calcular quanto tempo levará para verificar a simplicidade de todos os números para 2 ^ 64
Primeiro, vamos reduzir o número de iterações de 2 ^ 64 para 30000 e calcular o tempo de execução do método do cronômetro
para iterar números até 30.000, 1 segundo foi gasto
agora vamos criar uma tabela com outros valores do número de iterações
Vamos escrever o resultado no Excel e construir um gráfico de pontos para as coordenadas "Número de iterações por tempo" e "Número de primos por intervalo"
Agora podemos descobrir o número aproximado de primos até 2 ^ 64, e aproximadamente quanto tempo levará para encontrar todos eles
Se você adicionar uma linha de tendência "Linear" ao gráfico de "números primos por intervalo", o Excel fornecerá a fórmula y = 0,074x + 3004 (não sei quão precisa é a fórmula). Isso significa que o número aproximado de primos até ulong.MaxValue = 0,074 * 2 ^ 64 + 3004;
Da mesma forma, adicionando a linha de tendência "Polinomial" ao gráfico "Número de iterações ao longo do tempo", obtemos a fórmula y = 7E-10x2 + 6E-05x. Substituindo nosso número 2 ^ 64 em vez de x, você pode descobrir que, para encontrar todos os primos até 2 ^ 64, precisamos de aproximadamente 2,38E + 29 segundos, ou 7553198149564240000000 anos. Ok, eu não posso esperar muito.
Vamos tentar provar que a conjectura de Goldbach é verdadeira para todos os números pares até 300.000.
public static void checkGoldbach(IEnumerable<ulong> primeNumbers)
{
ulong numbersCount = 300000;
for (ulong number = 4; number<numbersCount; number+=2)
{
bool isGoldbachResult = false;
foreach(ulong primeNumber1 in primeNumbers)
{
foreach(ulong primeNumber2 in primeNumbers)
{
if(primeNumber1+primeNumber2==number)
{
Console.WriteLine("{0} = {1} + {2}", number, primeNumber1, primeNumber2);
isGoldbachResult = true;
break;
}
if(primeNumber1+primeNumber2>number)
{
break;
}
}
if(isGoldbachResult|| primeNumber1>number)
{
break;
}
}
if(!isGoldbachResult)
{
Console.WriteLine(" " + number + " ");
break;
}
}
}
Se a afirmação de Goldbach não for verdadeira para algum número, o método parará de calcular naquele número.
Após 9 minutos de cálculos, podemos dizer que a hipótese de Goldbach é válida para números menores que 300.000.
Total
Tudo acabou por não ser tão simples como me parecia no início, e entendo que não estou nem perto de resolver o problema.
Muito provavelmente, parece-me que existem opções melhores para verificar um número para simplificar. É possível que o método que verifica os números pares para a correção da afirmação de Goldbach possa ser implementado de forma mais racional do que uma simples enumeração de primos, mas eu não quero mais gastar tanto tempo nisso ...
Resolver o problema de Goldbach não dará nada à humanidade. Até agora foi provado que a hipótese é verdadeira para números até 4 * 10 ^ 18, mas de que adianta prová-la para todos os números? Com que propósito os matemáticos escrevem livros sobre este assunto e geralmente passam seu tempo resolvendo tais "problemas"?
Eu realmente quero perguntar às pessoas experientes se minha fórmula para calcular o número de números primos por intervalo tem o direito de existir.
PS
Provavelmente, não preciso escrever artigos sobre os quais conheço pouco. Eu não esperava que a comunidade reagisse dessa forma. Mas não fingi que minha decisão foi a única correta. Eu sou um amador neste campo.
Com que propósito escrevi este artigo?
Dediquei um tempo para pesquisar essa questão e pareceu-me que algumas pessoas poderiam gostar. Foi interessante para mim porque é uma tarefa divertida. Mas por que os matemáticos estão perdendo tempo com isso? Sinceramente, não entendo o real benefício de pesquisar especificamente essas questões.
PPS
Depois de ler as resenhas sobre o artigo, decidi tirar conclusões.
Muito provavelmente, parece-me que existem opções melhores para verificar um número para simplificar
Conforme sugerido por usuários dvserg drWhy e Pavel_The_Besté realmente. Por exemplo, usando a peneira de Eratóstenes, uma coleção de primos pode ser coletada muito mais rápido. Aqui estão os artigos que você pode ler sobre este tópico: Algoritmo para verificar a simplicidade em O (log N) , Wikipedia , você pode ler as obras de Srinivas Ramanujan Iyengor
Minha fórmula para calcular o número de números primos por intervalo tem o direito de existir?
Não
Resolver o problema de Goldbach não dará nada à humanidade?
Minha opinião de que alguns problemas matemáticos são inúteis causou uma atitude fortemente negativa da maioria dos usuários. Comercialvvadzim Refrigerador Bromzh Graph-in Refrigerador EimKR bfDeveloper e simforam capazes de me convencer disso. Retiro minhas palavras.
Desde os tempos antigos, os matemáticos buscam a verdade, e sua busca freqüentemente leva a consequências benéficas para o progresso. Talvez o problema em si e sua solução não dêem nada ao mundo aqui e agora, mas são as conclusões tiradas durante a busca por uma solução que podem ser úteis a longo prazo.