C'è un modo per trovare il valore approssimativo dell'ennesimo primo?

Question

Esiste una funzione che restituirà il valore approssimativo del n primo? Penso che questo sarebbe qualcosa come una funzione di conteggio primo inversa approssimativa. Ad esempio, se avessi dato questa funzione 25, avrebbe restituito un numero attorno a 100, o se avessi dato questa funzione 1000, avrebbe restituito un numero intorno a 8000. Non mi importa se il numero restituito è primo o no, ma voglio essere veloce (quindi non generare i primi n numeri primi per restituire il n th.)

Vorrei questo in modo da poter generare i primi n numeri primi usando un setaccio ( Eratosthenes o Atkin ). Pertanto, l'approssimazione di n idealmente non sottovaluterebbe mai il valore dell'attuale n primo.

(Aggiornamento: vedi la mia risposta per un buon metodo per trovare il limite superiore del n numero primo.)

Answer 1

Limiti più stretti:

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);
}

Questi non dovrebbero mai essere inferiori all'effettivo nth_prime, dovrebbero funzionare per qualsiasi input a 64 bit ed essere di un ordine di grandezza o più vicini alla formula di Robin data in precedenza (o alla complicata formula limitata da Wimblik). Per il mio uso ho una tabella di numeri primi leggermente più grande, quindi posso stringere un po 'di più l'ultima stima. Tecnicamente dalle formule potremmo usare floor () invece di ceil () ma mi preoccupo della precisione.

Modifica: un'altra opzione per migliorare un po 'è implementare buoni limiti di conteggio primi (ad es. Axler 2014) e fare una ricerca binaria su di essi. Il mio codice per questo metodo richiede circa 10 volte più tempo di quanto sopra (ancora in esecuzione in meno di un millisecondo), ma può ridurre la percentuale di errore di un ordine di grandezza.

Se vuoi una stima per l'ennesimo numero primo, puoi fare:

• Cipolla 1902 (vedi Dusart 1999 pagina 12 o questo documento . Trovo tre termini (m = 2) più un fattore di correzione del terzo ordine per essere utile, ma con più termini oscilla troppo. La formula mostrata nel link Wikipedia è questa formula (con m = 2). Usando l'inverso di due termini o viceversa Riemann R di seguito fornirà risultati migliori.
• Calcola i limiti superiore e inferiore di Dusart 2010 e calcola la media dei risultati. Non male, anche se sospetto che l'uso di una media ponderata funzionerà meglio poiché i limiti non sono ugualmente stretti.
• li ^ {- 1} (n) Poiché li (n) è un'approssimazione decente al conteggio dei primi, l'inverso è un'approssimazione decente di nth_prime. Questo, e tutto il resto, può essere fatto abbastanza rapidamente come una ricerca binaria sulla funzione.
• li ^ {- 1} (n) + li ^ {- 1} (sqrt (n)) / 4 Più vicino, poiché questo si avvicina a R (n)
• R ^ {- 1} La funzione inversa di Riemann R è l'approssimazione media più vicina che conosco sia ragionevole.

Infine, se hai un metodo di conteggio primo molto veloce come una delle implementazioni LMO (ora ci sono tre implementazioni open source), puoi scrivere un metodo nth_prime preciso e veloce. Il calcolo del 10 ^ 10esimo primo può essere eseguito in pochi millisecondi e il 10 ^ 13esimo in un paio di secondi (su una moderna macchina veloce). Le approssimazioni sono estremamente veloci in tutte le dimensioni e funzionano per numeri molto più grandi, ma ognuno ha un'idea diversa di cosa & Quot; large & Quot; significa.

Answer 2

Grazie per tutte queste risposte. Sospettavo che esistesse qualcosa di abbastanza semplice, ma non riuscivo a trovarlo in quel momento. Ho fatto anche un po 'più di ricerca.

Come voglio che un setaccio generi il primo n numeri primi, voglio che l'approssimazione sia maggiore o uguale al n primo numero. (Pertanto, desidero il limite superiore del n numero primo.)

Wikipedia indica il seguente limite superiore per n >= 6

p_n <= n log n + n log log n   (1)

dove p_n è il n primo e log è il logaritmo naturale. Questo è un buon inizio, ma può sopravvalutare di un importo non trascurabile. Questo articolo in The College Mathematics Journal offre un limite superiore più stretto per n >= 7022

p_n <= n log n + n (log log n - 0.9385)   (2)

Questo è un limite molto più stretto come mostra la seguente tabella

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

Ho implementato la mia n funzione di approssimazione primaria per utilizzare la seconda approssimazione per 6 <= n < 7022, la prima approssimazione per <=> e una ricerca di array per i primi 5 numeri primi.

(Anche se il primo metodo non è un limite molto stretto, specialmente per l'intervallo in cui lo uso, non mi preoccupo perché lo voglio per un setaccio, e un setaccio di numeri più piccoli è computazionalmente economico.)

Answer 3

Teorema dei numeri primi fornisce un numero di numeri primi al di sotto di un valore di soglia, quindi potrebbe essere usato per dare un valore approssimativo per l'ennesimo numero primo.

Answer 4

Come stima approssimativa, puoi usare n * ln (n) come approssimazione per l'ennesimo numero primo. Esiste un metodo molto più complesso, ma più accurato, i cui dettagli sono disponibili su Wikipedia qui .

Answer 5

Il mio miglior preventivo Prime (n)

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))))))

Ecco la mia formula sperimentale più recente. btw. Il decimo trilione primo è 323,780,508,946,331 questa formula funziona abbastanza bene su quella scala, non sono sicuro che continui ad avvicinarsi di 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)))))))

Answer 6

Un'implementazione efficiente non è probabilmente possibile con un setaccio. Pensa cosa succederebbe se vuoi avere i primi 10.000 numeri primi. Probabilmente dovresti fare un setaccio su una quantità enorme di numeri.

La tua propria impianto in questa domanda e la mia risposta sono buoni modi per implementarlo senza conoscere l'appr. valore di un primo

Answer 7

Per integrare il limite superiore di Dana J questa formula dovrebbe darti un limite inferiore buono.

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;