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-43x+3
f(0)=3
f(1)=13
f(2)=79
f(3)=1
f(4)=17
f(5)=11
f(6)=73
f(7)=83
f(8)=277
f(9)=101
f(10)=109
f(11)=349
f(12)=41
f(13)=43
f(14)=31
f(15)=139
f(16)=1
f(17)=439
f(18)=149
f(19)=151
f(20)=457
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=47
f(45)=1
f(46)=1
f(47)=191
f(48)=1
f(49)=1
f(50)=353
f(51)=137
f(52)=157
f(53)=1
f(54)=199
f(55)=1
f(56)=1
f(57)=89
f(58)=97
f(59)=947
f(60)=1
f(61)=367
f(62)=1181
f(63)=421
f(64)=449
f(65)=1433
f(66)=1
f(67)=179
f(68)=131
f(69)=599
f(70)=631
f(71)=181
f(72)=1
f(73)=1
f(74)=2297
f(75)=1
f(76)=1
f(77)=2621
f(78)=911
f(79)=1
f(80)=2963
f(81)=1
f(82)=1
f(83)=3323
f(84)=383
f(85)=397
f(86)=3701
f(87)=1277
f(88)=1321
f(89)=241
f(90)=1
f(91)=1
f(92)=347
f(93)=1
f(94)=1
f(95)=4943
f(96)=1697
f(97)=1747
f(98)=5393
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-43x+3 could be written as f(y)= y^2-459.25 with x=y+21.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-21.5
f'(x)>2x-44 with x > 21
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 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 51 | 19 | 32 | 0.510000 | 0.190000 | 0.510000 | 5.100000 | 4.750000 | 5.333333 |
3 | 1.000 | 643 | 119 | 524 | 0.643000 | 0.119000 | 0.643000 | 12.607843 | 6.263158 | 16.375000 |
4 | 10.000 | 6.815 | 827 | 5.988 | 0.681500 | 0.082700 | 0.681500 | 10.598756 | 6.949580 | 11.427481 |
5 | 100.000 | 68.782 | 6.231 | 62.551 | 0.687820 | 0.062310 | 0.687820 | 10.092736 | 7.534462 | 10.446059 |
6 | 1.000.000 | 688.335 | 51.592 | 636.743 | 0.688335 | 0.051592 | 0.688335 | 10.007487 | 8.279891 | 10.179582 |
7 | 10.000.000 | 6.887.856 | 438.366 | 6.449.490 | 0.688786 | 0.043837 | 0.688786 | 10.006546 | 8.496782 | 10.128875 |
8 | 100.000.000 | 68.925.210 | 3.797.452 | 65.127.758 | 0.689252 | 0.037975 | 0.689252 | 10.006772 | 8.662743 | 10.098125 |
9 | 1.000.000.000 | 689.605.296 | 33.513.591 | 656.091.705 | 0.689605 | 0.033514 | 0.689605 | 10.005125 | 8.825284 | 10.073918 |
10 | 10.000.000.000 | 6.898.915.768 | 299.878.025 | 6.599.037.743 | 0.689892 | 0.029988 | 0.689892 | 10.004151 | 8.947952 | 10.058103 |
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 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 2.000000 | 2.000000 |
4 | 16 | 15 | 5 | 10 | 0.937500 | 0.312500 | 0.625000 | 1.875000 | 1.250000 | 2.500000 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 1.266667 | 1.400000 | 1.200000 |
6 | 64 | 29 | 11 | 18 | 0.453125 | 0.171875 | 0.281250 | 1.526316 | 1.571429 | 1.500000 |
7 | 128 | 69 | 23 | 46 | 0.539062 | 0.179688 | 0.359375 | 2.379310 | 2.090909 | 2.555556 |
8 | 256 | 149 | 38 | 111 | 0.582031 | 0.148438 | 0.433594 | 2.159420 | 1.652174 | 2.413043 |
9 | 512 | 315 | 66 | 249 | 0.615234 | 0.128906 | 0.486328 | 2.114094 | 1.736842 | 2.243243 |
10 | 1.024 | 658 | 122 | 536 | 0.642578 | 0.119141 | 0.523438 | 2.088889 | 1.848485 | 2.152611 |
11 | 2.048 | 1.360 | 212 | 1.148 | 0.664062 | 0.103516 | 0.560547 | 2.066869 | 1.737705 | 2.141791 |
12 | 4.096 | 2.773 | 385 | 2.388 | 0.677002 | 0.093994 | 0.583008 | 2.038970 | 1.816038 | 2.080139 |
13 | 8.192 | 5.571 | 684 | 4.887 | 0.680054 | 0.083496 | 0.596558 | 2.009016 | 1.776623 | 2.046482 |
14 | 16.384 | 11.184 | 1.268 | 9.916 | 0.682617 | 0.077393 | 0.605225 | 2.007539 | 1.853801 | 2.029057 |
15 | 32.768 | 22.486 | 2.322 | 20.164 | 0.686218 | 0.070862 | 0.615356 | 2.010551 | 1.831230 | 2.033481 |
16 | 65.536 | 45.085 | 4.289 | 40.796 | 0.687943 | 0.065445 | 0.622498 | 2.005025 | 1.847115 | 2.023210 |
17 | 131.072 | 90.165 | 7.973 | 82.192 | 0.687904 | 0.060829 | 0.627075 | 1.999889 | 1.858941 | 2.014707 |
18 | 262.144 | 180.294 | 15.157 | 165.137 | 0.687767 | 0.057819 | 0.629948 | 1.999601 | 1.901041 | 2.009161 |
19 | 524.288 | 360.766 | 28.585 | 332.181 | 0.688107 | 0.054522 | 0.633585 | 2.000987 | 1.885927 | 2.011548 |
20 | 1.048.576 | 721.864 | 53.981 | 667.883 | 0.688423 | 0.051480 | 0.636943 | 2.000920 | 1.888438 | 2.010600 |
21 | 2.097.152 | 1.443.978 | 102.411 | 1.341.567 | 0.688542 | 0.048833 | 0.639709 | 2.000346 | 1.897168 | 2.008686 |
22 | 4.194.304 | 2.887.901 | 195.110 | 2.692.791 | 0.688529 | 0.046518 | 0.642011 | 1.999962 | 1.905166 | 2.007198 |
23 | 8.388.608 | 5.777.628 | 372.100 | 5.405.528 | 0.688747 | 0.044358 | 0.644389 | 2.000632 | 1.907129 | 2.007407 |
24 | 16.777.216 | 11.557.994 | 710.836 | 10.847.158 | 0.688910 | 0.042369 | 0.646541 | 2.000474 | 1.910336 | 2.006679 |
25 | 33.554.432 | 23.120.528 | 1.360.528 | 21.760.000 | 0.689045 | 0.040547 | 0.648499 | 2.000393 | 1.913983 | 2.006055 |
26 | 67.108.864 | 46.249.694 | 2.608.634 | 43.641.060 | 0.689174 | 0.038872 | 0.650302 | 2.000374 | 1.917369 | 2.005563 |
27 | 134.217.728 | 92.516.449 | 5.011.206 | 87.505.243 | 0.689301 | 0.037336 | 0.651965 | 2.000369 | 1.921008 | 2.005113 |
28 | 268.435.456 | 185.064.250 | 9.643.081 | 175.421.169 | 0.689418 | 0.035923 | 0.653495 | 2.000339 | 1.924303 | 2.004693 |
29 | 536.870.912 | 370.183.918 | 18.581.737 | 351.602.181 | 0.689521 | 0.034611 | 0.654910 | 2.000299 | 1.926950 | 2.004332 |
30 | 1.073.741.824 | 740.466.673 | 35.855.737 | 704.610.936 | 0.689613 | 0.033393 | 0.656220 | 2.000267 | 1.929623 | 2.004000 |
31 | 2.147.483.648 | 1.481.126.939 | 69.262.712 | 1.411.864.227 | 0.689703 | 0.032253 | 0.657450 | 2.000261 | 1.931705 | 2.003750 |
32 | 4.294.967.296 | 2.962.626.655 | 133.971.504 | 2.828.655.151 | 0.689790 | 0.031193 | 0.658598 | 2.000252 | 1.934252 | 2.003489 |
33 | 8.589.934.592 | 5.925.978.612 | 259.395.466 | 5.666.583.146 | 0.689875 | 0.030198 | 0.659677 | 2.000245 | 1.936199 | 2.003278 |
34 | 17.179.869.184 | 11.853.321.454 | 502.768.886 | 11.350.552.568 | 0.689954 | 0.029265 | 0.660689 | 2.000230 | 1.938233 | 2.003068 |
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 | 1 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 3 | 0 | 0 | 2 | 1 | 1 |
4 | 16 | 5 | 4 | 0 | 0 | 2 | 2 | 1 |
5 | 32 | 7 | 6 | 0 | 1 | 2 | 2 | 2 |
6 | 64 | 11 | 6 | 4 | 2 | 3 | 3 | 3 |
7 | 128 | 23 | 6 | 15 | 6 | 6 | 7 | 4 |
8 | 256 | 38 | 6 | 30 | 10 | 7 | 15 | 6 |
9 | 512 | 66 | 6 | 58 | 19 | 16 | 20 | 11 |
10 | 1.024 | 122 | 6 | 114 | 32 | 26 | 38 | 26 |
11 | 2.048 | 212 | 6 | 204 | 51 | 53 | 62 | 46 |
12 | 4.096 | 385 | 6 | 377 | 93 | 93 | 101 | 98 |
13 | 8.192 | 684 | 6 | 676 | 170 | 170 | 178 | 166 |
14 | 16.384 | 1.268 | 6 | 1.260 | 310 | 323 | 307 | 328 |
15 | 32.768 | 2.322 | 6 | 2.314 | 567 | 590 | 573 | 592 |
16 | 65.536 | 4.289 | 6 | 4.281 | 1.063 | 1.079 | 1.065 | 1.082 |
17 | 131.072 | 7.973 | 6 | 7.965 | 1.985 | 1.995 | 1.992 | 2.001 |
18 | 262.144 | 15.157 | 6 | 15.149 | 3.792 | 3.794 | 3.785 | 3.786 |
19 | 524.288 | 28.585 | 6 | 28.577 | 7.209 | 7.110 | 7.150 | 7.116 |
20 | 1.048.576 | 53.981 | 6 | 53.973 | 13.558 | 13.494 | 13.513 | 13.416 |
21 | 2.097.152 | 102.411 | 6 | 102.403 | 25.692 | 25.588 | 25.679 | 25.452 |
22 | 4.194.304 | 195.110 | 6 | 195.102 | 48.864 | 48.718 | 48.769 | 48.759 |
23 | 8.388.608 | 372.100 | 6 | 372.092 | 93.125 | 92.972 | 92.894 | 93.109 |
24 | 16.777.216 | 710.836 | 6 | 710.828 | 177.532 | 177.799 | 177.661 | 177.844 |
25 | 33.554.432 | 1.360.528 | 6 | 1.360.520 | 339.670 | 340.212 | 340.158 | 340.488 |
26 | 67.108.864 | 2.608.634 | 6 | 2.608.626 | 652.199 | 652.388 | 651.940 | 652.107 |
27 | 134.217.728 | 5.011.206 | 6 | 5.011.198 | 1.252.619 | 1.253.301 | 1.252.502 | 1.252.784 |
28 | 268.435.456 | 9.643.081 | 6 | 9.643.073 | 2.409.389 | 2.411.212 | 2.411.520 | 2.410.960 |
29 | 536.870.912 | 18.581.737 | 6 | 18.581.729 | 4.644.509 | 4.643.762 | 4.646.875 | 4.646.591 |
30 | 1.073.741.824 | 35.855.737 | 6 | 35.855.729 | 8.963.689 | 8.962.189 | 8.964.706 | 8.965.153 |
31 | 2.147.483.648 | 69.262.712 | 6 | 69.262.704 | 17.315.403 | 17.313.930 | 17.317.376 | 17.316.003 |
32 | 4.294.967.296 | 133.971.504 | 6 | 133.971.496 | 33.489.120 | 33.485.906 | 33.501.967 | 33.494.511 |
33 | 8.589.934.592 | 259.395.466 | 6 | 259.395.458 | 64.845.691 | 64.844.456 | 64.863.847 | 64.841.472 |
34 | 17.179.869.184 | 502.768.886 | 6 | 502.768.878 | 125.686.674 | 125.689.320 | 125.700.664 | 125.692.228 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 2 | 1 | 1 | 0 |
4 | 16 | 10 | 6 | 4 | 3 | 3 | 3 | 1 |
5 | 32 | 12 | 7 | 5 | 3 | 3 | 4 | 2 |
6 | 64 | 18 | 11 | 7 | 5 | 3 | 6 | 4 |
7 | 128 | 46 | 23 | 23 | 10 | 9 | 14 | 13 |
8 | 256 | 111 | 56 | 55 | 27 | 27 | 31 | 26 |
9 | 512 | 249 | 126 | 123 | 59 | 69 | 63 | 58 |
10 | 1.024 | 536 | 260 | 276 | 127 | 133 | 136 | 140 |
11 | 2.048 | 1.148 | 578 | 570 | 280 | 295 | 277 | 296 |
12 | 4.096 | 2.388 | 1.191 | 1.197 | 574 | 595 | 591 | 628 |
13 | 8.192 | 4.887 | 2.440 | 2.447 | 1.216 | 1.212 | 1.193 | 1.266 |
14 | 16.384 | 9.916 | 4.956 | 4.960 | 2.470 | 2.480 | 2.445 | 2.521 |
15 | 32.768 | 20.164 | 10.086 | 10.078 | 4.978 | 5.088 | 5.025 | 5.073 |
16 | 65.536 | 40.796 | 20.434 | 20.362 | 10.180 | 10.166 | 10.199 | 10.251 |
17 | 131.072 | 82.192 | 41.194 | 40.998 | 20.580 | 20.568 | 20.557 | 20.487 |
18 | 262.144 | 165.137 | 82.996 | 82.141 | 41.287 | 41.422 | 41.183 | 41.245 |
19 | 524.288 | 332.181 | 166.770 | 165.411 | 82.671 | 83.132 | 83.226 | 83.152 |
20 | 1.048.576 | 667.883 | 334.790 | 333.093 | 166.739 | 166.883 | 167.258 | 167.003 |
21 | 2.097.152 | 1.341.567 | 672.393 | 669.174 | 334.779 | 335.785 | 335.604 | 335.399 |
22 | 4.194.304 | 2.692.791 | 1.349.167 | 1.343.624 | 673.494 | 672.914 | 673.608 | 672.775 |
23 | 8.388.608 | 5.405.528 | 2.707.760 | 2.697.768 | 1.350.517 | 1.351.574 | 1.352.329 | 1.351.108 |
24 | 16.777.216 | 10.847.158 | 5.431.047 | 5.416.111 | 2.711.389 | 2.712.627 | 2.712.338 | 2.710.804 |
25 | 33.554.432 | 21.760.000 | 10.897.029 | 10.862.971 | 5.439.991 | 5.440.991 | 5.439.119 | 5.439.899 |
26 | 67.108.864 | 43.641.060 | 21.856.190 | 21.784.870 | 10.907.891 | 10.910.195 | 10.910.856 | 10.912.118 |
27 | 134.217.728 | 87.505.243 | 43.824.488 | 43.680.755 | 21.872.610 | 21.877.131 | 21.876.048 | 21.879.454 |
28 | 268.435.456 | 175.421.169 | 87.844.051 | 87.577.118 | 43.847.590 | 43.858.584 | 43.855.299 | 43.859.696 |
29 | 536.870.912 | 351.602.181 | 176.055.241 | 175.546.940 | 87.895.331 | 87.897.937 | 87.905.047 | 87.903.866 |
30 | 1.073.741.824 | 704.610.936 | 352.802.510 | 351.808.426 | 176.137.100 | 176.147.887 | 176.158.324 | 176.167.625 |
31 | 2.147.483.648 | 1.411.864.227 | 706.889.529 | 704.974.698 | 352.939.055 | 352.971.428 | 352.962.191 | 352.991.553 |
32 | 4.294.967.296 | 2.828.655.151 | 1.416.168.690 | 1.412.486.461 | 707.163.498 | 707.160.081 | 707.160.259 | 707.171.313 |
33 | 8.589.934.592 | 5.666.583.146 | 2.836.829.849 | 2.829.753.297 | 1.416.657.500 | 1.416.638.730 | 1.416.637.812 | 1.416.649.104 |
34 | 17.179.869.184 | 11.350.552.568 | 5.682.095.051 | 5.668.457.517 | 2.837.650.817 | 2.837.600.825 | 2.837.653.897 | 2.837.647.029 |