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+9x-17
f(0)=17
f(1)=7
f(2)=5
f(3)=19
f(4)=1
f(5)=53
f(6)=73
f(7)=1
f(8)=1
f(9)=29
f(10)=173
f(11)=1
f(12)=47
f(13)=269
f(14)=61
f(15)=1
f(16)=383
f(17)=1
f(18)=67
f(19)=103
f(20)=563
f(21)=613
f(22)=1
f(23)=719
f(24)=31
f(25)=1
f(26)=1
f(27)=191
f(28)=1019
f(29)=1
f(30)=1153
f(31)=1223
f(32)=37
f(33)=1
f(34)=1
f(35)=1523
f(36)=229
f(37)=337
f(38)=1
f(39)=1
f(40)=1
f(41)=107
f(42)=1
f(43)=317
f(44)=463
f(45)=127
f(46)=359
f(47)=523
f(48)=2719
f(49)=113
f(50)=419
f(51)=179
f(52)=631
f(53)=467
f(54)=677
f(55)=1
f(56)=3623
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=4253
f(62)=877
f(63)=4519
f(64)=1
f(65)=4793
f(66)=4933
f(67)=1
f(68)=307
f(69)=1
f(70)=149
f(71)=809
f(72)=1163
f(73)=1
f(74)=1
f(75)=1
f(76)=379
f(77)=1321
f(78)=967
f(79)=1
f(80)=7103
f(81)=1039
f(82)=1489
f(83)=401
f(84)=1559
f(85)=1
f(86)=263
f(87)=1667
f(88)=1217
f(89)=1741
f(90)=8893
f(91)=293
f(92)=1
f(93)=557
f(94)=1933
f(95)=1409
f(96)=347
f(97)=2053
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+9x-17 could be written as f(y)= y^2-37.25 with x=y-4.5
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+4.5
f'(x)>2x+8
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 | 8 | 7 | 1 | 0.800000 | 0.700000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 26 | 41 | 0.670000 | 0.260000 | 0.410000 | 8.375000 | 3.714286 | 41.000000 |
3 | 1.000 | 701 | 176 | 525 | 0.701000 | 0.176000 | 0.525000 | 10.462687 | 6.769231 | 12.804878 |
4 | 10.000 | 6.996 | 1.281 | 5.715 | 0.699600 | 0.128100 | 0.571500 | 9.980028 | 7.278409 | 10.885715 |
5 | 100.000 | 69.855 | 9.822 | 60.033 | 0.698550 | 0.098220 | 0.600330 | 9.984991 | 7.667447 | 10.504462 |
6 | 1.000.000 | 697.079 | 80.698 | 616.381 | 0.697079 | 0.080698 | 0.616381 | 9.978942 | 8.216045 | 10.267369 |
7 | 10.000.000 | 6.964.398 | 680.278 | 6.284.120 | 0.696440 | 0.068028 | 0.628412 | 9.990830 | 8.429924 | 10.195188 |
8 | 100.000.000 | 69.587.462 | 5.890.529 | 63.696.933 | 0.695875 | 0.058905 | 0.636969 | 9.991885 | 8.659002 | 10.136173 |
9 | 1.000.000.000 | 695.435.587 | 51.956.605 | 643.478.982 | 0.695436 | 0.051957 | 0.643479 | 9.993690 | 8.820363 | 10.102198 |
10 | 10.000.000.000 | 6.951.092.462 | 464.975.354 | 6.486.117.108 | 0.695109 | 0.046498 | 0.648612 | 9.995307 | 8.949303 | 10.079765 |
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 | 6 | 6 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
4 | 16 | 12 | 9 | 3 | 0.750000 | 0.562500 | 0.187500 | 2.000000 | 1.500000 | inf |
5 | 32 | 21 | 15 | 6 | 0.656250 | 0.468750 | 0.187500 | 1.750000 | 1.666667 | 2.000000 |
6 | 64 | 41 | 20 | 21 | 0.640625 | 0.312500 | 0.328125 | 1.952381 | 1.333333 | 3.500000 |
7 | 128 | 87 | 34 | 53 | 0.679688 | 0.265625 | 0.414062 | 2.121951 | 1.700000 | 2.523809 |
8 | 256 | 175 | 61 | 114 | 0.683594 | 0.238281 | 0.445312 | 2.011494 | 1.794118 | 2.150943 |
9 | 512 | 356 | 107 | 249 | 0.695312 | 0.208984 | 0.486328 | 2.034286 | 1.754098 | 2.184211 |
10 | 1.024 | 717 | 181 | 536 | 0.700195 | 0.176758 | 0.523438 | 2.014045 | 1.691589 | 2.152611 |
11 | 2.048 | 1.437 | 322 | 1.115 | 0.701660 | 0.157227 | 0.544434 | 2.004184 | 1.779006 | 2.080224 |
12 | 4.096 | 2.867 | 585 | 2.282 | 0.699951 | 0.142822 | 0.557129 | 1.995129 | 1.816770 | 2.046637 |
13 | 8.192 | 5.717 | 1.083 | 4.634 | 0.697876 | 0.132202 | 0.565674 | 1.994070 | 1.851282 | 2.030675 |
14 | 16.384 | 11.453 | 1.947 | 9.506 | 0.699036 | 0.118835 | 0.580200 | 2.003323 | 1.797784 | 2.051359 |
15 | 32.768 | 22.897 | 3.608 | 19.289 | 0.698761 | 0.110107 | 0.588654 | 1.999214 | 1.853107 | 2.029140 |
16 | 65.536 | 45.770 | 6.719 | 39.051 | 0.698395 | 0.102524 | 0.595871 | 1.998952 | 1.862251 | 2.024522 |
17 | 131.072 | 91.494 | 12.549 | 78.945 | 0.698044 | 0.095741 | 0.602303 | 1.998995 | 1.867689 | 2.021587 |
18 | 262.144 | 182.889 | 23.718 | 159.171 | 0.697666 | 0.090477 | 0.607189 | 1.998918 | 1.890031 | 2.016227 |
19 | 524.288 | 365.771 | 44.451 | 321.320 | 0.697653 | 0.084784 | 0.612869 | 1.999962 | 1.874146 | 2.018709 |
20 | 1.048.576 | 730.979 | 84.356 | 646.623 | 0.697116 | 0.080448 | 0.616668 | 1.998461 | 1.897730 | 2.012396 |
21 | 2.097.152 | 1.461.557 | 159.681 | 1.301.876 | 0.696925 | 0.076142 | 0.620783 | 1.999451 | 1.892942 | 2.013346 |
22 | 4.194.304 | 2.921.849 | 303.389 | 2.618.460 | 0.696623 | 0.072334 | 0.624290 | 1.999135 | 1.899969 | 2.011297 |
23 | 8.388.608 | 5.842.743 | 577.482 | 5.265.261 | 0.696509 | 0.068841 | 0.627668 | 1.999673 | 1.903437 | 2.010823 |
24 | 16.777.216 | 11.681.816 | 1.103.045 | 10.578.771 | 0.696290 | 0.065747 | 0.630544 | 1.999372 | 1.910094 | 2.009164 |
25 | 33.554.432 | 23.359.005 | 2.109.856 | 21.249.149 | 0.696153 | 0.062879 | 0.633274 | 1.999604 | 1.912756 | 2.008659 |
26 | 67.108.864 | 46.706.590 | 4.045.216 | 42.661.374 | 0.695982 | 0.060278 | 0.635704 | 1.999511 | 1.917295 | 2.007675 |
27 | 134.217.728 | 93.387.740 | 7.773.644 | 85.614.096 | 0.695793 | 0.057918 | 0.637875 | 1.999455 | 1.921688 | 2.006829 |
28 | 268.435.456 | 186.742.616 | 14.951.749 | 171.790.867 | 0.695670 | 0.055700 | 0.639971 | 1.999648 | 1.923390 | 2.006572 |
29 | 536.870.912 | 373.416.903 | 28.808.218 | 344.608.685 | 0.695543 | 0.053659 | 0.641884 | 1.999634 | 1.926746 | 2.005978 |
30 | 1.073.741.824 | 746.704.393 | 55.584.617 | 691.119.776 | 0.695423 | 0.051767 | 0.643655 | 1.999653 | 1.929471 | 2.005521 |
31 | 2.147.483.648 | 1.493.187.103 | 107.391.227 | 1.385.795.876 | 0.695319 | 0.050008 | 0.645311 | 1.999703 | 1.932031 | 2.005146 |
32 | 4.294.967.296 | 2.985.943.588 | 207.709.972 | 2.778.233.616 | 0.695219 | 0.048361 | 0.646858 | 1.999712 | 1.934143 | 2.004793 |
33 | 8.589.934.592 | 5.971.110.250 | 402.206.534 | 5.568.903.716 | 0.695129 | 0.046823 | 0.648306 | 1.999740 | 1.936385 | 2.004476 |
34 | 17.179.869.184 | 11.940.785.821 | 779.589.842 | 11.161.195.979 | 0.695045 | 0.045378 | 0.649667 | 1.999760 | 1.938282 | 2.004200 |
35 | 34.359.738.368 | 23.878.920.270 | 1.512.520.615 | 22.366.399.655 | 0.694968 | 0.044020 | 0.650948 | 1.999778 | 1.940149 | 2.003943 |
36 | 68.719.476.736 | 47.752.942.978 | 2.937.082.486 | 44.815.860.492 | 0.694897 | 0.042740 | 0.652157 | 1.999795 | 1.941846 | 2.003714 |
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 | 1 | 0 | 1 | 1 |
2 | 4 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
3 | 8 | 6 | 3 | 3 | 2 | 1 | 2 | 1 |
4 | 16 | 9 | 3 | 6 | 2 | 1 | 4 | 2 |
5 | 32 | 15 | 5 | 10 | 3 | 3 | 5 | 4 |
6 | 64 | 20 | 7 | 13 | 3 | 4 | 6 | 7 |
7 | 128 | 34 | 12 | 22 | 8 | 7 | 9 | 10 |
8 | 256 | 61 | 19 | 42 | 13 | 14 | 17 | 17 |
9 | 512 | 107 | 35 | 72 | 23 | 27 | 30 | 27 |
10 | 1.024 | 181 | 54 | 127 | 45 | 44 | 46 | 46 |
11 | 2.048 | 322 | 100 | 222 | 83 | 84 | 81 | 74 |
12 | 4.096 | 585 | 192 | 393 | 150 | 153 | 143 | 139 |
13 | 8.192 | 1.083 | 361 | 722 | 264 | 286 | 275 | 258 |
14 | 16.384 | 1.947 | 655 | 1.292 | 476 | 507 | 497 | 467 |
15 | 32.768 | 3.608 | 1.225 | 2.383 | 892 | 932 | 908 | 876 |
16 | 65.536 | 6.719 | 2.294 | 4.425 | 1.646 | 1.715 | 1.688 | 1.670 |
17 | 131.072 | 12.549 | 4.219 | 8.330 | 3.100 | 3.169 | 3.135 | 3.145 |
18 | 262.144 | 23.718 | 7.909 | 15.809 | 5.901 | 5.979 | 5.913 | 5.925 |
19 | 524.288 | 44.451 | 14.761 | 29.690 | 11.078 | 11.152 | 11.075 | 11.146 |
20 | 1.048.576 | 84.356 | 28.112 | 56.244 | 21.105 | 21.065 | 21.042 | 21.144 |
21 | 2.097.152 | 159.681 | 53.260 | 106.421 | 39.900 | 39.968 | 39.864 | 39.949 |
22 | 4.194.304 | 303.389 | 100.953 | 202.436 | 75.803 | 75.898 | 75.756 | 75.932 |
23 | 8.388.608 | 577.482 | 192.389 | 385.093 | 144.329 | 144.372 | 144.363 | 144.418 |
24 | 16.777.216 | 1.103.045 | 367.740 | 735.305 | 275.456 | 275.703 | 275.790 | 276.096 |
25 | 33.554.432 | 2.109.856 | 703.053 | 1.406.803 | 527.025 | 527.830 | 527.478 | 527.523 |
26 | 67.108.864 | 4.045.216 | 1.347.820 | 2.697.396 | 1.010.981 | 1.012.058 | 1.011.393 | 1.010.784 |
27 | 134.217.728 | 7.773.644 | 2.592.172 | 5.181.472 | 1.942.263 | 1.944.612 | 1.944.186 | 1.942.583 |
28 | 268.435.456 | 14.951.749 | 4.984.964 | 9.966.785 | 3.735.962 | 3.739.403 | 3.739.194 | 3.737.190 |
29 | 536.870.912 | 28.808.218 | 9.602.297 | 19.205.921 | 7.200.455 | 7.203.795 | 7.202.200 | 7.201.768 |
30 | 1.073.741.824 | 55.584.617 | 18.525.903 | 37.058.714 | 13.895.409 | 13.898.719 | 13.893.900 | 13.896.589 |
31 | 2.147.483.648 | 107.391.227 | 35.793.614 | 71.597.613 | 26.848.178 | 26.849.256 | 26.844.676 | 26.849.117 |
32 | 4.294.967.296 | 207.709.972 | 69.237.071 | 138.472.901 | 51.931.178 | 51.923.415 | 51.924.340 | 51.931.039 |
33 | 8.589.934.592 | 402.206.534 | 134.068.007 | 268.138.527 | 100.551.193 | 100.553.365 | 100.551.087 | 100.550.889 |
34 | 17.179.869.184 | 779.589.842 | 259.865.861 | 519.723.981 | 194.897.013 | 194.891.759 | 194.901.029 | 194.900.041 |
35 | 34.359.738.368 | 1.512.520.615 | 504.183.156 | 1.008.337.459 | 378.124.337 | 378.143.849 | 378.115.116 | 378.137.313 |
36 | 68.719.476.736 | 2.937.082.486 | 979.027.304 | 1.958.055.182 | 734.263.056 | 734.288.582 | 734.250.464 | 734.280.384 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 0 | 0 | 2 | 1 |
5 | 32 | 6 | 3 | 3 | 0 | 1 | 2 | 3 |
6 | 64 | 21 | 10 | 11 | 2 | 6 | 6 | 7 |
7 | 128 | 53 | 25 | 28 | 12 | 17 | 12 | 12 |
8 | 256 | 114 | 53 | 61 | 28 | 30 | 28 | 28 |
9 | 512 | 249 | 131 | 118 | 56 | 70 | 64 | 59 |
10 | 1.024 | 536 | 281 | 255 | 131 | 143 | 124 | 138 |
11 | 2.048 | 1.115 | 570 | 545 | 280 | 287 | 268 | 280 |
12 | 4.096 | 2.282 | 1.174 | 1.108 | 569 | 567 | 567 | 579 |
13 | 8.192 | 4.634 | 2.365 | 2.269 | 1.138 | 1.164 | 1.149 | 1.183 |
14 | 16.384 | 9.506 | 4.863 | 4.643 | 2.334 | 2.396 | 2.370 | 2.406 |
15 | 32.768 | 19.289 | 9.772 | 9.517 | 4.785 | 4.829 | 4.818 | 4.857 |
16 | 65.536 | 39.051 | 19.814 | 19.237 | 9.742 | 9.752 | 9.762 | 9.795 |
17 | 131.072 | 78.945 | 40.030 | 38.915 | 19.793 | 19.768 | 19.641 | 19.743 |
18 | 262.144 | 159.171 | 80.480 | 78.691 | 39.927 | 39.671 | 39.742 | 39.831 |
19 | 524.288 | 321.320 | 162.798 | 158.522 | 80.487 | 80.505 | 80.140 | 80.188 |
20 | 1.048.576 | 646.623 | 327.146 | 319.477 | 161.854 | 161.846 | 161.207 | 161.716 |
21 | 2.097.152 | 1.301.876 | 658.426 | 643.450 | 325.465 | 325.600 | 325.029 | 325.782 |
22 | 4.194.304 | 2.618.460 | 1.322.497 | 1.295.963 | 654.334 | 655.005 | 654.292 | 654.829 |
23 | 8.388.608 | 5.265.261 | 2.657.249 | 2.608.012 | 1.315.727 | 1.316.277 | 1.316.544 | 1.316.713 |
24 | 16.777.216 | 10.578.771 | 5.335.503 | 5.243.268 | 2.645.723 | 2.644.320 | 2.643.547 | 2.645.181 |
25 | 33.554.432 | 21.249.149 | 10.716.140 | 10.533.009 | 5.312.949 | 5.311.569 | 5.311.397 | 5.313.234 |
26 | 67.108.864 | 42.661.374 | 21.505.780 | 21.155.594 | 10.664.008 | 10.664.779 | 10.666.122 | 10.666.465 |
27 | 134.217.728 | 85.614.096 | 43.147.289 | 42.466.807 | 21.401.428 | 21.400.544 | 21.408.059 | 21.404.065 |
28 | 268.435.456 | 171.790.867 | 86.544.153 | 85.246.714 | 42.941.357 | 42.947.897 | 42.952.198 | 42.949.415 |
29 | 536.870.912 | 344.608.685 | 173.549.561 | 171.059.124 | 86.136.184 | 86.159.786 | 86.154.833 | 86.157.882 |
30 | 1.073.741.824 | 691.119.776 | 347.977.507 | 343.142.269 | 172.766.914 | 172.784.751 | 172.777.362 | 172.790.749 |
31 | 2.147.483.648 | 1.385.795.876 | 697.581.724 | 688.214.152 | 346.429.438 | 346.468.228 | 346.440.597 | 346.457.613 |
32 | 4.294.967.296 | 2.778.233.616 | 1.398.159.659 | 1.380.073.957 | 694.516.379 | 694.582.820 | 694.550.513 | 694.583.904 |
33 | 8.589.934.592 | 5.568.903.716 | 2.801.932.027 | 2.766.971.689 | 1.392.219.074 | 1.392.229.444 | 1.392.234.871 | 1.392.220.327 |
34 | 17.179.869.184 | 11.161.195.979 | 5.614.488.814 | 5.546.707.165 | 2.790.347.904 | 2.790.261.970 | 2.790.321.917 | 2.790.264.188 |
35 | 34.359.738.368 | 22.366.399.655 | 11.248.808.534 | 11.117.591.121 | 5.591.666.315 | 5.591.566.125 | 5.591.681.630 | 5.591.485.585 |
36 | 68.719.476.736 | 44.815.860.492 | 22.535.223.690 | 22.280.636.802 | 11.204.021.672 | 11.203.945.302 | 11.204.055.237 | 11.203.838.281 |