Development of |
|
liste_max:=100000; sieving:=proc (stelle, p) begin while (stelle<=liste_max) do erg:=liste[stelle]; while(erg mod p=0) do // Divison of the stored f(x) by the prime erg:=erg /p; end_while; liste[stelle]:=erg; stelle:=stelle+p; end_while; end_proc; // Calculation of the values of the polynom for x from 0 to liste_max for x from 0 to liste_max do p:=abs (a*x^2+b*x+c); while (p mod 2=0) p:=p/2; liste [x]:=p; end_for; for x from 0 to liste_max do p:=liste[x]; if (p>1) then // Printing the Primes print (x, p); // 1. Sieving sieving (x+p, p); t:=(-x-b/a) mod p;If you are interested in some better algorithms have a look at quadr_Sieb_x^2+1.php.
if t=0 then t:=p; end_if; // 2. Sieving sieving (t, p); end_if; end_for;
2. Mathematical background
Lemma: If p | f(x) then also p | f(x+p) and p | f(-x-b/a) a) p | f(x) <=> ax^2 + bx + c = 0 mod p p | f(x+p) <=> a(x+p)^2 + b(x+p) + c = 0 mod p <=> ax^2 + 2axp + ap^2 + bx + bp + c = 0 mod p <=> ax^2 + bx + c = 0 mod p Thus if p | f(x) then p | f(x+p) b) if b = 0 mod a p | f(x) <=> ax^2 + bx + c = 0 mod p p | f(-x-b/a) <=> a(-x-b/a)^2 + b(-x-b/a) + c = 0 mod p <=> ax^2 + 2bx + b^2/a - bx - b^2/a + c = 0 mod p <=> ax^2 + bx + c = 0 mod p Thus if p | f(x) then p | f(-x-b/a)3. Correctness of the algorithm
The proof for this polynom is similar to the proof for the polynom f(x)=x^2-4x+1. a) First terms for the polynom f(x) = x^2-120x-113
f(0)=113
f(1)=29
f(2)=349
f(3)=1
f(4)=577
f(5)=43
f(6)=797
f(7)=1
f(8)=1009
f(9)=139
f(10)=1213
f(11)=41
f(12)=1409
f(13)=47
f(14)=1597
f(15)=211
f(16)=1777
f(17)=233
f(18)=1949
f(19)=127
f(20)=2113
f(21)=137
f(22)=2269
f(23)=293
f(24)=2417
f(25)=311
f(26)=2557
f(27)=1
f(28)=2689
f(29)=1
f(30)=97
f(31)=359
f(32)=101
f(33)=373
f(34)=3037
f(35)=193
f(36)=3137
f(37)=199
f(38)=3229
f(39)=409
f(40)=3313
f(41)=419
f(42)=3389
f(43)=107
f(44)=3457
f(45)=109
f(46)=3517
f(47)=443
f(48)=83
f(49)=449
f(50)=3613
f(51)=227
f(52)=89
f(53)=229
f(54)=3677
f(55)=461
f(56)=3697
f(57)=463
f(58)=3709
f(59)=1
f(60)=79
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-120x-113 could be written as f(y)= y^2-3713 with x=y+60
c) Backsubstitution Beside by backsubstitution you get an estimation for the huge of the primes with p | f(x) and p < f(x) f'(y)>(2y-1) with with y=x-60
f'(x)>2x-121 with x > 61
A | B | C | D | E | F | G | H | I | J | K |
exponent =log10 (x) | <=x | number of all primes | number of primes p = f(x) | number of primes p | f(x) | C/x | D/x | E/x | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
1 | 10 | 9 | 6 | 3 | 0.900000 | 0.600000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 54 | 26 | 28 | 0.540000 | 0.260000 | 0.540000 | 6.000000 | 4.333333 | 9.333333 |
3 | 1.000 | 699 | 249 | 450 | 0.699000 | 0.249000 | 0.699000 | 12.944445 | 9.576923 | 16.071428 |
4 | 10.000 | 7.230 | 1.871 | 5.359 | 0.723000 | 0.187100 | 0.723000 | 10.343348 | 7.514056 | 11.908889 |
5 | 100.000 | 72.288 | 14.533 | 57.755 | 0.722880 | 0.145330 | 0.722880 | 9.998341 | 7.767504 | 10.777197 |
6 | 1.000.000 | 718.049 | 119.231 | 598.818 | 0.718049 | 0.119231 | 0.718049 | 9.933170 | 8.204156 | 10.368245 |
7 | 10.000.000 | 7.143.636 | 1.006.898 | 6.136.738 | 0.714364 | 0.100690 | 0.714364 | 9.948675 | 8.444935 | 10.248085 |
8 | 100.000.000 | 71.157.351 | 8.718.977 | 62.438.374 | 0.711574 | 0.087190 | 0.711574 | 9.960943 | 8.659245 | 10.174522 |
9 | 1.000.000.000 | 709.391.763 | 76.950.719 | 632.441.044 | 0.709392 | 0.076951 | 0.709392 | 9.969338 | 8.825659 | 10.129044 |
10 | 10.000.000.000 | 7.076.485.527 | 688.730.437 | 6.387.755.090 | 0.707649 | 0.068873 | 0.707649 | 9.975427 | 8.950279 | 10.100160 |
A | B | C | D | E | F | G | H | I | J | K |
exponent =log2 (x) | <=x | number of all primes | number of primes p = f(x) | number of primes p | f(x) | C/x | D/x | E/x | C(n) / C(n-1) | D(n) / D(n-1) | E(n) / E(n-1) |
1 | 2 | 3 | 2 | 1 | 1.500000 | 1.000000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 7 | 5 | 2 | 0.875000 | 0.625000 | 0.250000 | 1.750000 | 1.666667 | 2.000000 |
4 | 16 | 15 | 9 | 6 | 0.937500 | 0.562500 | 0.375000 | 2.142857 | 1.800000 | 3.000000 |
5 | 32 | 29 | 15 | 14 | 0.906250 | 0.468750 | 0.437500 | 1.933333 | 1.666667 | 2.333333 |
6 | 64 | 54 | 26 | 28 | 0.843750 | 0.406250 | 0.437500 | 1.862069 | 1.733333 | 2.000000 |
7 | 128 | 57 | 29 | 28 | 0.445312 | 0.226562 | 0.218750 | 1.055556 | 1.115385 | 1.000000 |
8 | 256 | 143 | 68 | 75 | 0.558594 | 0.265625 | 0.292969 | 2.508772 | 2.344828 | 2.678571 |
9 | 512 | 333 | 137 | 196 | 0.650391 | 0.267578 | 0.382812 | 2.328671 | 2.014706 | 2.613333 |
10 | 1.024 | 717 | 254 | 463 | 0.700195 | 0.248047 | 0.452148 | 2.153153 | 1.854015 | 2.362245 |
11 | 2.048 | 1.468 | 480 | 988 | 0.716797 | 0.234375 | 0.482422 | 2.047420 | 1.889764 | 2.133909 |
12 | 4.096 | 2.952 | 864 | 2.088 | 0.720703 | 0.210938 | 0.509766 | 2.010899 | 1.800000 | 2.113360 |
13 | 8.192 | 5.905 | 1.569 | 4.336 | 0.720825 | 0.191528 | 0.529297 | 2.000339 | 1.815972 | 2.076628 |
14 | 16.384 | 11.882 | 2.921 | 8.961 | 0.725220 | 0.178284 | 0.546936 | 2.012193 | 1.861695 | 2.066651 |
15 | 32.768 | 23.793 | 5.381 | 18.412 | 0.726105 | 0.164215 | 0.561890 | 2.002441 | 1.842177 | 2.054681 |
16 | 65.536 | 47.467 | 9.980 | 37.487 | 0.724289 | 0.152283 | 0.572006 | 1.994999 | 1.854674 | 2.036009 |
17 | 131.072 | 94.674 | 18.622 | 76.052 | 0.722305 | 0.142075 | 0.580231 | 1.994522 | 1.865932 | 2.028757 |
18 | 262.144 | 188.861 | 35.059 | 153.802 | 0.720448 | 0.133739 | 0.586708 | 1.994856 | 1.882666 | 2.022327 |
19 | 524.288 | 377.008 | 66.057 | 310.951 | 0.719086 | 0.125994 | 0.593092 | 1.996219 | 1.884167 | 2.021762 |
20 | 1.048.576 | 752.719 | 124.533 | 628.186 | 0.717849 | 0.118764 | 0.599085 | 1.996560 | 1.885235 | 2.020209 |
21 | 2.097.152 | 1.503.001 | 236.087 | 1.266.914 | 0.716687 | 0.112575 | 0.604112 | 1.996762 | 1.895779 | 2.016782 |
22 | 4.194.304 | 3.001.232 | 448.869 | 2.552.363 | 0.715549 | 0.107019 | 0.608531 | 1.996826 | 1.901286 | 2.014630 |
23 | 8.388.608 | 5.994.728 | 854.808 | 5.139.920 | 0.714627 | 0.101901 | 0.612726 | 1.997422 | 1.904360 | 2.013789 |
24 | 16.777.216 | 11.973.690 | 1.631.853 | 10.341.837 | 0.713688 | 0.097266 | 0.616422 | 1.997370 | 1.909029 | 2.012062 |
25 | 33.554.432 | 23.918.425 | 3.123.764 | 20.794.661 | 0.712825 | 0.093095 | 0.619729 | 1.997582 | 1.914243 | 2.010732 |
26 | 67.108.864 | 47.782.136 | 5.991.368 | 41.790.768 | 0.712009 | 0.089278 | 0.622731 | 1.997713 | 1.917996 | 2.009687 |
27 | 134.217.728 | 95.462.409 | 11.506.299 | 83.956.110 | 0.711250 | 0.085729 | 0.625522 | 1.997868 | 1.920479 | 2.008963 |
28 | 268.435.456 | 190.742.615 | 22.142.586 | 168.600.029 | 0.710572 | 0.082488 | 0.628084 | 1.998091 | 1.924388 | 2.008193 |
29 | 536.870.912 | 381.142.854 | 42.667.698 | 338.475.156 | 0.709934 | 0.079475 | 0.630459 | 1.998205 | 1.926952 | 2.007563 |
30 | 1.073.741.824 | 761.638.158 | 82.325.447 | 679.312.711 | 0.709331 | 0.076672 | 0.632659 | 1.998301 | 1.929456 | 2.006979 |
31 | 2.147.483.648 | 1.522.053.322 | 159.064.328 | 1.362.988.994 | 0.708761 | 0.074070 | 0.634691 | 1.998394 | 1.932140 | 2.006424 |
32 | 4.294.967.296 | 3.041.873.419 | 307.660.615 | 2.734.212.804 | 0.708241 | 0.071633 | 0.636609 | 1.998533 | 1.934190 | 2.006042 |
33 | 8.589.934.592 | 6.079.541.995 | 595.735.048 | 5.483.806.947 | 0.707752 | 0.069353 | 0.638399 | 1.998618 | 1.936338 | 2.005625 |
34 | 17.179.869.184 | 12.151.178.278 | 1.154.711.920 | 10.996.466.358 | 0.707292 | 0.067213 | 0.640079 | 1.998700 | 1.938298 | 2.005261 |
A | B | C | D | E | F | G | H | I |
exponent =log2 (x) | <=x | number of primes with p=f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
1 | 2 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 2 | 0 | 1 | 0 |
3 | 8 | 5 | 3 | 2 | 3 | 0 | 2 | 0 |
4 | 16 | 9 | 6 | 3 | 5 | 0 | 4 | 0 |
5 | 32 | 15 | 10 | 5 | 8 | 0 | 7 | 0 |
6 | 64 | 26 | 18 | 8 | 12 | 0 | 14 | 0 |
7 | 128 | 29 | 19 | 10 | 12 | 1 | 14 | 2 |
8 | 256 | 68 | 34 | 34 | 12 | 19 | 14 | 23 |
9 | 512 | 137 | 55 | 82 | 12 | 54 | 14 | 57 |
10 | 1.024 | 254 | 88 | 166 | 12 | 111 | 14 | 117 |
11 | 2.048 | 480 | 162 | 318 | 12 | 217 | 14 | 237 |
12 | 4.096 | 864 | 292 | 572 | 12 | 419 | 14 | 419 |
13 | 8.192 | 1.569 | 533 | 1.036 | 12 | 773 | 14 | 770 |
14 | 16.384 | 2.921 | 979 | 1.942 | 12 | 1.441 | 14 | 1.454 |
15 | 32.768 | 5.381 | 1.783 | 3.598 | 12 | 2.686 | 14 | 2.669 |
16 | 65.536 | 9.980 | 3.315 | 6.665 | 12 | 4.977 | 14 | 4.977 |
17 | 131.072 | 18.622 | 6.204 | 12.418 | 12 | 9.279 | 14 | 9.317 |
18 | 262.144 | 35.059 | 11.708 | 23.351 | 12 | 17.486 | 14 | 17.547 |
19 | 524.288 | 66.057 | 22.041 | 44.016 | 12 | 32.939 | 14 | 33.092 |
20 | 1.048.576 | 124.533 | 41.529 | 83.004 | 12 | 62.133 | 14 | 62.374 |
21 | 2.097.152 | 236.087 | 78.819 | 157.268 | 12 | 117.909 | 14 | 118.152 |
22 | 4.194.304 | 448.869 | 149.762 | 299.107 | 12 | 224.530 | 14 | 224.313 |
23 | 8.388.608 | 854.808 | 285.249 | 569.559 | 12 | 427.544 | 14 | 427.238 |
24 | 16.777.216 | 1.631.853 | 544.407 | 1.087.446 | 12 | 815.822 | 14 | 816.005 |
25 | 33.554.432 | 3.123.764 | 1.042.625 | 2.081.139 | 12 | 1.561.701 | 14 | 1.562.037 |
26 | 67.108.864 | 5.991.368 | 1.999.213 | 3.992.155 | 12 | 2.995.512 | 14 | 2.995.830 |
27 | 134.217.728 | 11.506.299 | 3.836.335 | 7.669.964 | 12 | 5.752.788 | 14 | 5.753.485 |
28 | 268.435.456 | 22.142.586 | 7.383.496 | 14.759.090 | 12 | 11.073.112 | 14 | 11.069.448 |
29 | 536.870.912 | 42.667.698 | 14.225.673 | 28.442.025 | 12 | 21.335.013 | 14 | 21.332.659 |
30 | 1.073.741.824 | 82.325.447 | 27.442.609 | 54.882.838 | 12 | 41.163.085 | 14 | 41.162.336 |
31 | 2.147.483.648 | 159.064.328 | 53.018.809 | 106.045.519 | 12 | 79.533.002 | 14 | 79.531.300 |
32 | 4.294.967.296 | 307.660.615 | 102.555.556 | 205.105.059 | 12 | 153.829.998 | 14 | 153.830.591 |
33 | 8.589.934.592 | 595.735.048 | 198.584.619 | 397.150.429 | 12 | 297.873.024 | 14 | 297.861.998 |
34 | 17.179.869.184 | 1.154.711.920 | 384.912.088 | 769.799.832 | 12 | 577.355.165 | 14 | 577.356.729 |
A | B | C | D | E | F | G | H | I |
exponent =log2 (x) | <=x | number of primes with p|f(x) | number of primes with p=f(x) and p%6=1 | number of primes with p=f(x) and p%6=5 | number of primes with p=f(x) and p%8=1 | number of primes with p=f(x) and p%8=3 | number of primes with p=f(x) and p%8=5 | number of primes with p=f(x) and p%8=7 |
1 | 2 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
4 | 16 | 6 | 3 | 3 | 1 | 3 | 1 | 1 |
5 | 32 | 14 | 5 | 9 | 4 | 3 | 3 | 4 |
6 | 64 | 28 | 13 | 15 | 7 | 7 | 7 | 7 |
7 | 128 | 28 | 13 | 15 | 7 | 7 | 7 | 7 |
8 | 256 | 75 | 39 | 36 | 18 | 19 | 18 | 20 |
9 | 512 | 196 | 106 | 90 | 46 | 50 | 51 | 49 |
10 | 1.024 | 463 | 250 | 213 | 108 | 116 | 116 | 123 |
11 | 2.048 | 988 | 529 | 459 | 222 | 245 | 254 | 267 |
12 | 4.096 | 2.088 | 1.089 | 999 | 499 | 518 | 516 | 555 |
13 | 8.192 | 4.336 | 2.270 | 2.066 | 1.056 | 1.097 | 1.065 | 1.118 |
14 | 16.384 | 8.961 | 4.733 | 4.228 | 2.197 | 2.247 | 2.222 | 2.295 |
15 | 32.768 | 18.412 | 9.629 | 8.783 | 4.485 | 4.694 | 4.571 | 4.662 |
16 | 65.536 | 37.487 | 19.540 | 17.947 | 9.173 | 9.483 | 9.282 | 9.549 |
17 | 131.072 | 76.052 | 39.567 | 36.485 | 18.737 | 19.285 | 18.831 | 19.199 |
18 | 262.144 | 153.802 | 79.687 | 74.115 | 37.909 | 38.787 | 38.095 | 39.011 |
19 | 524.288 | 310.951 | 160.209 | 150.742 | 76.940 | 78.422 | 76.728 | 78.861 |
20 | 1.048.576 | 628.186 | 322.684 | 305.502 | 155.361 | 158.726 | 155.235 | 158.864 |
21 | 2.097.152 | 1.266.914 | 649.777 | 617.137 | 313.293 | 319.735 | 313.568 | 320.318 |
22 | 4.194.304 | 2.552.363 | 1.308.011 | 1.244.352 | 631.378 | 644.640 | 632.104 | 644.241 |
23 | 8.388.608 | 5.139.920 | 2.631.683 | 2.508.237 | 1.272.901 | 1.296.890 | 1.274.251 | 1.295.878 |
24 | 16.777.216 | 10.341.837 | 5.289.713 | 5.052.124 | 2.562.183 | 2.609.126 | 2.563.334 | 2.607.194 |
25 | 33.554.432 | 20.794.661 | 10.626.343 | 10.168.318 | 5.154.053 | 5.243.830 | 5.155.095 | 5.241.683 |
26 | 67.108.864 | 41.790.768 | 21.330.611 | 20.460.157 | 10.365.575 | 10.531.190 | 10.362.977 | 10.531.026 |
27 | 134.217.728 | 83.956.110 | 42.807.145 | 41.148.965 | 20.826.625 | 21.153.691 | 20.829.419 | 21.146.375 |
28 | 268.435.456 | 168.600.029 | 85.898.917 | 82.701.112 | 41.835.804 | 42.460.107 | 41.844.671 | 42.459.447 |
29 | 536.870.912 | 338.475.156 | 172.320.375 | 166.154.781 | 84.021.221 | 85.209.289 | 84.031.857 | 85.212.789 |
30 | 1.073.741.824 | 679.312.711 | 345.596.238 | 333.716.473 | 168.674.533 | 170.971.477 | 168.687.492 | 170.979.209 |
31 | 2.147.483.648 | 1.362.988.994 | 692.971.330 | 670.017.664 | 338.524.656 | 342.953.907 | 338.546.191 | 342.964.240 |
32 | 4.294.967.296 | 2.734.212.804 | 1.389.250.603 | 1.344.962.201 | 679.277.944 | 687.812.631 | 679.302.241 | 687.819.988 |
33 | 8.589.934.592 | 5.483.806.947 | 2.784.708.895 | 2.699.098.052 | 1.362.707.181 | 1.379.175.386 | 1.362.745.264 | 1.379.179.116 |
34 | 17.179.869.184 | 10.996.466.358 | 5.581.043.581 | 5.415.422.777 | 2.733.152.597 | 2.765.035.334 | 2.733.274.416 | 2.765.004.011 |