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+36x-53
f(0)=53
f(1)=1
f(2)=23
f(3)=1
f(4)=107
f(5)=19
f(6)=199
f(7)=31
f(8)=13
f(9)=11
f(10)=37
f(11)=29
f(12)=523
f(13)=73
f(14)=647
f(15)=89
f(16)=41
f(17)=1
f(18)=919
f(19)=1
f(20)=97
f(21)=1
f(22)=1223
f(23)=163
f(24)=1
f(25)=1
f(26)=1559
f(27)=103
f(28)=47
f(29)=229
f(30)=1
f(31)=1
f(32)=193
f(33)=139
f(34)=179
f(35)=1
f(36)=2539
f(37)=331
f(38)=1
f(39)=359
f(40)=1
f(41)=1
f(42)=293
f(43)=1
f(44)=3467
f(45)=449
f(46)=3719
f(47)=1
f(48)=173
f(49)=257
f(50)=137
f(51)=1
f(52)=4523
f(53)=1
f(54)=1
f(55)=619
f(56)=5099
f(57)=1
f(58)=5399
f(59)=347
f(60)=439
f(61)=733
f(62)=317
f(63)=773
f(64)=577
f(65)=1
f(66)=6679
f(67)=1
f(68)=7019
f(69)=1
f(70)=1
f(71)=1
f(72)=7723
f(73)=1
f(74)=8087
f(75)=1
f(76)=769
f(77)=1
f(78)=8839
f(79)=1129
f(80)=9227
f(81)=1
f(82)=9623
f(83)=307
f(84)=271
f(85)=1279
f(86)=1
f(87)=1
f(88)=10859
f(89)=1
f(90)=11287
f(91)=719
f(92)=617
f(93)=1493
f(94)=1
f(95)=1549
f(96)=12619
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+36x-53 could be written as f(y)= y^2-377 with x=y-18
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+18
f'(x)>2x+35
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 | 8 | 5 | 3 | 0.800000 | 0.500000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 63 | 26 | 37 | 0.630000 | 0.260000 | 0.630000 | 7.875000 | 5.200000 | 12.333333 |
3 | 1.000 | 650 | 168 | 482 | 0.650000 | 0.168000 | 0.650000 | 10.317460 | 6.461538 | 13.027027 |
4 | 10.000 | 6.674 | 1.180 | 5.494 | 0.667400 | 0.118000 | 0.667400 | 10.267693 | 7.023809 | 11.398340 |
5 | 100.000 | 67.121 | 9.064 | 58.057 | 0.671210 | 0.090640 | 0.671210 | 10.057087 | 7.681356 | 10.567347 |
6 | 1.000.000 | 675.614 | 73.259 | 602.355 | 0.675614 | 0.073259 | 0.675614 | 10.065613 | 8.082414 | 10.375235 |
7 | 10.000.000 | 6.782.681 | 620.110 | 6.162.571 | 0.678268 | 0.062011 | 0.678268 | 10.039285 | 8.464625 | 10.230796 |
8 | 100.000.000 | 68.004.084 | 5.371.634 | 62.632.450 | 0.680041 | 0.053716 | 0.680041 | 10.026135 | 8.662389 | 10.163363 |
9 | 1.000.000.000 | 681.444.991 | 47.411.712 | 634.033.279 | 0.681445 | 0.047412 | 0.681445 | 10.020649 | 8.826311 | 10.123080 |
10 | 10.000.000.000 | 6.825.917.566 | 424.326.980 | 6.401.590.586 | 0.682592 | 0.042433 | 0.682592 | 10.016829 | 8.949835 | 10.096617 |
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 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 7 | 5 | 2 | 0.875000 | 0.625000 | 0.250000 | 2.333333 | 1.666667 | inf |
4 | 16 | 14 | 7 | 7 | 0.875000 | 0.437500 | 0.437500 | 2.000000 | 1.400000 | 3.500000 |
5 | 32 | 22 | 10 | 12 | 0.687500 | 0.312500 | 0.375000 | 1.571429 | 1.428571 | 1.714286 |
6 | 64 | 44 | 16 | 28 | 0.687500 | 0.250000 | 0.437500 | 2.000000 | 1.600000 | 2.333333 |
7 | 128 | 81 | 32 | 49 | 0.632812 | 0.250000 | 0.382812 | 1.840909 | 2.000000 | 1.750000 |
8 | 256 | 161 | 57 | 104 | 0.628906 | 0.222656 | 0.406250 | 1.987654 | 1.781250 | 2.122449 |
9 | 512 | 329 | 99 | 230 | 0.642578 | 0.193359 | 0.449219 | 2.043478 | 1.736842 | 2.211539 |
10 | 1.024 | 666 | 171 | 495 | 0.650391 | 0.166992 | 0.483398 | 2.024316 | 1.727273 | 2.152174 |
11 | 2.048 | 1.347 | 297 | 1.050 | 0.657715 | 0.145020 | 0.512695 | 2.022522 | 1.736842 | 2.121212 |
12 | 4.096 | 2.727 | 539 | 2.188 | 0.665771 | 0.131592 | 0.534180 | 2.024499 | 1.814815 | 2.083810 |
13 | 8.192 | 5.452 | 1.000 | 4.452 | 0.665527 | 0.122070 | 0.543457 | 1.999267 | 1.855288 | 2.034735 |
14 | 16.384 | 10.918 | 1.830 | 9.088 | 0.666382 | 0.111694 | 0.554688 | 2.002568 | 1.830000 | 2.041330 |
15 | 32.768 | 21.887 | 3.358 | 18.529 | 0.667938 | 0.102478 | 0.565460 | 2.004671 | 1.834973 | 2.038842 |
16 | 65.536 | 43.941 | 6.212 | 37.729 | 0.670486 | 0.094788 | 0.575699 | 2.007630 | 1.849911 | 2.036213 |
17 | 131.072 | 88.108 | 11.508 | 76.600 | 0.672211 | 0.087799 | 0.584412 | 2.005143 | 1.852543 | 2.030268 |
18 | 262.144 | 176.620 | 21.533 | 155.087 | 0.673752 | 0.082142 | 0.591610 | 2.004585 | 1.871133 | 2.024634 |
19 | 524.288 | 353.768 | 40.562 | 313.206 | 0.674759 | 0.077366 | 0.597393 | 2.002990 | 1.883713 | 2.019550 |
20 | 1.048.576 | 708.537 | 76.535 | 632.002 | 0.675714 | 0.072989 | 0.602724 | 2.002830 | 1.886865 | 2.017848 |
21 | 2.097.152 | 1.419.129 | 145.195 | 1.273.934 | 0.676693 | 0.069234 | 0.607459 | 2.002900 | 1.897106 | 2.015712 |
22 | 4.194.304 | 2.841.158 | 276.276 | 2.564.882 | 0.677385 | 0.065869 | 0.611516 | 2.002043 | 1.902793 | 2.013355 |
23 | 8.388.608 | 5.687.961 | 526.249 | 5.161.712 | 0.678058 | 0.062734 | 0.615324 | 2.001987 | 1.904794 | 2.012456 |
24 | 16.777.216 | 11.385.845 | 1.005.226 | 10.380.619 | 0.678649 | 0.059916 | 0.618733 | 2.001745 | 1.910172 | 2.011081 |
25 | 33.554.432 | 22.791.033 | 1.923.769 | 20.867.264 | 0.679226 | 0.057333 | 0.621893 | 2.001699 | 1.913768 | 2.010214 |
26 | 67.108.864 | 45.618.325 | 3.691.096 | 41.927.229 | 0.679766 | 0.055002 | 0.624764 | 2.001591 | 1.918679 | 2.009235 |
27 | 134.217.728 | 91.297.895 | 7.090.170 | 84.207.725 | 0.680222 | 0.052826 | 0.627396 | 2.001343 | 1.920885 | 2.008426 |
28 | 268.435.456 | 182.721.533 | 13.641.462 | 169.080.071 | 0.680691 | 0.050818 | 0.629872 | 2.001377 | 1.923996 | 2.007892 |
29 | 536.870.912 | 365.660.586 | 26.291.569 | 339.369.017 | 0.681096 | 0.048972 | 0.632124 | 2.001190 | 1.927328 | 2.007150 |
30 | 1.073.741.824 | 731.736.458 | 50.725.523 | 681.010.935 | 0.681483 | 0.047242 | 0.634241 | 2.001136 | 1.929346 | 2.006697 |
31 | 2.147.483.648 | 1.464.266.904 | 98.000.407 | 1.366.266.497 | 0.681852 | 0.045635 | 0.636217 | 2.001085 | 1.931974 | 2.006233 |
32 | 4.294.967.296 | 2.930.017.808 | 189.544.485 | 2.740.473.323 | 0.682198 | 0.044132 | 0.638066 | 2.001014 | 1.934119 | 2.005812 |
33 | 8.589.934.592 | 5.862.826.790 | 367.033.714 | 5.495.793.076 | 0.682523 | 0.042728 | 0.639795 | 2.000953 | 1.936399 | 2.005418 |
34 | 17.179.869.184 | 11.730.912.890 | 711.406.524 | 11.019.506.366 | 0.682829 | 0.041409 | 0.641420 | 2.000897 | 1.938259 | 2.005080 |
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 | 2 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 0 | 3 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 1 | 4 | 0 | 2 | 1 | 2 |
4 | 16 | 7 | 2 | 5 | 0 | 3 | 1 | 3 |
5 | 32 | 10 | 3 | 7 | 0 | 3 | 1 | 6 |
6 | 64 | 16 | 4 | 12 | 0 | 7 | 1 | 8 |
7 | 128 | 32 | 11 | 21 | 0 | 14 | 1 | 17 |
8 | 256 | 57 | 20 | 37 | 0 | 26 | 1 | 30 |
9 | 512 | 99 | 33 | 66 | 0 | 45 | 1 | 53 |
10 | 1.024 | 171 | 62 | 109 | 0 | 83 | 1 | 87 |
11 | 2.048 | 297 | 98 | 199 | 0 | 144 | 1 | 152 |
12 | 4.096 | 539 | 184 | 355 | 0 | 268 | 1 | 270 |
13 | 8.192 | 1.000 | 344 | 656 | 0 | 502 | 1 | 497 |
14 | 16.384 | 1.830 | 617 | 1.213 | 0 | 928 | 1 | 901 |
15 | 32.768 | 3.358 | 1.132 | 2.226 | 0 | 1.689 | 1 | 1.668 |
16 | 65.536 | 6.212 | 2.066 | 4.146 | 0 | 3.106 | 1 | 3.105 |
17 | 131.072 | 11.508 | 3.829 | 7.679 | 0 | 5.693 | 1 | 5.814 |
18 | 262.144 | 21.533 | 7.119 | 14.414 | 0 | 10.689 | 1 | 10.843 |
19 | 524.288 | 40.562 | 13.599 | 26.963 | 0 | 20.159 | 1 | 20.402 |
20 | 1.048.576 | 76.535 | 25.650 | 50.885 | 0 | 38.222 | 1 | 38.312 |
21 | 2.097.152 | 145.195 | 48.515 | 96.680 | 0 | 72.357 | 1 | 72.837 |
22 | 4.194.304 | 276.276 | 92.222 | 184.054 | 0 | 138.084 | 1 | 138.191 |
23 | 8.388.608 | 526.249 | 175.276 | 350.973 | 0 | 262.652 | 1 | 263.596 |
24 | 16.777.216 | 1.005.226 | 335.434 | 669.792 | 0 | 502.796 | 1 | 502.429 |
25 | 33.554.432 | 1.923.769 | 641.798 | 1.281.971 | 0 | 961.614 | 1 | 962.154 |
26 | 67.108.864 | 3.691.096 | 1.231.060 | 2.460.036 | 0 | 1.844.691 | 1 | 1.846.404 |
27 | 134.217.728 | 7.090.170 | 2.364.342 | 4.725.828 | 0 | 3.544.889 | 1 | 3.545.280 |
28 | 268.435.456 | 13.641.462 | 4.547.628 | 9.093.834 | 0 | 6.819.731 | 1 | 6.821.730 |
29 | 536.870.912 | 26.291.569 | 8.764.022 | 17.527.547 | 0 | 13.144.280 | 1 | 13.147.288 |
30 | 1.073.741.824 | 50.725.523 | 16.906.423 | 33.819.100 | 0 | 25.358.667 | 1 | 25.366.855 |
31 | 2.147.483.648 | 98.000.407 | 32.664.484 | 65.335.923 | 0 | 48.996.700 | 1 | 49.003.706 |
32 | 4.294.967.296 | 189.544.485 | 63.180.473 | 126.364.012 | 0 | 94.764.882 | 1 | 94.779.602 |
33 | 8.589.934.592 | 367.033.714 | 122.341.342 | 244.692.372 | 0 | 183.505.274 | 1 | 183.528.439 |
34 | 17.179.869.184 | 711.406.524 | 237.138.187 | 474.268.337 | 0 | 355.696.375 | 1 | 355.710.148 |
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 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
4 | 16 | 7 | 4 | 3 | 3 | 1 | 2 | 1 |
5 | 32 | 12 | 9 | 3 | 5 | 2 | 3 | 2 |
6 | 64 | 28 | 15 | 13 | 9 | 7 | 8 | 4 |
7 | 128 | 49 | 28 | 21 | 17 | 11 | 13 | 8 |
8 | 256 | 104 | 57 | 47 | 31 | 26 | 25 | 22 |
9 | 512 | 230 | 123 | 107 | 62 | 53 | 67 | 48 |
10 | 1.024 | 495 | 252 | 243 | 127 | 119 | 138 | 111 |
11 | 2.048 | 1.050 | 544 | 506 | 254 | 250 | 284 | 262 |
12 | 4.096 | 2.188 | 1.132 | 1.056 | 532 | 527 | 587 | 542 |
13 | 8.192 | 4.452 | 2.280 | 2.172 | 1.110 | 1.070 | 1.179 | 1.093 |
14 | 16.384 | 9.088 | 4.635 | 4.453 | 2.328 | 2.186 | 2.375 | 2.199 |
15 | 32.768 | 18.529 | 9.514 | 9.015 | 4.787 | 4.483 | 4.783 | 4.476 |
16 | 65.536 | 37.729 | 19.242 | 18.487 | 9.696 | 9.118 | 9.749 | 9.166 |
17 | 131.072 | 76.600 | 39.057 | 37.543 | 19.618 | 18.644 | 19.780 | 18.558 |
18 | 262.144 | 155.087 | 78.841 | 76.246 | 39.881 | 37.670 | 39.953 | 37.583 |
19 | 524.288 | 313.206 | 159.076 | 154.130 | 80.562 | 76.387 | 80.380 | 75.877 |
20 | 1.048.576 | 632.002 | 321.168 | 310.834 | 161.802 | 154.446 | 162.107 | 153.647 |
21 | 2.097.152 | 1.273.934 | 646.834 | 627.100 | 326.137 | 311.162 | 326.466 | 310.169 |
22 | 4.194.304 | 2.564.882 | 1.301.614 | 1.263.268 | 655.884 | 628.241 | 654.906 | 625.851 |
23 | 8.388.608 | 5.161.712 | 2.617.666 | 2.544.046 | 1.319.109 | 1.263.016 | 1.317.775 | 1.261.812 |
24 | 16.777.216 | 10.380.619 | 5.260.041 | 5.120.578 | 2.649.755 | 2.541.564 | 2.648.107 | 2.541.193 |
25 | 33.554.432 | 20.867.264 | 10.565.754 | 10.301.510 | 5.319.292 | 5.115.510 | 5.318.077 | 5.114.385 |
26 | 67.108.864 | 41.927.229 | 21.215.865 | 20.711.364 | 10.675.361 | 10.289.533 | 10.673.496 | 10.288.839 |
27 | 134.217.728 | 84.207.725 | 42.590.768 | 41.616.957 | 21.422.653 | 20.682.994 | 21.419.407 | 20.682.671 |
28 | 268.435.456 | 169.080.071 | 85.467.514 | 83.612.557 | 42.986.722 | 41.558.012 | 42.977.944 | 41.557.393 |
29 | 536.870.912 | 339.369.017 | 171.459.272 | 167.909.745 | 86.218.683 | 83.461.978 | 86.212.305 | 83.476.051 |
30 | 1.073.741.824 | 681.010.935 | 343.936.699 | 337.074.236 | 172.902.872 | 167.612.942 | 172.880.217 | 167.614.904 |
31 | 2.147.483.648 | 1.366.266.497 | 689.781.133 | 676.485.364 | 346.652.115 | 336.489.059 | 346.649.782 | 336.475.541 |
32 | 4.294.967.296 | 2.740.473.323 | 1.383.126.972 | 1.357.346.351 | 694.931.683 | 675.311.273 | 694.944.301 | 675.286.066 |
33 | 8.589.934.592 | 5.495.793.076 | 2.772.825.779 | 2.722.967.297 | 1.392.906.359 | 1.354.979.109 | 1.392.978.948 | 1.354.928.660 |
34 | 17.179.869.184 | 11.019.506.366 | 5.557.993.548 | 5.461.512.818 | 2.791.596.106 | 2.718.112.742 | 2.791.696.348 | 2.718.101.170 |