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-164x-13
f(0)=13
f(1)=11
f(2)=337
f(3)=31
f(4)=653
f(5)=101
f(6)=1
f(7)=139
f(8)=97
f(9)=1
f(10)=1553
f(11)=53
f(12)=167
f(13)=19
f(14)=2113
f(15)=281
f(16)=2381
f(17)=157
f(18)=1
f(19)=173
f(20)=263
f(21)=29
f(22)=3137
f(23)=37
f(24)=3373
f(25)=109
f(26)=277
f(27)=1
f(28)=3821
f(29)=491
f(30)=1
f(31)=47
f(32)=223
f(33)=271
f(34)=1
f(35)=283
f(36)=4621
f(37)=1
f(38)=4801
f(39)=1
f(40)=4973
f(41)=79
f(42)=467
f(43)=163
f(44)=67
f(45)=61
f(46)=5441
f(47)=1
f(48)=5581
f(49)=353
f(50)=197
f(51)=1
f(52)=449
f(53)=1
f(54)=5953
f(55)=751
f(56)=1
f(57)=191
f(58)=1
f(59)=1
f(60)=1
f(61)=787
f(62)=6337
f(63)=797
f(64)=1
f(65)=1
f(66)=6481
f(67)=1
f(68)=211
f(69)=821
f(70)=347
f(71)=827
f(72)=6637
f(73)=1
f(74)=6673
f(75)=1
f(76)=6701
f(77)=839
f(78)=1
f(79)=1
f(80)=6733
f(81)=421
f(82)=6737
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-164x-13 could be written as f(y)= y^2-6737 with x=y+82
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-82
f'(x)>2x-165 with x > 82
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 | 8 | 1 | 0.900000 | 0.800000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 54 | 44 | 10 | 0.540000 | 0.440000 | 0.100000 | 6.000000 | 5.500000 | 10.000000 |
3 | 1.000 | 526 | 315 | 211 | 0.526000 | 0.315000 | 0.211000 | 9.740741 | 7.159091 | 21.100000 |
4 | 10.000 | 6.364 | 2.375 | 3.989 | 0.636400 | 0.237500 | 0.398900 | 12.098860 | 7.539682 | 18.905212 |
5 | 100.000 | 65.911 | 18.240 | 47.671 | 0.659110 | 0.182400 | 0.476710 | 10.356851 | 7.680000 | 11.950614 |
6 | 1.000.000 | 666.138 | 147.184 | 518.954 | 0.666138 | 0.147184 | 0.518954 | 10.106628 | 8.069298 | 10.886157 |
7 | 10.000.000 | 6.700.037 | 1.232.252 | 5.467.785 | 0.670004 | 0.123225 | 0.546779 | 10.058031 | 8.372188 | 10.536165 |
8 | 100.000.000 | 67.303.223 | 10.593.954 | 56.709.269 | 0.673032 | 0.105940 | 0.567093 | 10.045202 | 8.597230 | 10.371525 |
9 | 1.000.000.000 | 675.317.025 | 92.960.017 | 582.357.008 | 0.675317 | 0.092960 | 0.582357 | 10.033948 | 8.774817 | 10.269168 |
10 | 10.000.000.000 | 6.771.293.607 | 828.410.663 | 5.942.882.944 | 0.677129 | 0.082841 | 0.594288 | 10.026836 | 8.911473 | 10.204880 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 14 | 12 | 2 | 0.875000 | 0.750000 | 0.125000 | 1.750000 | 1.714286 | 2.000000 |
5 | 32 | 24 | 19 | 5 | 0.750000 | 0.593750 | 0.156250 | 1.714286 | 1.583333 | 2.500000 |
6 | 64 | 42 | 34 | 8 | 0.656250 | 0.531250 | 0.125000 | 1.750000 | 1.789474 | 1.600000 |
7 | 128 | 54 | 44 | 10 | 0.421875 | 0.343750 | 0.078125 | 1.285714 | 1.294118 | 1.250000 |
8 | 256 | 97 | 73 | 24 | 0.378906 | 0.285156 | 0.093750 | 1.796296 | 1.659091 | 2.400000 |
9 | 512 | 237 | 162 | 75 | 0.462891 | 0.316406 | 0.146484 | 2.443299 | 2.219178 | 3.125000 |
10 | 1.024 | 538 | 322 | 216 | 0.525391 | 0.314453 | 0.210938 | 2.270042 | 1.987654 | 2.880000 |
11 | 2.048 | 1.201 | 592 | 609 | 0.586426 | 0.289062 | 0.297363 | 2.232342 | 1.838509 | 2.819444 |
12 | 4.096 | 2.518 | 1.101 | 1.417 | 0.614746 | 0.268799 | 0.345947 | 2.096586 | 1.859797 | 2.326765 |
13 | 8.192 | 5.174 | 2.013 | 3.161 | 0.631592 | 0.245728 | 0.385864 | 2.054806 | 1.828338 | 2.230769 |
14 | 16.384 | 10.549 | 3.647 | 6.902 | 0.643860 | 0.222595 | 0.421265 | 2.038848 | 1.811724 | 2.183486 |
15 | 32.768 | 21.373 | 6.743 | 14.630 | 0.652252 | 0.205780 | 0.446472 | 2.026069 | 1.848917 | 2.119675 |
16 | 65.536 | 43.072 | 12.493 | 30.579 | 0.657227 | 0.190628 | 0.466599 | 2.015253 | 1.852736 | 2.090157 |
17 | 131.072 | 86.519 | 23.322 | 63.197 | 0.660088 | 0.177933 | 0.482155 | 2.008706 | 1.866805 | 2.066680 |
18 | 262.144 | 173.683 | 43.458 | 130.225 | 0.662548 | 0.165779 | 0.496769 | 2.007455 | 1.863391 | 2.060620 |
19 | 524.288 | 348.491 | 81.596 | 266.895 | 0.664694 | 0.155632 | 0.509062 | 2.006477 | 1.877583 | 2.049491 |
20 | 1.048.576 | 698.620 | 153.785 | 544.835 | 0.666256 | 0.146661 | 0.519595 | 2.004700 | 1.884712 | 2.041383 |
21 | 2.097.152 | 1.399.805 | 290.496 | 1.109.309 | 0.667479 | 0.138519 | 0.528960 | 2.003671 | 1.888975 | 2.036046 |
22 | 4.194.304 | 2.804.888 | 550.663 | 2.254.225 | 0.668737 | 0.131288 | 0.537449 | 2.003771 | 1.895596 | 2.032098 |
23 | 8.388.608 | 5.618.279 | 1.046.732 | 4.571.547 | 0.669751 | 0.124780 | 0.544971 | 2.003031 | 1.900858 | 2.027991 |
24 | 16.777.216 | 11.253.890 | 1.994.236 | 9.259.654 | 0.670784 | 0.118866 | 0.551918 | 2.003085 | 1.905202 | 2.025497 |
25 | 33.554.432 | 22.539.464 | 3.806.994 | 18.732.470 | 0.671728 | 0.113457 | 0.558271 | 2.002815 | 1.908999 | 2.023021 |
26 | 67.108.864 | 45.135.227 | 7.285.340 | 37.849.887 | 0.672567 | 0.108560 | 0.564007 | 2.002498 | 1.913673 | 2.020550 |
27 | 134.217.728 | 90.378.337 | 13.968.254 | 76.410.083 | 0.673371 | 0.104072 | 0.569299 | 2.002390 | 1.917310 | 2.018766 |
28 | 268.435.456 | 180.949.870 | 26.828.304 | 154.121.566 | 0.674091 | 0.099943 | 0.574148 | 2.002138 | 1.920663 | 2.017032 |
29 | 536.870.912 | 362.257.552 | 51.614.811 | 310.642.741 | 0.674757 | 0.096140 | 0.578617 | 2.001977 | 1.923894 | 2.015570 |
30 | 1.073.741.824 | 725.182.913 | 99.438.706 | 625.744.207 | 0.675379 | 0.092610 | 0.582770 | 2.001843 | 1.926554 | 2.014353 |
31 | 2.147.483.648 | 1.451.622.820 | 191.849.130 | 1.259.773.690 | 0.675965 | 0.089337 | 0.586628 | 2.001733 | 1.929321 | 2.013241 |
32 | 4.294.967.296 | 2.905.590.845 | 370.604.621 | 2.534.986.224 | 0.676511 | 0.086288 | 0.590222 | 2.001616 | 1.931750 | 2.012255 |
33 | 8.589.934.592 | 5.815.583.087 | 716.739.561 | 5.098.843.526 | 0.677023 | 0.083439 | 0.593584 | 2.001515 | 1.933974 | 2.011389 |
34 | 17.179.869.184 | 11.639.421.349 | 1.387.698.868 | 10.251.722.481 | 0.677503 | 0.080775 | 0.596729 | 2.001419 | 1.936127 | 2.010598 |
35 | 34.359.738.368 | 23.294.388.774 | 2.689.542.879 | 20.604.845.895 | 0.677956 | 0.078276 | 0.599680 | 2.001336 | 1.938132 | 2.009891 |
36 | 68.719.476.736 | 46.618.061.743 | 5.217.738.224 | 41.400.323.519 | 0.678382 | 0.075928 | 0.602454 | 2.001257 | 1.940009 | 2.009252 |
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 | 1 | 1 | 1 | 0 |
2 | 4 | 5 | 3 | 2 | 1 | 1 | 2 | 1 |
3 | 8 | 7 | 4 | 3 | 1 | 2 | 3 | 1 |
4 | 16 | 12 | 5 | 7 | 4 | 2 | 5 | 1 |
5 | 32 | 19 | 8 | 11 | 5 | 3 | 10 | 1 |
6 | 64 | 34 | 18 | 16 | 10 | 6 | 14 | 4 |
7 | 128 | 44 | 23 | 21 | 13 | 7 | 19 | 5 |
8 | 256 | 73 | 38 | 35 | 18 | 19 | 21 | 15 |
9 | 512 | 162 | 69 | 93 | 26 | 52 | 36 | 48 |
10 | 1.024 | 322 | 144 | 178 | 51 | 112 | 58 | 101 |
11 | 2.048 | 592 | 255 | 337 | 89 | 214 | 95 | 194 |
12 | 4.096 | 1.101 | 482 | 619 | 156 | 411 | 152 | 382 |
13 | 8.192 | 2.013 | 905 | 1.108 | 278 | 752 | 275 | 708 |
14 | 16.384 | 3.647 | 1.634 | 2.013 | 528 | 1.343 | 499 | 1.277 |
15 | 32.768 | 6.743 | 3.060 | 3.683 | 951 | 2.441 | 925 | 2.426 |
16 | 65.536 | 12.493 | 5.671 | 6.822 | 1.738 | 4.518 | 1.681 | 4.556 |
17 | 131.072 | 23.322 | 10.517 | 12.805 | 3.149 | 8.460 | 3.159 | 8.554 |
18 | 262.144 | 43.458 | 19.582 | 23.876 | 5.832 | 15.918 | 5.864 | 15.844 |
19 | 524.288 | 81.596 | 36.775 | 44.821 | 10.871 | 30.047 | 10.893 | 29.785 |
20 | 1.048.576 | 153.785 | 69.302 | 84.483 | 20.364 | 56.633 | 20.436 | 56.352 |
21 | 2.097.152 | 290.496 | 130.507 | 159.989 | 38.520 | 107.012 | 38.335 | 106.629 |
22 | 4.194.304 | 550.663 | 247.083 | 303.580 | 72.442 | 203.260 | 72.442 | 202.519 |
23 | 8.388.608 | 1.046.732 | 469.573 | 577.159 | 137.245 | 385.902 | 137.810 | 385.775 |
24 | 16.777.216 | 1.994.236 | 894.427 | 1.099.809 | 260.711 | 736.048 | 261.312 | 736.165 |
25 | 33.554.432 | 3.806.994 | 1.708.242 | 2.098.752 | 497.130 | 1.405.844 | 497.469 | 1.406.551 |
26 | 67.108.864 | 7.285.340 | 3.266.698 | 4.018.642 | 949.957 | 2.692.294 | 950.050 | 2.693.039 |
27 | 134.217.728 | 13.968.254 | 6.262.837 | 7.705.417 | 1.818.607 | 5.165.846 | 1.819.757 | 5.164.044 |
28 | 268.435.456 | 26.828.304 | 12.023.288 | 14.805.016 | 3.489.322 | 9.925.032 | 3.487.730 | 9.926.220 |
29 | 536.870.912 | 51.614.811 | 23.121.601 | 28.493.210 | 6.701.804 | 19.108.961 | 6.698.850 | 19.105.196 |
30 | 1.073.741.824 | 99.438.706 | 44.531.839 | 54.906.867 | 12.891.533 | 36.830.743 | 12.887.723 | 36.828.707 |
31 | 2.147.483.648 | 191.849.130 | 85.890.531 | 105.958.599 | 24.839.584 | 71.085.172 | 24.834.559 | 71.089.815 |
32 | 4.294.967.296 | 370.604.621 | 165.873.960 | 204.730.661 | 47.918.620 | 137.380.532 | 47.911.981 | 137.393.488 |
33 | 8.589.934.592 | 716.739.561 | 320.727.002 | 396.012.559 | 92.571.921 | 265.783.529 | 92.568.414 | 265.815.697 |
34 | 17.179.869.184 | 1.387.698.868 | 620.834.881 | 766.863.987 | 179.029.888 | 514.798.860 | 179.032.151 | 514.837.969 |
35 | 34.359.738.368 | 2.689.542.879 | 1.203.022.490 | 1.486.520.389 | 346.632.600 | 998.102.810 | 346.662.967 | 998.144.502 |
36 | 68.719.476.736 | 5.217.738.224 | 2.333.371.161 | 2.884.367.063 | 671.870.637 | 1.936.970.480 | 671.923.367 | 1.936.973.740 |
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 | 1 | 0 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
5 | 32 | 5 | 3 | 2 | 1 | 0 | 1 | 3 |
6 | 64 | 8 | 3 | 5 | 2 | 1 | 2 | 3 |
7 | 128 | 10 | 4 | 6 | 2 | 3 | 2 | 3 |
8 | 256 | 24 | 10 | 14 | 6 | 6 | 6 | 6 |
9 | 512 | 75 | 32 | 43 | 20 | 19 | 21 | 15 |
10 | 1.024 | 216 | 93 | 123 | 60 | 54 | 56 | 46 |
11 | 2.048 | 609 | 298 | 311 | 162 | 144 | 155 | 148 |
12 | 4.096 | 1.417 | 672 | 745 | 358 | 337 | 371 | 351 |
13 | 8.192 | 3.161 | 1.517 | 1.644 | 818 | 752 | 787 | 804 |
14 | 16.384 | 6.902 | 3.385 | 3.517 | 1.769 | 1.693 | 1.719 | 1.721 |
15 | 32.768 | 14.630 | 7.205 | 7.425 | 3.696 | 3.574 | 3.704 | 3.656 |
16 | 65.536 | 30.579 | 15.196 | 15.383 | 7.686 | 7.569 | 7.815 | 7.509 |
17 | 131.072 | 63.197 | 31.458 | 31.739 | 16.030 | 15.568 | 16.124 | 15.475 |
18 | 262.144 | 130.225 | 64.718 | 65.507 | 32.922 | 32.097 | 33.180 | 32.026 |
19 | 524.288 | 266.895 | 132.525 | 134.370 | 67.583 | 66.034 | 67.454 | 65.824 |
20 | 1.048.576 | 544.835 | 271.062 | 273.773 | 137.698 | 134.824 | 137.845 | 134.468 |
21 | 2.097.152 | 1.109.309 | 551.960 | 557.349 | 280.080 | 274.447 | 281.137 | 273.645 |
22 | 4.194.304 | 2.254.225 | 1.121.669 | 1.132.556 | 568.953 | 557.760 | 570.641 | 556.871 |
23 | 8.388.608 | 4.571.547 | 2.275.740 | 2.295.807 | 1.154.866 | 1.130.281 | 1.155.463 | 1.130.937 |
24 | 16.777.216 | 9.259.654 | 4.612.093 | 4.647.561 | 2.337.651 | 2.292.340 | 2.337.180 | 2.292.483 |
25 | 33.554.432 | 18.732.470 | 9.333.128 | 9.399.342 | 4.724.851 | 4.639.139 | 4.727.923 | 4.640.557 |
26 | 67.108.864 | 37.849.887 | 18.858.785 | 18.991.102 | 9.540.995 | 9.379.931 | 9.547.606 | 9.381.355 |
27 | 134.217.728 | 76.410.083 | 38.085.439 | 38.324.644 | 19.254.174 | 18.946.995 | 19.262.937 | 18.945.977 |
28 | 268.435.456 | 154.121.566 | 76.833.561 | 77.288.005 | 38.828.257 | 38.231.105 | 38.833.562 | 38.228.642 |
29 | 536.870.912 | 310.642.741 | 154.882.538 | 155.760.203 | 78.236.935 | 77.088.825 | 78.238.533 | 77.078.448 |
30 | 1.073.741.824 | 625.744.207 | 312.021.298 | 313.722.909 | 157.545.473 | 155.337.632 | 157.535.932 | 155.325.170 |
31 | 2.147.483.648 | 1.259.773.690 | 628.276.188 | 631.497.502 | 317.078.314 | 312.829.437 | 317.074.285 | 312.791.654 |
32 | 4.294.967.296 | 2.534.986.224 | 1.264.386.100 | 1.270.600.124 | 637.879.601 | 629.626.838 | 637.886.784 | 629.593.001 |
33 | 8.589.934.592 | 5.098.843.526 | 2.543.387.650 | 2.555.455.876 | 1.282.690.783 | 1.266.733.441 | 1.282.720.937 | 1.266.698.365 |
34 | 17.179.869.184 | 10.251.722.481 | 5.114.170.637 | 5.137.551.844 | 2.578.383.196 | 2.547.443.747 | 2.578.456.150 | 2.547.439.388 |
35 | 34.359.738.368 | 20.604.845.895 | 10.279.688.132 | 10.325.157.763 | 5.181.136.429 | 5.121.278.873 | 5.181.244.516 | 5.121.186.077 |
36 | 68.719.476.736 | 41.400.323.519 | 20.656.205.250 | 20.744.118.269 | 10.408.164.479 | 10.292.053.251 | 10.408.291.207 | 10.291.814.582 |