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+54x-29
f(0)=29
f(1)=13
f(2)=83
f(3)=71
f(4)=7
f(5)=19
f(6)=331
f(7)=199
f(8)=467
f(9)=269
f(10)=47
f(11)=1
f(12)=109
f(13)=421
f(14)=1
f(15)=503
f(16)=1091
f(17)=31
f(18)=181
f(19)=97
f(20)=1451
f(21)=773
f(22)=53
f(23)=67
f(24)=1
f(25)=139
f(26)=293
f(27)=1
f(28)=2267
f(29)=41
f(30)=1
f(31)=1303
f(32)=389
f(33)=1
f(34)=2963
f(35)=1543
f(36)=1
f(37)=1669
f(38)=3467
f(39)=257
f(40)=1
f(41)=1933
f(42)=4003
f(43)=1
f(44)=4283
f(45)=2213
f(46)=653
f(47)=337
f(48)=157
f(49)=193
f(50)=5171
f(51)=2663
f(52)=5483
f(53)=1
f(54)=829
f(55)=1
f(56)=6131
f(57)=1
f(58)=223
f(59)=3319
f(60)=1
f(61)=499
f(62)=1
f(63)=3671
f(64)=7523
f(65)=3853
f(66)=607
f(67)=577
f(68)=1181
f(69)=4229
f(70)=211
f(71)=4423
f(72)=9043
f(73)=4621
f(74)=1
f(75)=1
f(76)=9851
f(77)=107
f(78)=10267
f(79)=1
f(80)=10691
f(81)=1
f(82)=227
f(83)=1
f(84)=373
f(85)=1
f(86)=12011
f(87)=1
f(88)=137
f(89)=907
f(90)=1
f(91)=1
f(92)=1031
f(93)=359
f(94)=13883
f(95)=1009
f(96)=2053
f(97)=7309
f(98)=14867
f(99)=7559
b) Substitution of the polynom
The polynom f(x)=x^2+54x-29 could be written as f(y)= y^2-758 with x=y-27
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+27
f'(x)>2x+53
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 | 10 | 8 | 2 | 1.000000 | 0.800000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 73 | 43 | 30 | 0.730000 | 0.430000 | 0.730000 | 7.300000 | 5.375000 | 15.000000 |
3 | 1.000 | 698 | 269 | 429 | 0.698000 | 0.269000 | 0.698000 | 9.561644 | 6.255814 | 14.300000 |
4 | 10.000 | 6.970 | 1.931 | 5.039 | 0.697000 | 0.193100 | 0.697000 | 9.985673 | 7.178439 | 11.745921 |
5 | 100.000 | 69.840 | 14.980 | 54.860 | 0.698400 | 0.149800 | 0.698400 | 10.020086 | 7.757638 | 10.887081 |
6 | 1.000.000 | 697.720 | 121.799 | 575.921 | 0.697720 | 0.121799 | 0.697720 | 9.990263 | 8.130774 | 10.498013 |
7 | 10.000.000 | 6.968.653 | 1.029.283 | 5.939.370 | 0.696865 | 0.102928 | 0.696865 | 9.987750 | 8.450668 | 10.312820 |
8 | 100.000.000 | 69.623.945 | 8.904.392 | 60.719.553 | 0.696239 | 0.089044 | 0.696239 | 9.991019 | 8.651063 | 10.223231 |
9 | 1.000.000.000 | 695.799.340 | 78.472.590 | 617.326.750 | 0.695799 | 0.078473 | 0.695799 | 9.993679 | 8.812797 | 10.166852 |
10 | 10.000.000.000 | 6.954.566.847 | 701.712.450 | 6.252.854.397 | 0.695457 | 0.070171 | 0.695457 | 9.995075 | 8.942134 | 10.128922 |
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 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 2.000000 | 1.750000 | inf |
4 | 16 | 14 | 11 | 3 | 0.875000 | 0.687500 | 0.187500 | 1.750000 | 1.571429 | 3.000000 |
5 | 32 | 25 | 15 | 10 | 0.781250 | 0.468750 | 0.312500 | 1.785714 | 1.363636 | 3.333333 |
6 | 64 | 48 | 30 | 18 | 0.750000 | 0.468750 | 0.281250 | 1.920000 | 2.000000 | 1.800000 |
7 | 128 | 95 | 49 | 46 | 0.742188 | 0.382812 | 0.359375 | 1.979167 | 1.633333 | 2.555556 |
8 | 256 | 187 | 83 | 104 | 0.730469 | 0.324219 | 0.406250 | 1.968421 | 1.693878 | 2.260870 |
9 | 512 | 363 | 153 | 210 | 0.708984 | 0.298828 | 0.410156 | 1.941176 | 1.843374 | 2.019231 |
10 | 1.024 | 714 | 274 | 440 | 0.697266 | 0.267578 | 0.429688 | 1.966942 | 1.790850 | 2.095238 |
11 | 2.048 | 1.418 | 495 | 923 | 0.692383 | 0.241699 | 0.450684 | 1.985994 | 1.806569 | 2.097727 |
12 | 4.096 | 2.852 | 880 | 1.972 | 0.696289 | 0.214844 | 0.481445 | 2.011283 | 1.777778 | 2.136511 |
13 | 8.192 | 5.709 | 1.629 | 4.080 | 0.696899 | 0.198853 | 0.498047 | 2.001753 | 1.851136 | 2.068965 |
14 | 16.384 | 11.437 | 2.995 | 8.442 | 0.698059 | 0.182800 | 0.515259 | 2.003328 | 1.838551 | 2.069118 |
15 | 32.768 | 22.847 | 5.565 | 17.282 | 0.697235 | 0.169830 | 0.527405 | 1.997639 | 1.858097 | 2.047145 |
16 | 65.536 | 45.776 | 10.234 | 35.542 | 0.698486 | 0.156158 | 0.542328 | 2.003589 | 1.838994 | 2.056591 |
17 | 131.072 | 91.520 | 19.177 | 72.343 | 0.698242 | 0.146309 | 0.551933 | 1.999301 | 1.873852 | 2.035423 |
18 | 262.144 | 183.016 | 35.879 | 147.137 | 0.698151 | 0.136868 | 0.561283 | 1.999738 | 1.870939 | 2.033880 |
19 | 524.288 | 365.995 | 67.516 | 298.479 | 0.698080 | 0.128777 | 0.569304 | 1.999798 | 1.881769 | 2.028579 |
20 | 1.048.576 | 731.615 | 127.143 | 604.472 | 0.697722 | 0.121253 | 0.576469 | 1.998975 | 1.883154 | 2.025174 |
21 | 2.097.152 | 1.462.856 | 241.284 | 1.221.572 | 0.697544 | 0.115053 | 0.582491 | 1.999489 | 1.897737 | 2.020891 |
22 | 4.194.304 | 2.924.499 | 458.238 | 2.466.261 | 0.697255 | 0.109252 | 0.588002 | 1.999171 | 1.899164 | 2.018924 |
23 | 8.388.608 | 5.846.429 | 873.373 | 4.973.056 | 0.696949 | 0.104114 | 0.592834 | 1.999122 | 1.905938 | 2.016435 |
24 | 16.777.216 | 11.687.807 | 1.668.702 | 10.019.105 | 0.696648 | 0.099462 | 0.597185 | 1.999136 | 1.910641 | 2.014678 |
25 | 33.554.432 | 23.370.273 | 3.192.935 | 20.177.338 | 0.696488 | 0.095157 | 0.601332 | 1.999543 | 1.913424 | 2.013886 |
26 | 67.108.864 | 46.729.195 | 6.118.953 | 40.610.242 | 0.696319 | 0.091180 | 0.605140 | 1.999514 | 1.916404 | 2.012666 |
27 | 134.217.728 | 93.440.397 | 11.746.632 | 81.693.765 | 0.696185 | 0.087519 | 0.608666 | 1.999615 | 1.919713 | 2.011654 |
28 | 268.435.456 | 186.839.874 | 22.594.139 | 164.245.735 | 0.696033 | 0.084170 | 0.611863 | 1.999562 | 1.923457 | 2.010505 |
29 | 536.870.912 | 373.607.402 | 43.526.641 | 330.080.761 | 0.695898 | 0.081075 | 0.614823 | 1.999613 | 1.926457 | 2.009676 |
30 | 1.073.741.824 | 747.093.948 | 83.951.369 | 663.142.579 | 0.695785 | 0.078186 | 0.617600 | 1.999677 | 1.928735 | 2.009031 |
31 | 2.147.483.648 | 1.493.945.227 | 162.161.651 | 1.331.783.576 | 0.695672 | 0.075512 | 0.620160 | 1.999675 | 1.931614 | 2.008291 |
32 | 4.294.967.296 | 2.987.452.199 | 313.578.925 | 2.673.873.274 | 0.695570 | 0.073011 | 0.622560 | 1.999707 | 1.933743 | 2.007739 |
33 | 8.589.934.592 | 5.974.104.058 | 607.004.390 | 5.367.099.668 | 0.695477 | 0.070665 | 0.624813 | 1.999732 | 1.935731 | 2.007238 |
34 | 17.179.869.184 | 11.946.703.326 | 1.176.244.151 | 10.770.459.175 | 0.695390 | 0.068466 | 0.626923 | 1.999748 | 1.937785 | 2.006756 |
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 | 1 | 2 | 0 | 1 | 2 | 0 |
2 | 4 | 4 | 1 | 3 | 0 | 1 | 2 | 1 |
3 | 8 | 7 | 3 | 4 | 0 | 3 | 2 | 2 |
4 | 16 | 11 | 4 | 7 | 0 | 4 | 4 | 3 |
5 | 32 | 15 | 5 | 10 | 0 | 6 | 5 | 4 |
6 | 64 | 30 | 10 | 20 | 0 | 14 | 8 | 8 |
7 | 128 | 49 | 21 | 28 | 0 | 24 | 14 | 11 |
8 | 256 | 83 | 39 | 44 | 0 | 37 | 23 | 23 |
9 | 512 | 153 | 78 | 75 | 0 | 74 | 37 | 42 |
10 | 1.024 | 274 | 137 | 137 | 0 | 131 | 67 | 76 |
11 | 2.048 | 495 | 248 | 247 | 0 | 235 | 126 | 134 |
12 | 4.096 | 880 | 438 | 442 | 0 | 420 | 225 | 235 |
13 | 8.192 | 1.629 | 813 | 816 | 0 | 793 | 406 | 430 |
14 | 16.384 | 2.995 | 1.489 | 1.506 | 0 | 1.467 | 769 | 759 |
15 | 32.768 | 5.565 | 2.770 | 2.795 | 0 | 2.733 | 1.420 | 1.412 |
16 | 65.536 | 10.234 | 5.143 | 5.091 | 0 | 5.008 | 2.623 | 2.603 |
17 | 131.072 | 19.177 | 9.676 | 9.501 | 0 | 9.437 | 4.850 | 4.890 |
18 | 262.144 | 35.879 | 18.032 | 17.847 | 0 | 17.695 | 9.092 | 9.092 |
19 | 524.288 | 67.516 | 33.935 | 33.581 | 0 | 33.365 | 17.045 | 17.106 |
20 | 1.048.576 | 127.143 | 63.816 | 63.327 | 0 | 62.970 | 32.104 | 32.069 |
21 | 2.097.152 | 241.284 | 120.962 | 120.322 | 0 | 119.328 | 60.778 | 61.178 |
22 | 4.194.304 | 458.238 | 229.923 | 228.315 | 0 | 226.503 | 115.362 | 116.373 |
23 | 8.388.608 | 873.373 | 438.117 | 435.256 | 0 | 432.053 | 220.286 | 221.034 |
24 | 16.777.216 | 1.668.702 | 837.293 | 831.409 | 0 | 825.133 | 421.635 | 421.934 |
25 | 33.554.432 | 3.192.935 | 1.602.404 | 1.590.531 | 0 | 1.578.811 | 806.501 | 807.623 |
26 | 67.108.864 | 6.118.953 | 3.069.044 | 3.049.909 | 0 | 3.026.885 | 1.544.898 | 1.547.170 |
27 | 134.217.728 | 11.746.632 | 5.892.777 | 5.853.855 | 0 | 5.813.204 | 2.966.389 | 2.967.039 |
28 | 268.435.456 | 22.594.139 | 11.332.323 | 11.261.816 | 0 | 11.186.559 | 5.703.360 | 5.704.220 |
29 | 536.870.912 | 43.526.641 | 21.827.830 | 21.698.811 | 0 | 21.560.678 | 10.982.697 | 10.983.266 |
30 | 1.073.741.824 | 83.951.369 | 42.096.296 | 41.855.073 | 0 | 41.598.200 | 21.176.644 | 21.176.525 |
31 | 2.147.483.648 | 162.161.651 | 81.308.897 | 80.852.754 | 0 | 80.380.211 | 40.888.043 | 40.893.397 |
32 | 4.294.967.296 | 313.578.925 | 157.217.326 | 156.361.599 | 0 | 155.491.725 | 79.034.862 | 79.052.338 |
33 | 8.589.934.592 | 607.004.390 | 304.304.506 | 302.699.884 | 0 | 301.071.943 | 152.958.778 | 152.973.669 |
34 | 17.179.869.184 | 1.176.244.151 | 589.647.401 | 586.596.750 | 0 | 583.551.689 | 296.337.670 | 296.354.792 |
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 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
5 | 32 | 10 | 6 | 4 | 1 | 3 | 5 | 1 |
6 | 64 | 18 | 12 | 6 | 4 | 4 | 8 | 2 |
7 | 128 | 46 | 29 | 17 | 13 | 10 | 14 | 9 |
8 | 256 | 104 | 51 | 53 | 32 | 24 | 26 | 22 |
9 | 512 | 210 | 101 | 109 | 63 | 50 | 52 | 45 |
10 | 1.024 | 440 | 218 | 222 | 111 | 109 | 126 | 94 |
11 | 2.048 | 923 | 482 | 441 | 243 | 215 | 251 | 214 |
12 | 4.096 | 1.972 | 986 | 986 | 499 | 471 | 525 | 477 |
13 | 8.192 | 4.080 | 2.018 | 2.062 | 1.037 | 990 | 1.058 | 995 |
14 | 16.384 | 8.442 | 4.221 | 4.221 | 2.149 | 2.055 | 2.168 | 2.070 |
15 | 32.768 | 17.282 | 8.609 | 8.673 | 4.456 | 4.195 | 4.472 | 4.159 |
16 | 65.536 | 35.542 | 17.748 | 17.794 | 9.200 | 8.535 | 9.180 | 8.627 |
17 | 131.072 | 72.343 | 36.234 | 36.109 | 18.695 | 17.428 | 18.651 | 17.569 |
18 | 262.144 | 147.137 | 73.691 | 73.446 | 37.853 | 35.867 | 37.720 | 35.697 |
19 | 524.288 | 298.479 | 149.536 | 148.943 | 76.975 | 72.630 | 76.226 | 72.648 |
20 | 1.048.576 | 604.472 | 302.604 | 301.868 | 155.862 | 147.228 | 154.491 | 146.891 |
21 | 2.097.152 | 1.221.572 | 611.388 | 610.184 | 313.662 | 298.498 | 311.971 | 297.441 |
22 | 4.194.304 | 2.466.261 | 1.234.329 | 1.231.932 | 632.251 | 602.567 | 629.542 | 601.901 |
23 | 8.388.608 | 4.973.056 | 2.487.986 | 2.485.070 | 1.274.020 | 1.215.296 | 1.268.743 | 1.214.997 |
24 | 16.777.216 | 10.019.105 | 5.011.593 | 5.007.512 | 2.563.061 | 2.450.654 | 2.553.625 | 2.451.765 |
25 | 33.554.432 | 20.177.338 | 10.093.057 | 10.084.281 | 5.153.155 | 4.941.288 | 5.139.587 | 4.943.308 |
26 | 67.108.864 | 40.610.242 | 20.313.196 | 20.297.046 | 10.362.286 | 9.955.509 | 10.336.296 | 9.956.151 |
27 | 134.217.728 | 81.693.765 | 40.862.881 | 40.830.884 | 20.828.931 | 20.046.606 | 20.774.172 | 20.044.056 |
28 | 268.435.456 | 164.245.735 | 82.155.758 | 82.089.977 | 41.832.528 | 40.340.404 | 41.743.557 | 40.329.246 |
29 | 536.870.912 | 330.080.761 | 165.099.425 | 164.981.336 | 84.006.190 | 81.126.328 | 83.846.841 | 81.101.402 |
30 | 1.073.741.824 | 663.142.579 | 331.677.570 | 331.465.009 | 168.634.483 | 163.097.614 | 168.353.151 | 163.057.331 |
31 | 2.147.483.648 | 1.331.783.576 | 666.066.021 | 665.717.555 | 338.430.160 | 327.748.108 | 337.928.254 | 327.677.054 |
32 | 4.294.967.296 | 2.673.873.274 | 1.337.246.189 | 1.336.627.085 | 679.017.823 | 658.451.508 | 678.122.363 | 658.281.580 |
33 | 8.589.934.592 | 5.367.099.668 | 2.684.114.358 | 2.682.985.310 | 1.362.147.433 | 1.322.394.888 | 1.360.504.116 | 1.322.053.231 |
34 | 17.179.869.184 | 10.770.459.175 | 5.386.290.246 | 5.384.168.929 | 2.731.967.679 | 2.655.229.323 | 2.728.938.977 | 2.654.323.196 |