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 10^20,
de tester ceux connus, 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 une partie des résultats des
calculs déjà effectués de ppi(n)=pi(n) mod 2, en particulier
pour 10^20 < n < 7*10^28. Pour cela l'algorithme d'origine
présenté dans l'article téléchargeable ci dessous à été largement optimisé
et porté sur GPU (mai-juin 2012).
Les parités calculées confirment les pi(n) connus y compris pour
pi(10^24) valeur calculée par 2 méthodes différentes(sous
condition
RH et sans condition RH).
Avec mon modeste pc (CPU I7 3770k, utilisation d'un seul coeur) et une
carte graphique (GTX 680) le calcul de ppi(10^24) =0 ne prend qu'environ 3
heures (63 000 heures pour le calcul complet par l'algorithme analytique
avec l'implémentation de David J. Platt), celui de ppi(5*10^28) =1
environ 39 jours !
Il semble possible d'obtenir un algorithme combiné utilisant la parité de
pi(n), permettant à l'algorithme analytique d'être plus rapide car
avec une erreur acceptable de +/- 1.5 au lieu +/- 0.5. Malheureusement, le
gain n'est que de 3%, car la courbe d'erreur est peu influencée par cette
information (courriel avec David J. Platt).
| n | 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 |
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)).
