I have found in june 1997 new and
numerous strange algorithms in order to compute the parity of various
arithmetic functions. These algorithms have allowed me to compute in
particular the parity of the number of prime numbers below or equal
to n for n > 10^20, to check known values and
to forecast the parity for new values of n.
The
complexity of the algorithm is in O(n1/2*logn)
with a storage space in O(1) !
But since May 2018 my new optimized algorithm is in practice now in O(n^0.46) only about.
You can find below some of the results of calculations already performed ppi (n) = pi(n) [mod 2], especially for 10^20 < n < 10^30. The original algorithm presented in the article below has been optimized much and use a GPU (May-June 2012) and now with openMp on multi-core cpu.
The computed
parities confirm the known pi(n) including pi(10^24)
calculated by two different methods (conditional
RH
and unconditional RH),
and those calculated by
Primecount (now <= 10^29).
With my modest PC (CPU I7
3770k, using a single core) and a graphics card (GTX 680) the
calculation of ppi(10^24) = 0 only takes about 3 hours (63,000 hours
for the complete calculation by analytical algorithm with the
implementation of David J. Platt), and ppi(5*10^28) = 1 in about 39
days!
It seems possible to obtain a combined algorithm
using parity of pi(n) for a faster analytical algorithm, because
acceptable error pass from +/- 0.5 to +/- 1.5. Unfortunately, the
gain is only 3%, because the error curve is not very influenced by
this information (email with David J. Platt).
n |
pi(n) (see references) |
ppi(n) |
|---|---|---|
10^20 |
2 220 819 602 560 918 840 |
0 |
2*10^20 |
4 374 267 703 076 959 271 |
1 |
3*10^20 |
6 503 696 293 016 202 398 |
0 |
5*10^20 |
10 720 710 117 789 005 897 |
1 |
10^21 |
21 127 269 486 018 731 928 |
0 |
2*10^21 |
41 644 391 885 053 857 293 |
1 |
3*10^21 |
61 943 374 158 983 520 871 |
1 |
5*10^21 |
102 160 925 813 497 229 402 |
0 |
10^22 |
201 467 286 689 315 906 290 |
0 |
2*10^22 |
397 382 840 070 993 192 736 |
0 |
3*10^22 |
591 308 502 828 791 273 105 |
1 |
10^(45/2) |
622 647 095 301 172 021 671 |
1 |
5*10^22 |
975 686 344 403 186 930 556 |
0 |
10^23 |
1 925 320 391 606 803 968 923 |
1 |
2*10^23 |
3 799 909 692 561 409 118 056 |
0 |
3*10^23 |
5 656 273 632 246 727 014 194 |
0 |
10^(47/2) |
5 956 317 545 928 249 075 039 |
1 |
5*10^23 |
9 337 160 048 750 070 138 549 |
1 |
10^24 |
18 435 599 767 349 200 867 866 |
0 |
2*10^24 |
36 405 815 887 319 744 845 222 |
0 |
3*10^24 |
54 208 488 048 698 205 810 926 |
0 |
10^(49/2) |
57 086 403 558 149 290 301 868 |
0 |
5*10^24 |
89 520 881 254 995 834 381 918 |
0 |
10^25 |
176 846 309 399 143 769 411 680 |
0 |
2*10^25 |
349 408 129 236 754 050 832 016 |
0 |
3*10^25 |
520 424 490 500 067 689 175 912 |
0 |
10^(51/2) |
548 074 549 053 620 897 173 483 |
1 |
5*10^25 |
859 752 970 040 850 921 856 285 |
1 |
10^26 |
1 699 246 750 872 437 141 327 603 |
1 |
2*10^26 |
3 358 919 076 009 897 107 088 448 |
0 |
3*10^26 |
5 004 291 029 389 141 305 029 065 |
1 |
10^(53/2) |
5 270 353 162 790 246 525 701 178 |
0 |
5*10^26 |
8 269 995 000 656 166 110 637 634 |
0 |
10^27 |
16 352 460 426 841 680 446 427 399 |
1 |
2*10^27 |
? |
0 |
3*10^27 |
? |
1 |
10^(55/2) |
? |
0 |
5*10^27 |
? |
1 |
10^28 |
157 589 269 275 973 410 412 739 598 |
0 |
2*10^28 |
? |
1 |
3*10^28 |
? |
1 |
10^(57/2) |
? |
0 |
5*10^28 |
? |
1 |
10^29 |
1 520 698 109 714 272 166 094 258 063 |
1 |
10^(59/2) |
? |
1 |
10^30 |
? |
1 |
10^31 |
? |
1 |
|
|
|
2^70 |
24 855 455 363 362 685 793 |
1 |
2^71 |
48 995 571 600 129 458 363 |
1 |
2^72 |
96 601 075 195 075 186 855 |
1 |
2^73 |
190 499 823 401 327 905 601 |
1 |
2^74 |
375 744 164 937 699 609 596 |
0 |
2^75 |
741 263 521 140 740 113 483 |
1 |
2^76 |
1 462 626 667 154 509 638 735 |
1 |
2^77 |
2 886 507 381 056 867 953 916 |
0 |
2^78 |
5 697 549 648 954 257 752 872 |
0 |
2^79 |
11 248 065 615 133 675 809 379 |
1 |
2^80 |
22 209 558 889 635 384 205 844 |
0 |
2^81 |
43 860 397 052 947 409 356 492 |
0 |
2^82 |
86 631 124 695 994 360 074 872 |
0 |
2^83 |
171 136 408 646 923 240 987 028 |
0 |
2^84 |
338 124 238 545 210 097 236 684 |
0 |
2^85 |
668 150 111 666 935 905 701 562 |
0 |
2^86 |
1 320 486 952 377 516 565 496 055 |
1 |
2^87 |
2 610 087 356 951 889 016 077 639 |
1 |
2^88 |
5 159 830 247 726 102 115 466 054 |
0 |
2^89 |
10 201 730 804 263 125 133 012 340 |
0 |
2^90 |
20 172 933 541 156 002 700 963 336 |
0 |
2^91 |
39 895 115 987 049 029 184 882 256 |
0 |
2^92 |
78 908 656 317 357 166 866 404 346 |
0 |
2^93 |
? |
1 |
2^94 |
? |
1 |
2^95 |
? |
1 |
2^96 |
? |
0 |
|
|
|
3^42 |
2 425 147 728 864 084 536 |
0 |
3^43 |
7 102 411 822 168 379 213 |
1 |
3^44 |
20 812 271 380 294 281 933 |
1 |
3^45 |
61 019 376 449 131 370 651 |
1 |
3^46 |
178 994 690 348 530 706 578 |
0 |
3^47 |
525 323 427 853 694 627 277 |
1 |
3^48 |
1 542 475 966 907 198 337 529 |
1 |
3^49 |
4 531 128 922 967 558 738 689 |
1 |
3^50 |
13 316 273 461 190 963 223 875 |
1 |
3^51 |
39 150 710 883 093 754 060 551 |
1 |
3^52 |
115 151 633 042 013 618 799 881 |
1 |
3^53 |
338 818 652 814 145 152 283 494 |
0 |
3^54 |
997 297 950 290 481 689 064 741 |
1 |
3^55 |
2 936 546 944 395 836 315 922 954 |
0 |
3^56 |
8 649 633 532 395 633 037 360 942 |
0 |
3^57 |
? |
0 |
3^58 |
? |
0 |
3^59 |
? |
1 |
3^60 |
? |
0 |
|
|
|
5^29 |
4 080 206 964 520 522 386 |
0 |
5^30 |
19 705 939 422 430 380 037 |
1 |
5^31 |
95 283 357 078 617 397 618 |
0 |
5^32 |
461 221 032 128 956 299 315 |
1 |
5^33 |
2 234 825 376 457 832 280 255 |
1 |
5^34 |
10 839 107 779 293 321 780 447 |
1 |
5^35 |
52 617 999 911 514 169 104 251 |
1 |
5^36 |
255 648 665 761 416 275 750 497 |
1 |
5^37 |
1 243 084 170 062 066 966 027 721 |
1 |
5^38 |
6 049 039 902 920 458 517 148 309 |
1 |
5^39 |
? |
0 |
5^40 |
? |
0 |
|
|
|
|
|
|
We can also notice that ppi(n)+ppi(n-1)=1
[mod 2] if and only if n is prime, which can allow to test the
primality of n.
But unfortunately this test isn't very
efficient (it is in O(n1/2*logn)) and now in
O(n^0.46).
Parpius.pdf : original paper (March 1998)
ppidemo.gp : pari-gp
demo of the original algorithm without optimizations.
use :
read("ppidemo.gp")
References :
June 1996 : (New
values of pi(x) : M. Deleglise et J. Rivat)
November 2000
: values of pi (n) found by Xavier
Gourdon confirm parities planned (December 1997). See explanations on
its website
September
2011 : Thesis
from David J. Platt - Chapter 6 Computing pi(x)
Analytically
March 2012 : David J. Platt - Computing
pi(x) Analytically
The PrimePages by Chris K. Caldwell
: How many primes are
there ?
Tables
of values of pi(x)
from Tomás Oliveira e Silva
From Douglas B. Staple :
http://www.mersenneforum.org/showthread.php?t=19863
From
Kim Walisch and David Baugh :
http://www.mersenneforum.org/showthread.php?t=20473
Primecount
records :
https://github.com/kimwalisch/primecount/blob/master/doc/Records.md
March
6 2015 : Douglas B. Staple : The
combinatorial algorithm for computing pi(x)
March 11 2015,
November 4 2015, June 13 2021, July 9 2021, March 3 2022 : emails
from David Baugh
Integer Sequences (OEIS) : A071986,
A219071, A219097,
A219098, A219189,
A055729, A055730
Created by Henri Lifchitz : September, 13 1998, last modification: December, 10 2022.
