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 > 1020, to check known
values (New
values of pi(x) : M. Deleglise et J. Rivat) , 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 the results of the computations already done of
ppi(n)=pi(n) mod 2, in particular for n>=
1018 :
The computed parities confirm the known pi(n).
| n | pi(n) |
ppi(n)
|
|---|---|---|
| 1018 | 24 739 954 287 740 860 |
0
|
| 2*1018 | 48 645 161 281 738 535 |
1
|
| 3*1018 | 72 254 704 797 687 083 |
1
|
| 4*1018 | 95 676 260 903 887 607 |
1
|
| 5*1018 | 118 959 989 688 273 472 |
0
|
| 6*1018 | 142 135 049 412 622 144 |
0
|
| 7*1018 | 165 220 513 980 969 424 |
0
|
| 8*1018 | 188 229 829 247 429 504 |
0
|
| 9*1018 | 211 172 979 243 258 278 |
0
|
| 1019 | 234 057 667 276 344 607 |
1
|
| 2*1019 | 460 637 655 126 005 490 |
0
|
| 3*1019 | 684 559 920 583 084 690 * |
0
|
| 4*1019 | 906 790 515 105 576 571 |
1
|
| 5*1019 | ? |
0
|
| 6*1019 | ? |
0
|
| 7*1019 | ? |
1
|
| 8*1019 | ? |
0
|
| 9*1019 | ? |
1
|
| 1020 | 2 220 819 602 560 918 840 |
0
|
| 2*1020 | 4 374 267 703 076 959 271* |
1
|
| 3*1020 | 6 503 696 293 016 202 398 * |
0
|
| 4*1020 | 8 617 821 096 373 621 600 * |
0
|
| 5*1020 | 10 720 710 117 789 005 897 * |
1
|
| 6*1020 | ? |
1
|
| 7*1020 | ? |
0
|
| 8*1020 | ? |
0
|
| 9*1020 | ? |
1
|
| 1021 | 21 127 269 486 018 731 928* |
0
|
| 2*1021 | ? |
0
|
| 10^22 | ||
| 10^23 |
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)).
* Last values of pi(n) found by Xavier Gourdon (november 2000) which confirm the parities I found (december 1997). Have a look at his site for explanations about the exact computing of pi(n).
