Dado um número inteiro não negativo N, imprima o menor número inteiro positivo ímpar que é um forte pseudoprime para todas as primeiras Nbases primárias.

Esta é a sequência O0IS A014233 .

Casos de teste (um indexado)

1       2047
2       1373653
3       25326001
4       3215031751
5       2152302898747
6       3474749660383
7       341550071728321
8       341550071728321
9       3825123056546413051
10      3825123056546413051
11      3825123056546413051
12      318665857834031151167461
13      3317044064679887385961981

Os casos de teste para N > 13não estão disponíveis porque esses valores ainda não foram encontrados. Se você conseguir encontrar o (s) próximo (s) termo (s) na sequência, certifique-se de enviá-lo à OEIS!

Regras

• Você pode optar por usar Ncomo um valor indexado a zero ou um indexado.
• É aceitável que sua solução funcione apenas para os valores representáveis ​​no intervalo inteiro do seu idioma (até N = 12números inteiros de 64 bits não assinados), mas sua solução deve teoricamente funcionar para qualquer entrada, supondo que seu idioma suporte números inteiros de comprimento arbitrário.

fundo

Qualquer inteiro par positivo xpode ser escrito na forma x = d*2^sem que dé estranho. de spode ser calculado dividindo repetidamente npor 2 até que o quociente não seja mais divisível por 2. dé esse quociente final e sé o número de vezes que 2 divide n.

Se um número inteiro positivo né primo, o pequeno teorema de Fermat declara:

Em qualquer campo finito Z/pZ (onde pé primo), as únicas raízes quadradas de 1são 1e -1(ou, equivalentemente 1e p-1).

Podemos usar esses três fatos para provar que uma das duas declarações a seguir deve ser verdadeira para um primo n(onde d*2^s = n-1e ré um número inteiro [0, s)):

O teste de primalidade de Miller-Rabin opera testando o contrapositivo da reivindicação acima: se existe uma base atal que ambas as condições acima sejam falsas, então nnão é primo. Essa base aé chamada de testemunha .

Agora, testar todas as bases [1, n)seria proibitivamente caro em tempo de computação para grandes empresas n. Existe uma variante probabilística do teste de Miller-Rabin que apenas testa algumas bases escolhidas aleatoriamente no campo finito. No entanto, foi descoberto que testar apenas abases primárias é suficiente e, portanto, o teste pode ser realizado de maneira eficiente e determinística. De fato, nem todas as bases principais precisam ser testadas - apenas um certo número é necessário, e esse número depende do tamanho do valor que está sendo testado para a primalidade.

Se um número insuficiente de bases primárias for testado, o teste poderá produzir falsos positivos - números inteiros compostos ímpares em que o teste falha em provar sua composição. Especificamente, se uma base afalhar em provar a composição de um número composto ímpar, esse número será chamado de forte pseudo-tempo para a base a. Esse desafio consiste em encontrar os números compostos ímpares que são psuedoprimes fortes para todas as bases menores ou iguais ao Nnúmero primo (o que equivale a dizer que eles são pseudoprimes fortes para todas as bases primárias menores ou iguais ao Nnúmero primo) .

C, 349 295 277 267 255 bytes

N,i;__int128 n=2,b,o,l[999];P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}main(r){for(P(scanf("%d",&N));r|!b;)for(++n,b=i=N;i--&&b;){for(b=n-1,r=0;~b&1;b/=2)++r;for(o=1;b--;o=o*l[i]%n);for(b=o==1;r--;o=o*o%n)b|=o>n-2;for(o=r=1;++o<n;r&=n%o>0);}printf("%llu",n);}

Recebe entrada baseada em 1 no stdin, por exemplo:

echo "1" | ./millerRabin

Certamente não descobrirá novos valores na sequência tão cedo, mas faz o trabalho. ATUALIZAÇÃO: agora ainda mais lenta!

• Um pouco mais rápido e mais curto, com inspiração na resposta de Neil A ( a^(d*2^r) == (a^d)^(2^r))
• Significativamente mais lento novamente depois de perceber que todas as soluções para esse desafio serão ímpares, portanto não há necessidade de impor explicitamente que apenas verifiquemos números ímpares.
• Agora, usando o GCC __int128, que é mais curto do que unsigned long longenquanto trabalha com números maiores! Também em máquinas little-endian, o printf with %lluainda funciona bem.

Menos minificado

N,i;
__int128 n=2,b,o,l[999];
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}
main(r){
    for(P(scanf("%d",&N));r|!b;)
        for(++n,b=i=N;i--&&b;){
            for(b=n-1,r=0;~b&1;b/=2)++r;
            for(o=1;b--;o=o*l[i]%n);
            for(b=o==1;r--;o=o*o%n)b|=o>n-2;
            for(o=r=1;++o<n;r&=n%o>0);
        }
    printf("%llu",n);
}

Composição (desatualizada)

unsigned long long                  // Use the longest type available
n=2,N,b,i,d,p,o,                    // Globals (mostly share names with question)
l[999];                             // Primes to check (limited to 999, but if you
                                    // want it to be "unlimited", change to -1u)
m(){for(o=1;p--;o=o*l[i]%n);}       // Inefficiently calculates (l[i]^p) mod n

// I cannot possibly take credit for this amazing prime finder;
// See /codegolf//a/5818/8927
P(m){i<N&&P(m<2?l[i++]=n:n%m?m-1:n++);}

main(r){
    for(
        P(scanf("%llu",&N));        // Read & calculate desired number of primes
        r|!b;){                     // While we haven't got an answer:
        n=n+1|1;                    // Advance to next odd number
        for(b=1,i=N;i--&&b;){       // For each prime...
            for(d=n-1,r=0;~d&1;d/=2)++r; // Calculate d and r: d*2^r = n-1
            // Check if there exists any r such that a^(d*2^r) == -1 mod n
            // OR a^d == 1 mod n
            m(p=d);
            for(b=o==1;r--;b|=o==n-1)m(p=d<<r);
            // If neither of these exist, we have proven n is not prime,
            // and the outer loop will keep going (!b)
        }
        // Check if n is actually prime;
        // if it is, the outer loop will keep going (r)
        for(i=r=1;++i<n;r&=n%i!=0);
    }
    printf("%llu",n);               // We found a non-prime; print it & stop.
}

Como mencionado, isso usa entrada baseada em 1. Mas para n = 0, produz 9, que segue a sequência relacionada https://oeis.org/A006945 . Não mais; agora ele fica no 0.

Deve funcionar para todos os n (pelo menos até a saída atingir 2 ^ 64), mas é incrivelmente lento. Eu verifiquei em n = 0, n = 1 e (depois de muita espera), n = 2.

Python 2, 633 465 435 292 282 275 256 247 bytes

Indexado a 0

Questione sua implementação e tente algo novo

A conversão de uma função para um programa salva alguns bytes de alguma forma ...

Se o Python 2 me fornecer uma maneira mais curta de fazer a mesma coisa, vou usar o Python 2. A divisão é por padrão um número inteiro, portanto, é uma maneira mais fácil de dividir por 2 e printnão precisa de parênteses.

n=input()
f=i=3
z={2}
a=lambda:min([i%k for k in range(2,i)])
while n:
 if a():z|={i};n-=1
 i+=2
while f:
 i+=2;d,s,f=~-i,0,a()
 while~d&1:d/=2;s+=1
 for y in z:
  x=y**d%i
  if x-1:
   for _ in[]*s:
    x*=x
    if~x%i<1:break
   else:f=1
print i

Experimente online!

O Python é notoriamente lento em comparação com outros idiomas.

Define um teste de divisão de teste para correção absoluta e aplica repetidamente o teste de Miller-Rabin até que um pseudoprime seja encontrado.

Experimente online!

EDIT : Finalmente jogou a resposta

EDIT : Usado minpara o teste de primalidade da divisão de teste e alterado para a lambda. Menos eficiente, mas mais curto. Também não pude evitar e usei alguns operadores bit a bit (sem diferença de comprimento). Em teoria, deve funcionar (um pouco) mais rápido.

EDIT : Obrigado @Dave. Meu editor me trollou. Eu pensei que estava usando guias, mas estava sendo convertido em 4 espaços. Também passou por praticamente todas as dicas de Python e a aplicou.

EDIT : Comutado para indexação 0, permite-me salvar alguns bytes com a geração dos números primos. Também repensou algumas comparações

EDIT : Usou uma variável para armazenar o resultado dos testes em vez de for/elseinstruções.

EDIT : Moveu a parte lambdainterna da função para eliminar a necessidade de um parâmetro.

EDIT : convertido em um programa para salvar bytes

EDIT : Python 2 me salva bytes! Também não tenho que converter a entrada paraint

Perl + Math :: Prime :: Util, 81 + 27 = 108 bytes

1 until!is_provable_prime(++$\)&&is_strong_pseudoprime($\,2..nth_prime($_));$_=""

Corra com -lpMMath::Prime::Util=:all(penalidade de 27 bytes, ai).

Explicação

Não é apenas o Mathematica que tem um construído para basicamente qualquer coisa. O Perl possui o CPAN, um dos primeiros grandes repositórios de bibliotecas, e que possui uma enorme coleção de soluções prontas para tarefas como esta. Infelizmente, eles não são importados (ou mesmo instalados) por padrão, o que significa que basicamente nunca é uma boa opção usá-los no code-golf , mas quando um deles se encaixa perfeitamente no problema…

Corremos através inteiros consecutivos até encontrar um que não é nobre, e ainda um pseudoprimo forte para todas as bases inteiro de 2 a o n º prime. A opção de linha de comando importa a biblioteca que contém o interno em questão e também define a entrada implícita (para linha por vez; Math::Prime::Utilpossui sua própria biblioteca de bignum interna que não gosta de novas linhas em seus números inteiros). Isso usa o truque Perl padrão de usar$\ (separador de linha de saída) como uma variável, a fim de reduzir as análises estranhas e permitir que a saída seja gerada implicitamente.

Observe que precisamos usar is_provable_primeaqui para solicitar um teste principal determinístico, e não probabilístico. (Especialmente considerando que um teste probabilístico de primeira ordem provavelmente usa Miller-Rabin em primeiro lugar, o que não podemos esperar fornecer resultados confiáveis ​​neste caso!)

Perl + Math :: Prime :: Util, 71 + 17 = 88 bytes, em colaboração com @Dada

1until!is_provable_prime(++$\)&is_strong_pseudoprime$\,2..n‌​th_prime$_}{

Corra com -lpMntheory=:all(penalidade de 17 bytes).

Isso usa alguns truques de golfe Perl que eu não conhecia (aparentemente Math :: Prime :: Util tem uma abreviação!), Conhecia, mas não pensava em usar ( }{para gerar $\implicitamente uma vez, em vez de "$_$\"implicitamente todas as linhas) , ou sabia, mas de alguma forma conseguiu aplicar incorretamente (remover parênteses das chamadas de função). Agradeço a @Dada por me indicar isso. Além disso, é idêntico.