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+13x-3
f(0)=3
f(1)=11
f(2)=1
f(3)=5
f(4)=13
f(5)=29
f(6)=37
f(7)=137
f(8)=1
f(9)=1
f(10)=227
f(11)=1
f(12)=1
f(13)=67
f(14)=1
f(15)=139
f(16)=461
f(17)=1
f(18)=1
f(19)=1
f(20)=73
f(21)=79
f(22)=59
f(23)=1
f(24)=1
f(25)=947
f(26)=337
f(27)=359
f(28)=229
f(29)=1
f(30)=1
f(31)=1361
f(32)=479
f(33)=101
f(34)=1
f(35)=43
f(36)=587
f(37)=1847
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=769
f(43)=1
f(44)=167
f(45)=1
f(46)=2711
f(47)=313
f(48)=1
f(49)=607
f(50)=1049
f(51)=1087
f(52)=307
f(53)=233
f(54)=241
f(55)=1
f(56)=1
f(57)=443
f(58)=823
f(59)=283
f(60)=1459
f(61)=347
f(62)=1549
f(63)=1
f(64)=197
f(65)=563
f(66)=193
f(67)=487
f(68)=367
f(69)=1
f(70)=5807
f(71)=1987
f(72)=2039
f(73)=251
f(74)=1
f(75)=733
f(76)=6761
f(77)=2309
f(78)=1
f(79)=1453
f(80)=1
f(81)=1
f(82)=599
f(83)=1
f(84)=181
f(85)=757
f(86)=2837
f(87)=223
f(88)=1777
f(89)=1
f(90)=3089
f(91)=9461
f(92)=1
f(93)=1
f(94)=2011
f(95)=263
f(96)=317
f(97)=10667
f(98)=1
f(99)=739
b) Substitution of the polynom
The polynom f(x)=x^2+13x-3 could be written as f(y)= y^2-45.25 with x=y-6.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+6.5
f'(x)>2x+12
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 | 4 | 3 | 0.700000 | 0.400000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 14 | 50 | 0.640000 | 0.140000 | 0.500000 | 9.142858 | 3.500000 | 16.666666 |
3 | 1.000 | 659 | 87 | 572 | 0.659000 | 0.087000 | 0.572000 | 10.296875 | 6.214286 | 11.440000 |
4 | 10.000 | 6.715 | 571 | 6.144 | 0.671500 | 0.057100 | 0.614400 | 10.189681 | 6.563219 | 10.741259 |
5 | 100.000 | 67.634 | 4.279 | 63.355 | 0.676340 | 0.042790 | 0.633550 | 10.072078 | 7.493870 | 10.311687 |
6 | 1.000.000 | 678.962 | 34.918 | 644.044 | 0.678962 | 0.034918 | 0.644044 | 10.038768 | 8.160317 | 10.165638 |
7 | 10.000.000 | 6.806.274 | 295.859 | 6.510.415 | 0.680627 | 0.029586 | 0.651042 | 10.024529 | 8.472965 | 10.108649 |
8 | 100.000.000 | 68.201.483 | 2.565.195 | 65.636.288 | 0.682015 | 0.025652 | 0.656363 | 10.020384 | 8.670329 | 10.081737 |
9 | 1.000.000.000 | 683.137.298 | 22.621.103 | 660.516.195 | 0.683137 | 0.022621 | 0.660516 | 10.016459 | 8.818474 | 10.063278 |
10 | 10.000.000.000 | 6.840.595.009 | 202.403.848 | 6.638.191.161 | 0.684060 | 0.020240 | 0.663819 | 10.013499 | 8.947567 | 10.050005 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.500000 | 1.000000 | inf |
3 | 8 | 6 | 3 | 3 | 0.750000 | 0.375000 | 0.375000 | 2.000000 | 1.500000 | 3.000000 |
4 | 16 | 10 | 5 | 5 | 0.625000 | 0.312500 | 0.312500 | 1.666667 | 1.666667 | 1.666667 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 1.900000 | 1.400000 | 2.400000 |
6 | 64 | 39 | 9 | 30 | 0.609375 | 0.140625 | 0.468750 | 2.052632 | 1.285714 | 2.500000 |
7 | 128 | 82 | 17 | 65 | 0.640625 | 0.132812 | 0.507812 | 2.102564 | 1.888889 | 2.166667 |
8 | 256 | 170 | 32 | 138 | 0.664062 | 0.125000 | 0.539062 | 2.073171 | 1.882353 | 2.123077 |
9 | 512 | 336 | 53 | 283 | 0.656250 | 0.103516 | 0.552734 | 1.976471 | 1.656250 | 2.050725 |
10 | 1.024 | 677 | 89 | 588 | 0.661133 | 0.086914 | 0.574219 | 2.014881 | 1.679245 | 2.077739 |
11 | 2.048 | 1.355 | 150 | 1.205 | 0.661621 | 0.073242 | 0.588379 | 2.001477 | 1.685393 | 2.049320 |
12 | 4.096 | 2.730 | 273 | 2.457 | 0.666504 | 0.066650 | 0.599854 | 2.014760 | 1.820000 | 2.039004 |
13 | 8.192 | 5.488 | 481 | 5.007 | 0.669922 | 0.058716 | 0.611206 | 2.010257 | 1.761905 | 2.037851 |
14 | 16.384 | 11.045 | 852 | 10.193 | 0.674133 | 0.052002 | 0.622131 | 2.012573 | 1.771310 | 2.035750 |
15 | 32.768 | 22.095 | 1.554 | 20.541 | 0.674286 | 0.047424 | 0.626862 | 2.000453 | 1.823944 | 2.015207 |
16 | 65.536 | 44.278 | 2.904 | 41.374 | 0.675629 | 0.044312 | 0.631317 | 2.003983 | 1.868726 | 2.014215 |
17 | 131.072 | 88.659 | 5.469 | 83.190 | 0.676414 | 0.041725 | 0.634689 | 2.002326 | 1.883264 | 2.010683 |
18 | 262.144 | 177.561 | 10.306 | 167.255 | 0.677341 | 0.039314 | 0.638027 | 2.002741 | 1.884440 | 2.010518 |
19 | 524.288 | 355.454 | 19.343 | 336.111 | 0.677975 | 0.036894 | 0.641081 | 2.001870 | 1.876868 | 2.009572 |
20 | 1.048.576 | 711.927 | 36.525 | 675.402 | 0.678946 | 0.034833 | 0.644114 | 2.002867 | 1.888280 | 2.009461 |
21 | 2.097.152 | 1.425.000 | 69.235 | 1.355.765 | 0.679493 | 0.033014 | 0.646479 | 2.001610 | 1.895551 | 2.007345 |
22 | 4.194.304 | 2.852.122 | 131.968 | 2.720.154 | 0.679999 | 0.031464 | 0.648535 | 2.001489 | 1.906088 | 2.006361 |
23 | 8.388.608 | 5.708.588 | 251.171 | 5.457.417 | 0.680517 | 0.029942 | 0.650575 | 2.001523 | 1.903272 | 2.006290 |
24 | 16.777.216 | 11.424.681 | 479.475 | 10.945.206 | 0.680964 | 0.028579 | 0.652385 | 2.001315 | 1.908958 | 2.005565 |
25 | 33.554.432 | 22.863.524 | 919.190 | 21.944.334 | 0.681386 | 0.027394 | 0.653992 | 2.001240 | 1.917076 | 2.004926 |
26 | 67.108.864 | 45.755.130 | 1.763.127 | 43.992.003 | 0.681805 | 0.026273 | 0.655532 | 2.001228 | 1.918131 | 2.004709 |
27 | 134.217.728 | 91.559.515 | 3.384.585 | 88.174.930 | 0.682172 | 0.025217 | 0.656954 | 2.001076 | 1.919649 | 2.004340 |
28 | 268.435.456 | 183.214.401 | 6.509.683 | 176.704.718 | 0.682527 | 0.024250 | 0.658276 | 2.001042 | 1.923333 | 2.004025 |
29 | 536.870.912 | 366.603.553 | 12.541.507 | 354.062.046 | 0.682852 | 0.023360 | 0.659492 | 2.000954 | 1.926593 | 2.003693 |
30 | 1.073.741.824 | 733.545.238 | 24.199.843 | 709.345.395 | 0.683167 | 0.022538 | 0.660629 | 2.000922 | 1.929580 | 2.003449 |
31 | 2.147.483.648 | 1.467.718.600 | 46.746.534 | 1.420.972.066 | 0.683460 | 0.021768 | 0.661692 | 2.000856 | 1.931687 | 2.003216 |
32 | 4.294.967.296 | 2.936.647.235 | 90.421.419 | 2.846.225.816 | 0.683741 | 0.021053 | 0.662689 | 2.000824 | 1.934291 | 2.003013 |
33 | 8.589.934.592 | 5.875.536.919 | 175.081.584 | 5.700.455.335 | 0.684003 | 0.020382 | 0.663620 | 2.000764 | 1.936284 | 2.002812 |
34 | 17.179.869.184 | 11.755.345.528 | 339.347.168 | 11.415.998.360 | 0.684251 | 0.019753 | 0.664499 | 2.000727 | 1.938223 | 2.002647 |
35 | 34.359.738.368 | 23.518.756.231 | 658.383.726 | 22.860.372.505 | 0.684486 | 0.019161 | 0.665324 | 2.000686 | 1.940148 | 2.002486 |
36 | 68.719.476.736 | 47.052.896.058 | 1.278.493.752 | 45.774.402.306 | 0.684710 | 0.018605 | 0.666105 | 2.000654 | 1.941867 | 2.002347 |
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 | 2 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 0 | 2 | 1 | 2 | 0 | 0 |
4 | 16 | 5 | 0 | 4 | 1 | 3 | 1 | 0 |
5 | 32 | 7 | 0 | 6 | 2 | 4 | 1 | 0 |
6 | 64 | 9 | 0 | 8 | 2 | 4 | 1 | 2 |
7 | 128 | 17 | 0 | 15 | 4 | 6 | 4 | 3 |
8 | 256 | 32 | 0 | 30 | 8 | 11 | 6 | 7 |
9 | 512 | 53 | 0 | 51 | 14 | 17 | 9 | 13 |
10 | 1.024 | 89 | 0 | 87 | 25 | 24 | 14 | 26 |
11 | 2.048 | 150 | 0 | 148 | 35 | 42 | 30 | 43 |
12 | 4.096 | 273 | 0 | 271 | 65 | 71 | 59 | 78 |
13 | 8.192 | 481 | 0 | 479 | 121 | 122 | 113 | 125 |
14 | 16.384 | 852 | 0 | 850 | 222 | 211 | 202 | 217 |
15 | 32.768 | 1.554 | 0 | 1.552 | 397 | 387 | 397 | 373 |
16 | 65.536 | 2.904 | 0 | 2.902 | 747 | 728 | 745 | 684 |
17 | 131.072 | 5.469 | 0 | 5.467 | 1.409 | 1.344 | 1.384 | 1.332 |
18 | 262.144 | 10.306 | 0 | 10.304 | 2.617 | 2.525 | 2.590 | 2.574 |
19 | 524.288 | 19.343 | 0 | 19.341 | 4.889 | 4.743 | 4.848 | 4.863 |
20 | 1.048.576 | 36.525 | 0 | 36.523 | 9.151 | 9.030 | 9.130 | 9.214 |
21 | 2.097.152 | 69.235 | 0 | 69.233 | 17.332 | 17.212 | 17.342 | 17.349 |
22 | 4.194.304 | 131.968 | 0 | 131.966 | 33.055 | 32.941 | 32.967 | 33.005 |
23 | 8.388.608 | 251.171 | 0 | 251.169 | 62.824 | 62.791 | 62.714 | 62.842 |
24 | 16.777.216 | 479.475 | 0 | 479.473 | 119.913 | 119.925 | 119.778 | 119.859 |
25 | 33.554.432 | 919.190 | 0 | 919.188 | 229.713 | 229.857 | 229.607 | 230.013 |
26 | 67.108.864 | 1.763.127 | 0 | 1.763.125 | 440.376 | 441.458 | 440.506 | 440.787 |
27 | 134.217.728 | 3.384.585 | 0 | 3.384.583 | 846.126 | 847.034 | 845.811 | 845.614 |
28 | 268.435.456 | 6.509.683 | 0 | 6.509.681 | 1.627.378 | 1.627.782 | 1.627.206 | 1.627.317 |
29 | 536.870.912 | 12.541.507 | 0 | 12.541.505 | 3.136.046 | 3.135.289 | 3.134.927 | 3.135.245 |
30 | 1.073.741.824 | 24.199.843 | 0 | 24.199.841 | 6.050.372 | 6.050.330 | 6.049.618 | 6.049.523 |
31 | 2.147.483.648 | 46.746.534 | 0 | 46.746.532 | 11.688.715 | 11.685.784 | 11.685.532 | 11.686.503 |
32 | 4.294.967.296 | 90.421.419 | 0 | 90.421.417 | 22.609.732 | 22.603.991 | 22.604.187 | 22.603.509 |
33 | 8.589.934.592 | 175.081.584 | 0 | 175.081.582 | 43.774.362 | 43.773.490 | 43.763.913 | 43.769.819 |
34 | 17.179.869.184 | 339.347.168 | 0 | 339.347.166 | 84.837.259 | 84.849.029 | 84.826.092 | 84.834.788 |
35 | 34.359.738.368 | 658.383.726 | 0 | 658.383.724 | 164.601.619 | 164.606.019 | 164.579.457 | 164.596.631 |
36 | 68.719.476.736 | 1.278.493.752 | 0 | 1.278.493.750 | 319.619.688 | 319.631.005 | 319.608.591 | 319.634.468 |
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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 3 | 2 | 1 | 0 | 0 | 3 | 0 |
4 | 16 | 5 | 4 | 1 | 0 | 2 | 3 | 0 |
5 | 32 | 12 | 8 | 4 | 2 | 3 | 4 | 3 |
6 | 64 | 30 | 18 | 12 | 7 | 9 | 7 | 7 |
7 | 128 | 65 | 40 | 25 | 14 | 18 | 18 | 15 |
8 | 256 | 138 | 75 | 63 | 29 | 38 | 38 | 33 |
9 | 512 | 283 | 149 | 134 | 62 | 75 | 78 | 68 |
10 | 1.024 | 588 | 301 | 287 | 134 | 144 | 157 | 153 |
11 | 2.048 | 1.205 | 623 | 582 | 285 | 306 | 301 | 313 |
12 | 4.096 | 2.457 | 1.289 | 1.168 | 583 | 614 | 625 | 635 |
13 | 8.192 | 5.007 | 2.599 | 2.408 | 1.218 | 1.267 | 1.242 | 1.280 |
14 | 16.384 | 10.193 | 5.281 | 4.912 | 2.505 | 2.551 | 2.542 | 2.595 |
15 | 32.768 | 20.541 | 10.618 | 9.923 | 5.129 | 5.096 | 5.133 | 5.183 |
16 | 65.536 | 41.374 | 21.299 | 20.075 | 10.327 | 10.267 | 10.336 | 10.444 |
17 | 131.072 | 83.190 | 42.766 | 40.424 | 20.710 | 20.667 | 20.887 | 20.926 |
18 | 262.144 | 167.255 | 86.089 | 81.166 | 41.703 | 41.772 | 41.847 | 41.933 |
19 | 524.288 | 336.111 | 172.424 | 163.687 | 83.974 | 83.951 | 83.958 | 84.228 |
20 | 1.048.576 | 675.402 | 346.126 | 329.276 | 169.044 | 168.524 | 168.852 | 168.982 |
21 | 2.097.152 | 1.355.765 | 694.087 | 661.678 | 339.160 | 338.465 | 339.240 | 338.900 |
22 | 4.194.304 | 2.720.154 | 1.390.379 | 1.329.775 | 680.847 | 679.467 | 679.814 | 680.026 |
23 | 8.388.608 | 5.457.417 | 2.787.201 | 2.670.216 | 1.364.694 | 1.364.103 | 1.364.081 | 1.364.539 |
24 | 16.777.216 | 10.945.206 | 5.583.370 | 5.361.836 | 2.736.135 | 2.736.531 | 2.736.735 | 2.735.805 |
25 | 33.554.432 | 21.944.334 | 11.185.799 | 10.758.535 | 5.485.618 | 5.486.618 | 5.488.062 | 5.484.036 |
26 | 67.108.864 | 43.992.003 | 22.405.717 | 21.586.286 | 10.998.589 | 10.999.715 | 10.999.428 | 10.994.271 |
27 | 134.217.728 | 88.174.930 | 44.871.512 | 43.303.418 | 22.043.017 | 22.048.769 | 22.044.492 | 22.038.652 |
28 | 268.435.456 | 176.704.718 | 89.861.800 | 86.842.918 | 44.173.772 | 44.181.278 | 44.181.575 | 44.168.093 |
29 | 536.870.912 | 354.062.046 | 179.941.248 | 174.120.798 | 88.516.195 | 88.517.786 | 88.511.381 | 88.516.684 |
30 | 1.073.741.824 | 709.345.395 | 360.272.552 | 349.072.843 | 177.320.884 | 177.345.681 | 177.339.889 | 177.338.941 |
31 | 2.147.483.648 | 1.420.972.066 | 721.292.012 | 699.680.054 | 355.238.280 | 355.248.435 | 355.251.394 | 355.233.957 |
32 | 4.294.967.296 | 2.846.225.816 | 1.444.017.268 | 1.402.208.548 | 711.552.265 | 711.585.260 | 711.542.959 | 711.545.332 |
33 | 8.589.934.592 | 5.700.455.335 | 2.890.670.939 | 2.809.784.396 | 1.425.071.466 | 1.425.165.951 | 1.425.137.388 | 1.425.080.530 |
34 | 17.179.869.184 | 11.415.998.360 | 5.786.259.146 | 5.629.739.214 | 2.853.976.810 | 2.854.002.740 | 2.854.027.978 | 2.853.990.832 |
35 | 34.359.738.368 | 22.860.372.505 | 11.581.886.042 | 11.278.486.463 | 5.715.062.372 | 5.715.067.940 | 5.715.180.281 | 5.715.061.912 |
36 | 68.719.476.736 | 45.774.402.306 | 23.181.515.347 | 22.592.886.959 | 11.443.588.488 | 11.443.654.474 | 11.443.613.800 | 11.443.545.544 |