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-120x+167
f(0)=167
f(1)=3
f(2)=23
f(3)=1
f(4)=11
f(5)=17
f(6)=47
f(7)=13
f(8)=1
f(9)=1
f(10)=311
f(11)=43
f(12)=1129
f(13)=1
f(14)=439
f(15)=1
f(16)=499
f(17)=1
f(18)=1669
f(19)=73
f(20)=1
f(21)=239
f(22)=1
f(23)=1
f(24)=2137
f(25)=1
f(26)=1
f(27)=293
f(28)=1
f(29)=103
f(30)=149
f(31)=1
f(32)=883
f(33)=1
f(34)=919
f(35)=1
f(36)=2857
f(37)=1
f(38)=983
f(39)=1
f(40)=337
f(41)=1
f(42)=3109
f(43)=131
f(44)=353
f(45)=401
f(46)=83
f(47)=1
f(48)=1
f(49)=1
f(50)=101
f(51)=419
f(52)=1123
f(53)=1
f(54)=79
f(55)=71
f(56)=67
f(57)=107
f(58)=127
f(59)=1
f(60)=3433
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
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-120x+167 could be written as f(y)= y^2-3433 with x=y+60
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-60
f'(x)>2x-121 with x > 59
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 | 7 | 2 | 5 | 0.700000 | 0.200000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 32 | 12 | 20 | 0.320000 | 0.120000 | 0.200000 | 4.571429 | 6.000000 | 4.000000 |
3 | 1.000 | 495 | 110 | 385 | 0.495000 | 0.110000 | 0.385000 | 15.468750 | 9.166667 | 19.250000 |
4 | 10.000 | 5.966 | 855 | 5.111 | 0.596600 | 0.085500 | 0.511100 | 12.052526 | 7.772727 | 13.275325 |
5 | 100.000 | 62.273 | 6.547 | 55.726 | 0.622730 | 0.065470 | 0.557260 | 10.437982 | 7.657310 | 10.903150 |
6 | 1.000.000 | 636.585 | 52.487 | 584.098 | 0.636585 | 0.052487 | 0.584098 | 10.222488 | 8.016954 | 10.481606 |
7 | 10.000.000 | 6.450.065 | 439.615 | 6.010.450 | 0.645006 | 0.043961 | 0.601045 | 10.132292 | 8.375693 | 10.290139 |
8 | 100.000.000 | 65.125.415 | 3.785.223 | 61.340.192 | 0.651254 | 0.037852 | 0.613402 | 10.096862 | 8.610313 | 10.205590 |
9 | 1.000.000.000 | 656.070.921 | 33.214.627 | 622.856.294 | 0.656071 | 0.033215 | 0.622856 | 10.073961 | 8.774814 | 10.154131 |
10 | 10.000.000.000 | 6.598.687.777 | 296.012.199 | 6.302.675.578 | 0.659869 | 0.029601 | 0.630268 | 10.057888 | 8.912104 | 10.118988 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 1.000000 | 2.000000 |
4 | 16 | 11 | 3 | 8 | 0.687500 | 0.187500 | 0.500000 | 1.833333 | 1.500000 | 2.000000 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 1.727273 | 2.333333 | 1.500000 |
6 | 64 | 32 | 12 | 20 | 0.500000 | 0.187500 | 0.312500 | 1.684211 | 1.714286 | 1.666667 |
7 | 128 | 33 | 12 | 21 | 0.257812 | 0.093750 | 0.164062 | 1.031250 | 1.000000 | 1.050000 |
8 | 256 | 79 | 23 | 56 | 0.308594 | 0.089844 | 0.218750 | 2.393939 | 1.916667 | 2.666667 |
9 | 512 | 212 | 59 | 153 | 0.414062 | 0.115234 | 0.298828 | 2.683544 | 2.565217 | 2.732143 |
10 | 1.024 | 510 | 112 | 398 | 0.498047 | 0.109375 | 0.388672 | 2.405660 | 1.898305 | 2.601307 |
11 | 2.048 | 1.116 | 215 | 901 | 0.544922 | 0.104980 | 0.439941 | 2.188235 | 1.919643 | 2.263819 |
12 | 4.096 | 2.352 | 401 | 1.951 | 0.574219 | 0.097900 | 0.476318 | 2.107527 | 1.865116 | 2.165372 |
13 | 8.192 | 4.840 | 713 | 4.127 | 0.590820 | 0.087036 | 0.503784 | 2.057823 | 1.778055 | 2.115325 |
14 | 16.384 | 9.893 | 1.328 | 8.565 | 0.603821 | 0.081055 | 0.522766 | 2.044008 | 1.862553 | 2.075357 |
15 | 32.768 | 20.119 | 2.485 | 17.634 | 0.613983 | 0.075836 | 0.538147 | 2.033660 | 1.871235 | 2.058844 |
16 | 65.536 | 40.613 | 4.508 | 36.105 | 0.619705 | 0.068787 | 0.550919 | 2.018639 | 1.814085 | 2.047465 |
17 | 131.072 | 81.987 | 8.288 | 73.699 | 0.625511 | 0.063232 | 0.562279 | 2.018738 | 1.838509 | 2.041241 |
18 | 262.144 | 165.007 | 15.522 | 149.485 | 0.629452 | 0.059212 | 0.570240 | 2.012599 | 1.872828 | 2.028318 |
19 | 524.288 | 332.129 | 29.148 | 302.981 | 0.633486 | 0.055595 | 0.577890 | 2.012818 | 1.877851 | 2.026832 |
20 | 1.048.576 | 667.758 | 54.803 | 612.955 | 0.636824 | 0.052264 | 0.584559 | 2.010538 | 1.880163 | 2.023081 |
21 | 2.097.152 | 1.341.360 | 103.503 | 1.237.857 | 0.639610 | 0.049354 | 0.590256 | 2.008752 | 1.888638 | 2.019491 |
22 | 4.194.304 | 2.693.398 | 196.613 | 2.496.785 | 0.642156 | 0.046876 | 0.595280 | 2.007961 | 1.899587 | 2.017022 |
23 | 8.388.608 | 5.406.173 | 373.595 | 5.032.578 | 0.644466 | 0.044536 | 0.599930 | 2.007194 | 1.900154 | 2.015623 |
24 | 16.777.216 | 10.848.311 | 712.126 | 10.136.185 | 0.646610 | 0.042446 | 0.604164 | 2.006653 | 1.906144 | 2.014114 |
25 | 33.554.432 | 21.761.597 | 1.360.323 | 20.401.274 | 0.648546 | 0.040541 | 0.608005 | 2.005989 | 1.910228 | 2.012717 |
26 | 67.108.864 | 43.641.043 | 2.603.527 | 41.037.516 | 0.650302 | 0.038796 | 0.611507 | 2.005416 | 1.913904 | 2.011517 |
27 | 134.217.728 | 87.503.268 | 4.991.127 | 82.512.141 | 0.651950 | 0.037187 | 0.614763 | 2.005068 | 1.917064 | 2.010652 |
28 | 268.435.456 | 175.415.063 | 9.583.951 | 165.831.112 | 0.653472 | 0.035703 | 0.617769 | 2.004669 | 1.920198 | 2.009778 |
29 | 536.870.912 | 351.591.885 | 18.439.169 | 333.152.716 | 0.654891 | 0.034346 | 0.620545 | 2.004343 | 1.923963 | 2.008988 |
30 | 1.073.741.824 | 704.593.407 | 35.530.568 | 669.062.839 | 0.656204 | 0.033090 | 0.623113 | 2.004009 | 1.926907 | 2.008277 |
31 | 2.147.483.648 | 1.411.796.929 | 68.555.632 | 1.343.241.297 | 0.657419 | 0.031924 | 0.625495 | 2.003705 | 1.929483 | 2.007646 |
32 | 4.294.967.296 | 2.828.523.767 | 132.421.479 | 2.696.102.288 | 0.658567 | 0.030832 | 0.627735 | 2.003492 | 1.931592 | 2.007162 |
33 | 8.589.934.592 | 5.666.282.011 | 256.108.151 | 5.410.173.860 | 0.659642 | 0.029815 | 0.629827 | 2.003265 | 1.934038 | 2.006665 |
34 | 17.179.869.184 | 11.349.913.204 | 495.840.031 | 10.854.073.173 | 0.660652 | 0.028862 | 0.631790 | 2.003062 | 1.936057 | 2.006234 |
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 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 3 | 1 | 1 | 1 | 1 | 0 | 1 |
5 | 32 | 7 | 3 | 3 | 2 | 1 | 2 | 2 |
6 | 64 | 12 | 6 | 5 | 5 | 2 | 3 | 2 |
7 | 128 | 12 | 6 | 5 | 5 | 2 | 3 | 2 |
8 | 256 | 23 | 8 | 14 | 7 | 5 | 4 | 7 |
9 | 512 | 59 | 20 | 38 | 11 | 20 | 8 | 20 |
10 | 1.024 | 112 | 40 | 71 | 23 | 35 | 18 | 36 |
11 | 2.048 | 215 | 79 | 135 | 32 | 78 | 31 | 74 |
12 | 4.096 | 401 | 147 | 253 | 63 | 144 | 55 | 139 |
13 | 8.192 | 713 | 260 | 452 | 101 | 256 | 103 | 253 |
14 | 16.384 | 1.328 | 483 | 844 | 189 | 497 | 184 | 458 |
15 | 32.768 | 2.485 | 899 | 1.585 | 334 | 916 | 355 | 880 |
16 | 65.536 | 4.508 | 1.614 | 2.893 | 607 | 1.646 | 618 | 1.637 |
17 | 131.072 | 8.288 | 2.945 | 5.342 | 1.111 | 3.019 | 1.148 | 3.010 |
18 | 262.144 | 15.522 | 5.439 | 10.082 | 2.084 | 5.738 | 2.074 | 5.626 |
19 | 524.288 | 29.148 | 10.237 | 18.910 | 3.908 | 10.664 | 3.891 | 10.685 |
20 | 1.048.576 | 54.803 | 19.088 | 35.714 | 7.280 | 20.064 | 7.268 | 20.191 |
21 | 2.097.152 | 103.503 | 35.867 | 67.635 | 13.532 | 38.186 | 13.702 | 38.083 |
22 | 4.194.304 | 196.613 | 68.238 | 128.374 | 25.803 | 72.402 | 25.912 | 72.496 |
23 | 8.388.608 | 373.595 | 129.433 | 244.161 | 48.942 | 137.817 | 48.907 | 137.929 |
24 | 16.777.216 | 712.126 | 246.271 | 465.854 | 92.994 | 263.000 | 92.771 | 263.361 |
25 | 33.554.432 | 1.360.323 | 469.828 | 890.494 | 177.360 | 502.768 | 177.354 | 502.841 |
26 | 67.108.864 | 2.603.527 | 898.369 | 1.705.157 | 339.130 | 962.544 | 339.815 | 962.038 |
27 | 134.217.728 | 4.991.127 | 1.720.506 | 3.270.620 | 649.263 | 1.845.524 | 649.845 | 1.846.495 |
28 | 268.435.456 | 9.583.951 | 3.299.204 | 6.284.746 | 1.245.925 | 3.545.490 | 1.245.683 | 3.546.853 |
29 | 536.870.912 | 18.439.169 | 6.340.203 | 12.098.965 | 2.393.129 | 6.827.687 | 2.392.203 | 6.826.150 |
30 | 1.073.741.824 | 35.530.568 | 12.201.137 | 23.329.430 | 4.606.509 | 13.161.904 | 4.603.077 | 13.159.078 |
31 | 2.147.483.648 | 68.555.632 | 23.517.205 | 45.038.426 | 8.873.924 | 25.402.146 | 8.874.366 | 25.405.196 |
32 | 4.294.967.296 | 132.421.479 | 45.385.708 | 87.035.770 | 17.119.782 | 49.085.567 | 17.126.106 | 49.090.024 |
33 | 8.589.934.592 | 256.108.151 | 87.703.794 | 168.404.356 | 33.076.750 | 94.973.576 | 33.082.027 | 94.975.798 |
34 | 17.179.869.184 | 495.840.031 | 169.652.594 | 326.187.436 | 63.969.050 | 183.941.175 | 63.977.726 | 183.952.080 |
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 | 0 | 1 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 0 | 4 | 1 | 1 | 0 | 2 |
4 | 16 | 8 | 3 | 5 | 1 | 3 | 0 | 4 |
5 | 32 | 12 | 6 | 6 | 2 | 4 | 1 | 5 |
6 | 64 | 20 | 10 | 10 | 4 | 6 | 2 | 8 |
7 | 128 | 21 | 11 | 10 | 4 | 6 | 3 | 8 |
8 | 256 | 56 | 30 | 26 | 13 | 13 | 16 | 14 |
9 | 512 | 153 | 82 | 71 | 42 | 33 | 42 | 36 |
10 | 1.024 | 398 | 213 | 185 | 108 | 93 | 119 | 78 |
11 | 2.048 | 901 | 458 | 443 | 249 | 196 | 244 | 212 |
12 | 4.096 | 1.951 | 997 | 954 | 540 | 436 | 532 | 443 |
13 | 8.192 | 4.127 | 2.082 | 2.045 | 1.080 | 936 | 1.133 | 978 |
14 | 16.384 | 8.565 | 4.317 | 4.248 | 2.254 | 1.960 | 2.340 | 2.011 |
15 | 32.768 | 17.634 | 8.875 | 8.759 | 4.671 | 4.092 | 4.772 | 4.099 |
16 | 65.536 | 36.105 | 18.248 | 17.857 | 9.484 | 8.500 | 9.637 | 8.484 |
17 | 131.072 | 73.699 | 37.244 | 36.455 | 19.343 | 17.439 | 19.631 | 17.286 |
18 | 262.144 | 149.485 | 75.229 | 74.256 | 39.297 | 35.347 | 39.440 | 35.401 |
19 | 524.288 | 302.981 | 152.526 | 150.455 | 79.258 | 72.186 | 79.472 | 72.065 |
20 | 1.048.576 | 612.955 | 308.525 | 304.430 | 159.623 | 146.703 | 160.056 | 146.573 |
21 | 2.097.152 | 1.237.857 | 623.035 | 614.822 | 322.213 | 296.877 | 321.906 | 296.861 |
22 | 4.194.304 | 2.496.785 | 1.256.153 | 1.240.632 | 648.628 | 600.442 | 647.499 | 600.216 |
23 | 8.388.608 | 5.032.578 | 2.531.117 | 2.501.461 | 1.303.118 | 1.212.627 | 1.302.986 | 1.213.847 |
24 | 16.777.216 | 10.136.185 | 5.097.232 | 5.038.953 | 2.619.725 | 2.447.031 | 2.620.198 | 2.449.231 |
25 | 33.554.432 | 20.401.274 | 10.256.312 | 10.144.962 | 5.264.634 | 4.936.071 | 5.264.350 | 4.936.219 |
26 | 67.108.864 | 41.037.516 | 20.627.449 | 20.410.067 | 10.572.486 | 9.943.345 | 10.574.894 | 9.946.791 |
27 | 134.217.728 | 82.512.141 | 41.462.022 | 41.050.119 | 21.232.653 | 20.018.197 | 21.236.092 | 20.025.199 |
28 | 268.435.456 | 165.831.112 | 83.315.707 | 82.515.405 | 42.632.218 | 40.286.678 | 42.618.476 | 40.293.740 |
29 | 536.870.912 | 333.152.716 | 167.342.715 | 165.810.001 | 85.550.871 | 81.030.624 | 85.536.883 | 81.034.338 |
30 | 1.073.741.824 | 669.062.839 | 336.015.283 | 333.047.556 | 171.621.926 | 162.913.754 | 171.612.437 | 162.914.722 |
31 | 2.147.483.648 | 1.343.241.297 | 674.472.122 | 668.769.175 | 344.208.088 | 327.435.017 | 344.176.798 | 327.421.394 |
32 | 4.294.967.296 | 2.696.102.288 | 1.353.539.634 | 1.342.562.654 | 690.248.984 | 657.818.519 | 690.240.211 | 657.794.574 |
33 | 8.589.934.592 | 5.410.173.860 | 2.715.729.710 | 2.694.444.150 | 1.383.926.777 | 1.321.153.813 | 1.383.960.045 | 1.321.133.225 |
34 | 17.179.869.184 | 10.854.073.173 | 5.447.640.007 | 5.406.433.166 | 2.774.342.898 | 2.652.670.579 | 2.774.392.446 | 2.652.667.250 |