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+19x-7
f(0)=7
f(1)=13
f(2)=5
f(3)=59
f(4)=17
f(5)=113
f(6)=11
f(7)=1
f(8)=19
f(9)=1
f(10)=283
f(11)=1
f(12)=73
f(13)=409
f(14)=1
f(15)=503
f(16)=79
f(17)=1
f(18)=659
f(19)=1
f(20)=773
f(21)=1
f(22)=179
f(23)=137
f(24)=41
f(25)=1093
f(26)=1163
f(27)=1
f(28)=1
f(29)=277
f(30)=1
f(31)=1543
f(32)=1
f(33)=1709
f(34)=359
f(35)=269
f(36)=1973
f(37)=1
f(38)=127
f(39)=1
f(40)=181
f(41)=223
f(42)=1
f(43)=2659
f(44)=1
f(45)=1
f(46)=157
f(47)=619
f(48)=3209
f(49)=1
f(50)=313
f(51)=509
f(52)=67
f(53)=293
f(54)=787
f(55)=239
f(56)=599
f(57)=173
f(58)=1
f(59)=919
f(60)=4733
f(61)=443
f(62)=1
f(63)=1
f(64)=1061
f(65)=1
f(66)=431
f(67)=1151
f(68)=311
f(69)=1213
f(70)=1
f(71)=491
f(72)=1
f(73)=6709
f(74)=1
f(75)=7043
f(76)=7213
f(77)=211
f(78)=7559
f(79)=1
f(80)=193
f(81)=8093
f(82)=331
f(83)=769
f(84)=1
f(85)=1
f(86)=1289
f(87)=97
f(88)=1
f(89)=1
f(90)=9803
f(91)=1429
f(92)=1
f(93)=1487
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1637
f(99)=467
b) Substitution of the polynom
The polynom f(x)=x^2+19x-7 could be written as f(y)= y^2-97.25 with x=y-9.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+9.5
f'(x)>2x+18
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 | 5 | 3 | 0.800000 | 0.500000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 63 | 23 | 40 | 0.630000 | 0.230000 | 0.400000 | 7.875000 | 4.600000 | 13.333333 |
3 | 1.000 | 672 | 150 | 522 | 0.672000 | 0.150000 | 0.522000 | 10.666667 | 6.521739 | 13.050000 |
4 | 10.000 | 6.787 | 1.035 | 5.752 | 0.678700 | 0.103500 | 0.575200 | 10.099703 | 6.900000 | 11.019157 |
5 | 100.000 | 68.259 | 8.072 | 60.187 | 0.682590 | 0.080720 | 0.601870 | 10.057316 | 7.799034 | 10.463665 |
6 | 1.000.000 | 684.385 | 66.248 | 618.137 | 0.684385 | 0.066248 | 0.618137 | 10.026297 | 8.207136 | 10.270274 |
7 | 10.000.000 | 6.855.795 | 559.900 | 6.295.895 | 0.685579 | 0.055990 | 0.629589 | 10.017453 | 8.451576 | 10.185274 |
8 | 100.000.000 | 68.637.084 | 4.856.080 | 63.781.004 | 0.686371 | 0.048561 | 0.637810 | 10.011543 | 8.673120 | 10.130569 |
9 | 1.000.000.000 | 687.031.870 | 42.874.585 | 644.157.285 | 0.687032 | 0.042875 | 0.644157 | 10.009630 | 8.829052 | 10.099517 |
10 | 10.000.000.000 | 6.875.742.258 | 383.734.460 | 6.492.007.798 | 0.687574 | 0.038373 | 0.649201 | 10.007895 | 8.950162 | 10.078296 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.400000 | 1.333333 | 1.500000 |
4 | 16 | 12 | 7 | 5 | 0.750000 | 0.437500 | 0.312500 | 1.714286 | 1.750000 | 1.666667 |
5 | 32 | 20 | 12 | 8 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.714286 | 1.600000 |
6 | 64 | 42 | 17 | 25 | 0.656250 | 0.265625 | 0.390625 | 2.100000 | 1.416667 | 3.125000 |
7 | 128 | 82 | 27 | 55 | 0.640625 | 0.210938 | 0.429688 | 1.952381 | 1.588235 | 2.200000 |
8 | 256 | 170 | 49 | 121 | 0.664062 | 0.191406 | 0.472656 | 2.073171 | 1.814815 | 2.200000 |
9 | 512 | 342 | 91 | 251 | 0.667969 | 0.177734 | 0.490234 | 2.011765 | 1.857143 | 2.074380 |
10 | 1.024 | 691 | 153 | 538 | 0.674805 | 0.149414 | 0.525391 | 2.020468 | 1.681319 | 2.143426 |
11 | 2.048 | 1.384 | 258 | 1.126 | 0.675781 | 0.125977 | 0.549805 | 2.002894 | 1.686275 | 2.092937 |
12 | 4.096 | 2.770 | 476 | 2.294 | 0.676270 | 0.116211 | 0.560059 | 2.001445 | 1.844961 | 2.037300 |
13 | 8.192 | 5.573 | 869 | 4.704 | 0.680298 | 0.106079 | 0.574219 | 2.011913 | 1.825630 | 2.050567 |
14 | 16.384 | 11.138 | 1.591 | 9.547 | 0.679810 | 0.097107 | 0.582703 | 1.998564 | 1.830840 | 2.029549 |
15 | 32.768 | 22.297 | 2.957 | 19.340 | 0.680450 | 0.090240 | 0.590210 | 2.001885 | 1.858580 | 2.025767 |
16 | 65.536 | 44.699 | 5.515 | 39.184 | 0.682053 | 0.084152 | 0.597900 | 2.004709 | 1.865066 | 2.026060 |
17 | 131.072 | 89.588 | 10.366 | 79.222 | 0.683502 | 0.079086 | 0.604416 | 2.004251 | 1.879601 | 2.021795 |
18 | 262.144 | 179.110 | 19.482 | 159.628 | 0.683250 | 0.074318 | 0.608932 | 1.999263 | 1.879413 | 2.014945 |
19 | 524.288 | 358.575 | 36.493 | 322.082 | 0.683928 | 0.069605 | 0.614323 | 2.001982 | 1.873165 | 2.017704 |
20 | 1.048.576 | 717.805 | 69.176 | 648.629 | 0.684552 | 0.065971 | 0.618581 | 2.001827 | 1.895596 | 2.013863 |
21 | 2.097.152 | 1.436.399 | 131.044 | 1.305.355 | 0.684928 | 0.062487 | 0.622442 | 2.001099 | 1.894356 | 2.012483 |
22 | 4.194.304 | 2.873.956 | 249.767 | 2.624.189 | 0.685205 | 0.059549 | 0.625655 | 2.000806 | 1.905978 | 2.010326 |
23 | 8.388.608 | 5.751.090 | 475.273 | 5.275.817 | 0.685583 | 0.056657 | 0.628926 | 2.001106 | 1.902866 | 2.010456 |
24 | 16.777.216 | 11.505.597 | 908.188 | 10.597.409 | 0.685787 | 0.054132 | 0.631655 | 2.000594 | 1.910877 | 2.008676 |
25 | 33.554.432 | 23.018.743 | 1.740.446 | 21.278.297 | 0.686012 | 0.051869 | 0.634143 | 2.000656 | 1.916394 | 2.007877 |
26 | 67.108.864 | 46.053.053 | 3.336.837 | 42.716.216 | 0.686244 | 0.049723 | 0.636521 | 2.000676 | 1.917231 | 2.007502 |
27 | 134.217.728 | 92.136.230 | 6.408.931 | 85.727.299 | 0.686468 | 0.047750 | 0.638718 | 2.000654 | 1.920660 | 2.006903 |
28 | 268.435.456 | 184.328.659 | 12.333.025 | 171.995.634 | 0.686678 | 0.045944 | 0.640734 | 2.000610 | 1.924350 | 2.006311 |
29 | 536.870.912 | 368.761.981 | 23.768.117 | 344.993.864 | 0.686873 | 0.044272 | 0.642601 | 2.000568 | 1.927193 | 2.005829 |
30 | 1.073.741.824 | 737.720.502 | 45.869.981 | 691.850.521 | 0.687056 | 0.042720 | 0.644336 | 2.000533 | 1.929896 | 2.005399 |
31 | 2.147.483.648 | 1.475.811.881 | 88.630.354 | 1.387.181.527 | 0.687228 | 0.041272 | 0.645957 | 2.000503 | 1.932208 | 2.005031 |
32 | 4.294.967.296 | 2.952.310.283 | 171.423.771 | 2.780.886.512 | 0.687388 | 0.039913 | 0.647476 | 2.000465 | 1.934143 | 2.004703 |
33 | 8.589.934.592 | 5.905.929.015 | 331.930.171 | 5.573.998.844 | 0.687541 | 0.038642 | 0.648899 | 2.000443 | 1.936314 | 2.004396 |
34 | 17.179.869.184 | 11.814.387.494 | 643.343.836 | 11.171.043.658 | 0.687688 | 0.037448 | 0.650240 | 2.000428 | 1.938190 | 2.004135 |
35 | 34.359.738.368 | 23.633.556.391 | 1.248.165.416 | 22.385.390.975 | 0.687827 | 0.036326 | 0.651501 | 2.000405 | 1.940122 | 2.003876 |
36 | 68.719.476.736 | 47.276.196.592 | 2.423.781.186 | 44.852.415.406 | 0.687959 | 0.035271 | 0.652689 | 2.000384 | 1.941875 | 2.003647 |
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 | 2 | 0 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 7 | 4 | 3 | 2 | 2 | 1 | 2 |
5 | 32 | 12 | 6 | 6 | 2 | 4 | 3 | 3 |
6 | 64 | 17 | 7 | 10 | 3 | 5 | 6 | 3 |
7 | 128 | 27 | 9 | 18 | 5 | 7 | 10 | 5 |
8 | 256 | 49 | 18 | 31 | 10 | 13 | 15 | 11 |
9 | 512 | 91 | 32 | 59 | 21 | 22 | 25 | 23 |
10 | 1.024 | 153 | 47 | 106 | 37 | 40 | 38 | 38 |
11 | 2.048 | 258 | 79 | 179 | 67 | 67 | 63 | 61 |
12 | 4.096 | 476 | 142 | 334 | 122 | 120 | 116 | 118 |
13 | 8.192 | 869 | 258 | 611 | 227 | 220 | 207 | 215 |
14 | 16.384 | 1.591 | 533 | 1.058 | 396 | 406 | 391 | 398 |
15 | 32.768 | 2.957 | 1.013 | 1.944 | 741 | 733 | 750 | 733 |
16 | 65.536 | 5.515 | 1.849 | 3.666 | 1.358 | 1.383 | 1.396 | 1.378 |
17 | 131.072 | 10.366 | 3.465 | 6.901 | 2.567 | 2.597 | 2.627 | 2.575 |
18 | 262.144 | 19.482 | 6.545 | 12.937 | 4.858 | 4.854 | 4.872 | 4.898 |
19 | 524.288 | 36.493 | 12.255 | 24.238 | 9.092 | 9.134 | 9.134 | 9.133 |
20 | 1.048.576 | 69.176 | 23.191 | 45.985 | 17.297 | 17.245 | 17.304 | 17.330 |
21 | 2.097.152 | 131.044 | 43.770 | 87.274 | 32.730 | 32.650 | 32.762 | 32.902 |
22 | 4.194.304 | 249.767 | 83.382 | 166.385 | 62.549 | 62.465 | 62.435 | 62.318 |
23 | 8.388.608 | 475.273 | 158.573 | 316.700 | 119.097 | 118.881 | 118.776 | 118.519 |
24 | 16.777.216 | 908.188 | 302.949 | 605.239 | 227.655 | 227.265 | 226.548 | 226.720 |
25 | 33.554.432 | 1.740.446 | 580.573 | 1.159.873 | 435.719 | 435.074 | 434.656 | 434.997 |
26 | 67.108.864 | 3.336.837 | 1.112.871 | 2.223.966 | 834.717 | 835.101 | 833.102 | 833.917 |
27 | 134.217.728 | 6.408.931 | 2.136.750 | 4.272.181 | 1.603.382 | 1.602.717 | 1.601.091 | 1.601.741 |
28 | 268.435.456 | 12.333.025 | 4.110.699 | 8.222.326 | 3.084.893 | 3.083.516 | 3.083.831 | 3.080.785 |
29 | 536.870.912 | 23.768.117 | 7.921.879 | 15.846.238 | 5.943.477 | 5.941.922 | 5.943.347 | 5.939.371 |
30 | 1.073.741.824 | 45.869.981 | 15.288.062 | 30.581.919 | 11.468.078 | 11.467.362 | 11.467.018 | 11.467.523 |
31 | 2.147.483.648 | 88.630.354 | 29.540.193 | 59.090.161 | 22.156.455 | 22.156.958 | 22.156.931 | 22.160.010 |
32 | 4.294.967.296 | 171.423.771 | 57.138.959 | 114.284.812 | 42.851.785 | 42.857.363 | 42.852.847 | 42.861.776 |
33 | 8.589.934.592 | 331.930.171 | 110.646.105 | 221.284.066 | 82.972.511 | 82.980.899 | 82.985.138 | 82.991.623 |
34 | 17.179.869.184 | 643.343.836 | 214.442.472 | 428.901.364 | 160.832.715 | 160.834.710 | 160.833.007 | 160.843.404 |
35 | 34.359.738.368 | 1.248.165.416 | 416.063.684 | 832.101.732 | 312.043.210 | 312.040.596 | 312.035.577 | 312.046.033 |
36 | 68.719.476.736 | 2.423.781.186 | 807.935.306 | 1.615.845.880 | 605.972.040 | 605.930.487 | 605.921.302 | 605.957.357 |
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 | 2 | 0 | 2 | 1 | 0 | 1 | 0 |
3 | 8 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
4 | 16 | 5 | 3 | 2 | 2 | 1 | 1 | 1 |
5 | 32 | 8 | 4 | 4 | 3 | 2 | 2 | 1 |
6 | 64 | 25 | 12 | 13 | 4 | 5 | 9 | 7 |
7 | 128 | 55 | 28 | 27 | 10 | 14 | 18 | 13 |
8 | 256 | 121 | 59 | 62 | 27 | 27 | 31 | 36 |
9 | 512 | 251 | 119 | 132 | 57 | 61 | 64 | 69 |
10 | 1.024 | 538 | 279 | 259 | 112 | 141 | 138 | 147 |
11 | 2.048 | 1.126 | 568 | 558 | 268 | 290 | 285 | 283 |
12 | 4.096 | 2.294 | 1.165 | 1.129 | 559 | 601 | 573 | 561 |
13 | 8.192 | 4.704 | 2.391 | 2.313 | 1.167 | 1.220 | 1.139 | 1.178 |
14 | 16.384 | 9.547 | 4.808 | 4.739 | 2.378 | 2.419 | 2.367 | 2.383 |
15 | 32.768 | 19.340 | 9.802 | 9.538 | 4.833 | 4.788 | 4.858 | 4.861 |
16 | 65.536 | 39.184 | 19.952 | 19.232 | 9.805 | 9.750 | 9.870 | 9.759 |
17 | 131.072 | 79.222 | 40.226 | 38.996 | 19.909 | 19.724 | 19.805 | 19.784 |
18 | 262.144 | 159.628 | 80.736 | 78.892 | 39.836 | 39.813 | 39.999 | 39.980 |
19 | 524.288 | 322.082 | 162.558 | 159.524 | 80.265 | 80.478 | 80.439 | 80.900 |
20 | 1.048.576 | 648.629 | 327.335 | 321.294 | 161.745 | 162.247 | 162.114 | 162.523 |
21 | 2.097.152 | 1.305.355 | 658.792 | 646.563 | 325.758 | 326.723 | 326.446 | 326.428 |
22 | 4.194.304 | 2.624.189 | 1.324.289 | 1.299.900 | 655.578 | 656.692 | 655.326 | 656.593 |
23 | 8.388.608 | 5.275.817 | 2.661.078 | 2.614.739 | 1.317.882 | 1.319.083 | 1.318.421 | 1.320.431 |
24 | 16.777.216 | 10.597.409 | 5.342.284 | 5.255.125 | 2.648.137 | 2.649.120 | 2.650.047 | 2.650.105 |
25 | 33.554.432 | 21.278.297 | 10.723.890 | 10.554.407 | 5.317.019 | 5.319.113 | 5.321.477 | 5.320.688 |
26 | 67.108.864 | 42.716.216 | 21.521.904 | 21.194.312 | 10.676.204 | 10.679.417 | 10.684.561 | 10.676.034 |
27 | 134.217.728 | 85.727.299 | 43.179.735 | 42.547.564 | 21.427.899 | 21.437.443 | 21.433.793 | 21.428.164 |
28 | 268.435.456 | 171.995.634 | 86.599.825 | 85.395.809 | 42.995.966 | 43.008.076 | 42.994.184 | 42.997.408 |
29 | 536.870.912 | 344.993.864 | 173.650.441 | 171.343.423 | 86.247.919 | 86.257.109 | 86.237.848 | 86.250.988 |
30 | 1.073.741.824 | 691.850.521 | 348.137.445 | 343.713.076 | 172.959.775 | 172.981.963 | 172.949.290 | 172.959.493 |
31 | 2.147.483.648 | 1.387.181.527 | 697.861.186 | 689.320.341 | 346.791.502 | 346.815.349 | 346.793.971 | 346.780.705 |
32 | 4.294.967.296 | 2.780.886.512 | 1.398.680.597 | 1.382.205.915 | 695.244.551 | 695.219.190 | 695.211.679 | 695.211.092 |
33 | 8.589.934.592 | 5.573.998.844 | 2.802.957.651 | 2.771.041.193 | 1.393.505.580 | 1.393.516.056 | 1.393.493.389 | 1.393.483.819 |
34 | 17.179.869.184 | 11.171.043.658 | 5.616.455.290 | 5.554.588.368 | 2.792.768.891 | 2.792.767.847 | 2.792.759.223 | 2.792.747.697 |
35 | 34.359.738.368 | 22.385.390.975 | 11.252.615.459 | 11.132.775.516 | 5.596.364.552 | 5.596.371.146 | 5.596.370.238 | 5.596.285.039 |
36 | 68.719.476.736 | 44.852.415.406 | 22.542.596.414 | 22.309.818.992 | 11.213.140.088 | 11.213.199.624 | 11.212.999.341 | 11.213.076.353 |