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-12x+5
f(0)=5
f(1)=3
f(2)=1
f(3)=11
f(4)=1
f(5)=1
f(6)=31
f(7)=1
f(8)=1
f(9)=1
f(10)=1
f(11)=1
f(12)=1
f(13)=1
f(14)=1
f(15)=1
f(16)=23
f(17)=1
f(18)=113
f(19)=1
f(20)=1
f(21)=97
f(22)=1
f(23)=43
f(24)=293
f(25)=1
f(26)=41
f(27)=1
f(28)=151
f(29)=83
f(30)=109
f(31)=1
f(32)=1
f(33)=349
f(34)=251
f(35)=1
f(36)=79
f(37)=1
f(38)=331
f(39)=1
f(40)=1
f(41)=199
f(42)=1
f(43)=223
f(44)=157
f(45)=149
f(46)=523
f(47)=1
f(48)=1733
f(49)=101
f(50)=127
f(51)=997
f(52)=139
f(53)=1
f(54)=2273
f(55)=1
f(56)=823
f(57)=257
f(58)=1
f(59)=463
f(60)=577
f(61)=499
f(62)=1
f(63)=1609
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=179
f(70)=271
f(71)=233
f(72)=173
f(73)=743
f(74)=1531
f(75)=1
f(76)=541
f(77)=167
f(78)=5153
f(79)=883
f(80)=1
f(81)=2797
f(82)=383
f(83)=983
f(84)=6053
f(85)=1
f(86)=193
f(87)=653
f(88)=1
f(89)=1
f(90)=281
f(91)=1
f(92)=491
f(93)=3769
f(94)=857
f(95)=263
f(96)=8069
f(97)=1
f(98)=937
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-12x+5 could be written as f(y)= y^2-31 with x=y+6
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
f'(x)>2x-13 with x > 6
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 | 4 | 4 | 0 | 0.400000 | 0.400000 | 0.000000 | |||
2 | 100 | 55 | 17 | 38 | 0.550000 | 0.170000 | 0.380000 | 13.750000 | 4.250000 | inf |
3 | 1.000 | 648 | 95 | 553 | 0.648000 | 0.095000 | 0.553000 | 11.781818 | 5.588235 | 14.552631 |
4 | 10.000 | 6.651 | 631 | 6.020 | 0.665100 | 0.063100 | 0.602000 | 10.263889 | 6.642105 | 10.886076 |
5 | 100.000 | 67.133 | 4.860 | 62.273 | 0.671330 | 0.048600 | 0.622730 | 10.093670 | 7.702060 | 10.344352 |
6 | 1.000.000 | 675.275 | 39.881 | 635.394 | 0.675275 | 0.039881 | 0.635394 | 10.058764 | 8.205967 | 10.203362 |
7 | 10.000.000 | 6.775.603 | 335.754 | 6.439.849 | 0.677560 | 0.033575 | 0.643985 | 10.033842 | 8.418897 | 10.135206 |
8 | 100.000.000 | 67.940.549 | 2.905.752 | 65.034.797 | 0.679406 | 0.029058 | 0.650348 | 10.027233 | 8.654408 | 10.098807 |
9 | 1.000.000.000 | 680.819.180 | 25.628.036 | 655.191.144 | 0.680819 | 0.025628 | 0.655191 | 10.020807 | 8.819760 | 10.074471 |
10 | 10.000.000.000 | 6.819.663.025 | 229.115.455 | 6.590.547.570 | 0.681966 | 0.022912 | 0.659055 | 10.016849 | 8.940032 | 10.058969 |
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 | |||
2 | 4 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 4 | 4 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.333333 | 1.333333 | -nan |
4 | 16 | 4 | 4 | 0 | 0.250000 | 0.250000 | 0.000000 | 1.000000 | 1.000000 | -nan |
5 | 32 | 10 | 7 | 3 | 0.312500 | 0.218750 | 0.093750 | 2.500000 | 1.750000 | inf |
6 | 64 | 31 | 12 | 19 | 0.484375 | 0.187500 | 0.296875 | 3.100000 | 1.714286 | 6.333333 |
7 | 128 | 71 | 20 | 51 | 0.554688 | 0.156250 | 0.398438 | 2.290323 | 1.666667 | 2.684211 |
8 | 256 | 154 | 34 | 120 | 0.601562 | 0.132812 | 0.468750 | 2.169014 | 1.700000 | 2.352941 |
9 | 512 | 320 | 58 | 262 | 0.625000 | 0.113281 | 0.511719 | 2.077922 | 1.705882 | 2.183333 |
10 | 1.024 | 663 | 97 | 566 | 0.647461 | 0.094727 | 0.552734 | 2.071875 | 1.672414 | 2.160305 |
11 | 2.048 | 1.343 | 171 | 1.172 | 0.655762 | 0.083496 | 0.572266 | 2.025641 | 1.762887 | 2.070671 |
12 | 4.096 | 2.707 | 291 | 2.416 | 0.660889 | 0.071045 | 0.589844 | 2.015637 | 1.701754 | 2.061434 |
13 | 8.192 | 5.444 | 523 | 4.921 | 0.664551 | 0.063843 | 0.600708 | 2.011082 | 1.797251 | 2.036838 |
14 | 16.384 | 10.909 | 977 | 9.932 | 0.665833 | 0.059631 | 0.606201 | 2.003857 | 1.868069 | 2.018289 |
15 | 32.768 | 21.970 | 1.764 | 20.206 | 0.670471 | 0.053833 | 0.616638 | 2.013933 | 1.805527 | 2.034434 |
16 | 65.536 | 44.005 | 3.314 | 40.691 | 0.671463 | 0.050568 | 0.620895 | 2.002959 | 1.878685 | 2.013808 |
17 | 131.072 | 88.023 | 6.239 | 81.784 | 0.671562 | 0.047600 | 0.623962 | 2.000295 | 1.882619 | 2.009879 |
18 | 262.144 | 176.580 | 11.716 | 164.864 | 0.673599 | 0.044693 | 0.628906 | 2.006067 | 1.877865 | 2.015847 |
19 | 524.288 | 353.650 | 22.139 | 331.511 | 0.674534 | 0.042227 | 0.632307 | 2.002775 | 1.889638 | 2.010815 |
20 | 1.048.576 | 708.075 | 41.656 | 666.419 | 0.675273 | 0.039726 | 0.635547 | 2.002192 | 1.881567 | 2.010247 |
21 | 2.097.152 | 1.418.056 | 78.760 | 1.339.296 | 0.676182 | 0.037556 | 0.638626 | 2.002692 | 1.890724 | 2.009691 |
22 | 4.194.304 | 2.838.717 | 149.641 | 2.689.076 | 0.676803 | 0.035677 | 0.641126 | 2.001837 | 1.899962 | 2.007828 |
23 | 8.388.608 | 5.682.097 | 285.108 | 5.396.989 | 0.677359 | 0.033988 | 0.643371 | 2.001643 | 1.905280 | 2.007005 |
24 | 16.777.216 | 11.376.220 | 544.235 | 10.831.985 | 0.678076 | 0.032439 | 0.645637 | 2.002116 | 1.908873 | 2.007042 |
25 | 33.554.432 | 22.770.377 | 1.041.230 | 21.729.147 | 0.678610 | 0.031031 | 0.647579 | 2.001577 | 1.913199 | 2.006017 |
26 | 67.108.864 | 45.576.532 | 1.996.339 | 43.580.193 | 0.679143 | 0.029748 | 0.649395 | 2.001571 | 1.917289 | 2.005610 |
27 | 134.217.728 | 91.216.056 | 3.834.384 | 87.381.672 | 0.679613 | 0.028568 | 0.651044 | 2.001382 | 1.920708 | 2.005078 |
28 | 268.435.456 | 182.552.265 | 7.375.997 | 175.176.268 | 0.680060 | 0.027478 | 0.652582 | 2.001317 | 1.923646 | 2.004725 |
29 | 536.870.912 | 365.323.268 | 14.212.813 | 351.110.455 | 0.680468 | 0.026473 | 0.653994 | 2.001198 | 1.926901 | 2.004327 |
30 | 1.073.741.824 | 731.066.867 | 27.417.391 | 703.649.476 | 0.680859 | 0.025534 | 0.655325 | 2.001151 | 1.929062 | 2.004069 |
31 | 2.147.483.648 | 1.462.915.021 | 52.944.916 | 1.409.970.105 | 0.681223 | 0.024654 | 0.656568 | 2.001069 | 1.931070 | 2.003796 |
32 | 4.294.967.296 | 2.927.317.310 | 102.384.666 | 2.824.932.644 | 0.681569 | 0.023838 | 0.657731 | 2.001017 | 1.933796 | 2.003541 |
33 | 8.589.934.592 | 5.857.451.161 | 198.189.482 | 5.659.261.679 | 0.681897 | 0.023072 | 0.658825 | 2.000962 | 1.935734 | 2.003326 |
34 | 17.179.869.184 | 11.720.212.867 | 384.046.706 | 11.336.166.161 | 0.682206 | 0.022354 | 0.659852 | 2.000907 | 1.937775 | 2.003118 |
35 | 34.359.738.368 | 23.450.502.558 | 744.937.723 | 22.705.564.835 | 0.682499 | 0.021681 | 0.660819 | 2.000860 | 1.939706 | 2.002932 |
36 | 68.719.476.736 | 46.920.173.811 | 1.446.222.624 | 45.473.951.187 | 0.682778 | 0.021045 | 0.661733 | 2.000818 | 1.941401 | 2.002767 |
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 | 1 | 0 |
2 | 4 | 3 | 0 | 2 | 0 | 2 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 0 | 2 | 1 | 1 |
4 | 16 | 4 | 1 | 2 | 0 | 2 | 1 | 1 |
5 | 32 | 7 | 2 | 4 | 2 | 2 | 2 | 1 |
6 | 64 | 12 | 5 | 6 | 4 | 2 | 5 | 1 |
7 | 128 | 20 | 8 | 11 | 8 | 2 | 9 | 1 |
8 | 256 | 34 | 16 | 17 | 14 | 2 | 17 | 1 |
9 | 512 | 58 | 29 | 28 | 26 | 2 | 29 | 1 |
10 | 1.024 | 97 | 48 | 48 | 47 | 2 | 47 | 1 |
11 | 2.048 | 171 | 86 | 84 | 80 | 2 | 88 | 1 |
12 | 4.096 | 291 | 150 | 140 | 141 | 2 | 147 | 1 |
13 | 8.192 | 523 | 263 | 259 | 260 | 2 | 260 | 1 |
14 | 16.384 | 977 | 491 | 485 | 489 | 2 | 485 | 1 |
15 | 32.768 | 1.764 | 892 | 871 | 866 | 2 | 895 | 1 |
16 | 65.536 | 3.314 | 1.681 | 1.632 | 1.661 | 2 | 1.650 | 1 |
17 | 131.072 | 6.239 | 3.158 | 3.080 | 3.136 | 2 | 3.100 | 1 |
18 | 262.144 | 11.716 | 5.910 | 5.805 | 5.837 | 2 | 5.876 | 1 |
19 | 524.288 | 22.139 | 11.230 | 10.908 | 11.061 | 2 | 11.075 | 1 |
20 | 1.048.576 | 41.656 | 21.111 | 20.544 | 20.837 | 2 | 20.816 | 1 |
21 | 2.097.152 | 78.760 | 39.852 | 38.907 | 39.469 | 2 | 39.288 | 1 |
22 | 4.194.304 | 149.641 | 75.778 | 73.862 | 74.948 | 2 | 74.690 | 1 |
23 | 8.388.608 | 285.108 | 144.227 | 140.880 | 142.806 | 2 | 142.299 | 1 |
24 | 16.777.216 | 544.235 | 275.413 | 268.821 | 272.497 | 2 | 271.735 | 1 |
25 | 33.554.432 | 1.041.230 | 526.573 | 514.656 | 521.180 | 2 | 520.047 | 1 |
26 | 67.108.864 | 1.996.339 | 1.009.151 | 987.187 | 998.611 | 2 | 997.725 | 1 |
27 | 134.217.728 | 3.834.384 | 1.936.142 | 1.898.241 | 1.917.929 | 2 | 1.916.452 | 1 |
28 | 268.435.456 | 7.375.997 | 3.723.254 | 3.652.742 | 3.689.060 | 2 | 3.686.934 | 1 |
29 | 536.870.912 | 14.212.813 | 7.170.748 | 7.042.064 | 7.107.422 | 2 | 7.105.388 | 1 |
30 | 1.073.741.824 | 27.417.391 | 13.828.480 | 13.588.910 | 13.710.648 | 2 | 13.706.740 | 1 |
31 | 2.147.483.648 | 52.944.916 | 26.694.274 | 26.250.641 | 26.470.565 | 2 | 26.474.348 | 1 |
32 | 4.294.967.296 | 102.384.666 | 51.613.280 | 50.771.385 | 51.193.230 | 2 | 51.191.433 | 1 |
33 | 8.589.934.592 | 198.189.482 | 99.888.794 | 98.300.687 | 99.094.585 | 2 | 99.094.894 | 1 |
34 | 17.179.869.184 | 384.046.706 | 193.508.528 | 190.538.177 | 192.016.944 | 2 | 192.029.759 | 1 |
35 | 34.359.738.368 | 744.937.723 | 375.268.895 | 369.668.827 | 372.464.330 | 2 | 372.473.390 | 1 |
36 | 68.719.476.736 | 1.446.222.624 | 728.392.200 | 717.830.423 | 723.104.085 | 2 | 723.118.536 | 1 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
6 | 64 | 19 | 14 | 5 | 2 | 6 | 4 | 7 |
7 | 128 | 51 | 25 | 26 | 10 | 13 | 10 | 18 |
8 | 256 | 120 | 63 | 57 | 17 | 37 | 27 | 39 |
9 | 512 | 262 | 138 | 124 | 48 | 83 | 55 | 76 |
10 | 1.024 | 566 | 274 | 292 | 107 | 176 | 125 | 158 |
11 | 2.048 | 1.172 | 582 | 590 | 240 | 350 | 254 | 328 |
12 | 4.096 | 2.416 | 1.217 | 1.199 | 521 | 704 | 510 | 681 |
13 | 8.192 | 4.921 | 2.432 | 2.489 | 1.080 | 1.389 | 1.067 | 1.385 |
14 | 16.384 | 9.932 | 4.922 | 5.010 | 2.187 | 2.804 | 2.215 | 2.726 |
15 | 32.768 | 20.206 | 10.049 | 10.157 | 4.573 | 5.605 | 4.578 | 5.450 |
16 | 65.536 | 40.691 | 20.173 | 20.518 | 9.358 | 11.100 | 9.279 | 10.954 |
17 | 131.072 | 81.784 | 40.663 | 41.121 | 18.788 | 22.109 | 18.748 | 22.139 |
18 | 262.144 | 164.864 | 82.322 | 82.542 | 38.069 | 44.280 | 38.200 | 44.315 |
19 | 524.288 | 331.511 | 165.513 | 165.998 | 77.019 | 88.663 | 77.294 | 88.535 |
20 | 1.048.576 | 666.419 | 333.089 | 333.330 | 155.592 | 177.490 | 155.869 | 177.468 |
21 | 2.097.152 | 1.339.296 | 669.259 | 670.037 | 314.097 | 355.408 | 314.420 | 355.371 |
22 | 4.194.304 | 2.689.076 | 1.343.013 | 1.346.063 | 633.730 | 711.186 | 633.357 | 710.803 |
23 | 8.388.608 | 5.396.989 | 2.695.422 | 2.701.567 | 1.275.000 | 1.423.122 | 1.275.272 | 1.423.595 |
24 | 16.777.216 | 10.831.985 | 5.412.280 | 5.419.705 | 2.565.416 | 2.850.044 | 2.568.473 | 2.848.052 |
25 | 33.554.432 | 21.729.147 | 10.857.438 | 10.871.709 | 5.163.447 | 5.700.547 | 5.164.645 | 5.700.508 |
26 | 67.108.864 | 43.580.193 | 21.780.534 | 21.799.659 | 10.378.777 | 11.413.914 | 10.381.204 | 11.406.298 |
27 | 134.217.728 | 87.381.672 | 43.678.979 | 43.702.693 | 20.856.356 | 22.835.133 | 20.860.509 | 22.829.674 |
28 | 268.435.456 | 175.176.268 | 87.563.440 | 87.612.828 | 41.895.955 | 45.691.020 | 41.899.364 | 45.689.929 |
29 | 536.870.912 | 351.110.455 | 175.506.533 | 175.603.922 | 84.133.110 | 91.418.285 | 84.145.240 | 91.413.820 |
30 | 1.073.741.824 | 703.649.476 | 351.743.540 | 351.905.936 | 168.892.433 | 182.931.691 | 168.893.878 | 182.931.474 |
31 | 2.147.483.648 | 1.409.970.105 | 704.831.126 | 705.138.979 | 338.927.760 | 366.050.653 | 338.955.398 | 366.036.294 |
32 | 4.294.967.296 | 2.824.932.644 | 1.412.202.956 | 1.412.729.688 | 680.053.364 | 732.414.682 | 680.057.309 | 732.407.289 |
33 | 8.589.934.592 | 5.659.261.679 | 2.829.179.169 | 2.830.082.510 | 1.364.144.504 | 1.465.469.463 | 1.364.179.523 | 1.465.468.189 |
34 | 17.179.869.184 | 11.336.166.161 | 5.667.217.111 | 5.668.949.050 | 2.735.956.134 | 2.932.127.342 | 2.735.960.485 | 2.932.122.200 |
35 | 34.359.738.368 | 22.705.564.835 | 11.351.095.659 | 11.354.469.176 | 5.486.232.214 | 5.866.513.810 | 5.486.334.761 | 5.866.484.050 |
36 | 68.719.476.736 | 45.473.951.187 | 22.733.793.316 | 22.740.157.871 | 10.999.580.846 | 11.737.417.067 | 10.999.631.600 | 11.737.321.674 |