Parité de Pi(n)

J'ai trouvé en juin 1997 de nouveaux et curieux algorithmes pour calculer la parité de nombreuses fonctions arithmétiques. Ces algorithmes m'ont permis de calculer en particulier la parité du nombre de nombres premiers plus petits ou égaux à n pour des n plus grands que 1020, de tester ceux connus (New values of pi(x) : M. Deleglise et J. Rivat). , et de prévoir la parité pour de nouveaux  n.
La complexité de l'algorithme est en O(n1/2*logn) et avec un espace de stockage en O(1) !
Vous trouverez ci-dessous les résultats des calculs déjà effectués de ppi(n)=pi(n) mod 2, en particulier pour n>= 1018 :
Les parités calculées confirment les pi(n) connus.

  

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    

 On remarquera aussi que ppi(n)+ppi(n-1)=1 si et seulement n premier, ce qui permet de tester la primalité de n. Mais malheureusement ce test n'est pas très efficace (en O(n1/2*logn)).

* Dernières valeurs de pi(n) trouvées par Xavier Gourdon (novembre 2000) qui confirment les parités prévues (décembre 1997). Voir sur son site des explications sur le calcul exact de pi(n).

Télécharger la démonstration de l'algorithme du calcul de ppi(n).

Télécharger un programme de calcul de ppi(n) pour n<=1019.

Création par  Henri Lifchitz le 13 septembre 1998, dernière modification: 24 mai 2003.