Existe uma maneira de encontrar o valor aproximado do nobre enésimo?
https://stackoverflow.com/questions/1042717
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Existe uma função que irá retornar o valor aproximado do n th nobre? Eu acho que isso seria algo como uma função de contagem de números primos inversa aproximada. Por exemplo, se eu dei esta função 25 retornaria um número em torno de 100, ou se eu dei esta função 1000 que iria retornar um número em torno de 8000. Eu não me importo se o número retornado é primo ou não, mas eu quero que ele seja rápido (por isso não gerar o primeiro n números primos para retornar o n th.)
Gostaria que este para que eu possa gerar a primeira n números primos usando uma peneira ( Eratóstenes ou Atkin ). Portanto, a aproximação para n th o ideal nunca subestimar o valor do real n th prime.
(Update: veja minha resposta para um bom método de encontrar o limite superior do n th número primo.)
Solução
limites mais apertados:
static const unsigned short primes_small[] = {0,2,3,5,7,11};
static unsigned long nth_prime_upper(unsigned long n) {
double fn = (double) n;
double flogn, flog2n, upper;
if (n < 6) return primes_small[n];
flogn = log(n);
flog2n = log(flogn);
if (n >= 688383) /* Dusart 2010 page 2 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn));
else if (n >= 178974) /* Dusart 2010 page 7 */
upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn));
else if (n >= 39017) /* Dusart 1999 page 14 */
upper = fn * (flogn + flog2n - 0.9484);
else /* Modified from Robin 1983 for 6-39016 _only_ */
upper = fn * ( flogn + 0.6000 * flog2n );
if (upper >= (double) ULONG_MAX) {
/* Adjust this as needed for your type and exception method */
if (n <= 425656284035217743UL) return 18446744073709551557UL;
fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1);
}
return (unsigned long) ceil(upper);
}
Estes não deve nunca ser inferior ao nth_prime real, deve funcionar para qualquer entrada de 64 bits, e ser uma ordem de magnitude ou mais perto do que a fórmula de Robin dada anteriormente (ou complicada fórmula gama-limitada da Wimblik). Para meu uso eu tenho uma tabela pequenos primos um pouco maior para que possa apertar a última estimativa um pouco mais. Tecnicamente a partir das fórmulas poderíamos usar andar () em vez de ceil (), mas eu me preocupo com precisão.
Edit: Outra opção para melhorar isso um pouco é a implementação de boas limites nobre contagem (por exemplo Axler 2014) e fazer uma busca binária sobre eles. Meu código para este método leva ~ 10 vezes mais tempo do que o anterior (ainda funcionando em menos de um milésimo de segundo), mas pode reduzir a percentagem de erro por uma ordem de magnitude.
Se você quiser uma estimativa para o primeiro-n, você pode fazer:
- Cipolla 1902 (ver Dusart 1999 página 12 ou este papel . Acho três termos (m = 2), além de um terceiro factor de correcção para ser útil, mas com mais termos que oscila muito. a fórmula apresentada na ligação Wikipedia é esta fórmula (com m = 2). Usando os dois prazo inversa li ou inversa Riemann R seguir lhe dará melhores resultados.
- Calcule o Dusart 2010 limites superior e inferior e média dos resultados. Não é tão ruim, embora eu suspeite usando uma média ponderada irá funcionar melhor como os limites não são igualmente apertado.
- li ^ {- 1} (n) Uma vez que li (n) é uma aproximação decente para a contagem privilegiada, o inverso é uma aproximação nth_prime decente. Este, e todo o resto, pode ser feito com bastante rapidez como uma busca binária sobre a função.
- li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Closer, uma vez que este está se aproximando de R (n)
- R ^. {- 1} O inverso função Riemann R está à aproximação média mais próximo que eu sei que é razoável
Por último, se você tem um método de contagem muito rápido privilegiada como uma das implementações OVM (há três implementações de código aberto agora), você pode escrever um método nth_prime rápido e preciso. Calculando a 10 ^ 10 nobre pode ser feito em poucos milissegundos, ea 10 ^ 13 em alguns segundos (em uma máquina rápida moderna). As aproximações são extremamente rápidos em todos os tamanhos e de trabalho para números muito maiores, mas todo mundo tem uma idéia diferente do que significa "grandes".
Outras dicas
Obrigado por todas essas respostas. Eu suspeitava que havia algo bastante simples assim, mas eu não poderia encontrá-lo no momento. Eu tenho feito um pouco mais investigação também.
Como eu quero-o para um peneira para gerar a primeira n números primos, eu quero que a aproximação seja maior ou igual à n th prime. (Portanto, quero que o limite superior da n th número primo.)
Wikipedia profere o limite superior para n >= 6
p_n <= n log n + n log log n (1)
onde p_n é a n th privilegiada, e log é o logaritmo natural. Este é um bom começo, mas pode superestimar por uma quantidade não negligenciável. Este artigo em O Colégio Matemática Jornal dá um apertado limite superior para n >= 7022
p_n <= n log n + n (log log n - 0.9385) (2)
Este é um muito mais apertado ligado como mostra a tabela seguinte
n p_n approx 1 error% approx 2 error%
1 2
10 29 31 6.90
100 541 613 13.31
1000 7919 8840 11.63
10000 104729 114306 9.14 104921 0.18
100000 1299709 1395639 7.38 1301789 0.16
1000000 15485863 16441302 6.17 15502802 0.11
10000000 179424673 188980382 5.33 179595382 0.10
Eu implementei o meu n th função primordial aproximação usar a segunda aproximação para n >= 7022, a primeira aproximação para 6 <= n < 7022, e uma pesquisa de matriz para os 5 primeiros números primos.
(Embora o primeiro método não é muito apertado obrigado, especialmente para a faixa onde eu usá-lo, eu não estou preocupado quanto eu quero isso por uma peneira, e uma peneira de números menores é computacionalmente barato.)
teorema do número primo dá um número de primos abaixo de um valor limite, assim que poderia ser usado para dar um valor aproximado para o primeiro-enésimo.
Como uma estimativa grosseira, você pode usar n * ln (n) como uma aproximação para o número primo enésimo. Há um método muito mais complexa, mas mais precisos, cujos detalhes você pode encontrar na Wikipedia aqui .
My Best Prime (n) Estimativa
1/2*(8-8.7*n-n^2+
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2))))))
Aqui está a minha mais recente fórmula mais experimental.
btw. O primeiro-trilionésimo dez é 323,780,508,946,331 esta fórmula funciona muito bem nessa escala não tenho certeza se ele continua a chegar mais perto do que n*ln(n)+n*(ln(ln(n))-0.9385).
1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))*
ln(ln((n*ln(8*n))/ln(n))/ln(2)))))))
Uma execução eficiente provavelmente não é possível com uma peneira. Pense o que aconteceria se você quiser ter os primeiros 10.000 números primos. Você provavelmente teria que fazer uma peneira sobre uma enorme quantidade maior de números.
O seu próprio implentation em esta questão e my resposta são boas maneiras de implementar isso sem saber o aprox. valor de uma nobre
Para complementar Superior de Dana J obrigado esta fórmula deve dar-lhe um bom limite inferior.
P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;
