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+16x-7
f(0)=7
f(1)=5
f(2)=29
f(3)=1
f(4)=73
f(5)=1
f(6)=1
f(7)=11
f(8)=37
f(9)=109
f(10)=23
f(11)=1
f(12)=47
f(13)=1
f(14)=59
f(15)=229
f(16)=101
f(17)=277
f(18)=1
f(19)=1
f(20)=31
f(21)=1
f(22)=829
f(23)=89
f(24)=953
f(25)=509
f(26)=1
f(27)=577
f(28)=1
f(29)=1
f(30)=1373
f(31)=1
f(32)=139
f(33)=1
f(34)=1693
f(35)=127
f(36)=373
f(37)=977
f(38)=409
f(39)=1069
f(40)=1
f(41)=233
f(42)=347
f(43)=1
f(44)=2633
f(45)=1
f(46)=569
f(47)=211
f(48)=613
f(49)=227
f(50)=1
f(51)=1
f(52)=3529
f(53)=1
f(54)=1
f(55)=1949
f(56)=1
f(57)=67
f(58)=857
f(59)=1
f(60)=157
f(61)=1
f(62)=439
f(63)=71
f(64)=5113
f(65)=239
f(66)=1
f(67)=2777
f(68)=163
f(69)=1
f(70)=859
f(71)=617
f(72)=6329
f(73)=1
f(74)=6653
f(75)=487
f(76)=1
f(77)=1
f(78)=293
f(79)=1
f(80)=7673
f(81)=1
f(82)=1
f(83)=821
f(84)=1
f(85)=4289
f(86)=1753
f(87)=1
f(88)=1
f(89)=1
f(90)=9533
f(91)=1
f(92)=9929
f(93)=1013
f(94)=10333
f(95)=479
f(96)=307
f(97)=5477
f(98)=1
f(99)=5689
b) Substitution of the polynom
The polynom f(x)=x^2+16x-7 could be written as f(y)= y^2-71 with x=y-8
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+8
f'(x)>2x+15
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 | 7 | 5 | 2 | 0.700000 | 0.500000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 60 | 30 | 30 | 0.600000 | 0.300000 | 0.300000 | 8.571428 | 6.000000 | 15.000000 |
3 | 1.000 | 672 | 174 | 498 | 0.672000 | 0.174000 | 0.498000 | 11.200000 | 5.800000 | 16.600000 |
4 | 10.000 | 6.745 | 1.240 | 5.505 | 0.674500 | 0.124000 | 0.550500 | 10.037203 | 7.126437 | 11.054217 |
5 | 100.000 | 68.058 | 9.527 | 58.531 | 0.680580 | 0.095270 | 0.585310 | 10.090141 | 7.683064 | 10.632335 |
6 | 1.000.000 | 681.983 | 77.653 | 604.330 | 0.681983 | 0.077653 | 0.604330 | 10.020615 | 8.150834 | 10.324956 |
7 | 10.000.000 | 6.834.589 | 654.760 | 6.179.829 | 0.683459 | 0.065476 | 0.617983 | 10.021642 | 8.431870 | 10.225918 |
8 | 100.000.000 | 68.452.569 | 5.671.271 | 62.781.298 | 0.684526 | 0.056713 | 0.627813 | 10.015609 | 8.661603 | 10.159067 |
9 | 1.000.000.000 | 685.370.554 | 49.997.456 | 635.373.098 | 0.685371 | 0.049997 | 0.635373 | 10.012342 | 8.815917 | 10.120420 |
10 | 10.000.000.000 | 6.860.707.384 | 447.074.648 | 6.413.632.736 | 0.686071 | 0.044707 | 0.641363 | 10.010216 | 8.941948 | 10.094277 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 5 | 4 | 1 | 0.625000 | 0.500000 | 0.125000 | 1.250000 | 1.000000 | inf |
4 | 16 | 11 | 6 | 5 | 0.687500 | 0.375000 | 0.312500 | 2.200000 | 1.500000 | 5.000000 |
5 | 32 | 19 | 12 | 7 | 0.593750 | 0.375000 | 0.218750 | 1.727273 | 2.000000 | 1.400000 |
6 | 64 | 38 | 19 | 19 | 0.593750 | 0.296875 | 0.296875 | 2.000000 | 1.583333 | 2.714286 |
7 | 128 | 78 | 35 | 43 | 0.609375 | 0.273438 | 0.335938 | 2.052632 | 1.842105 | 2.263158 |
8 | 256 | 166 | 57 | 109 | 0.648438 | 0.222656 | 0.425781 | 2.128205 | 1.628571 | 2.534884 |
9 | 512 | 338 | 99 | 239 | 0.660156 | 0.193359 | 0.466797 | 2.036144 | 1.736842 | 2.192661 |
10 | 1.024 | 687 | 177 | 510 | 0.670898 | 0.172852 | 0.498047 | 2.032544 | 1.787879 | 2.133891 |
11 | 2.048 | 1.367 | 332 | 1.035 | 0.667480 | 0.162109 | 0.505371 | 1.989811 | 1.875706 | 2.029412 |
12 | 4.096 | 2.760 | 589 | 2.171 | 0.673828 | 0.143799 | 0.530029 | 2.019020 | 1.774096 | 2.097584 |
13 | 8.192 | 5.526 | 1.040 | 4.486 | 0.674561 | 0.126953 | 0.547607 | 2.002174 | 1.765705 | 2.066329 |
14 | 16.384 | 11.091 | 1.922 | 9.169 | 0.676941 | 0.117310 | 0.559631 | 2.007057 | 1.848077 | 2.043914 |
15 | 32.768 | 22.239 | 3.509 | 18.730 | 0.678680 | 0.107086 | 0.571594 | 2.005139 | 1.825702 | 2.042753 |
16 | 65.536 | 44.544 | 6.522 | 38.022 | 0.679688 | 0.099518 | 0.580170 | 2.002968 | 1.858649 | 2.030005 |
17 | 131.072 | 89.240 | 12.128 | 77.112 | 0.680847 | 0.092529 | 0.588318 | 2.003412 | 1.859552 | 2.028089 |
18 | 262.144 | 178.478 | 22.786 | 155.692 | 0.680840 | 0.086922 | 0.593918 | 1.999978 | 1.878793 | 2.019037 |
19 | 524.288 | 357.391 | 42.926 | 314.465 | 0.681669 | 0.081875 | 0.599794 | 2.002437 | 1.883876 | 2.019789 |
20 | 1.048.576 | 715.248 | 81.094 | 634.154 | 0.682114 | 0.077337 | 0.604776 | 2.001304 | 1.889158 | 2.016612 |
21 | 2.097.152 | 1.431.444 | 153.644 | 1.277.800 | 0.682566 | 0.073263 | 0.609303 | 2.001325 | 1.894641 | 2.014968 |
22 | 4.194.304 | 2.864.643 | 291.703 | 2.572.940 | 0.682984 | 0.069547 | 0.613437 | 2.001226 | 1.898564 | 2.013570 |
23 | 8.388.608 | 5.732.389 | 556.043 | 5.176.346 | 0.683354 | 0.066285 | 0.617069 | 2.001083 | 1.906196 | 2.011841 |
24 | 16.777.216 | 11.470.523 | 1.062.952 | 10.407.571 | 0.683696 | 0.063357 | 0.620340 | 2.001002 | 1.911636 | 2.010602 |
25 | 33.554.432 | 22.952.765 | 2.033.376 | 20.919.389 | 0.684046 | 0.060599 | 0.623446 | 2.001022 | 1.912952 | 2.010016 |
26 | 67.108.864 | 45.925.445 | 3.897.087 | 42.028.358 | 0.684342 | 0.058071 | 0.626271 | 2.000868 | 1.916560 | 2.009063 |
27 | 134.217.728 | 91.892.294 | 7.482.635 | 84.409.659 | 0.684651 | 0.055750 | 0.628901 | 2.000902 | 1.920058 | 2.008398 |
28 | 268.435.456 | 183.855.431 | 14.393.790 | 169.461.641 | 0.684915 | 0.053621 | 0.631294 | 2.000771 | 1.923626 | 2.007610 |
29 | 536.870.912 | 367.841.077 | 27.728.255 | 340.112.822 | 0.685157 | 0.051648 | 0.633510 | 2.000708 | 1.926404 | 2.007020 |
30 | 1.073.741.824 | 735.940.229 | 53.488.637 | 682.451.592 | 0.685398 | 0.049815 | 0.635583 | 2.000701 | 1.929030 | 2.006545 |
31 | 2.147.483.648 | 1.472.361.267 | 103.312.720 | 1.369.048.547 | 0.685622 | 0.048109 | 0.637513 | 2.000653 | 1.931489 | 2.006074 |
32 | 4.294.967.296 | 2.945.621.656 | 199.775.816 | 2.745.845.840 | 0.685831 | 0.046514 | 0.639317 | 2.000611 | 1.933700 | 2.005660 |
33 | 8.589.934.592 | 5.892.936.907 | 386.742.320 | 5.506.194.587 | 0.686028 | 0.045023 | 0.641005 | 2.000575 | 1.935882 | 2.005282 |
34 | 17.179.869.184 | 11.789.133.989 | 749.423.899 | 11.039.710.090 | 0.686218 | 0.043622 | 0.642596 | 2.000553 | 1.937786 | 2.004962 |
35 | 34.359.738.368 | 23.584.484.846 | 1.453.615.889 | 22.130.868.957 | 0.686399 | 0.042306 | 0.644093 | 2.000527 | 1.939644 | 2.004660 |
36 | 68.719.476.736 | 47.180.785.914 | 2.822.109.578 | 44.358.676.336 | 0.686571 | 0.041067 | 0.645504 | 2.000501 | 1.941441 | 2.004380 |
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 | 3 | 1 | 2 | 0 | 0 | 2 | 1 |
2 | 4 | 4 | 2 | 2 | 1 | 0 | 2 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 0 | 2 | 1 |
4 | 16 | 6 | 4 | 2 | 1 | 0 | 4 | 1 |
5 | 32 | 12 | 7 | 5 | 3 | 0 | 8 | 1 |
6 | 64 | 19 | 11 | 8 | 7 | 0 | 11 | 1 |
7 | 128 | 35 | 15 | 20 | 17 | 0 | 17 | 1 |
8 | 256 | 57 | 33 | 24 | 26 | 0 | 30 | 1 |
9 | 512 | 99 | 53 | 46 | 49 | 0 | 49 | 1 |
10 | 1.024 | 177 | 87 | 90 | 85 | 0 | 91 | 1 |
11 | 2.048 | 332 | 167 | 165 | 163 | 0 | 168 | 1 |
12 | 4.096 | 589 | 290 | 299 | 296 | 0 | 292 | 1 |
13 | 8.192 | 1.040 | 525 | 515 | 525 | 0 | 514 | 1 |
14 | 16.384 | 1.922 | 975 | 947 | 953 | 0 | 968 | 1 |
15 | 32.768 | 3.509 | 1.767 | 1.742 | 1.727 | 0 | 1.781 | 1 |
16 | 65.536 | 6.522 | 3.277 | 3.245 | 3.249 | 0 | 3.272 | 1 |
17 | 131.072 | 12.128 | 6.087 | 6.041 | 6.116 | 0 | 6.011 | 1 |
18 | 262.144 | 22.786 | 11.525 | 11.261 | 11.402 | 0 | 11.383 | 1 |
19 | 524.288 | 42.926 | 21.622 | 21.304 | 21.470 | 0 | 21.455 | 1 |
20 | 1.048.576 | 81.094 | 40.777 | 40.317 | 40.576 | 0 | 40.517 | 1 |
21 | 2.097.152 | 153.644 | 77.219 | 76.425 | 76.843 | 0 | 76.800 | 1 |
22 | 4.194.304 | 291.703 | 146.626 | 145.077 | 145.821 | 0 | 145.881 | 1 |
23 | 8.388.608 | 556.043 | 279.168 | 276.875 | 277.873 | 0 | 278.169 | 1 |
24 | 16.777.216 | 1.062.952 | 533.377 | 529.575 | 531.660 | 0 | 531.291 | 1 |
25 | 33.554.432 | 2.033.376 | 1.020.168 | 1.013.208 | 1.016.942 | 0 | 1.016.433 | 1 |
26 | 67.108.864 | 3.897.087 | 1.956.126 | 1.940.961 | 1.949.184 | 0 | 1.947.902 | 1 |
27 | 134.217.728 | 7.482.635 | 3.754.923 | 3.727.712 | 3.742.315 | 0 | 3.740.319 | 1 |
28 | 268.435.456 | 14.393.790 | 7.221.300 | 7.172.490 | 7.197.184 | 0 | 7.196.605 | 1 |
29 | 536.870.912 | 27.728.255 | 13.908.556 | 13.819.699 | 13.863.643 | 0 | 13.864.611 | 1 |
30 | 1.073.741.824 | 53.488.637 | 26.824.732 | 26.663.905 | 26.743.507 | 0 | 26.745.129 | 1 |
31 | 2.147.483.648 | 103.312.720 | 51.804.975 | 51.507.745 | 51.658.219 | 0 | 51.654.500 | 1 |
32 | 4.294.967.296 | 199.775.816 | 100.160.063 | 99.615.753 | 99.888.816 | 0 | 99.886.999 | 1 |
33 | 8.589.934.592 | 386.742.320 | 193.881.451 | 192.860.869 | 193.371.819 | 0 | 193.370.500 | 1 |
34 | 17.179.869.184 | 749.423.899 | 375.670.217 | 373.753.682 | 374.712.076 | 0 | 374.711.822 | 1 |
35 | 34.359.738.368 | 1.453.615.889 | 728.619.864 | 724.996.025 | 726.811.342 | 0 | 726.804.546 | 1 |
36 | 68.719.476.736 | 2.822.109.578 | 1.414.479.179 | 1.407.630.399 | 1.411.040.016 | 0 | 1.411.069.561 | 1 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
4 | 16 | 5 | 1 | 4 | 0 | 1 | 2 | 2 |
5 | 32 | 7 | 2 | 5 | 1 | 2 | 2 | 2 |
6 | 64 | 19 | 9 | 10 | 5 | 5 | 5 | 4 |
7 | 128 | 43 | 22 | 21 | 10 | 13 | 12 | 8 |
8 | 256 | 109 | 49 | 60 | 22 | 36 | 25 | 26 |
9 | 512 | 239 | 124 | 115 | 50 | 73 | 53 | 63 |
10 | 1.024 | 510 | 251 | 259 | 111 | 148 | 113 | 138 |
11 | 2.048 | 1.035 | 497 | 538 | 240 | 288 | 237 | 270 |
12 | 4.096 | 2.171 | 1.040 | 1.131 | 503 | 585 | 507 | 576 |
13 | 8.192 | 4.486 | 2.203 | 2.283 | 1.059 | 1.189 | 1.064 | 1.174 |
14 | 16.384 | 9.169 | 4.549 | 4.620 | 2.188 | 2.395 | 2.213 | 2.373 |
15 | 32.768 | 18.730 | 9.308 | 9.422 | 4.460 | 4.860 | 4.537 | 4.873 |
16 | 65.536 | 38.022 | 18.945 | 19.077 | 9.127 | 9.964 | 9.173 | 9.758 |
17 | 131.072 | 77.112 | 38.543 | 38.569 | 18.585 | 19.981 | 18.680 | 19.866 |
18 | 262.144 | 155.692 | 77.791 | 77.901 | 37.628 | 40.085 | 37.805 | 40.174 |
19 | 524.288 | 314.465 | 156.910 | 157.555 | 76.519 | 80.758 | 76.382 | 80.806 |
20 | 1.048.576 | 634.154 | 316.973 | 317.181 | 154.742 | 162.587 | 154.393 | 162.432 |
21 | 2.097.152 | 1.277.800 | 638.812 | 638.988 | 311.953 | 326.631 | 311.688 | 327.528 |
22 | 4.194.304 | 2.572.940 | 1.286.404 | 1.286.536 | 629.313 | 657.372 | 627.915 | 658.340 |
23 | 8.388.608 | 5.176.346 | 2.587.942 | 2.588.404 | 1.267.259 | 1.320.567 | 1.266.500 | 1.322.020 |
24 | 16.777.216 | 10.407.571 | 5.201.023 | 5.206.548 | 2.550.620 | 2.652.207 | 2.550.890 | 2.653.854 |
25 | 33.554.432 | 20.919.389 | 10.455.578 | 10.463.811 | 5.133.067 | 5.327.109 | 5.133.601 | 5.325.612 |
26 | 67.108.864 | 42.028.358 | 21.009.038 | 21.019.320 | 10.324.668 | 10.692.318 | 10.323.562 | 10.687.810 |
27 | 134.217.728 | 84.409.659 | 42.201.960 | 42.207.699 | 20.753.431 | 21.454.030 | 20.754.862 | 21.447.336 |
28 | 268.435.456 | 169.461.641 | 84.725.263 | 84.736.378 | 41.700.733 | 43.039.811 | 41.695.007 | 43.026.090 |
29 | 536.870.912 | 340.112.822 | 170.048.492 | 170.064.330 | 83.749.286 | 86.304.865 | 83.755.817 | 86.302.854 |
30 | 1.073.741.824 | 682.451.592 | 341.194.154 | 341.257.438 | 168.160.492 | 173.069.626 | 168.161.315 | 173.060.159 |
31 | 2.147.483.648 | 1.369.048.547 | 684.470.594 | 684.577.953 | 337.551.690 | 347.000.451 | 337.545.877 | 346.950.529 |
32 | 4.294.967.296 | 2.745.845.840 | 1.372.803.562 | 1.373.042.278 | 677.386.343 | 695.556.129 | 677.383.640 | 695.519.728 |
33 | 8.589.934.592 | 5.506.194.587 | 2.752.831.689 | 2.753.362.898 | 1.359.062.466 | 1.394.088.921 | 1.359.043.363 | 1.393.999.837 |
34 | 17.179.869.184 | 11.039.710.090 | 5.519.406.022 | 5.520.304.068 | 2.726.157.036 | 2.793.681.639 | 2.726.223.430 | 2.793.647.985 |
35 | 34.359.738.368 | 22.130.868.957 | 11.064.597.886 | 11.066.271.071 | 5.467.481.466 | 5.597.997.134 | 5.467.502.116 | 5.597.888.241 |
36 | 68.719.476.736 | 44.358.676.336 | 22.177.712.255 | 22.180.964.081 | 10.963.405.690 | 11.216.046.554 | 10.963.376.919 | 11.215.847.173 |