Parity of Pi(n)


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) ! 
You can find below some of the results of calculations already performed ppi (n) = pi (n) mod 2, especially for 10^20 < n < 7*10^28. The original algorithm presented in the article below has been optimized much and use a GPU (May-June 2012).

The computed parities confirm the known pi(n) including pi (10^24) calculated by two different methods (conditional RH and unconditional RH).
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).


pi(n)  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
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
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
5*10^24 ? 0
10^25 176 846 309 399 143 769 411 680 0
2*10^25 ? 0
3*10^25 ? 0
5*10^25 ? 1
10^26 1 699 246 750 872 437 141 327 603
1
2*10^26 ? 0
3*10^26 ? 1
5*10^26 ? 0
10^27 ? 1
2*10^27 ? 0
3*10^27 ? 1
5*10^27 ? 1
10^28 ? 0
2*10^28 ? ?
3*10^28 ? ?
5*10^28 ? 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 ? 1
2^88 ? 0
2^89 ? 0
2^90 ? 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 ? 0
3^54 ? 1
3^55 ? 0
3^56 ? 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
5^38 ? 1




We can also notice that ppi(n)+ppi(n-1)=1 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)).



Download the demonstration of the algorithm computing ppi(n) (original paper).

In preparation, paper or article with additions and optimizations
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
Prime page 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
March 6 2015 : Douglas B. Staple : The combinatorial algorithm for computing pi(x)
March 11 2015, November 4 2015 : emails from David Baugh
Integer Sequences (OEIS) : A071986, A219071, A219097, A219098, A219189, A055729, A055730
Created by  Henri Lifchitz : September, 13  1998, last modification: November, 24  2015.