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+52x-79
f(0)=79
f(1)=13
f(2)=29
f(3)=43
f(4)=5
f(5)=103
f(6)=269
f(7)=167
f(8)=401
f(9)=47
f(10)=541
f(11)=307
f(12)=53
f(13)=383
f(14)=1
f(15)=463
f(16)=1009
f(17)=547
f(18)=1181
f(19)=127
f(20)=1361
f(21)=727
f(22)=1549
f(23)=823
f(24)=349
f(25)=71
f(26)=1949
f(27)=1
f(28)=2161
f(29)=227
f(30)=2381
f(31)=1
f(32)=2609
f(33)=1
f(34)=569
f(35)=1483
f(36)=3089
f(37)=1607
f(38)=257
f(39)=347
f(40)=277
f(41)=1867
f(42)=73
f(43)=2003
f(44)=829
f(45)=2143
f(46)=1
f(47)=2287
f(48)=4721
f(49)=487
f(50)=5021
f(51)=199
f(52)=1
f(53)=211
f(54)=1129
f(55)=2903
f(56)=1
f(57)=3067
f(58)=6301
f(59)=647
f(60)=229
f(61)=3407
f(62)=241
f(63)=3583
f(64)=113
f(65)=1
f(66)=593
f(67)=3947
f(68)=8081
f(69)=827
f(70)=8461
f(71)=4327
f(72)=8849
f(73)=4523
f(74)=1
f(75)=4723
f(76)=9649
f(77)=379
f(78)=10061
f(79)=1
f(80)=223
f(81)=5347
f(82)=10909
f(83)=5563
f(84)=2269
f(85)=5783
f(86)=11789
f(87)=6007
f(88)=12241
f(89)=1
f(90)=977
f(91)=1
f(92)=1013
f(93)=6703
f(94)=2729
f(95)=131
f(96)=1
f(97)=7187
f(98)=14621
f(99)=1487
b) Substitution of the polynom
The polynom f(x)=x^2+52x-79 could be written as f(y)= y^2-755 with x=y-26
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+26
f'(x)>2x+51
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 | 6 | 5 | 1.100000 | 0.600000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 85 | 28 | 57 | 0.850000 | 0.280000 | 0.850000 | 7.727273 | 4.666667 | 11.400000 |
3 | 1.000 | 774 | 171 | 603 | 0.774000 | 0.171000 | 0.774000 | 9.105883 | 6.107143 | 10.578947 |
4 | 10.000 | 7.481 | 1.264 | 6.217 | 0.748100 | 0.126400 | 0.748100 | 9.665375 | 7.391813 | 10.310116 |
5 | 100.000 | 73.608 | 9.796 | 63.812 | 0.736080 | 0.097960 | 0.736080 | 9.839326 | 7.750000 | 10.264114 |
6 | 1.000.000 | 728.383 | 80.391 | 647.992 | 0.728383 | 0.080391 | 0.728383 | 9.895432 | 8.206512 | 10.154704 |
7 | 10.000.000 | 7.232.188 | 678.897 | 6.553.291 | 0.723219 | 0.067890 | 0.723219 | 9.929100 | 8.444938 | 10.113228 |
8 | 100.000.000 | 71.922.565 | 5.889.562 | 66.033.003 | 0.719226 | 0.058896 | 0.719226 | 9.944787 | 8.675192 | 10.076312 |
9 | 1.000.000.000 | 716.126.588 | 51.993.516 | 664.133.072 | 0.716127 | 0.051994 | 0.716127 | 9.956911 | 8.828078 | 10.057592 |
10 | 10.000.000.000 | 7.137.049.065 | 465.276.969 | 6.671.772.096 | 0.713705 | 0.046528 | 0.713705 | 9.966184 | 8.948750 | 10.045836 |
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 | 16 | 7 | 9 | 1.000000 | 0.437500 | 0.562500 | 1.777778 | 1.400000 | 2.250000 |
5 | 32 | 30 | 14 | 16 | 0.937500 | 0.437500 | 0.500000 | 1.875000 | 2.000000 | 1.777778 |
6 | 64 | 56 | 18 | 38 | 0.875000 | 0.281250 | 0.593750 | 1.866667 | 1.285714 | 2.375000 |
7 | 128 | 105 | 33 | 72 | 0.820312 | 0.257812 | 0.562500 | 1.875000 | 1.833333 | 1.894737 |
8 | 256 | 209 | 56 | 153 | 0.816406 | 0.218750 | 0.597656 | 1.990476 | 1.696970 | 2.125000 |
9 | 512 | 405 | 101 | 304 | 0.791016 | 0.197266 | 0.593750 | 1.937799 | 1.803571 | 1.986928 |
10 | 1.024 | 792 | 173 | 619 | 0.773438 | 0.168945 | 0.604492 | 1.955556 | 1.712871 | 2.036184 |
11 | 2.048 | 1.565 | 322 | 1.243 | 0.764160 | 0.157227 | 0.606934 | 1.976010 | 1.861272 | 2.008078 |
12 | 4.096 | 3.108 | 584 | 2.524 | 0.758789 | 0.142578 | 0.616211 | 1.985942 | 1.813665 | 2.030571 |
13 | 8.192 | 6.148 | 1.067 | 5.081 | 0.750488 | 0.130249 | 0.620239 | 1.978121 | 1.827055 | 2.013074 |
14 | 16.384 | 12.208 | 1.966 | 10.242 | 0.745117 | 0.119995 | 0.625122 | 1.985686 | 1.842549 | 2.015745 |
15 | 32.768 | 24.245 | 3.617 | 20.628 | 0.739899 | 0.110382 | 0.629517 | 1.985993 | 1.839776 | 2.014060 |
16 | 65.536 | 48.334 | 6.705 | 41.629 | 0.737518 | 0.102310 | 0.635208 | 1.993566 | 1.853746 | 2.018082 |
17 | 131.072 | 96.372 | 12.554 | 83.818 | 0.735260 | 0.095779 | 0.639481 | 1.993876 | 1.872334 | 2.013452 |
18 | 262.144 | 192.045 | 23.576 | 168.469 | 0.732594 | 0.089935 | 0.642658 | 1.992747 | 1.877967 | 2.009938 |
19 | 524.288 | 382.826 | 44.394 | 338.432 | 0.730183 | 0.084675 | 0.645508 | 1.993418 | 1.883017 | 2.008868 |
20 | 1.048.576 | 763.671 | 83.992 | 679.679 | 0.728293 | 0.080101 | 0.648192 | 1.994825 | 1.891967 | 2.008318 |
21 | 2.097.152 | 1.523.941 | 158.915 | 1.365.026 | 0.726672 | 0.075777 | 0.650895 | 1.995546 | 1.892025 | 2.008339 |
22 | 4.194.304 | 3.040.897 | 302.759 | 2.738.138 | 0.725006 | 0.072183 | 0.652823 | 1.995417 | 1.905163 | 2.005924 |
23 | 8.388.608 | 6.069.845 | 576.395 | 5.493.450 | 0.723582 | 0.068712 | 0.654870 | 1.996071 | 1.903808 | 2.006272 |
24 | 16.777.216 | 12.117.063 | 1.101.366 | 11.015.697 | 0.722233 | 0.065647 | 0.656587 | 1.996272 | 1.910783 | 2.005242 |
25 | 33.554.432 | 24.191.988 | 2.110.204 | 22.081.784 | 0.720977 | 0.062889 | 0.658088 | 1.996522 | 1.915988 | 2.004574 |
26 | 67.108.864 | 48.307.025 | 4.044.497 | 44.262.528 | 0.719831 | 0.060268 | 0.659563 | 1.996819 | 1.916638 | 2.004482 |
27 | 134.217.728 | 96.473.296 | 7.774.438 | 88.698.858 | 0.718782 | 0.057924 | 0.660858 | 1.997086 | 1.922226 | 2.003927 |
28 | 268.435.456 | 192.681.407 | 14.960.648 | 177.720.759 | 0.717794 | 0.055733 | 0.662061 | 1.997251 | 1.924338 | 2.003642 |
29 | 536.870.912 | 384.869.913 | 28.830.301 | 356.039.612 | 0.716876 | 0.053701 | 0.663175 | 1.997442 | 1.927076 | 2.003366 |
30 | 1.073.741.824 | 768.845.076 | 55.628.131 | 713.216.945 | 0.716043 | 0.051808 | 0.664235 | 1.997675 | 1.929502 | 2.003196 |
31 | 2.147.483.648 | 1.536.023.777 | 107.462.638 | 1.428.561.139 | 0.715267 | 0.050041 | 0.665226 | 1.997833 | 1.931804 | 2.002983 |
32 | 4.294.967.296 | 3.068.897.697 | 207.854.600 | 2.861.043.097 | 0.714533 | 0.048395 | 0.666139 | 1.997949 | 1.934203 | 2.002745 |
33 | 8.589.934.592 | 6.131.904.011 | 402.459.092 | 5.729.444.919 | 0.713848 | 0.046852 | 0.666995 | 1.998080 | 1.936253 | 2.002572 |
34 | 17.179.869.184 | 12.252.799.793 | 780.094.476 | 11.472.705.317 | 0.713207 | 0.045407 | 0.667799 | 1.998205 | 1.938320 | 2.002411 |
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 | 1 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 2 | 1 | 1 | 0 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 2 | 0 | 2 | 1 |
4 | 16 | 7 | 4 | 3 | 3 | 0 | 3 | 1 |
5 | 32 | 14 | 6 | 8 | 6 | 0 | 7 | 1 |
6 | 64 | 18 | 7 | 11 | 8 | 0 | 9 | 1 |
7 | 128 | 33 | 13 | 20 | 15 | 0 | 17 | 1 |
8 | 256 | 56 | 19 | 37 | 27 | 0 | 28 | 1 |
9 | 512 | 101 | 35 | 66 | 48 | 0 | 52 | 1 |
10 | 1.024 | 173 | 62 | 111 | 87 | 0 | 85 | 1 |
11 | 2.048 | 322 | 116 | 206 | 152 | 0 | 169 | 1 |
12 | 4.096 | 584 | 198 | 386 | 273 | 0 | 310 | 1 |
13 | 8.192 | 1.067 | 349 | 718 | 516 | 0 | 550 | 1 |
14 | 16.384 | 1.966 | 652 | 1.314 | 943 | 0 | 1.022 | 1 |
15 | 32.768 | 3.617 | 1.211 | 2.406 | 1.787 | 0 | 1.829 | 1 |
16 | 65.536 | 6.705 | 2.238 | 4.467 | 3.333 | 0 | 3.371 | 1 |
17 | 131.072 | 12.554 | 4.191 | 8.363 | 6.245 | 0 | 6.308 | 1 |
18 | 262.144 | 23.576 | 7.797 | 15.779 | 11.827 | 0 | 11.748 | 1 |
19 | 524.288 | 44.394 | 14.671 | 29.723 | 22.239 | 0 | 22.154 | 1 |
20 | 1.048.576 | 83.992 | 27.836 | 56.156 | 41.986 | 0 | 42.005 | 1 |
21 | 2.097.152 | 158.915 | 52.804 | 106.111 | 79.248 | 0 | 79.666 | 1 |
22 | 4.194.304 | 302.759 | 100.699 | 202.060 | 151.054 | 0 | 151.704 | 1 |
23 | 8.388.608 | 576.395 | 191.623 | 384.772 | 287.874 | 0 | 288.520 | 1 |
24 | 16.777.216 | 1.101.366 | 366.891 | 734.475 | 550.578 | 0 | 550.787 | 1 |
25 | 33.554.432 | 2.110.204 | 703.181 | 1.407.023 | 1.054.308 | 0 | 1.055.895 | 1 |
26 | 67.108.864 | 4.044.497 | 1.347.486 | 2.697.011 | 2.021.714 | 0 | 2.022.782 | 1 |
27 | 134.217.728 | 7.774.438 | 2.592.460 | 5.181.978 | 3.886.756 | 0 | 3.887.681 | 1 |
28 | 268.435.456 | 14.960.648 | 4.987.145 | 9.973.503 | 7.479.524 | 0 | 7.481.123 | 1 |
29 | 536.870.912 | 28.830.301 | 9.610.059 | 19.220.242 | 14.414.935 | 0 | 14.415.365 | 1 |
30 | 1.073.741.824 | 55.628.131 | 18.541.860 | 37.086.271 | 27.810.573 | 0 | 27.817.557 | 1 |
31 | 2.147.483.648 | 107.462.638 | 35.822.337 | 71.640.301 | 53.731.237 | 0 | 53.731.400 | 1 |
32 | 4.294.967.296 | 207.854.600 | 69.285.798 | 138.568.802 | 103.936.623 | 0 | 103.917.976 | 1 |
33 | 8.589.934.592 | 402.459.092 | 134.161.631 | 268.297.461 | 201.234.212 | 0 | 201.224.879 | 1 |
34 | 17.179.869.184 | 780.094.476 | 260.029.550 | 520.064.926 | 390.035.281 | 0 | 390.059.194 | 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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 3 | 1 | 0 | 1 | 1 | 2 |
4 | 16 | 9 | 5 | 4 | 0 | 2 | 2 | 5 |
5 | 32 | 16 | 10 | 6 | 0 | 4 | 3 | 9 |
6 | 64 | 38 | 24 | 14 | 4 | 10 | 6 | 18 |
7 | 128 | 72 | 44 | 28 | 8 | 24 | 12 | 28 |
8 | 256 | 153 | 84 | 69 | 20 | 51 | 25 | 57 |
9 | 512 | 304 | 168 | 136 | 42 | 103 | 52 | 107 |
10 | 1.024 | 619 | 355 | 264 | 104 | 194 | 109 | 212 |
11 | 2.048 | 1.243 | 695 | 548 | 211 | 397 | 241 | 394 |
12 | 4.096 | 2.524 | 1.360 | 1.164 | 480 | 800 | 480 | 764 |
13 | 8.192 | 5.081 | 2.737 | 2.344 | 995 | 1.558 | 982 | 1.546 |
14 | 16.384 | 10.242 | 5.412 | 4.830 | 2.019 | 3.099 | 2.049 | 3.075 |
15 | 32.768 | 20.628 | 10.903 | 9.725 | 4.151 | 6.146 | 4.195 | 6.136 |
16 | 65.536 | 41.629 | 21.922 | 19.707 | 8.573 | 12.208 | 8.696 | 12.152 |
17 | 131.072 | 83.818 | 44.017 | 39.801 | 17.589 | 24.379 | 17.650 | 24.200 |
18 | 262.144 | 168.469 | 88.207 | 80.262 | 36.019 | 48.322 | 35.820 | 48.308 |
19 | 524.288 | 338.432 | 176.458 | 161.974 | 72.900 | 96.385 | 73.041 | 96.106 |
20 | 1.048.576 | 679.679 | 353.697 | 325.982 | 148.051 | 192.043 | 147.900 | 191.685 |
21 | 2.097.152 | 1.365.026 | 708.859 | 656.167 | 299.626 | 382.530 | 300.359 | 382.511 |
22 | 4.194.304 | 2.738.138 | 1.420.374 | 1.317.764 | 605.804 | 762.603 | 606.158 | 763.573 |
23 | 8.388.608 | 5.493.450 | 2.845.000 | 2.648.450 | 1.224.059 | 1.523.189 | 1.224.153 | 1.522.049 |
24 | 16.777.216 | 11.015.697 | 5.695.559 | 5.320.138 | 2.470.478 | 3.038.676 | 2.468.827 | 3.037.716 |
25 | 33.554.432 | 22.081.784 | 11.397.332 | 10.684.452 | 4.977.445 | 6.062.559 | 4.976.037 | 6.065.743 |
26 | 67.108.864 | 44.262.528 | 22.814.053 | 21.448.475 | 10.023.920 | 12.105.001 | 10.025.378 | 12.108.229 |
27 | 134.217.728 | 88.698.858 | 45.663.192 | 43.035.666 | 20.177.259 | 24.170.005 | 20.174.447 | 24.177.147 |
28 | 268.435.456 | 177.720.759 | 91.392.846 | 86.327.913 | 40.588.579 | 48.264.282 | 40.591.219 | 48.276.679 |
29 | 536.870.912 | 356.039.612 | 182.904.904 | 173.134.708 | 81.606.231 | 96.398.384 | 81.624.023 | 96.410.974 |
30 | 1.073.741.824 | 713.216.945 | 366.003.665 | 347.213.280 | 164.044.209 | 192.565.109 | 164.042.851 | 192.564.776 |
31 | 2.147.483.648 | 1.428.561.139 | 732.431.857 | 696.129.282 | 329.615.481 | 384.658.632 | 329.637.065 | 384.649.961 |
32 | 4.294.967.296 | 2.861.043.097 | 1.465.632.719 | 1.395.410.378 | 662.076.121 | 768.440.828 | 662.096.765 | 768.429.383 |
33 | 8.589.934.592 | 5.729.444.919 | 2.932.697.890 | 2.796.747.029 | 1.329.467.337 | 1.535.276.074 | 1.329.487.928 | 1.535.213.580 |
34 | 17.179.869.184 | 11.472.705.317 | 5.868.051.176 | 5.604.654.141 | 2.668.877.592 | 3.067.505.682 | 2.668.889.709 | 3.067.432.334 |