20190510, 06:37  #12 
Romulan Interpreter
"name field"
Jun 2011
Thailand
3^{5}×41 Posts 
eulerphi()
Last fiddled with by LaurV on 20190510 at 06:38 
20190510, 06:56  #13 
Apr 2019
11001101_{2} Posts 

20190510, 08:21  #14  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
5×31×73 Posts 
Quote:


20190510, 19:39  #15 
∂^{2}ω=0
Sep 2002
Repรบblica de California
2^{4}·733 Posts 
If one's aim is to support e.g. get_nth_prime(n) or "quickly enumerate all primes up to some limit"style functionality, the way my code does this is:
1. Use a simple sieve to generate candidates not divisible by really small primes; 2. Feed surviving candidates  batches of 48 here tend to allow for good hiding of integer MUL latencies  to a base2 Fermat PRP routine; 3. Do a fast lookup of the surviving candidates in a precomputed table of known base2 Fermat pseudoprimes; 4. If a candidate does not appear in said table, it's prime. So there's still a table involved, but it's *much* smaller than any needed for explicit prime storage. Here is the associated commentary in my code: Code:
/* There are 10403 ( = 101*103) base2 Fermat pseudoprimes < 2^32. [Cf. http://home.att.net/~numericana/answer/pseudo.htm#pseudoprime for this and other tables related to the pseudoprimes of various types]. We split these into 2 subsets  [1] those divisible by 3 or 5 and [2] those not. Some General Observations: The largest base2 Fermat pseudoprime < 2^32 is 4294901761 = 193*22253377 = 2^32  2^16 + 1, which is reminiscent of the 64bit (genuine) prime 2^64  2^32 + 1 used by Nick CraigWood in his pureinteger Mersennemod DWTbased convolution code. The only twin pseudoprimes < 2^32 are 4369 (which = 17*257, the product of the Fermat primes F2 and F3) and 4371. Similarly to F2*F3, the product F3*F4 = 16843009 is a base2 Fermat pseudoprime. Other products of Fermat primes are "near pseudoprimes" in the sense that their base2 Fermat residue is a power of 2, e.g. for n=17*65537, 2^(n1)%n = 2^16. The largest (gap/2) between adjacent pseudoprimes (either in the merged length10403 table or the f2psp[] one below  the number is set by two adjacent elements of the latter  is 4199775, requiring 3 bytes to store, so no significant compactification via a difference table is possible, as there is for the primes. */ 
20190510, 21:47  #16 
Jan 2008
France
2·281 Posts 
Given the speed computers have reached, I have stopped using any list, and I just run Kim Walisch primesieve. It can sieve up to 10^10 in less than 2s.

20190510, 23:16  #17  
∂^{2}ω=0
Sep 2002
Repรบblica de California
2^{4}×733 Posts 
Quote:


20190511, 06:53  #18  
Jan 2008
France
2×281 Posts 
Quote:
https://github.com/kimwalisch/primes.../ALGORITHMS.md 

20190511, 09:00  #19  
Apr 2019
5×41 Posts 
Quote:
It seems like a fermat test would slow things down a bit though? What does the complexity look like for a good powm algorithm? I've mostly just played a little with GMP so far, and started picking up a bit of PARI lately. Quote:
One thing I have started wondering about, is if there is some way to further compact a very large wheel, maybe some sort of recursive implementation could use smaller wheels to save space in the larger one? Not sure if that makes any sense, still thinking it over... 

20190511, 09:40  #20  
Apr 2019
5·41 Posts 
Quote:
Playing around some more in PARI, I decided to write a pseudoprime counting function: Code:
fermat_test(b,p)=Mod(b,p)^(p1)==1 pseudoprimepi(b,limit)={ my(prev=4,count=0); forprime(p=3,limit,forstep(n=prev,p1,2,if(fermat_test(b,n),count++));prev=p+2); count } Code:
? pseudoprimepi(2,2^32) %70 = 10403 ? ## *** last result computed in 32min, 5,043 ms. Note: it skips even numbers so the count is not technically correct if counting base 3 for example. Here's a version that should count all of them, but is slightly slower: Code:
pseudoprimepi(b,limit)={ my(prev=4,count=0); forprime(p=3,limit,for(n=prev,p1,if(gcd(b,n)==1&&fermat_test(b,n),count++));prev=p+1); count } 

20190512, 13:25  #21  
Feb 2017
Nowhere
2·11·263 Posts 
Quote:
The paper Carmichael numbers and pseudoprimes may be instructive. In particular, by the result labelled 2.1, both 17 and 257 are == 1 (mod 16) and both divide 2^16  1, so their product is automatically 2psp. Statistics for various types of pseudoprimes up to 10^{k} for k = 9 to 14 are compiled here. Tables of base2 pseudoprimes up to 2^{64} (list of numbers, list of factorizations, annotated list with factorizations and indicating Carmichael numbers, all compressed, .txt.bz2) may be downloaded from here. 

20190512, 19:26  #22 
∂^{2}ω=0
Sep 2002
Repรบblica de California
2^{4}·733 Posts 
FYI, It seems the pseudoprime page I linked in my code comment has moved to http://www.numericana.com/answer/pseudo.htm#pseudoprime .

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Intel Compute Stick (1GB RAM/8GB storage w/ Ubuntu 64bit)  ssybesma  Hardware  4  20190310 06:19 
Prime gaps and storage  HellGauss  Computer Science & Computational Number Theory  18  20151116 14:21 
feature request: P1 file storage on server  tha  Software  13  20140304 15:09 
Two (unrelated) questions about storage and hypert  Dubslow  Hardware  11  20110730 06:08 
A Lot Of Storage  moo  Hardware  0  20051123 03:16 