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-3
f(0)=3
f(1)=17
f(2)=13
f(3)=7
f(4)=89
f(5)=1
f(6)=1
f(7)=179
f(8)=71
f(9)=83
f(10)=41
f(11)=109
f(12)=1
f(13)=59
f(14)=1
f(15)=1
f(16)=557
f(17)=29
f(18)=1
f(19)=719
f(20)=37
f(21)=31
f(22)=1
f(23)=107
f(24)=1
f(25)=1097
f(26)=389
f(27)=1
f(28)=101
f(29)=463
f(30)=163
f(31)=1
f(32)=181
f(33)=571
f(34)=257
f(35)=1
f(36)=659
f(37)=2069
f(38)=103
f(39)=251
f(40)=2357
f(41)=1
f(42)=853
f(43)=2663
f(44)=1
f(45)=137
f(46)=1
f(47)=1033
f(48)=1
f(49)=3329
f(50)=383
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1399
f(57)=1
f(58)=4463
f(59)=73
f(60)=1579
f(61)=4877
f(62)=239
f(63)=1721
f(64)=5309
f(65)=1
f(66)=1
f(67)=443
f(68)=1
f(69)=1
f(70)=479
f(71)=2129
f(72)=1
f(73)=1
f(74)=2293
f(75)=1
f(76)=1031
f(77)=821
f(78)=2521
f(79)=1
f(80)=1
f(81)=2699
f(82)=487
f(83)=1
f(84)=1
f(85)=8837
f(86)=1
f(87)=439
f(88)=9413
f(89)=3203
f(90)=467
f(91)=10007
f(92)=1
f(93)=1
f(94)=1
f(95)=401
f(96)=283
f(97)=1607
f(98)=3821
f(99)=229
b) Substitution of the polynom
The polynom f(x)=x^2+19x-3 could be written as f(y)= y^2-93.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 | 9 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 61 | 18 | 43 | 0.610000 | 0.180000 | 0.430000 | 6.777778 | 4.500000 | 8.600000 |
3 | 1.000 | 666 | 100 | 566 | 0.666000 | 0.100000 | 0.566000 | 10.918033 | 5.555555 | 13.162790 |
4 | 10.000 | 6.715 | 659 | 6.056 | 0.671500 | 0.065900 | 0.605600 | 10.082582 | 6.590000 | 10.699647 |
5 | 100.000 | 67.761 | 5.107 | 62.654 | 0.677610 | 0.051070 | 0.626540 | 10.090990 | 7.749620 | 10.345773 |
6 | 1.000.000 | 680.556 | 41.512 | 639.044 | 0.680556 | 0.041512 | 0.639044 | 10.043476 | 8.128451 | 10.199573 |
7 | 10.000.000 | 6.820.782 | 351.527 | 6.469.255 | 0.682078 | 0.035153 | 0.646926 | 10.022367 | 8.468081 | 10.123333 |
8 | 100.000.000 | 68.336.192 | 3.050.453 | 65.285.739 | 0.683362 | 0.030505 | 0.652857 | 10.018821 | 8.677720 | 10.091694 |
9 | 1.000.000.000 | 684.326.206 | 26.910.114 | 657.416.092 | 0.684326 | 0.026910 | 0.657416 | 10.014111 | 8.821678 | 10.069826 |
10 | 10.000.000.000 | 6.851.406.123 | 240.869.858 | 6.610.536.265 | 0.685141 | 0.024087 | 0.661054 | 10.011901 | 8.950904 | 10.055331 |
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 | 5 | 7 | 0.750000 | 0.312500 | 0.437500 | 1.714286 | 1.250000 | 2.333333 |
5 | 32 | 20 | 7 | 13 | 0.625000 | 0.218750 | 0.406250 | 1.666667 | 1.400000 | 1.857143 |
6 | 64 | 40 | 14 | 26 | 0.625000 | 0.218750 | 0.406250 | 2.000000 | 2.000000 | 2.000000 |
7 | 128 | 82 | 22 | 60 | 0.640625 | 0.171875 | 0.468750 | 2.050000 | 1.571429 | 2.307692 |
8 | 256 | 166 | 33 | 133 | 0.648438 | 0.128906 | 0.519531 | 2.024390 | 1.500000 | 2.216667 |
9 | 512 | 337 | 58 | 279 | 0.658203 | 0.113281 | 0.544922 | 2.030120 | 1.757576 | 2.097744 |
10 | 1.024 | 681 | 102 | 579 | 0.665039 | 0.099609 | 0.565430 | 2.020772 | 1.758621 | 2.075269 |
11 | 2.048 | 1.369 | 179 | 1.190 | 0.668457 | 0.087402 | 0.581055 | 2.010279 | 1.754902 | 2.055268 |
12 | 4.096 | 2.757 | 309 | 2.448 | 0.673096 | 0.075439 | 0.597656 | 2.013879 | 1.726257 | 2.057143 |
13 | 8.192 | 5.506 | 557 | 4.949 | 0.672119 | 0.067993 | 0.604126 | 1.997098 | 1.802589 | 2.021650 |
14 | 16.384 | 11.057 | 1.022 | 10.035 | 0.674866 | 0.062378 | 0.612488 | 2.008173 | 1.834829 | 2.027682 |
15 | 32.768 | 22.140 | 1.878 | 20.262 | 0.675659 | 0.057312 | 0.618347 | 2.002352 | 1.837573 | 2.019133 |
16 | 65.536 | 44.390 | 3.501 | 40.889 | 0.677338 | 0.053421 | 0.623917 | 2.004968 | 1.864217 | 2.018014 |
17 | 131.072 | 88.864 | 6.511 | 82.353 | 0.677979 | 0.049675 | 0.628304 | 2.001892 | 1.859754 | 2.014062 |
18 | 262.144 | 177.969 | 12.262 | 165.707 | 0.678898 | 0.046776 | 0.632122 | 2.002712 | 1.883274 | 2.012155 |
19 | 524.288 | 356.433 | 23.134 | 333.299 | 0.679842 | 0.044125 | 0.635717 | 2.002781 | 1.886642 | 2.011375 |
20 | 1.048.576 | 713.670 | 43.386 | 670.284 | 0.680609 | 0.041376 | 0.639233 | 2.002256 | 1.875421 | 2.011059 |
21 | 2.097.152 | 1.428.242 | 82.314 | 1.345.928 | 0.681039 | 0.039250 | 0.641788 | 2.001264 | 1.897248 | 2.007997 |
22 | 4.194.304 | 2.858.944 | 156.445 | 2.702.499 | 0.681625 | 0.037299 | 0.644326 | 2.001722 | 1.900588 | 2.007908 |
23 | 8.388.608 | 5.720.924 | 298.540 | 5.422.384 | 0.681987 | 0.035589 | 0.646399 | 2.001062 | 1.908275 | 2.006433 |
24 | 16.777.216 | 11.449.043 | 570.994 | 10.878.049 | 0.682416 | 0.034034 | 0.648382 | 2.001258 | 1.912621 | 2.006138 |
25 | 33.554.432 | 22.911.068 | 1.092.829 | 21.818.239 | 0.682803 | 0.032569 | 0.650234 | 2.001134 | 1.913906 | 2.005713 |
26 | 67.108.864 | 45.845.474 | 2.096.426 | 43.749.048 | 0.683151 | 0.031239 | 0.651912 | 2.001019 | 1.918348 | 2.005159 |
27 | 134.217.728 | 91.735.360 | 4.025.490 | 87.709.870 | 0.683482 | 0.029992 | 0.653489 | 2.000969 | 1.920168 | 2.004841 |
28 | 268.435.456 | 183.552.880 | 7.744.499 | 175.808.381 | 0.683788 | 0.028851 | 0.654937 | 2.000896 | 1.923865 | 2.004431 |
29 | 536.870.912 | 367.260.702 | 14.922.552 | 352.338.150 | 0.684076 | 0.027795 | 0.656281 | 2.000844 | 1.926858 | 2.004103 |
30 | 1.073.741.824 | 734.820.496 | 28.788.658 | 706.031.838 | 0.684355 | 0.026812 | 0.657543 | 2.000814 | 1.929205 | 2.003847 |
31 | 2.147.483.648 | 1.470.200.092 | 55.628.955 | 1.414.571.137 | 0.684615 | 0.025904 | 0.658711 | 2.000761 | 1.932322 | 2.003551 |
32 | 4.294.967.296 | 2.941.456.725 | 107.604.331 | 2.833.852.394 | 0.684861 | 0.025054 | 0.659808 | 2.000719 | 1.934322 | 2.003330 |
33 | 8.589.934.592 | 5.884.893.195 | 208.350.748 | 5.676.542.447 | 0.685092 | 0.024255 | 0.660837 | 2.000673 | 1.936267 | 2.003119 |
34 | 17.179.869.184 | 11.773.555.929 | 403.844.194 | 11.369.711.735 | 0.685311 | 0.023507 | 0.661804 | 2.000641 | 1.938290 | 2.002929 |
35 | 34.359.738.368 | 23.554.244.096 | 783.552.601 | 22.770.691.495 | 0.685519 | 0.022804 | 0.662714 | 2.000606 | 1.940235 | 2.002750 |
36 | 68.719.476.736 | 47.121.985.858 | 1.521.582.502 | 45.600.403.356 | 0.685715 | 0.022142 | 0.663573 | 2.000573 | 1.941902 | 2.002592 |
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 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 2 | 1 | 0 | 0 |
3 | 8 | 4 | 0 | 3 | 2 | 2 | 0 | 0 |
4 | 16 | 5 | 0 | 4 | 2 | 2 | 1 | 0 |
5 | 32 | 7 | 0 | 6 | 3 | 2 | 1 | 1 |
6 | 64 | 14 | 0 | 13 | 4 | 2 | 5 | 3 |
7 | 128 | 22 | 0 | 21 | 7 | 3 | 8 | 4 |
8 | 256 | 33 | 0 | 31 | 9 | 7 | 10 | 7 |
9 | 512 | 58 | 0 | 56 | 17 | 11 | 18 | 12 |
10 | 1.024 | 102 | 0 | 100 | 30 | 23 | 27 | 22 |
11 | 2.048 | 179 | 0 | 177 | 51 | 45 | 45 | 38 |
12 | 4.096 | 309 | 0 | 307 | 83 | 75 | 82 | 69 |
13 | 8.192 | 557 | 0 | 555 | 146 | 133 | 149 | 129 |
14 | 16.384 | 1.022 | 0 | 1.020 | 263 | 261 | 264 | 234 |
15 | 32.768 | 1.878 | 0 | 1.876 | 483 | 473 | 478 | 444 |
16 | 65.536 | 3.501 | 0 | 3.499 | 875 | 880 | 888 | 858 |
17 | 131.072 | 6.511 | 0 | 6.509 | 1.608 | 1.606 | 1.659 | 1.638 |
18 | 262.144 | 12.262 | 0 | 12.260 | 3.013 | 3.077 | 3.094 | 3.078 |
19 | 524.288 | 23.134 | 0 | 23.132 | 5.754 | 5.787 | 5.821 | 5.772 |
20 | 1.048.576 | 43.386 | 0 | 43.384 | 10.845 | 10.898 | 10.784 | 10.859 |
21 | 2.097.152 | 82.314 | 0 | 82.312 | 20.588 | 20.548 | 20.565 | 20.613 |
22 | 4.194.304 | 156.445 | 0 | 156.443 | 39.214 | 38.867 | 39.232 | 39.132 |
23 | 8.388.608 | 298.540 | 0 | 298.538 | 74.787 | 74.415 | 74.587 | 74.751 |
24 | 16.777.216 | 570.994 | 0 | 570.992 | 142.881 | 142.296 | 142.744 | 143.073 |
25 | 33.554.432 | 1.092.829 | 0 | 1.092.827 | 273.551 | 273.050 | 273.002 | 273.226 |
26 | 67.108.864 | 2.096.426 | 0 | 2.096.424 | 524.392 | 523.353 | 524.154 | 524.527 |
27 | 134.217.728 | 4.025.490 | 0 | 4.025.488 | 1.006.310 | 1.006.177 | 1.006.674 | 1.006.329 |
28 | 268.435.456 | 7.744.499 | 0 | 7.744.497 | 1.937.451 | 1.936.122 | 1.934.815 | 1.936.111 |
29 | 536.870.912 | 14.922.552 | 0 | 14.922.550 | 3.732.980 | 3.729.205 | 3.729.621 | 3.730.746 |
30 | 1.073.741.824 | 28.788.658 | 0 | 28.788.656 | 7.198.011 | 7.197.219 | 7.197.951 | 7.195.477 |
31 | 2.147.483.648 | 55.628.955 | 0 | 55.628.953 | 13.906.326 | 13.906.917 | 13.906.951 | 13.908.761 |
32 | 4.294.967.296 | 107.604.331 | 0 | 107.604.329 | 26.900.586 | 26.904.545 | 26.898.674 | 26.900.526 |
33 | 8.589.934.592 | 208.350.748 | 0 | 208.350.746 | 52.089.017 | 52.083.990 | 52.086.597 | 52.091.144 |
34 | 17.179.869.184 | 403.844.194 | 0 | 403.844.192 | 100.965.940 | 100.958.443 | 100.956.682 | 100.963.129 |
35 | 34.359.738.368 | 783.552.601 | 0 | 783.552.599 | 195.888.803 | 195.886.608 | 195.882.143 | 195.895.047 |
36 | 68.719.476.736 | 1.521.582.502 | 0 | 1.521.582.500 | 380.399.112 | 380.396.834 | 380.392.610 | 380.393.946 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 2 | 0 | 0 | 0 | 1 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 0 | 1 | 2 |
4 | 16 | 7 | 3 | 4 | 1 | 2 | 2 | 2 |
5 | 32 | 13 | 6 | 7 | 1 | 4 | 5 | 3 |
6 | 64 | 26 | 12 | 14 | 5 | 8 | 6 | 7 |
7 | 128 | 60 | 28 | 32 | 14 | 17 | 15 | 14 |
8 | 256 | 133 | 55 | 78 | 32 | 36 | 30 | 35 |
9 | 512 | 279 | 126 | 153 | 61 | 80 | 68 | 70 |
10 | 1.024 | 579 | 266 | 313 | 134 | 160 | 142 | 143 |
11 | 2.048 | 1.190 | 564 | 626 | 287 | 308 | 297 | 298 |
12 | 4.096 | 2.448 | 1.171 | 1.277 | 592 | 636 | 606 | 614 |
13 | 8.192 | 4.949 | 2.372 | 2.577 | 1.197 | 1.276 | 1.231 | 1.245 |
14 | 16.384 | 10.035 | 4.826 | 5.209 | 2.461 | 2.545 | 2.503 | 2.526 |
15 | 32.768 | 20.262 | 9.843 | 10.419 | 5.062 | 5.121 | 5.015 | 5.064 |
16 | 65.536 | 40.889 | 19.936 | 20.953 | 10.220 | 10.208 | 10.194 | 10.267 |
17 | 131.072 | 82.353 | 40.189 | 42.164 | 20.646 | 20.557 | 20.413 | 20.737 |
18 | 262.144 | 165.707 | 81.090 | 84.617 | 41.263 | 41.404 | 41.343 | 41.697 |
19 | 524.288 | 333.299 | 163.271 | 170.028 | 82.855 | 83.303 | 83.396 | 83.745 |
20 | 1.048.576 | 670.284 | 328.336 | 341.948 | 167.029 | 167.627 | 167.676 | 167.952 |
21 | 2.097.152 | 1.345.928 | 659.862 | 686.066 | 335.917 | 336.626 | 336.711 | 336.674 |
22 | 4.194.304 | 2.702.499 | 1.326.024 | 1.376.475 | 674.926 | 675.928 | 676.222 | 675.423 |
23 | 8.388.608 | 5.422.384 | 2.663.888 | 2.758.496 | 1.355.368 | 1.355.462 | 1.355.635 | 1.355.919 |
24 | 16.777.216 | 10.878.049 | 5.348.464 | 5.529.585 | 2.717.667 | 2.720.882 | 2.719.496 | 2.720.004 |
25 | 33.554.432 | 21.818.239 | 10.738.243 | 11.079.996 | 5.452.183 | 5.455.297 | 5.455.810 | 5.454.949 |
26 | 67.108.864 | 43.749.048 | 21.547.423 | 22.201.625 | 10.937.110 | 10.936.966 | 10.938.014 | 10.936.958 |
27 | 134.217.728 | 87.709.870 | 43.226.992 | 44.482.878 | 21.926.747 | 21.927.209 | 21.929.605 | 21.926.309 |
28 | 268.435.456 | 175.808.381 | 86.695.451 | 89.112.930 | 43.947.351 | 43.954.288 | 43.953.693 | 43.953.049 |
29 | 536.870.912 | 352.338.150 | 173.833.585 | 178.504.565 | 88.081.306 | 88.075.112 | 88.089.570 | 88.092.162 |
30 | 1.073.741.824 | 706.031.838 | 348.504.203 | 357.527.635 | 176.505.472 | 176.497.655 | 176.500.890 | 176.527.821 |
31 | 2.147.483.648 | 1.414.571.137 | 698.570.232 | 716.000.905 | 353.642.695 | 353.637.773 | 353.622.138 | 353.668.531 |
32 | 4.294.967.296 | 2.833.852.394 | 1.400.053.609 | 1.433.798.785 | 708.474.486 | 708.457.502 | 708.452.353 | 708.468.053 |
33 | 8.589.934.592 | 5.676.542.447 | 2.805.593.863 | 2.870.948.584 | 1.419.158.352 | 1.419.119.453 | 1.419.126.488 | 1.419.138.154 |
34 | 17.179.869.184 | 11.369.711.735 | 5.621.509.958 | 5.748.201.777 | 2.842.415.594 | 2.842.445.638 | 2.842.429.515 | 2.842.420.988 |
35 | 34.359.738.368 | 22.770.691.495 | 11.262.529.191 | 11.508.162.304 | 5.692.642.581 | 5.692.724.150 | 5.692.667.160 | 5.692.657.604 |
36 | 68.719.476.736 | 45.600.403.356 | 22.561.917.203 | 23.038.486.153 | 11.400.084.735 | 11.400.191.381 | 11.400.082.605 | 11.400.044.635 |