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-70x+47
f(0)=47
f(1)=11
f(2)=89
f(3)=7
f(4)=31
f(5)=139
f(6)=337
f(7)=197
f(8)=449
f(9)=251
f(10)=79
f(11)=43
f(12)=59
f(13)=347
f(14)=67
f(15)=389
f(16)=19
f(17)=61
f(18)=127
f(19)=461
f(20)=953
f(21)=491
f(22)=1009
f(23)=1
f(24)=151
f(25)=1
f(26)=1097
f(27)=557
f(28)=1129
f(29)=571
f(30)=1153
f(31)=83
f(32)=167
f(33)=587
f(34)=107
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)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=191
f(73)=1
f(74)=1
f(75)=211
f(76)=503
f(77)=293
f(78)=1
f(79)=379
f(80)=1
f(81)=1
f(82)=1031
f(83)=563
f(84)=1223
f(85)=661
f(86)=1423
f(87)=109
f(88)=233
f(89)=1
f(90)=1847
f(91)=1
f(92)=1
f(93)=1093
f(94)=1
f(95)=173
f(96)=2543
f(97)=1
f(98)=2791
f(99)=1459
b) Substitution of the polynom
The polynom f(x)=x^2-70x+47 could be written as f(y)= y^2-1178 with x=y+35
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-35
f'(x)>2x-71 with x > 34
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 | 11 | 5 | 6 | 1.100000 | 0.500000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 50 | 19 | 31 | 0.500000 | 0.190000 | 0.500000 | 4.545455 | 3.800000 | 5.166667 |
3 | 1.000 | 695 | 150 | 545 | 0.695000 | 0.150000 | 0.695000 | 13.900000 | 7.894737 | 17.580645 |
4 | 10.000 | 7.126 | 1.035 | 6.091 | 0.712600 | 0.103500 | 0.712600 | 10.253238 | 6.900000 | 11.176147 |
5 | 100.000 | 71.037 | 8.067 | 62.970 | 0.710370 | 0.080670 | 0.710370 | 9.968706 | 7.794203 | 10.338204 |
6 | 1.000.000 | 708.165 | 65.702 | 642.463 | 0.708165 | 0.065702 | 0.708165 | 9.968960 | 8.144540 | 10.202683 |
7 | 10.000.000 | 7.058.868 | 556.875 | 6.501.993 | 0.705887 | 0.055687 | 0.705887 | 9.967830 | 8.475769 | 10.120417 |
8 | 100.000.000 | 70.411.275 | 4.830.749 | 65.580.526 | 0.704113 | 0.048307 | 0.704113 | 9.974868 | 8.674746 | 10.086220 |
9 | 1.000.000.000 | 702.772.184 | 42.622.924 | 660.149.260 | 0.702772 | 0.042623 | 0.702772 | 9.980961 | 8.823254 | 10.066238 |
10 | 10.000.000.000 | 7.017.081.893 | 381.489.714 | 6.635.592.179 | 0.701708 | 0.038149 | 0.701708 | 9.984860 | 8.950341 | 10.051655 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 17 | 6 | 11 | 1.062500 | 0.375000 | 0.687500 | 1.888889 | 1.200000 | 2.750000 |
5 | 32 | 31 | 11 | 20 | 0.968750 | 0.343750 | 0.625000 | 1.823529 | 1.833333 | 1.818182 |
6 | 64 | 33 | 11 | 22 | 0.515625 | 0.171875 | 0.343750 | 1.064516 | 1.000000 | 1.100000 |
7 | 128 | 70 | 26 | 44 | 0.546875 | 0.203125 | 0.343750 | 2.121212 | 2.363636 | 2.000000 |
8 | 256 | 158 | 49 | 109 | 0.617188 | 0.191406 | 0.425781 | 2.257143 | 1.884615 | 2.477273 |
9 | 512 | 341 | 85 | 256 | 0.666016 | 0.166016 | 0.500000 | 2.158228 | 1.734694 | 2.348624 |
10 | 1.024 | 711 | 154 | 557 | 0.694336 | 0.150391 | 0.543945 | 2.085044 | 1.811765 | 2.175781 |
11 | 2.048 | 1.430 | 266 | 1.164 | 0.698242 | 0.129883 | 0.568359 | 2.011252 | 1.727273 | 2.089767 |
12 | 4.096 | 2.890 | 477 | 2.413 | 0.705566 | 0.116455 | 0.589111 | 2.020979 | 1.793233 | 2.073024 |
13 | 8.192 | 5.820 | 865 | 4.955 | 0.710449 | 0.105591 | 0.604858 | 2.013841 | 1.813417 | 2.053460 |
14 | 16.384 | 11.643 | 1.608 | 10.035 | 0.710632 | 0.098145 | 0.612488 | 2.000515 | 1.858960 | 2.025227 |
15 | 32.768 | 23.305 | 2.955 | 20.350 | 0.711212 | 0.090179 | 0.621033 | 2.001632 | 1.837687 | 2.027902 |
16 | 65.536 | 46.581 | 5.477 | 41.104 | 0.710770 | 0.083572 | 0.627197 | 1.998756 | 1.853469 | 2.019853 |
17 | 131.072 | 93.066 | 10.268 | 82.798 | 0.710037 | 0.078339 | 0.631699 | 1.997939 | 1.874749 | 2.014354 |
18 | 262.144 | 185.960 | 19.291 | 166.669 | 0.709381 | 0.073589 | 0.635792 | 1.998152 | 1.878749 | 2.012959 |
19 | 524.288 | 371.586 | 36.242 | 335.344 | 0.708744 | 0.069126 | 0.639618 | 1.998204 | 1.878700 | 2.012036 |
20 | 1.048.576 | 742.406 | 68.635 | 673.771 | 0.708014 | 0.065455 | 0.642558 | 1.997939 | 1.893797 | 2.009194 |
21 | 2.097.152 | 1.483.470 | 130.139 | 1.353.331 | 0.707374 | 0.062055 | 0.645319 | 1.998192 | 1.896103 | 2.008592 |
22 | 4.194.304 | 2.963.950 | 247.969 | 2.715.981 | 0.706661 | 0.059120 | 0.647540 | 1.997984 | 1.905416 | 2.006886 |
23 | 8.388.608 | 5.922.828 | 472.781 | 5.450.047 | 0.706056 | 0.056360 | 0.649696 | 1.998289 | 1.906613 | 2.006659 |
24 | 16.777.216 | 11.835.875 | 903.406 | 10.932.469 | 0.705473 | 0.053847 | 0.651626 | 1.998349 | 1.910834 | 2.005940 |
25 | 33.554.432 | 23.653.144 | 1.730.263 | 21.922.881 | 0.704919 | 0.051566 | 0.653353 | 1.998428 | 1.915266 | 2.005300 |
26 | 67.108.864 | 47.271.588 | 3.317.943 | 43.953.645 | 0.704402 | 0.049441 | 0.654960 | 1.998533 | 1.917595 | 2.004921 |
27 | 134.217.728 | 94.478.669 | 6.374.429 | 88.104.240 | 0.703921 | 0.047493 | 0.656428 | 1.998635 | 1.921199 | 2.004481 |
28 | 268.435.456 | 188.840.106 | 12.265.150 | 176.574.956 | 0.703484 | 0.045691 | 0.657793 | 1.998759 | 1.924117 | 2.004160 |
29 | 536.870.912 | 377.474.204 | 23.633.490 | 353.840.714 | 0.703101 | 0.044021 | 0.659080 | 1.998909 | 1.926881 | 2.003912 |
30 | 1.073.741.824 | 754.552.567 | 45.602.334 | 708.950.233 | 0.702732 | 0.042470 | 0.660261 | 1.998951 | 1.929564 | 2.003586 |
31 | 2.147.483.648 | 1.508.365.873 | 88.103.228 | 1.420.262.645 | 0.702388 | 0.041026 | 0.661361 | 1.999020 | 1.931989 | 2.003332 |
32 | 4.294.967.296 | 3.015.364.783 | 170.413.506 | 2.844.951.277 | 0.702069 | 0.039677 | 0.662392 | 1.999094 | 1.934248 | 2.003116 |
33 | 8.589.934.592 | 6.028.169.940 | 329.989.011 | 5.698.180.929 | 0.701771 | 0.038416 | 0.663356 | 1.999151 | 1.936402 | 2.002910 |
34 | 17.179.869.184 | 12.051.573.294 | 639.614.889 | 11.411.958.405 | 0.701494 | 0.037230 | 0.664263 | 1.999209 | 1.938291 | 2.002737 |
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 | 1 | 0 | 0 | 1 |
2 | 4 | 3 | 1 | 2 | 2 | 0 | 0 | 1 |
3 | 8 | 5 | 2 | 3 | 4 | 0 | 0 | 1 |
4 | 16 | 6 | 3 | 3 | 5 | 0 | 0 | 1 |
5 | 32 | 11 | 6 | 5 | 10 | 0 | 0 | 1 |
6 | 64 | 11 | 6 | 5 | 10 | 0 | 0 | 1 |
7 | 128 | 26 | 10 | 16 | 10 | 0 | 0 | 16 |
8 | 256 | 49 | 17 | 32 | 10 | 0 | 0 | 39 |
9 | 512 | 85 | 29 | 56 | 10 | 0 | 0 | 75 |
10 | 1.024 | 154 | 51 | 103 | 10 | 0 | 0 | 144 |
11 | 2.048 | 266 | 88 | 178 | 10 | 0 | 0 | 256 |
12 | 4.096 | 477 | 165 | 312 | 10 | 0 | 0 | 467 |
13 | 8.192 | 865 | 290 | 575 | 10 | 0 | 0 | 855 |
14 | 16.384 | 1.608 | 542 | 1.066 | 10 | 0 | 0 | 1.598 |
15 | 32.768 | 2.955 | 966 | 1.989 | 10 | 0 | 0 | 2.945 |
16 | 65.536 | 5.477 | 1.818 | 3.659 | 10 | 0 | 0 | 5.467 |
17 | 131.072 | 10.268 | 3.425 | 6.843 | 10 | 0 | 0 | 10.258 |
18 | 262.144 | 19.291 | 6.417 | 12.874 | 10 | 0 | 0 | 19.281 |
19 | 524.288 | 36.242 | 12.071 | 24.171 | 10 | 0 | 0 | 36.232 |
20 | 1.048.576 | 68.635 | 22.780 | 45.855 | 10 | 0 | 0 | 68.625 |
21 | 2.097.152 | 130.139 | 43.247 | 86.892 | 10 | 0 | 0 | 130.129 |
22 | 4.194.304 | 247.969 | 82.490 | 165.479 | 10 | 0 | 0 | 247.959 |
23 | 8.388.608 | 472.781 | 157.603 | 315.178 | 10 | 0 | 0 | 472.771 |
24 | 16.777.216 | 903.406 | 301.153 | 602.253 | 10 | 0 | 0 | 903.396 |
25 | 33.554.432 | 1.730.263 | 576.873 | 1.153.390 | 10 | 0 | 0 | 1.730.253 |
26 | 67.108.864 | 3.317.943 | 1.106.028 | 2.211.915 | 10 | 0 | 0 | 3.317.933 |
27 | 134.217.728 | 6.374.429 | 2.124.627 | 4.249.802 | 10 | 0 | 0 | 6.374.419 |
28 | 268.435.456 | 12.265.150 | 4.089.145 | 8.176.005 | 10 | 0 | 0 | 12.265.140 |
29 | 536.870.912 | 23.633.490 | 7.876.905 | 15.756.585 | 10 | 0 | 0 | 23.633.480 |
30 | 1.073.741.824 | 45.602.334 | 15.199.564 | 30.402.770 | 10 | 0 | 0 | 45.602.324 |
31 | 2.147.483.648 | 88.103.228 | 29.368.831 | 58.734.397 | 10 | 0 | 0 | 88.103.218 |
32 | 4.294.967.296 | 170.413.506 | 56.806.317 | 113.607.189 | 10 | 0 | 0 | 170.413.496 |
33 | 8.589.934.592 | 329.989.011 | 110.004.841 | 219.984.170 | 10 | 0 | 0 | 329.989.001 |
34 | 17.179.869.184 | 639.614.889 | 213.213.885 | 426.401.004 | 10 | 0 | 0 | 639.614.879 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 0 | 2 | 1 | 1 |
4 | 16 | 11 | 5 | 6 | 0 | 7 | 2 | 2 |
5 | 32 | 20 | 9 | 11 | 0 | 10 | 5 | 5 |
6 | 64 | 22 | 9 | 13 | 0 | 12 | 5 | 5 |
7 | 128 | 44 | 23 | 21 | 3 | 22 | 14 | 5 |
8 | 256 | 109 | 54 | 55 | 18 | 42 | 37 | 12 |
9 | 512 | 256 | 134 | 122 | 46 | 88 | 88 | 34 |
10 | 1.024 | 557 | 293 | 264 | 118 | 174 | 192 | 73 |
11 | 2.048 | 1.164 | 618 | 546 | 248 | 339 | 406 | 171 |
12 | 4.096 | 2.413 | 1.266 | 1.147 | 549 | 685 | 796 | 383 |
13 | 8.192 | 4.955 | 2.618 | 2.337 | 1.157 | 1.393 | 1.558 | 847 |
14 | 16.384 | 10.035 | 5.303 | 4.732 | 2.361 | 2.738 | 3.134 | 1.802 |
15 | 32.768 | 20.350 | 10.689 | 9.661 | 4.796 | 5.516 | 6.264 | 3.774 |
16 | 65.536 | 41.104 | 21.510 | 19.594 | 9.858 | 11.038 | 12.483 | 7.725 |
17 | 131.072 | 82.798 | 43.180 | 39.618 | 19.830 | 22.229 | 24.607 | 16.132 |
18 | 262.144 | 166.669 | 86.817 | 79.852 | 40.138 | 44.191 | 49.105 | 33.235 |
19 | 524.288 | 335.344 | 173.925 | 161.419 | 81.217 | 88.628 | 97.781 | 67.718 |
20 | 1.048.576 | 673.771 | 349.091 | 324.680 | 163.366 | 177.670 | 194.660 | 138.075 |
21 | 2.097.152 | 1.353.331 | 699.464 | 653.867 | 328.764 | 355.691 | 387.927 | 280.949 |
22 | 4.194.304 | 2.715.981 | 1.401.559 | 1.314.422 | 661.275 | 711.880 | 773.628 | 569.198 |
23 | 8.388.608 | 5.450.047 | 2.806.339 | 2.643.708 | 1.327.777 | 1.425.338 | 1.543.073 | 1.153.859 |
24 | 16.777.216 | 10.932.469 | 5.620.761 | 5.311.708 | 2.667.386 | 2.852.836 | 3.076.418 | 2.335.829 |
25 | 33.554.432 | 21.922.881 | 11.256.617 | 10.666.264 | 5.355.058 | 5.708.173 | 6.137.842 | 4.721.808 |
26 | 67.108.864 | 43.953.645 | 22.541.444 | 21.412.201 | 10.746.028 | 11.426.061 | 12.244.604 | 9.536.952 |
27 | 134.217.728 | 88.104.240 | 45.140.774 | 42.963.466 | 21.557.664 | 22.869.932 | 24.433.072 | 19.243.572 |
28 | 268.435.456 | 176.574.956 | 90.380.195 | 86.194.761 | 43.243.481 | 45.764.632 | 48.764.897 | 38.801.946 |
29 | 536.870.912 | 353.840.714 | 180.948.469 | 172.892.245 | 86.724.759 | 91.586.566 | 97.351.877 | 78.177.512 |
30 | 1.073.741.824 | 708.950.233 | 362.246.973 | 346.703.260 | 173.869.974 | 183.270.157 | 194.391.666 | 157.418.436 |
31 | 2.147.483.648 | 1.420.262.645 | 725.142.757 | 695.119.888 | 348.538.776 | 366.741.057 | 388.173.502 | 316.809.310 |
32 | 4.294.967.296 | 2.844.951.277 | 1.451.497.309 | 1.393.453.968 | 698.595.534 | 733.790.154 | 775.247.677 | 637.317.912 |
33 | 8.589.934.592 | 5.698.180.929 | 2.905.251.824 | 2.792.929.105 | 1.400.038.676 | 1.468.234.348 | 1.548.386.739 | 1.281.521.166 |
34 | 17.179.869.184 | 11.411.958.405 | 5.814.797.297 | 5.597.161.108 | 2.805.407.108 | 2.937.741.925 | 3.092.820.149 | 2.575.989.223 |