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+8x+47
f(0)=47
f(1)=7
f(2)=67
f(3)=5
f(4)=19
f(5)=1
f(6)=131
f(7)=1
f(8)=1
f(9)=1
f(10)=227
f(11)=1
f(12)=41
f(13)=1
f(14)=71
f(15)=1
f(16)=431
f(17)=59
f(18)=103
f(19)=1
f(20)=607
f(21)=1
f(22)=101
f(23)=1
f(24)=163
f(25)=109
f(26)=1
f(27)=31
f(28)=211
f(29)=1
f(30)=1187
f(31)=157
f(32)=1327
f(33)=1
f(34)=1
f(35)=97
f(36)=233
f(37)=107
f(38)=359
f(39)=1
f(40)=281
f(41)=257
f(42)=113
f(43)=1
f(44)=467
f(45)=1
f(46)=2531
f(47)=1
f(48)=547
f(49)=1
f(50)=421
f(51)=191
f(52)=3167
f(53)=1
f(54)=1
f(55)=439
f(56)=3631
f(57)=1
f(58)=1
f(59)=1
f(60)=4127
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=599
f(66)=4931
f(67)=317
f(68)=149
f(69)=1
f(70)=5507
f(71)=1
f(72)=5807
f(73)=1
f(74)=1223
f(75)=1
f(76)=1
f(77)=1
f(78)=193
f(79)=173
f(80)=373
f(81)=907
f(82)=1061
f(83)=1
f(84)=311
f(85)=1
f(86)=1
f(87)=1039
f(88)=1699
f(89)=1
f(90)=8867
f(91)=283
f(92)=1321
f(93)=1
f(94)=1
f(95)=1229
f(96)=1433
f(97)=1279
f(98)=2087
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+8x+47 could be written as f(y)= y^2+31 with x=y-4
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
f'(x)>2x+7
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 | 6 | 5 | 1 | 0.600000 | 0.500000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 33 | 25 | 0.580000 | 0.330000 | 0.250000 | 9.666667 | 6.600000 | 25.000000 |
3 | 1.000 | 630 | 238 | 392 | 0.630000 | 0.238000 | 0.392000 | 10.862069 | 7.212121 | 15.680000 |
4 | 10.000 | 6.451 | 1.666 | 4.785 | 0.645100 | 0.166600 | 0.478500 | 10.239682 | 7.000000 | 12.206633 |
5 | 100.000 | 65.604 | 12.800 | 52.804 | 0.656040 | 0.128000 | 0.528040 | 10.169586 | 7.683073 | 11.035318 |
6 | 1.000.000 | 662.506 | 103.189 | 559.317 | 0.662506 | 0.103189 | 0.559317 | 10.098561 | 8.061641 | 10.592322 |
7 | 10.000.000 | 6.669.923 | 862.123 | 5.807.800 | 0.666992 | 0.086212 | 0.580780 | 10.067718 | 8.354795 | 10.383736 |
8 | 100.000.000 | 67.027.665 | 7.423.309 | 59.604.356 | 0.670277 | 0.074233 | 0.596044 | 10.049241 | 8.610498 | 10.262812 |
9 | 1.000.000.000 | 672.816.440 | 65.138.106 | 607.678.334 | 0.672816 | 0.065138 | 0.607678 | 10.037892 | 8.774807 | 10.195200 |
10 | 10.000.000.000 | 6.748.432.824 | 580.419.373 | 6.168.013.451 | 0.674843 | 0.058042 | 0.616801 | 10.030125 | 8.910597 | 10.150128 |
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 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.000000 | inf |
3 | 8 | 5 | 4 | 1 | 0.625000 | 0.500000 | 0.125000 | 1.250000 | 1.333333 | 1.000000 |
4 | 16 | 9 | 6 | 3 | 0.562500 | 0.375000 | 0.187500 | 1.800000 | 1.500000 | 3.000000 |
5 | 32 | 19 | 12 | 7 | 0.593750 | 0.375000 | 0.218750 | 2.111111 | 2.000000 | 2.333333 |
6 | 64 | 35 | 21 | 14 | 0.546875 | 0.328125 | 0.218750 | 1.842105 | 1.750000 | 2.000000 |
7 | 128 | 76 | 42 | 34 | 0.593750 | 0.328125 | 0.265625 | 2.171429 | 2.000000 | 2.428571 |
8 | 256 | 150 | 77 | 73 | 0.585938 | 0.300781 | 0.285156 | 1.973684 | 1.833333 | 2.147059 |
9 | 512 | 309 | 138 | 171 | 0.603516 | 0.269531 | 0.333984 | 2.060000 | 1.792208 | 2.342466 |
10 | 1.024 | 642 | 242 | 400 | 0.626953 | 0.236328 | 0.390625 | 2.077670 | 1.753623 | 2.339181 |
11 | 2.048 | 1.291 | 438 | 853 | 0.630371 | 0.213867 | 0.416504 | 2.010903 | 1.809917 | 2.132500 |
12 | 4.096 | 2.610 | 774 | 1.836 | 0.637207 | 0.188965 | 0.448242 | 2.021689 | 1.767123 | 2.152403 |
13 | 8.192 | 5.279 | 1.393 | 3.886 | 0.644409 | 0.170044 | 0.474365 | 2.022605 | 1.799742 | 2.116558 |
14 | 16.384 | 10.617 | 2.560 | 8.057 | 0.648010 | 0.156250 | 0.491760 | 2.011176 | 1.837760 | 2.073340 |
15 | 32.768 | 21.384 | 4.721 | 16.663 | 0.652588 | 0.144073 | 0.508514 | 2.014128 | 1.844141 | 2.068140 |
16 | 65.536 | 42.900 | 8.797 | 34.103 | 0.654602 | 0.134232 | 0.520370 | 2.006173 | 1.863376 | 2.046630 |
17 | 131.072 | 86.114 | 16.321 | 69.793 | 0.656998 | 0.124519 | 0.532478 | 2.007319 | 1.855292 | 2.046535 |
18 | 262.144 | 172.758 | 30.586 | 142.172 | 0.659019 | 0.116676 | 0.542343 | 2.006155 | 1.874027 | 2.037052 |
19 | 524.288 | 346.607 | 57.197 | 289.410 | 0.661100 | 0.109095 | 0.552006 | 2.006315 | 1.870039 | 2.035633 |
20 | 1.048.576 | 694.863 | 107.736 | 587.127 | 0.662673 | 0.102745 | 0.559928 | 2.004758 | 1.883595 | 2.028703 |
21 | 2.097.152 | 1.392.743 | 203.432 | 1.189.311 | 0.664112 | 0.097004 | 0.567108 | 2.004342 | 1.888245 | 2.025645 |
22 | 4.194.304 | 2.791.329 | 385.490 | 2.405.839 | 0.665505 | 0.091908 | 0.573597 | 2.004195 | 1.894933 | 2.022885 |
23 | 8.388.608 | 5.593.061 | 732.569 | 4.860.492 | 0.666745 | 0.087329 | 0.579416 | 2.003727 | 1.900358 | 2.020290 |
24 | 16.777.216 | 11.204.512 | 1.395.899 | 9.808.613 | 0.667841 | 0.083202 | 0.584639 | 2.003288 | 1.905485 | 2.018029 |
25 | 33.554.432 | 22.441.609 | 2.666.642 | 19.774.967 | 0.668812 | 0.079472 | 0.589340 | 2.002908 | 1.910340 | 2.016082 |
26 | 67.108.864 | 44.946.017 | 5.103.614 | 39.842.403 | 0.669748 | 0.076050 | 0.593698 | 2.002798 | 1.913873 | 2.014790 |
27 | 134.217.728 | 90.010.728 | 9.788.061 | 80.222.667 | 0.670632 | 0.072927 | 0.597705 | 2.002641 | 1.917869 | 2.013499 |
28 | 268.435.456 | 180.239.643 | 18.796.445 | 161.443.198 | 0.671445 | 0.070022 | 0.601423 | 2.002424 | 1.920344 | 2.012439 |
29 | 536.870.912 | 360.875.951 | 36.164.393 | 324.711.558 | 0.672184 | 0.067361 | 0.604822 | 2.002201 | 1.924002 | 2.011305 |
30 | 1.073.741.824 | 722.503.498 | 69.678.394 | 652.825.104 | 0.672884 | 0.064893 | 0.607991 | 2.002083 | 1.926713 | 2.010477 |
31 | 2.147.483.648 | 1.446.402.787 | 134.426.042 | 1.311.976.745 | 0.673534 | 0.062597 | 0.610937 | 2.001932 | 1.929236 | 2.009691 |
32 | 4.294.967.296 | 2.895.433.388 | 259.660.409 | 2.635.772.979 | 0.674146 | 0.060457 | 0.613689 | 2.001817 | 1.931623 | 2.009009 |
33 | 8.589.934.592 | 5.795.816.032 | 502.192.104 | 5.293.623.928 | 0.674722 | 0.058463 | 0.616259 | 2.001709 | 1.934034 | 2.008376 |
34 | 17.179.869.184 | 11.600.906.752 | 972.300.136 | 10.628.606.616 | 0.675262 | 0.056595 | 0.618666 | 2.001600 | 1.936112 | 2.007813 |
35 | 34.359.738.368 | 23.219.315.838 | 1.884.462.397 | 21.334.853.441 | 0.675771 | 0.054845 | 0.620926 | 2.001509 | 1.938149 | 2.007305 |
36 | 68.719.476.736 | 46.471.741.440 | 3.655.795.648 | 42.815.945.792 | 0.676253 | 0.053199 | 0.623054 | 2.001426 | 1.939968 | 2.006855 |
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 | 2 | 1 | 0 | 1 | 0 | 2 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 0 | 2 |
3 | 8 | 4 | 2 | 2 | 0 | 2 | 0 | 2 |
4 | 16 | 6 | 2 | 4 | 0 | 3 | 0 | 3 |
5 | 32 | 12 | 6 | 6 | 0 | 5 | 2 | 5 |
6 | 64 | 21 | 9 | 12 | 2 | 7 | 2 | 10 |
7 | 128 | 42 | 18 | 24 | 5 | 15 | 4 | 18 |
8 | 256 | 77 | 32 | 45 | 6 | 33 | 8 | 30 |
9 | 512 | 138 | 60 | 78 | 15 | 53 | 16 | 54 |
10 | 1.024 | 242 | 106 | 136 | 34 | 97 | 28 | 83 |
11 | 2.048 | 438 | 192 | 246 | 59 | 169 | 56 | 154 |
12 | 4.096 | 774 | 358 | 416 | 106 | 292 | 104 | 272 |
13 | 8.192 | 1.393 | 635 | 758 | 194 | 517 | 188 | 494 |
14 | 16.384 | 2.560 | 1.138 | 1.422 | 363 | 939 | 341 | 917 |
15 | 32.768 | 4.721 | 2.119 | 2.602 | 649 | 1.709 | 645 | 1.718 |
16 | 65.536 | 8.797 | 3.940 | 4.857 | 1.155 | 3.215 | 1.218 | 3.209 |
17 | 131.072 | 16.321 | 7.322 | 8.999 | 2.174 | 5.949 | 2.227 | 5.971 |
18 | 262.144 | 30.586 | 13.728 | 16.858 | 4.025 | 11.180 | 4.093 | 11.288 |
19 | 524.288 | 57.197 | 25.691 | 31.506 | 7.519 | 21.056 | 7.639 | 20.983 |
20 | 1.048.576 | 107.736 | 48.350 | 59.386 | 14.269 | 39.576 | 14.334 | 39.557 |
21 | 2.097.152 | 203.432 | 91.350 | 112.082 | 26.702 | 74.827 | 26.929 | 74.974 |
22 | 4.194.304 | 385.490 | 173.191 | 212.299 | 50.579 | 142.029 | 50.763 | 142.119 |
23 | 8.388.608 | 732.569 | 329.435 | 403.134 | 95.795 | 269.720 | 96.393 | 270.661 |
24 | 16.777.216 | 1.395.899 | 627.086 | 768.813 | 182.474 | 515.000 | 182.920 | 515.505 |
25 | 33.554.432 | 2.666.642 | 1.197.424 | 1.469.218 | 348.219 | 984.322 | 348.701 | 985.400 |
26 | 67.108.864 | 5.103.614 | 2.290.129 | 2.813.485 | 664.968 | 1.886.764 | 665.435 | 1.886.447 |
27 | 134.217.728 | 9.788.061 | 4.388.688 | 5.399.373 | 1.273.765 | 3.620.322 | 1.274.640 | 3.619.334 |
28 | 268.435.456 | 18.796.445 | 8.423.455 | 10.372.990 | 2.443.391 | 6.955.539 | 2.443.452 | 6.954.063 |
29 | 536.870.912 | 36.164.393 | 16.199.768 | 19.964.625 | 4.693.564 | 13.387.188 | 4.693.361 | 13.390.280 |
30 | 1.073.741.824 | 69.678.394 | 31.205.932 | 38.472.462 | 9.031.283 | 25.804.933 | 9.031.005 | 25.811.173 |
31 | 2.147.483.648 | 134.426.042 | 60.184.281 | 74.241.761 | 17.403.154 | 49.810.771 | 17.401.747 | 49.810.370 |
32 | 4.294.967.296 | 259.660.409 | 116.225.859 | 143.434.550 | 33.578.234 | 96.256.599 | 33.573.490 | 96.252.086 |
33 | 8.589.934.592 | 502.192.104 | 224.725.193 | 277.466.911 | 64.863.894 | 186.230.296 | 64.864.613 | 186.233.301 |
34 | 17.179.869.184 | 972.300.136 | 434.989.666 | 537.310.470 | 125.450.298 | 360.700.282 | 125.453.973 | 360.695.583 |
35 | 34.359.738.368 | 1.884.462.397 | 842.904.274 | 1.041.558.123 | 242.890.081 | 699.335.936 | 242.897.822 | 699.338.558 |
36 | 68.719.476.736 | 3.655.795.648 | 1.634.893.116 | 2.020.902.532 | 470.768.551 | 1.357.132.842 | 470.781.650 | 1.357.112.605 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
5 | 32 | 7 | 4 | 3 | 1 | 3 | 1 | 2 |
6 | 64 | 14 | 6 | 8 | 4 | 5 | 2 | 3 |
7 | 128 | 34 | 14 | 20 | 8 | 10 | 8 | 8 |
8 | 256 | 73 | 34 | 39 | 16 | 20 | 22 | 15 |
9 | 512 | 171 | 95 | 76 | 42 | 42 | 44 | 43 |
10 | 1.024 | 400 | 208 | 192 | 101 | 93 | 104 | 102 |
11 | 2.048 | 853 | 440 | 413 | 217 | 212 | 212 | 212 |
12 | 4.096 | 1.836 | 924 | 912 | 469 | 453 | 473 | 441 |
13 | 8.192 | 3.886 | 1.953 | 1.933 | 957 | 977 | 998 | 954 |
14 | 16.384 | 8.057 | 4.115 | 3.942 | 2.055 | 1.979 | 2.047 | 1.976 |
15 | 32.768 | 16.663 | 8.463 | 8.200 | 4.189 | 4.083 | 4.247 | 4.144 |
16 | 65.536 | 34.103 | 17.239 | 16.864 | 8.528 | 8.445 | 8.662 | 8.468 |
17 | 131.072 | 69.793 | 35.085 | 34.708 | 17.416 | 17.325 | 17.669 | 17.383 |
18 | 262.144 | 142.172 | 71.592 | 70.580 | 35.618 | 35.299 | 35.807 | 35.448 |
19 | 524.288 | 289.410 | 145.625 | 143.785 | 72.909 | 71.561 | 72.697 | 72.243 |
20 | 1.048.576 | 587.127 | 295.237 | 291.890 | 147.612 | 145.884 | 147.537 | 146.094 |
21 | 2.097.152 | 1.189.311 | 597.810 | 591.501 | 298.817 | 295.600 | 299.184 | 295.710 |
22 | 4.194.304 | 2.405.839 | 1.209.394 | 1.196.445 | 605.060 | 597.275 | 605.629 | 597.875 |
23 | 8.388.608 | 4.860.492 | 2.439.860 | 2.420.632 | 1.222.845 | 1.207.355 | 1.221.669 | 1.208.623 |
24 | 16.777.216 | 9.808.613 | 4.922.686 | 4.885.927 | 2.465.664 | 2.436.947 | 2.465.981 | 2.440.021 |
25 | 33.554.432 | 19.774.967 | 9.920.505 | 9.854.462 | 4.967.837 | 4.916.758 | 4.971.526 | 4.918.846 |
26 | 67.108.864 | 39.842.403 | 19.985.841 | 19.856.562 | 10.007.567 | 9.911.252 | 10.010.238 | 9.913.346 |
27 | 134.217.728 | 80.222.667 | 40.239.141 | 39.983.526 | 20.146.771 | 19.965.043 | 20.148.123 | 19.962.730 |
28 | 268.435.456 | 161.443.198 | 80.969.380 | 80.473.818 | 40.534.653 | 40.189.464 | 40.533.636 | 40.185.445 |
29 | 536.870.912 | 324.711.558 | 162.829.427 | 161.882.131 | 81.510.944 | 80.854.144 | 81.505.818 | 80.840.652 |
30 | 1.073.741.824 | 652.825.104 | 327.330.841 | 325.494.263 | 163.842.873 | 162.571.674 | 163.852.783 | 162.557.774 |
31 | 2.147.483.648 | 1.311.976.745 | 657.767.620 | 654.209.125 | 329.220.844 | 326.779.903 | 329.203.423 | 326.772.575 |
32 | 4.294.967.296 | 2.635.772.979 | 1.321.329.879 | 1.314.443.100 | 661.297.527 | 656.601.235 | 661.286.527 | 656.587.690 |
33 | 8.589.934.592 | 5.293.623.928 | 2.653.480.479 | 2.640.143.449 | 1.327.913.678 | 1.318.889.345 | 1.327.902.520 | 1.318.918.385 |
34 | 17.179.869.184 | 10.628.606.616 | 5.327.228.550 | 5.301.378.066 | 2.665.800.228 | 2.648.462.851 | 2.665.853.259 | 2.648.490.278 |
35 | 34.359.738.368 | 21.334.853.441 | 10.692.365.686 | 10.642.487.755 | 5.350.326.399 | 5.317.040.323 | 5.350.497.840 | 5.316.988.879 |
36 | 68.719.476.736 | 42.815.945.792 | 21.456.336.468 | 21.359.609.324 | 10.736.065.647 | 10.671.790.945 | 10.736.228.131 | 10.671.861.069 |