[math-fun] the impressive speed of primecount
Hello, there is a little jewel of program called primecount (easy to find on Windows, mac or linux). It counts the primes. Here is a table of results (see below), from 10^1 to 10^20 with primecount and mathematica : mathematica stops giving answers after 10^14 and takes 26.2656 seconds to find PrimePi[10^14] when primecount takes only : 0.069 seconds (!). This is 431 times faster. I do not mention Maple for decency, it is too slow by far, Pari-Gp is not bad but limited in range too. The -g option stands for the Gourdon method (apparently the fastest). You can download the program here : https://github.com/kimwalisch/primecount it comes with a short but very useful explanation. See for yourself : results are astonishing. The recent record result of Pi(10^27) is mainly due to this program. See http://oeis.org/A006880 for more details. Last thing : the program is 1.52 megs in size and takes all the cpus/threads you may have on one machine automatically. primecount -g 10^1 --time; 4 seconds: 0.000 primecount -g 10^2 --time; 25 seconds: 0.000 primecount -g 10^3 --time; 168 seconds: 0.000 primecount -g 10^4 --time; 1229 seconds: 0.000 primecount -g 10^5 --time; 9592 seconds: 0.000 primecount -g 10^6 --time; 78498 seconds: 0.000 primecount -g 10^7 --time; 664579 seconds: 0.000 primecount -g 10^8 --time; 5761455 seconds: 0.001 primecount -g 10^9 --time; 50847534 seconds: 0.001 primecount -g 10^10 --time; 455052511 seconds: 0.003 primecount -g 10^11 --time; 4118054813 seconds: 0.007 primecount -g 10^12 --time; 37607912018 seconds: 0.015 primecount -g 10^13 --time; 346065536839 seconds: 0.026 primecount -g 10^14 --time; 3204941750802 seconds: 0.069 primecount -g 10^15 --time; 29844570422669 seconds: 0.204 primecount -g 10^16 --time; 279238341033925 seconds: 0.647 primecount -g 10^17 --time; 2623557157654233 seconds: 2.276 primecount -g 10^18 --time; 24739954287740860 seconds: 8.334 primecount -g 10^19 --time; 234057667276344607 seconds: 35.579 primecount -g 10^20 --time; 2220819602560918840 seconds: 155.561 Timing[PrimePi[10^1]] {0., 4} Timing[PrimePi[10^2]] {0., 25} Timing[PrimePi[10^3]] {0., 168} Timing[PrimePi[10^4]] {0., 1229} Timing[PrimePi[10^5]] {0., 9592} Timing[PrimePi[10^6]] {0., 78498} Timing[PrimePi[10^7]] {0., 664579} Timing[PrimePi[10^8]] {0., 5761455} Timing[PrimePi[10^9]] {0., 50847534} Timing[PrimePi[10^10]] {0.046875, 455052511} Timing[PrimePi[10^11]] {0.1875, 4118054813} Timing[PrimePi[10^12]] {1.03125, 37607912018} Timing[PrimePi[10^13]] {5.34375, 346065536839} Timing[PrimePi[10^14]] {26.2656, 3204941750802} Have fun !, Simon Plouffe
* Simon Plouffe <simon.plouffe@gmail.com> [Nov 11. 2019 17:13]:
Hello,
 there is a little jewel of program called primecount (easy to find on Windows, mac or linux).
[...]
Last thing : the program is 1.52 megs in size and takes all the cpus/threads you may have on one machine automatically.
Now THERE is my reason to buy that AMD CPU with 64 physical cores!
[...] primecount -g 10^20 --time; 2220819602560918840 seconds: 155.561
Impressive indeed.
[...]
Best regards, jj
Try something less likely to be cached. In[359]:= PrimePi[98765432101234] // Timing Out[359]= {38.587819, 3166636765112} But still PrimePi[987654321012345] // Timing PrimePi::largp: Argument 987654321012345 in PrimePi[987654321012345] is too large for this implementation. —rwg On 2019-11-11 08:17, Joerg Arndt wrote:
* Simon Plouffe <simon.plouffe@gmail.com> [Nov 11. 2019 17:13]:
Hello,
there is a little jewel of program called primecount (easy to find on Windows, mac or linux).
[...]
Last thing : the program is 1.52 megs in size and takes all the cpus/threads you may have on one machine automatically.
Now THERE is my reason to buy that AMD CPU with 64 physical cores!
[...] primecount -g 10^20 --time; 2220819602560918840 seconds: 155.561
Impressive indeed.
[...]
Best regards, jj
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Hello Math-Fun, Extend S so that the cumultive sum P = a(1) +/- a(2) +/- ... +/- a(k) is always a palindrome. But remember: 1) S must be the lexicographically earliest seq of distinct terms with this propety and a(1) = 1; 2) Add the odd terms and subtract the even ones. + - + - + + - - + + - - + - + - S = 1, 3, 2, 5, 4, 19, 11, 22, 6, 17, 33, 44, 8, 41, 36, 25, 24, ... P = 1 4 2 7 3 22 33 11 5 22 55 11 3 44 8 33 9 ... Is S a permutation of the integers > 0? I guess yes -- but can't prove. (as always, forgive my errors) Best, É.
Jean-Marc Falcoz has computed 50 000 terms -- the graph is mysterious and fascinating. I will submit that to the OEIS tonight (Belgian time). No negative palindromes were allowed (the smallest being 0) and indeed, this looks like a permutation of the integers > 0. Best, É.
Le 15 nov. 2019 à 19:33, Éric Angelini <bk263401@skynet.be> a écrit :
Hello Math-Fun, Extend S so that the cumultive sum P = a(1) +/- a(2) +/- ... +/- a(k) is always a palindrome. But remember: 1) S must be the lexicographically earliest seq of distinct terms with this propety and a(1) = 1; 2) Add the odd terms and subtract the even ones. + - + - + + - - + + - - + - + - S = 1, 3, 2, 5, 4, 19, 11, 22, 6, 17, 33, 44, 8, 41, 36, 25, 24, ... P = 1 4 2 7 3 22 33 11 5 22 55 11 3 44 8 33 9 ...
Is S a permutation of the integers > 0? I guess yes -- but can't prove. (as always, forgive my errors) Best, É.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
EA: "the graph is mysterious and fascinating" Here's one in blue and red: http://chesswanks.com/num/PalindromicFantasy.png
participants (6)
-
Hans Havermann -
Joerg Arndt -
rwg -
Simon Plouffe -
Éric Angelini -
Éric Angelini