O número 113
é o primeiro primo cujo comprimento 3
é primo, a soma digital 5 = 1 + 1 + 3
é primo e o produto digital 3 = 1 * 1 * 3
é primo.
Um primo que possui essas três propriedades será chamado de primo primordial . Os primos 11117
e 1111151
são outros exemplos.
Objetivo
Escreva um programa que encontre o maior número supremamente possível em menos de uma hora em um computador pessoal moderno decente (como a especificação preferida aqui ).
Você não deve simplesmente nos dar um grande supremo supremo. Você precisa nos mostrar seu processo de pesquisa com o código que realmente funciona. Você pode criar soluções suas ou de outras pessoas, mas não se esqueça de dar crédito a elas. Estamos meio que tentando encontrar o maior primo supremo possível de realizar em um computador normal em uma hora.
Pontuação
A finalização que encontra as maiores vitórias supremas. Se houver finitos numeros primos supremos, então a primeira submissão que gera as vitórias supremos mais altas.
(Se você puder provar matematicamente que existem ou não infinitos primos supremos, darei a você 200 representantes de recompensa só porque. :))
Detalhes
- Você pode usar qualquer fonte para gerar seus números primos (por exemplo, internet).
- Você pode usar métodos probabilísticos de teste principal.
- Tudo está na base 10.
- Zero e um NÃO são considerados primos.
- Primes que contêm
0
têm um produto digital0
tão obviamente que não podem ser supremos. Para manter a página menos confusa, coloque números primos supremos grandes (mais de 100 dígitos) no formato:
{[number of 1's before the prime digit]}[prime digit]{[number of 1's after the prime digit]}
Então,
1111151
pode ser expresso como{5}5{1}
.
fonte
Respostas:
Perl, 15101 dígitos, {83} 7 {15017}, 8 minutos. Máximo encontrado: 72227 dígitos
Usando meu módulo Math :: Prime :: Util e seu back-end GMP . Possui vários testes de composição, incluindo is_prob_prime () com um teste ES BPSW ( um pouco mais rigoroso que o ispseudoprime de Pari), is_prime () que adiciona um MR de base aleatória e is_provable_prime () que executará o BLS75 T5 ou o ECPP. Nesses tamanhos e tipos, fazer uma prova vai demorar muito tempo. Joguei outro teste de RM no submarino pedante. Vezes em um Core2 E7500 que definitivamente não é o meu computador mais rápido (leva 2,5 minutos no meu i7-4770K).
Como Tim S. ressalta, podemos continuar procurando valores maiores, até o ponto em que um único teste leva uma hora. Com ~ 15.000 dígitos neste E7500, são necessários cerca de 26s para um teste de RM e 2 minutos para o is_prime completo (divisão de teste mais MR de base 2 mais ES Lucas mais um MR de base aleatória). Meu i7-4770K é 3x mais rápido. Tentei alguns tamanhos, principalmente vendo como funcionava nos resultados de outras pessoas. Eu tentei 8k, 20k e 16k, matando cada um após ~ 5 minutos. Eu tentei 15k em progressão por ~ 10m cada e tive sorte no quarto.
Os testes de PRP do OpenPFGW são certamente mais rápidos, depois dos 4000 ou mais dígitos, e muito mais rápidos na faixa de 50k +. No entanto, seu teste possui uma quantidade razoável de falsos positivos, o que o torna um ótimo pré-teste, mas ainda assim gostaria de verificar os resultados com outra coisa.
Isso pode ser paralelo com threads perl ou usando o MCE semelhante aos exemplos paralelos de busca de Fibonacci no módulo.
Tempo e resultados em um i7-4770K inativo usando o núcleo único:
Para o resultado de 32k dígitos, iniciei 6 scripts em execução ao mesmo tempo, cada um com argumentos sucessivos começando em 32000. Após 26,5 minutos, um terminou com o resultado de 32063 dígitos mostrado. Para 57k, permiti que scripts sucessivos executassem 6 por vez, durante uma hora, em incrementos de entrada de 500 até que o resultado de 57k retornasse em 57 minutos. O resultado de 72k dígitos foi encontrado com primos sucessivos de 70k em diante, portanto, definitivamente não foi encontrado em uma hora (embora depois que você saiba por onde começar, é).
O script:
fonte
gmpy2
e PyPy commy_math
): codepad.org/aSzc0esTforprimes { ...do stuff... } 1e7;
que é 10x ou mais rápido (parabéns ao Pari / GP por muitas ótimas idéias). Eu sempre aprecio o feedback, então, deixe-me saber se algo não está funcionando da maneira que você deseja.Python 2.7 no PyPy, {2404} 3 {1596} (~ 10 ^ 4000)
Encontrei este cerca de 50 minutos após o início de 4000. Portanto, eu estimaria que esse é o limite superior dessa abordagem de código.
Alteração: notei que alguns comprimentos parecem ser mais proveitosos para gerar esse tipo de primo do que outros, então decidi verificar apenas 50 locais aleatórios do dígito que não é 1, em vez de todos os locais possíveis, antes de mudar em. Não tenho certeza absoluta de que isso melhore o desempenho ou que 50 esteja correto, mas veremos.
A lista de possibilidades é gerada com base no fato de que, para que o requisito de produtos seja atendido, o número deve ser todos, exceto um primo. Além disso, o número primo não pode ser 2 por causa da relação soma e comprimento, e a soma digital não deve ser divisível por três, fornecendo os requisitos de% 3.
is_prime extraído de http://codepad.org/KtXsydxK , escrito por @primo
Nota: essa função is_prime é na verdade um teste de pseudoprime Baillie-PSW, mas não há contra-exemplos conhecidos, portanto, não vou me preocupar com a distinção.
fonte
is_very_very_very_very_very_very_very_probably_prime()
...PARI / GP, 4127 dígitos
(10 4127 -1) / 9 + 2 * 10 515
Essa é uma pesquisa bastante direta: verifique apenas os comprimentos dos dígitos primos, depois calcule os números primos possíveis de usar e, em seguida, repita todas as possibilidades. Eu casei especialmente os casos comuns em que existem 0 ou 1 dígitos primos adequados para usar.
Demorou 36 minutos para calcular em um núcleo de uma máquina bastante antiga. Não seria difícil encontrar um número tão alto de mais de 5000 dígitos em uma hora, tenho certeza, mas também estou impaciente.
Uma solução melhor seria usar qualquer linguagem razoável para fazer tudo, exceto o loop mais interno, e então construir um arquivo abc para o primeform, otimizado para esse tipo específico de cálculo. Isso deve poder empurrar o cálculo para pelo menos 10.000 dígitos.
Edit : Eu implementei a solução híbrida descrita acima, mas na minha máquina antiga não consigo encontrar o primeiro termo com> = 10.000 dígitos em menos de uma hora. A menos que eu execute algo mais rápido, terei que mudar para um alvo menos elevado.
fonte
Dígitos do Mathematica 3181
Atualização: houve alguns erros graves na minha primeira submissão. Consegui dedicar algum tempo para verificar os resultados deste. A saída é formatada como uma lista de dígitos. Isso facilita a verificação de cada uma das condições.
Exemplo
Este foi o meu primeiro teste, uma busca por uma solução com 3181 dígitos. Encontrou o primeiro caso em 26 segundos.
Vamos analisar o raciocínio. Então entraremos no programa em si.
Vamos começar, como eu fiz, "Qual é o 450º primo?" Podemos encontrar uma solução com tantos dígitos (3181)?
O número é encontrado juntando os dígitos.
Mas, em vez de exibi-lo, podemos perguntar quais são os dígitos e onde estão.
Isso significa que havia 3180 instâncias do dígito 1 e uma única instância do dígito 7.
Em que posição está o dígito 7?
Portanto, o dígito 7 é o 142º dígito. Todos os outros são 1's.
Obviamente, o produto dos dígitos deve ser primo, ou seja, 7.
E a soma dos dígitos também é primordial.
E sabemos que o número de dígitos é primo. Lembre-se, selecionamos o 450º primo, ou seja, 3118.
Então, todas as condições foram cumpridas.
fonte
4002 * 1 + 7 = 4009
e não o 4003, de acordo com as especificações.Python 2.7, 6217 dígitos: {23} 5 {6193} 6 minutos 51 segundos
Eu estava trabalhando em minha própria versão e fiquei desapontado ao ver que @issacg havia me superado com uma abordagem muito semelhante, embora com is_ (very_probably) _prime (). No entanto, vejo que tenho algumas diferenças significativas que resultam em uma resposta melhor em menos tempo (quando eu também uso is_prime). Para deixar isso claro, quando também a partir de 4000, chego a uma resposta melhor de 4001 dígitos ({393} 7 {3607}) em apenas 26 minutos, 37 segundos usando o interpretador Python padrão (também na versão 2.7), não o PyPy versão. Além disso, não estou 'verificando' os números. Todos os candidatos são verificados.
Aqui estão as principais melhorias:
Use um gerador principal ( https://stackoverflow.com/questions/567222/simple-prime-generator-in-python/568618#568618 ) para criar uma lista de números primos a serem verificados (e sua versão de "números primos pequenos") e para gerar comprimentos de número elegíveis.
Queremos gastar nosso tempo procurando o maior número primo supremo de um determinado comprimento, não o menor; portanto, construo os maiores números possíveis primeiro para verificação, não o menor. Então, uma vez encontrado, podemos passar imediatamente para o próximo comprimento.
EDIT: Agora com multiprocessamento
Esta é uma alteração significativa para as versões anteriores. Antes, notei que minha máquina com 8 núcleos mal estava funcionando, então decidi tentar o multiprocessamento em Python (primeira vez). Os resultados são muito bons!
Nesta versão, são gerados 7 processos filhos, que retiram uma 'tarefa' de uma fila de possibilidades em potencial (num_length + dígitos elegíveis). Eles agitam tentando diferentes [7,5,3] posições até encontrar uma. Se assim for, informa o processo mestre do novo comprimento mais longo que foi encontrado. Se as crianças estiverem trabalhando em um num_length menor, elas apenas pagam a fiança e vão para a próxima.
Comecei esta corrida com 6000, e ela ainda está em execução, mas até agora estou muito satisfeito com os resultados.
O programa ainda não para corretamente, mas não é um grande negócio para mim.
Agora o código:
fonte
my_math
também pode ser usado para gerar uma lista de números primos, à lawhile prime < 20006: prime = next_prime(prime)
. Parece ser cerca de três vezes mais rápidogen_primes
e muito mais eficiente em termos de memória.C, GMP - {7224} 5 {564} = 7789
Parabéns a @issacg e a todos vocês pelas inspirações e truques.
E também a pergunta magistral solicitada @ Calvin's Hobbies para esta pergunta.
Compilar:
gcc -I/usr/local/include -o p_out p.c -pthread -L/usr/local/lib -lgmp
Se você deseja doar seu poder computacional ou curioso pelo desempenho, copie o código e compile. ;) Você precisará do GMP instalado.
fonte
PFGW, 6067 dígitos, {5956} 7 {110}
Execute PFGW com o seguinte arquivo de entrada e
-f100
para pré-fatorar os números. Em cerca de 2-3 minutos de CPU no meu computador (i5 Haswell), ele encontra o PRP (10 ^ (6073-6) -1) / 9 + 6 * 10 ^ 110 ou {5956} 7 {110} . Eu escolhi 6000 dígitos como ponto de partida como um número do tipo "nada na minha manga", que é um pouco maior do que todos os envios anteriores.Com base na rapidez com que consegui encontrar esse, pude facilmente aumentar o número de dígitos e ainda encontrar um PRP em uma hora. Com a forma como as regras são escritas, posso até encontrar o tamanho em que minha CPU, rodando nos quatro núcleos, pode concluir um teste de PRP em uma hora, demorar muito tempo para encontrar um PRP e fazer com que minha "pesquisa" seja apenas de um PRP.
PS Em alguns sentidos, essa não é uma solução de "código" porque eu não escrevi nada além do arquivo de entrada ... mas, em seguida, muitas soluções Mathematica de uma linha para problemas matemáticos poderiam ser descritas da mesma maneira, como poderiam usando uma biblioteca que faz o trabalho duro para você. Na realidade, acho difícil traçar uma boa linha entre os dois. Se você preferir, eu poderia escrever um script que crie o arquivo de entrada PFGW e chame PFGW. O script pode até pesquisar em paralelo, para usar todos os 4 núcleos e acelerar a pesquisa em ~ 4 vezes (na minha CPU).
PPS Acho que o LLR pode fazer os testes de PRP para esses números, e espero que seja muito mais rápido que o PFGW . Um programa dedicado de peneiração também poderia ser melhor para fatorar esses números do que o PFGW, um de cada vez. Se você combinou isso, tenho certeza de que poderia aumentar os limites muito mais do que as soluções atuais.
fonte
Python 2.7, 17-19 dígitos
Encontrado 5111111111111 (13 dígitos) em 3 segundos e esse supremo supremo de 17 dígitos em 3 minutos. Suponho que a máquina alvo possa executar isso e obter um primo supremo de 19 dígitos em menos de uma hora. Essa abordagem não é bem dimensionada porque mantém primos até a metade do número de dígitos de destino na memória. A pesquisa de 17 dígitos requer o armazenamento de uma matriz de 100 milhões de booleanos. 19 dígitos exigiriam uma matriz de elementos 1B e a memória se esgotaria antes de chegar a 23 dígitos. O tempo de execução provavelmente também seria.
As abordagens de teste de primazia que não envolvem uma variedade ridiculamente grande de números primos divisores serão muito melhores.
fonte
Mathematica
42114259 dígitosCom o número:
{1042} 7 {3168}{388} 3 {3870}Que foi gerado pelo seguinte código:
Os lançamentos fazem com que ele pare de testar outros números com os mesmos dígitos que o encontrado atualmente. como começa o teste no dígito mais significativo, isso significa que ele sempre retorna o maior número, a menos que o número de dígitos seja um membro de um trigêmeo primo.
Simplesmente comecei a testar logo abaixo do valor de uma das respostas anteriores :)
Quando termina, o número é armazenado na variável mais baixa
fonte
JavaScript, 3019 dígitos, {2.273} 5 {745}
Isso usa o teste MillerRabin incluído no BigInteger.js por Tom Wu.
A partir de 0 => 2.046 dígitos = {1799} 7 {263} em uma hora .
A partir de 3000 => 3.019 dígitos = {2.273} 5 {745} em uma hora, menos 3 segundos .
Quando começou a partir de 0, o programa avançou e começou a procurar novamente a uma extensão de 1,5X a duração do último s-prime encontrado. Então, quando eu vi o quão rápido ele estava rodando, imaginei que encontraria um começando em 3000 em uma hora - o que aconteceu com apenas 3 segundos de sobra.
Você pode experimentá-lo aqui: http://goo.gl/t3TmTk
(Defina para calcular todos os primos s ou pule adiante).
O programa funciona construindo sequências de todos os "1" s, mas com um "3", "5" ou "7". Eu adicionei uma verificação rápida na função IsStrPrime para rejeitar os números que terminam em "5".
Isso foi bem divertido. Lembra-me de um quebra-cabeça que fiz há muitos anos para calcular o que é chamado de dígito removido primo . Este é um número primo que, se você remover qualquer dígito, o número restante ainda será primo. Por exemplo 1037 é um número primo removido porque 1037, 037, 137, 107 e 103 são números primos. Encontrei 84 dígitos, e o mais longo que conheço tem 332 dígitos. Tenho certeza de que poderíamos encontrar um muito mais tempo com as técnicas usadas para este quebra-cabeça. (Mas escolher os números dos testes é um pouco mais complicado - talvez?)
fonte
Axioma, 3019 dígitos {318} 5 {2700}
resultado do valor inicial 3000 em 529 seg
fonte