Est-il possible de trouver la valeur approximative de la nième premier?
Est-il une fonction qui renvoie la valeur approximative de la n e premier? Je pense que ce serait quelque chose comme une fonction de comptage inverse des nombres premiers. Par exemple, si je donnais cette fonction 25, elle renverrait un nombre d'environ 100, ou si je donnais cette fonction 1000, elle renverrait un nombre d'environ 8000. Je ne me soucie pas si le nombre retourné est Premier ou pas, mais je ne veux pas qu'il soit rapide (donc pas de générer le premier n prime nombres pour retourner le n th.)
j'aimerais pouvoir générer les premiers nombres premiers n à l'aide d'un tamis ( Eratosthènes ou Atkin ). Par conséquent, l'approximation pour n th l'idéal ne sous-estimerait jamais la valeur de la réelle n TH prime.
(mise à jour: voir ma réponse pour une bonne méthode de recherche de la limite supérieure de la n ème nombre premier.)
7 réponses
le Resserrement des limites:
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);
}
ceux-ci ne devraient jamais être inférieurs à la nth_prime réelle, devraient fonctionner pour n'importe quelle entrée de 64 bits, et être un ordre de grandeur ou plus proche de la formule de Robin donnée plus tôt (ou de la formule compliquée de wimblik à portée limitée). Pour mon usage, j'ai une petite table de nombres premiers un peu plus grand donc peut resserrer la dernière estimation un peu plus. Techniquement, à partir des formules nous pourrions utiliser floor () au lieu de ceil() mais je m'inquiète de précision.
Edit: une autre option pour améliorer cela un peu est de mettre en œuvre de bonnes limites de prime count (par exemple Axler 2014) et de faire une recherche binaire sur eux. Mon code pour cette méthode prend ~10x plus de temps que ci-dessus (toujours en cours d'exécution sous une milliseconde), mais peut réduire le pourcentage d'erreur d'un ordre de grandeur.
si vous voulez un devis pour le nième prime, vous pouvez faire:
- Cipolla 1902 (voir Dusart 1999 à la page 12 ou ce document . Je trouve que trois termes (m=2) plus un troisième facteur de correction d'ordre sont utiles, mais avec plus de termes il oscille trop. La formule indiquée dans le lien Wikipédia est cette formule (avec m=2). L'utilisation des deux termes inverse li ou inverse Riemann R ci-dessous donnera de meilleurs résultats.
- calculez le Dusart 2010 limites supérieure et inférieure et la moyenne des résultats. Pas trop mal, Même si je soupçonne l'utilisation d'un pondéré moyenne fonctionnera mieux que les limites ne sont pas aussi serré.
- li^{-1} (n) comme li(n) est une approximation décente du nombre de nombres premiers, l'inverse est une approximation nth_prime décente. Ceci, et tout le reste, peut être fait assez rapidement comme une recherche binaire sur la fonction.
- li^{-1}(n) + li^{-1}(sqrt(n))/4 de plus près, puisque c'est de se rapprocher de R(n)
- R^{-1} La Fonction R inverse de Riemann est la moyenne la plus proche rapprochement je sais que c'est raisonnable.
enfin, si vous avez une méthode de comptage de prime très rapide telle que L'une des implémentations LMO (il y a maintenant trois implémentations open source), vous pouvez écrire une méthode nth_prime très précise. Le calcul de la prime 10^10 peut être fait en quelques millisecondes, et la prime 10^13 en quelques secondes (sur une machine rapide moderne). Les approximations sont extrêmement rapides à toutes les tailles et fonctionnent pour des nombres beaucoup plus grands, mais tout le monde a une idée différente de ce "grand" signifie.
Merci pour toutes ces réponses. Je me doutais qu'il y avait quelque chose d'assez simple comme ça, mais je n'ai pas pu le trouver à l'époque. J'ai fait un peu plus de recherches aussi.
Comme je le veux pour un tamis pour générer le premier n nombres premiers, je veux le rapprochement être supérieure ou égale à la n e premier. (Par conséquent, je veux la limite supérieure de la n th nombre premier.)
Wikipedia donne la limite supérieure suivante pour n >= 6
p_n <= n log n + n log log n (1)
où p_n est le n e premier, et log est le logarithme naturel. C'est un bon début, mais il peut surestimer par une quantité non négligeable. Cet article dans Les Mathématiques de niveau Collégial Journal donne un resserrement de la limite supérieure pour l' n >= 7022
p_n <= n log n + n (log log n - 0.9385) (2)
il s'agit d'une limite beaucoup plus serrée que le tableau suivant montre
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
j'ai mis en place mon n e premier approximation de la fonction pour utiliser la seconde approximation pour n >= 7022 , la première approximation pour 6 <= n < 7022 , et un tableau de recherche pour les 5 premiers nombres premiers.
(bien que la première méthode n'est pas une limite très serrée, surtout pour la gamme où j'utilise il, Je ne suis pas concerné car je veux cela pour un tamis, et un tamis de plus petits nombres est computationnellement bon marché.)
théorème du nombre premier donne un nombre de nombres premiers en dessous d'une valeur seuil, de sorte qu'il pourrait être utilisé pour donner une valeur approximative pour le nième premier.
Mon Meilleur Premier(n) Estimation
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))))))
voici ma plus récente formule expérimentale.
btw. Le premier de dix trillionèmes est 323,780,508,946,331 cette formule fonctionne assez bien à cette échelle pas sûr si elle continue à se rapprocher de 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)))))))
une mise en œuvre efficace n'est probablement pas possible avec un tamis. Pensez à ce qui se passerait si vous vouliez avoir les 10.000 premiers nombres premiers. Vous devriez probablement faire un tamis sur une énorme quantité plus grande de nombres.
Votre propre implémentation cette question et ma réponse sont de bons moyens à mettre en œuvre sans savoir le rapp. valeur d'un prime
pour compléter la limite supérieure de Dana J cette formule devrait vous donner une bonne limite inférieure.
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;