Encontre o maior número primo que ainda é um número primo após a exclusão de dígitos

Em /math/33094/deleting-any-digit-yields-a-prime-is-there-a-name-for-this a seguinte pergunta é feita. Quantos primos existem que permanecem primos após a exclusão de qualquer um de seus dígitos? Por exemplo, 719é o melhor possível 71, 19e 79. Embora essa questão não tenha sido resolvida, achei que seria um bom desafio de codificação.

Tarefa. Dê o maior número primo possível de você que permanece um primo depois de excluir qualquer um de seus dígitos. Você também deve fornecer o código que o encontra.

Ponto. O valor do prime que você dá.

Você pode usar qualquer linguagem de programação e bibliotecas que desejar, desde que sejam gratuitas.

Para começar, 99444901133é o maior dado na página vinculada.

Prazo. Aceitarei a maior resposta correta dada exatamente uma semana após a primeira resposta correta maior do que a 99444901133dada em uma resposta.

Pontuações até agora.

Python (primo)

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

J (randomra) (Esta resposta iniciou o cronômetro de uma semana em 21 de fevereiro de 2013.)

222223333333

274 dígitos

4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111

Isso levou cerca de 20 horas de tempo de CPU para encontrar e cerca de 2 minutos por prime para provar. Por outro lado, a solução de 84 dígitos pode ser encontrada em cerca de 3 minutos.

84 dígitos

444444444444444444444444444444444444444444444444441111111113333333333333333333333333

77777777999999999999999777777777 (32 dígitos)
66666666666666622222222222222333 (32 dígitos)
647777777777777777777777777 (27 dígitos)
44444441333333333333 (20 dígitos)
999996677777777777777 (15 dígitos)
1699 )

Eu recomendo esta ferramenta se você deseja confirmar a primalidade: D. Alpern's ECM Applet

Também usando uma abordagem de repdigit, que parece ser a abordagem mais provável de encontrar valores grandes. O script a seguir ignora algoritmicamente a maioria dos números ou truncamentos que resultarão em múltiplos de 2, 3, 5 e agora 11 c / o PeterTaylor (sua contribuição aumentou a eficiência em aproximadamente 50%).

from my_math import is_prime

sets = [
 (set('147'), set('0147369'), set('1379')),
 (set('369'), set('147'), set('1379')),
 (set('369'), set('0369'), set('17')),
 (set('258'), set('0258369'), set('39')),
 (set('369'), set('258'), set('39'))]

div2or5 = set('024568')

for n in range(3, 100):
 for sa, sb, sc in sets:
  for a in sa:
   for b in sb-set([a]):
    bm1 = int(b in div2or5)
    for c in sc-set([b]):
     if int(a+b+c)%11 == 0: continue
     for na in xrange(1, n-1, 1+(n&1)):
      eb = n - na
      for nb in xrange(1, eb-bm1, 1+(~eb&1)):
       nc = eb - nb
       if not is_prime(long(a*(na-1) + b*nb + c*nc)):
        continue
       if not is_prime(long(a*na + b*(nb-1) + c*nc)):
        continue
       if not is_prime(long(a*na + b*nb + c*(nc-1))):
        continue
       if not is_prime(long(a*na + b*nb + c*nc)):
        continue
       print a*na + b*nb + c*nc

my_math.pypode ser encontrada aqui: http://codepad.org/KtXsydxK
Como alternativa, você também pode usar a gmpy.is_primefunção: Projeto GMPY

Algumas pequenas melhorias na velocidade como resultado da criação de perfil. A verificação de primalidade para o mais longo dos quatro candidatos foi movida para o final, xrangesubstitui rangee longsubstitui as intconversões de tipo. intparece ter sobrecarga desnecessária se a expressão avaliada resultar em a long.

Regras de Divisibilidade

Deixe- N ser um número inteiro de postitive a forma de um ... ab bc ... ... c , onde um , b e c são repetidos dígitos.

Por 2 e 5
- Para evitar a divisibilidade por 2 e 5 , c pode não estar no conjunto [0, 2, 4, 5, 6, 8] . Além disso, se b for um membro deste conjunto, o comprimento de c não poderá ser inferior a 2.

Por 3
- Se N = 1 (mod 3) , N pode não conter nenhum de [1, 4, 7] , pois a remoção de qualquer um deles resultaria trivialmente em um múltiplo de 3 . Da mesma forma para N = 2 (mod 3) e [2, 5, 8] . Esta implementação usa uma forma levemente enfraquecida disso: se N contiver um de [1, 4, 7] , ele não poderá conter nenhum de [2, 5, 8] e vice-versa. Além disso, N pode não consistir apenas em [0, 3, 6, 9] . Esta é em grande parte uma declaração equivalente, mas permite para alguns casos triviais, por exemplo a , b e ccada um sendo repetido um múltiplo de 3 vezes.

Por 11
- Como PeterTaylor observa, se N é da forma aabbcc ... xxyyzz , ou seja, consiste apenas em dígitos repetidos um número par de vezes, é trivialmente divisível por 11 : a0b0c ... x0y0z . Essa observação elimina metade do espaço de pesquisa. Se N é de comprimento ímpar, então o comprimento de um , b e c deve ser todos estranho, bem como (redução do espaço de busca 75%), e se N é de comprimento par, então apenas um de um , b ou c pode ser ainda de comprimento (redução de 25% do espaço de pesquisa).
- Conjectura: Se abc é um múltiplo de 11 , por exemplo 407 , em seguida, todas as repetições ímpares de um , b e c vão também ser múltiplos de 11 . Isso cai fora do escopo da divisibilidade acima pela regra 11 ; de fato, apenas repetições ímpares estão entre aquelas explicitamente permitidas. Não tenho uma prova disso, mas o teste sistemático não conseguiu encontrar um contra-exemplo. Compare: 444077777 , 44444000777 , 4444444000007777777777777 , etc. Qualquer pessoa pode se sentir à vontade para provar ou refutar essa conjectura. Desde então, o aditsu demonstrou que isso está correto.

Outras formas

2 conjuntos de dígitos repetidos Os
números da forma que a randomra estava seguindo, a ... ab ... b , parecem ser muito mais raros. Existem apenas 7 soluções com menos de 10 ¹⁷⁰⁰ , a maior das quais com 12 dígitos.

4 conjuntos de dígitos repetidos Os
números dessa forma, a ... ab ... bc ... cd ... d , parecem estar mais densamente distribuídos do que aqueles que eu estava procurando. Existem 69 soluções com menos de 10 ¹⁰⁰ , em comparação com as 32 usando 3 conjuntos de dígitos repetidos. Aqueles entre 10 ¹¹ e 10 ¹⁰⁰ são os seguintes:

190000007777
700000011119
955666663333
47444444441111
66666622222399
280000000033333
1111333333334999
1111333333377779
1199999999900111
3355555666999999
2222233333000099
55555922222222233333
444444440004449999999
3366666633333333377777
3333333333999888883333
4441111113333333333311111
2222222293333333333333999999
999999999339999999977777777777
22222226666666222222222299999999
333333333333333333339944444444444999999999
559999999999933333333333339999999999999999
3333333333333333333111111111111666666666611111
11111111333330000000000000111111111111111111111
777777777770000000000000000000033333339999999999999999999999999
3333333333333333333333333333333333333333333333336666666977777777777777
666666666666666666611111113333337777777777777777777777777777777777777777
3333333333333333333888889999999999999999999999999999999999999999999999999933333333

Há um argumento heurístico simples sobre por que esse deveria ser o caso. Para cada comprimento digital, há um número de conjuntos repetidos (ou seja, 3 conjuntos repetidos ou 4 conjuntos repetidos, etc.) para os quais o número esperado de soluções será o mais alto. A transição ocorre quando o número de soluções possíveis adicionais, tomadas como uma proporção, supera a probabilidade de que o número adicional a ser verificado seja primo. Dada a natureza exponencial das possibilidades de verificação e a natureza logarítmica da distribuição de números primos, isso acontece relativamente rápido.

Se, por exemplo, desejássemos encontrar uma solução de 300 dígitos, a verificação de 4 conjuntos de dígitos repetidos teria muito mais probabilidade de produzir uma solução do que 3 conjuntos e 5 conjuntos ainda mais. No entanto, com o poder de computação que tenho à minha disposição, encontrar uma solução muito superior a 100 dígitos com 4 conjuntos estaria fora da minha capacidade, quanto mais 5 ou 6.

222223333333 (12 dígitos)

Aqui, procurei apenas no formato aa..aabb..bb até 100 dígitos. Apenas outros hits são 23 37 53 73 113 311.

Código J (limpo) (desculpe, sem explicação):

a=.>,{,~<>:i.100
b=.>,{,~<i.10
num=.".@(1&":)@#~
p=.(*/"1@:((1&p:)@num) (]-"1(0,=@i.@#)))"1 1
]res=./:~~.,b (p#num)"1 1/ a

Edit: Alguém já fez uma análise mais profunda do que eu fiz aqui.

Não é uma solução, mas uma estimativa aproximada do número de soluções com n dígitos.

Gerando código J

   ops=: 'title ','Estimated number of solutions by digits',';xcaption ','digits',';ycaption ','log10 #'
   ops plot 10^.((%^.)%(2&(%~)@^.@(%&10))^(10&^.))(10&^(2+i.100))

Javascript (força bruta)

Ainda não encontrou um número maior

http://jsfiddle.net/79FDr/4/

Sem uma biblioteca bigint, o javascript é limitado a números inteiros <= 2^53.

Como é Javascript, o navegador reclamará se não liberarmos o thread de execução para a atualização da interface do usuário. Como resultado, decidi rastrear onde o algoritmo está em sua progressão na interface do usuário.

function isPrime(n){
    return n==2||(n>1&&n%2!=0&&(function(){
        for(var i=3,max=Math.sqrt(n);i<=max;i+=2)if(n%i==0)return false;
        return true;
    })());
};

var o=$("#o"), m=Math.pow(2,53),S=$("#s");

(function loop(n){
    var s = n.toString(),t,p=true,i=l=s.length,h={};
    if(isPrime(n)){
        while(--i){
            t=s.substring(0,i-1) + s.substring(i,l); // cut out a digit
            if(!h[t]){   // keep a hash of numbers tested so we don't end up testing 
                h[t]=1;  // the same number multiple times
                if(!isPrime(+t)){p=false;break;}
            }
        }
        if(p)
            o.append($("<span>"+n+"</span>"));
    }
    S.text(n);
    if(n+2 < m)setTimeout(function(){
        loop(n+2);
    },1);
})(99444901133);

Um link para uma análise do problema foi publicado, mas achei que faltavam algumas coisas. Vejamos o número de m dígitos, consistindo em k sequências de 1 ou mais dígitos idênticos. Foi demonstrado que, se dividirmos os dígitos nos grupos {0, 3, 6, 9}, {1, 4, 7} e {2, 5, 8}, uma solução não poderá conter dígitos do segundo e do terceiro grupo e deve conter 3n + 2 dígitos de um desses grupos. Pelo menos duas das k sequências devem ter um número ímpar de dígitos. Dos dígitos {1, 4, 7}, apenas 1 e 7 podem ser o dígito mais baixo. Nenhum de {2, 5, 8} pode ser o dígito mais baixo. Portanto, existem quatro (1, 3, 7, 9) ou duas (3, 9) opções para o dígito mais baixo,

Quantos candidatos existem? Temos m dígitos divididos em k seqüências de pelo menos 1 dígito. Existem (m - k + 1) mais de (k - 1) maneiras de escolher os comprimentos dessas seqüências, que são aproximadamente (m - 1,5k + 2) ^ (k - 1) / (k - 1) !. Existem 2 ou 4 opções para o dígito mais baixo, seis no total. Existem seis opções para os outros dígitos, exceto as opções 36/7 para o dígito mais alto; o total é (6/7) * 6 ^ k. Existem 2 ^ k maneiras de escolher se o comprimento de uma sequência é par ou ímpar; k + 1 destes são excluídos porque nenhum ou apenas um são ímpares; multiplicamos o número de opções por (1 - (k + 1) / 2 ^ k), que é 1/4 quando k = 2, 1/2 quando k = 3, 11/16 quando k = 4 etc. de dígitos do conjunto {1, 4, 7} ou {2, 5, 8} deve ser 3n + 2, para que o número de opções seja dividido por 3.

Multiplicando todos esses números, o número de candidatos é

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (6/7) * 6^k * (1 - (k + 1) / 2^k) / 3

ou

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k)

O candidato em si e os números k criados pela remoção de um dígito devem ser primos. A probabilidade de um inteiro aleatório em torno de N ser primo é de cerca de 1 / ln N. A probabilidade de um número aleatório de dígitos m é de cerca de 1 / (mln 10). No entanto, os números aqui não são aleatórios. Todos foram escolhidos para não serem divisíveis por 2, 3 ou 5. 8 dos 30 números inteiros consecutivos não são divisíveis por 2, 3 ou 5. Portanto, a probabilidade de ser um primo é (30/8) / (m ln 10) ou cerca de 1,6286 / m.

O número esperado de soluções é de cerca de

(m - 1.5k + 2)^(k - 1) / (k - 1)! * (2/7) * 6^k * (1 - (k + 1) / 2^k) * (1.6286 / m)^(k + 1)

ou para grandes m sobre

(1 - (1.5k - 2) / m)^(k - 1) / (k - 1)! * 0.465 * 9.772^k * (1 - (k + 1) / 2^k) / m^2

Para k = 2, 3, 4, ... obtemos o seguinte:

k = 2: 11.1 * (1 - 1/m) / m^2
k = 3: 108 * (1 - 2.5/m)^2 / m^2 
k = 4: 486 * (1 - 4/m)^3 / m^2


k = 10: 10,065 * (1 - 13/m)^9 / m^2

A partir de k = 10 em diante, o número diminui novamente.