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-88x+43
f(0)=43
f(1)=11
f(2)=3
f(3)=53
f(4)=293
f(5)=31
f(6)=449
f(7)=131
f(8)=199
f(9)=167
f(10)=67
f(11)=1
f(12)=79
f(13)=233
f(14)=331
f(15)=263
f(16)=1109
f(17)=97
f(18)=1217
f(19)=317
f(20)=439
f(21)=1
f(22)=1409
f(23)=1
f(24)=1493
f(25)=383
f(26)=523
f(27)=401
f(28)=1637
f(29)=139
f(30)=1697
f(31)=431
f(32)=1
f(33)=443
f(34)=163
f(35)=151
f(36)=59
f(37)=461
f(38)=619
f(39)=467
f(40)=1877
f(41)=157
f(42)=1889
f(43)=1
f(44)=631
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)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=223
f(91)=1
f(92)=137
f(93)=127
f(94)=607
f(95)=1
f(96)=811
f(97)=229
f(98)=1
f(99)=283
b) Substitution of the polynom
The polynom f(x)=x^2-88x+43 could be written as f(y)= y^2-1893 with x=y+44
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-44
f'(x)>2x-89 with x > 44
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 | 4 | 7 | 1.100000 | 0.400000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 44 | 15 | 29 | 0.440000 | 0.150000 | 0.440000 | 4.000000 | 3.750000 | 4.142857 |
3 | 1.000 | 699 | 144 | 555 | 0.699000 | 0.144000 | 0.699000 | 15.886364 | 9.600000 | 19.137932 |
4 | 10.000 | 7.210 | 1.061 | 6.149 | 0.721000 | 0.106100 | 0.721000 | 10.314735 | 7.368055 | 11.079279 |
5 | 100.000 | 71.863 | 8.030 | 63.833 | 0.718630 | 0.080300 | 0.718630 | 9.967129 | 7.568332 | 10.381038 |
6 | 1.000.000 | 714.452 | 66.243 | 648.209 | 0.714452 | 0.066243 | 0.714452 | 9.941861 | 8.249439 | 10.154763 |
7 | 10.000.000 | 7.113.903 | 558.876 | 6.555.027 | 0.711390 | 0.055888 | 0.711390 | 9.957147 | 8.436755 | 10.112521 |
8 | 100.000.000 | 70.895.418 | 4.841.961 | 66.053.457 | 0.708954 | 0.048420 | 0.708954 | 9.965755 | 8.663749 | 10.076763 |
9 | 1.000.000.000 | 707.023.587 | 42.739.892 | 664.283.695 | 0.707024 | 0.042740 | 0.707024 | 9.972769 | 8.826980 | 10.056760 |
10 | 10.000.000.000 | 7.055.071.022 | 382.480.890 | 6.672.590.132 | 0.705507 | 0.038248 | 0.705507 | 9.978551 | 8.949038 | 10.044790 |
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 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 1.333333 | 2.500000 |
4 | 16 | 16 | 5 | 11 | 1.000000 | 0.312500 | 0.687500 | 1.777778 | 1.250000 | 2.200000 |
5 | 32 | 29 | 10 | 19 | 0.906250 | 0.312500 | 0.593750 | 1.812500 | 2.000000 | 1.727273 |
6 | 64 | 39 | 12 | 27 | 0.609375 | 0.187500 | 0.421875 | 1.344828 | 1.200000 | 1.421053 |
7 | 128 | 66 | 22 | 44 | 0.515625 | 0.171875 | 0.343750 | 1.692308 | 1.833333 | 1.629630 |
8 | 256 | 159 | 41 | 118 | 0.621094 | 0.160156 | 0.460938 | 2.409091 | 1.863636 | 2.681818 |
9 | 512 | 337 | 82 | 255 | 0.658203 | 0.160156 | 0.498047 | 2.119497 | 2.000000 | 2.161017 |
10 | 1.024 | 716 | 148 | 568 | 0.699219 | 0.144531 | 0.554688 | 2.124629 | 1.804878 | 2.227451 |
11 | 2.048 | 1.459 | 275 | 1.184 | 0.712402 | 0.134277 | 0.578125 | 2.037709 | 1.858108 | 2.084507 |
12 | 4.096 | 2.935 | 495 | 2.440 | 0.716553 | 0.120850 | 0.595703 | 2.011652 | 1.800000 | 2.060811 |
13 | 8.192 | 5.909 | 892 | 5.017 | 0.721313 | 0.108887 | 0.612427 | 2.013288 | 1.802020 | 2.056148 |
14 | 16.384 | 11.842 | 1.627 | 10.215 | 0.722778 | 0.099304 | 0.623474 | 2.004062 | 1.823991 | 2.036077 |
15 | 32.768 | 23.624 | 3.006 | 20.618 | 0.720947 | 0.091736 | 0.629211 | 1.994933 | 1.847572 | 2.018404 |
16 | 65.536 | 47.188 | 5.472 | 41.716 | 0.720032 | 0.083496 | 0.636536 | 1.997460 | 1.820359 | 2.023281 |
17 | 131.072 | 94.136 | 10.305 | 83.831 | 0.718201 | 0.078621 | 0.639580 | 1.994914 | 1.883224 | 2.009565 |
18 | 262.144 | 187.970 | 19.364 | 168.606 | 0.717049 | 0.073868 | 0.643181 | 1.996792 | 1.879088 | 2.011261 |
19 | 524.288 | 375.184 | 36.563 | 338.621 | 0.715607 | 0.069738 | 0.645868 | 1.995978 | 1.888195 | 2.008357 |
20 | 1.048.576 | 749.012 | 69.219 | 679.793 | 0.714314 | 0.066012 | 0.648301 | 1.996386 | 1.893143 | 2.007534 |
21 | 2.097.152 | 1.496.335 | 130.828 | 1.365.507 | 0.713508 | 0.062384 | 0.651124 | 1.997745 | 1.890059 | 2.008710 |
22 | 4.194.304 | 2.988.284 | 249.055 | 2.739.229 | 0.712462 | 0.059379 | 0.653083 | 1.997069 | 1.903683 | 2.006016 |
23 | 8.388.608 | 5.969.437 | 474.295 | 5.495.142 | 0.711612 | 0.056540 | 0.655072 | 1.997614 | 1.904379 | 2.006091 |
24 | 16.777.216 | 11.924.237 | 906.205 | 11.018.032 | 0.710740 | 0.054014 | 0.656726 | 1.997548 | 1.910636 | 2.005049 |
25 | 33.554.432 | 23.823.702 | 1.735.699 | 22.088.003 | 0.710002 | 0.051728 | 0.658274 | 1.997923 | 1.915349 | 2.004714 |
26 | 67.108.864 | 47.603.011 | 3.326.440 | 44.276.571 | 0.709340 | 0.049568 | 0.659772 | 1.998137 | 1.916484 | 2.004553 |
27 | 134.217.728 | 95.117.737 | 6.389.196 | 88.728.541 | 0.708682 | 0.047603 | 0.661079 | 1.998145 | 1.920731 | 2.003962 |
28 | 268.435.456 | 190.070.228 | 12.295.279 | 177.774.949 | 0.708067 | 0.045803 | 0.662263 | 1.998263 | 1.924386 | 2.003582 |
29 | 536.870.912 | 379.836.936 | 23.694.392 | 356.142.544 | 0.707501 | 0.044134 | 0.663367 | 1.998403 | 1.927113 | 2.003334 |
30 | 1.073.741.824 | 759.105.999 | 45.725.084 | 713.380.915 | 0.706973 | 0.042585 | 0.664388 | 1.998505 | 1.929785 | 2.003077 |
31 | 2.147.483.648 | 1.517.158.844 | 88.335.710 | 1.428.823.134 | 0.706482 | 0.041135 | 0.665348 | 1.998613 | 1.931887 | 2.002889 |
32 | 4.294.967.296 | 3.032.353.526 | 170.862.924 | 2.861.490.602 | 0.706025 | 0.039782 | 0.666243 | 1.998706 | 1.934245 | 2.002691 |
33 | 8.589.934.592 | 6.061.037.167 | 330.846.930 | 5.730.190.237 | 0.705598 | 0.038516 | 0.667082 | 1.998790 | 1.936330 | 2.002519 |
34 | 17.179.869.184 | 12.115.184.099 | 641.280.878 | 11.473.903.221 | 0.705196 | 0.037327 | 0.667869 | 1.998863 | 1.938301 | 2.002360 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 1 | 1 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 2 | 1 | 1 | 0 |
4 | 16 | 5 | 1 | 3 | 2 | 1 | 2 | 0 |
5 | 32 | 10 | 1 | 8 | 5 | 1 | 4 | 0 |
6 | 64 | 12 | 1 | 10 | 6 | 1 | 5 | 0 |
7 | 128 | 22 | 11 | 10 | 6 | 5 | 5 | 6 |
8 | 256 | 41 | 30 | 10 | 6 | 17 | 5 | 13 |
9 | 512 | 82 | 71 | 10 | 6 | 35 | 5 | 36 |
10 | 1.024 | 148 | 137 | 10 | 6 | 70 | 5 | 67 |
11 | 2.048 | 275 | 264 | 10 | 6 | 129 | 5 | 135 |
12 | 4.096 | 495 | 484 | 10 | 6 | 243 | 5 | 241 |
13 | 8.192 | 892 | 881 | 10 | 6 | 444 | 5 | 437 |
14 | 16.384 | 1.627 | 1.616 | 10 | 6 | 803 | 5 | 813 |
15 | 32.768 | 3.006 | 2.995 | 10 | 6 | 1.479 | 5 | 1.516 |
16 | 65.536 | 5.472 | 5.461 | 10 | 6 | 2.694 | 5 | 2.767 |
17 | 131.072 | 10.305 | 10.294 | 10 | 6 | 5.103 | 5 | 5.191 |
18 | 262.144 | 19.364 | 19.353 | 10 | 6 | 9.677 | 5 | 9.676 |
19 | 524.288 | 36.563 | 36.552 | 10 | 6 | 18.269 | 5 | 18.283 |
20 | 1.048.576 | 69.219 | 69.208 | 10 | 6 | 34.565 | 5 | 34.643 |
21 | 2.097.152 | 130.828 | 130.817 | 10 | 6 | 65.359 | 5 | 65.458 |
22 | 4.194.304 | 249.055 | 249.044 | 10 | 6 | 124.595 | 5 | 124.449 |
23 | 8.388.608 | 474.295 | 474.284 | 10 | 6 | 237.176 | 5 | 237.108 |
24 | 16.777.216 | 906.205 | 906.194 | 10 | 6 | 453.501 | 5 | 452.693 |
25 | 33.554.432 | 1.735.699 | 1.735.688 | 10 | 6 | 868.531 | 5 | 867.157 |
26 | 67.108.864 | 3.326.440 | 3.326.429 | 10 | 6 | 1.663.573 | 5 | 1.662.856 |
27 | 134.217.728 | 6.389.196 | 6.389.185 | 10 | 6 | 3.195.017 | 5 | 3.194.168 |
28 | 268.435.456 | 12.295.279 | 12.295.268 | 10 | 6 | 6.149.194 | 5 | 6.146.074 |
29 | 536.870.912 | 23.694.392 | 23.694.381 | 10 | 6 | 11.848.271 | 5 | 11.846.110 |
30 | 1.073.741.824 | 45.725.084 | 45.725.073 | 10 | 6 | 22.862.679 | 5 | 22.862.394 |
31 | 2.147.483.648 | 88.335.710 | 88.335.699 | 10 | 6 | 44.169.792 | 5 | 44.165.907 |
32 | 4.294.967.296 | 170.862.924 | 170.862.913 | 10 | 6 | 85.433.196 | 5 | 85.429.717 |
33 | 8.589.934.592 | 330.846.930 | 330.846.919 | 10 | 6 | 165.420.794 | 5 | 165.426.125 |
34 | 17.179.869.184 | 641.280.878 | 641.280.867 | 10 | 6 | 320.647.268 | 5 | 320.633.599 |
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 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 1 | 2 |
4 | 16 | 11 | 5 | 6 | 1 | 4 | 1 | 5 |
5 | 32 | 19 | 9 | 10 | 3 | 6 | 2 | 8 |
6 | 64 | 27 | 14 | 13 | 3 | 10 | 4 | 10 |
7 | 128 | 44 | 23 | 21 | 10 | 13 | 8 | 13 |
8 | 256 | 118 | 56 | 62 | 30 | 25 | 32 | 31 |
9 | 512 | 255 | 121 | 134 | 69 | 52 | 74 | 60 |
10 | 1.024 | 568 | 272 | 296 | 155 | 117 | 167 | 129 |
11 | 2.048 | 1.184 | 567 | 617 | 321 | 256 | 357 | 250 |
12 | 4.096 | 2.440 | 1.193 | 1.247 | 680 | 509 | 725 | 526 |
13 | 8.192 | 5.017 | 2.446 | 2.571 | 1.394 | 1.107 | 1.404 | 1.112 |
14 | 16.384 | 10.215 | 5.008 | 5.207 | 2.812 | 2.289 | 2.828 | 2.286 |
15 | 32.768 | 20.618 | 10.100 | 10.518 | 5.646 | 4.671 | 5.655 | 4.646 |
16 | 65.536 | 41.716 | 20.428 | 21.288 | 11.424 | 9.485 | 11.416 | 9.391 |
17 | 131.072 | 83.831 | 41.200 | 42.631 | 22.788 | 19.146 | 22.804 | 19.093 |
18 | 262.144 | 168.606 | 82.761 | 85.845 | 45.653 | 38.771 | 45.468 | 38.714 |
19 | 524.288 | 338.621 | 166.332 | 172.289 | 90.760 | 78.461 | 90.909 | 78.491 |
20 | 1.048.576 | 679.793 | 334.638 | 345.155 | 181.794 | 158.099 | 181.733 | 158.167 |
21 | 2.097.152 | 1.365.507 | 673.158 | 692.349 | 363.761 | 318.995 | 364.093 | 318.658 |
22 | 4.194.304 | 2.739.229 | 1.350.463 | 1.388.766 | 727.860 | 641.897 | 727.840 | 641.632 |
23 | 8.388.608 | 5.495.142 | 2.712.239 | 2.782.903 | 1.454.963 | 1.291.944 | 1.456.442 | 1.291.793 |
24 | 16.777.216 | 11.018.032 | 5.443.240 | 5.574.792 | 2.909.981 | 2.598.875 | 2.911.519 | 2.597.657 |
25 | 33.554.432 | 22.088.003 | 10.920.447 | 11.167.556 | 5.819.800 | 5.224.074 | 5.823.312 | 5.220.817 |
26 | 67.108.864 | 44.276.571 | 21.901.726 | 22.374.845 | 11.640.952 | 10.499.155 | 11.642.316 | 10.494.148 |
27 | 134.217.728 | 88.728.541 | 43.915.902 | 44.812.639 | 23.280.529 | 21.088.134 | 23.281.904 | 21.077.974 |
28 | 268.435.456 | 177.774.949 | 88.030.659 | 89.744.290 | 46.557.642 | 42.330.834 | 46.562.044 | 42.324.429 |
29 | 536.870.912 | 356.142.544 | 176.420.933 | 179.721.611 | 93.098.641 | 84.984.767 | 93.093.697 | 84.965.439 |
30 | 1.073.741.824 | 713.380.915 | 353.504.780 | 359.876.135 | 186.183.138 | 170.525.043 | 186.164.125 | 170.508.609 |
31 | 2.147.483.648 | 1.428.823.134 | 708.302.448 | 720.520.686 | 372.308.140 | 342.122.630 | 372.296.099 | 342.096.265 |
32 | 4.294.967.296 | 2.861.490.602 | 1.418.965.558 | 1.442.525.044 | 744.570.442 | 686.217.951 | 744.520.841 | 686.181.368 |
33 | 8.589.934.592 | 5.730.190.237 | 2.842.424.668 | 2.887.765.569 | 1.489.043.045 | 1.376.108.876 | 1.488.922.966 | 1.376.115.350 |
34 | 17.179.869.184 | 11.473.903.221 | 5.693.083.697 | 5.780.819.524 | 2.977.883.490 | 2.759.132.081 | 2.977.762.880 | 2.759.124.770 |