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+36x-13
f(0)=13
f(1)=3
f(2)=7
f(3)=1
f(4)=1
f(5)=1
f(6)=239
f(7)=1
f(8)=113
f(9)=1
f(10)=149
f(11)=1
f(12)=563
f(13)=1
f(14)=229
f(15)=47
f(16)=1
f(17)=37
f(18)=137
f(19)=43
f(20)=41
f(21)=1
f(22)=421
f(23)=1
f(24)=1427
f(25)=1
f(26)=1
f(27)=211
f(28)=593
f(29)=1
f(30)=281
f(31)=1
f(32)=103
f(33)=283
f(34)=263
f(35)=1
f(36)=2579
f(37)=1
f(38)=311
f(39)=1
f(40)=1009
f(41)=131
f(42)=251
f(43)=1
f(44)=167
f(45)=227
f(46)=179
f(47)=1
f(48)=4019
f(49)=173
f(50)=1429
f(51)=79
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=571
f(57)=661
f(58)=1
f(59)=233
f(60)=821
f(61)=1
f(62)=1
f(63)=389
f(64)=2129
f(65)=1
f(66)=6719
f(67)=1
f(68)=181
f(69)=1
f(70)=823
f(71)=1
f(72)=1109
f(73)=331
f(74)=1
f(75)=1039
f(76)=2833
f(77)=1
f(78)=683
f(79)=1
f(80)=3089
f(81)=1
f(82)=3221
f(83)=1
f(84)=10067
f(85)=107
f(86)=499
f(87)=1
f(88)=1
f(89)=463
f(90)=241
f(91)=1
f(92)=1307
f(93)=1
f(94)=313
f(95)=1
f(96)=12659
f(97)=1
f(98)=4373
f(99)=1669
b) Substitution of the polynom
The polynom f(x)=x^2+36x-13 could be written as f(y)= y^2-337 with x=y-18
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+18
f'(x)>2x+35
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 | 6 | 3 | 3 | 0.600000 | 0.300000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 18 | 40 | 0.580000 | 0.180000 | 0.400000 | 9.666667 | 6.000000 | 13.333333 |
3 | 1.000 | 598 | 124 | 474 | 0.598000 | 0.124000 | 0.474000 | 10.310345 | 6.888889 | 11.850000 |
4 | 10.000 | 6.267 | 896 | 5.371 | 0.626700 | 0.089600 | 0.537100 | 10.479933 | 7.225806 | 11.331223 |
5 | 100.000 | 64.135 | 6.820 | 57.315 | 0.641350 | 0.068200 | 0.573150 | 10.233764 | 7.611607 | 10.671197 |
6 | 1.000.000 | 650.048 | 54.896 | 595.152 | 0.650048 | 0.054896 | 0.595152 | 10.135620 | 8.049267 | 10.383879 |
7 | 10.000.000 | 6.565.772 | 459.760 | 6.106.012 | 0.656577 | 0.045976 | 0.610601 | 10.100442 | 8.375110 | 10.259584 |
8 | 100.000.000 | 66.113.312 | 3.955.583 | 62.157.729 | 0.661133 | 0.039556 | 0.621577 | 10.069389 | 8.603582 | 10.179759 |
9 | 1.000.000.000 | 664.727.472 | 34.727.197 | 630.000.275 | 0.664728 | 0.034727 | 0.630000 | 10.054367 | 8.779286 | 10.135509 |
10 | 10.000.000.000 | 6.675.875.903 | 309.478.942 | 6.366.396.961 | 0.667588 | 0.030948 | 0.636640 | 10.043027 | 8.911717 | 10.105388 |
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 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 5 | 3 | 2 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.500000 | 2.000000 |
4 | 16 | 9 | 5 | 4 | 0.562500 | 0.312500 | 0.250000 | 1.800000 | 1.666667 | 2.000000 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 2.111111 | 1.400000 | 3.000000 |
6 | 64 | 38 | 13 | 25 | 0.593750 | 0.203125 | 0.390625 | 2.000000 | 1.857143 | 2.083333 |
7 | 128 | 75 | 20 | 55 | 0.585938 | 0.156250 | 0.429688 | 1.973684 | 1.538462 | 2.200000 |
8 | 256 | 142 | 36 | 106 | 0.554688 | 0.140625 | 0.414062 | 1.893333 | 1.800000 | 1.927273 |
9 | 512 | 304 | 71 | 233 | 0.593750 | 0.138672 | 0.455078 | 2.140845 | 1.972222 | 2.198113 |
10 | 1.024 | 615 | 126 | 489 | 0.600586 | 0.123047 | 0.477539 | 2.023026 | 1.774648 | 2.098712 |
11 | 2.048 | 1.247 | 232 | 1.015 | 0.608887 | 0.113281 | 0.495605 | 2.027642 | 1.841270 | 2.075665 |
12 | 4.096 | 2.525 | 420 | 2.105 | 0.616455 | 0.102539 | 0.513916 | 2.024860 | 1.810345 | 2.073892 |
13 | 8.192 | 5.119 | 761 | 4.358 | 0.624878 | 0.092896 | 0.531982 | 2.027327 | 1.811905 | 2.070309 |
14 | 16.384 | 10.330 | 1.392 | 8.938 | 0.630493 | 0.084961 | 0.545532 | 2.017972 | 1.829172 | 2.050941 |
15 | 32.768 | 20.806 | 2.551 | 18.255 | 0.634949 | 0.077850 | 0.557098 | 2.014134 | 1.832615 | 2.042403 |
16 | 65.536 | 41.922 | 4.657 | 37.265 | 0.639679 | 0.071060 | 0.568619 | 2.014899 | 1.825559 | 2.041358 |
17 | 131.072 | 84.237 | 8.689 | 75.548 | 0.642677 | 0.066292 | 0.576385 | 2.009375 | 1.865793 | 2.027318 |
18 | 262.144 | 169.227 | 16.177 | 153.050 | 0.645550 | 0.061710 | 0.583839 | 2.008939 | 1.861779 | 2.025864 |
19 | 524.288 | 339.763 | 30.402 | 309.361 | 0.648046 | 0.057987 | 0.590059 | 2.007735 | 1.879335 | 2.021307 |
20 | 1.048.576 | 681.716 | 57.353 | 624.363 | 0.650135 | 0.054696 | 0.595439 | 2.006446 | 1.886488 | 2.018234 |
21 | 2.097.152 | 1.368.331 | 108.188 | 1.260.143 | 0.652471 | 0.051588 | 0.600883 | 2.007186 | 1.886353 | 2.018286 |
22 | 4.194.304 | 2.744.680 | 205.619 | 2.539.061 | 0.654383 | 0.049023 | 0.605359 | 2.005860 | 1.900571 | 2.014899 |
23 | 8.388.608 | 5.504.061 | 390.750 | 5.113.311 | 0.656135 | 0.046581 | 0.609554 | 2.005356 | 1.900359 | 2.013859 |
24 | 16.777.216 | 11.034.067 | 744.369 | 10.289.698 | 0.657682 | 0.044368 | 0.613314 | 2.004714 | 1.904975 | 2.012336 |
25 | 33.554.432 | 22.114.764 | 1.422.549 | 20.692.215 | 0.659071 | 0.042395 | 0.616676 | 2.004226 | 1.911080 | 2.010964 |
26 | 67.108.864 | 44.320.272 | 2.720.637 | 41.599.635 | 0.660424 | 0.040541 | 0.619883 | 2.004103 | 1.912508 | 2.010400 |
27 | 134.217.728 | 88.805.018 | 5.217.244 | 83.587.774 | 0.661649 | 0.038871 | 0.622777 | 2.003711 | 1.917655 | 2.009339 |
28 | 268.435.456 | 177.916.791 | 10.020.555 | 167.896.236 | 0.662792 | 0.037329 | 0.625462 | 2.003454 | 1.920661 | 2.008622 |
29 | 536.870.912 | 356.399.620 | 19.278.109 | 337.121.511 | 0.663846 | 0.035908 | 0.627938 | 2.003181 | 1.923856 | 2.007916 |
30 | 1.073.741.824 | 713.856.141 | 37.147.222 | 676.708.919 | 0.664830 | 0.034596 | 0.630234 | 2.002965 | 1.926912 | 2.007315 |
31 | 2.147.483.648 | 1.429.687.395 | 71.665.061 | 1.358.022.334 | 0.665750 | 0.033372 | 0.632378 | 2.002767 | 1.929217 | 2.006804 |
32 | 4.294.967.296 | 2.863.064.851 | 138.435.558 | 2.724.629.293 | 0.666609 | 0.032232 | 0.634377 | 2.002581 | 1.931702 | 2.006321 |
33 | 8.589.934.592 | 5.733.071.012 | 267.761.230 | 5.465.309.782 | 0.667417 | 0.031172 | 0.636246 | 2.002424 | 1.934194 | 2.005891 |
34 | 17.179.869.184 | 11.479.221.756 | 518.406.738 | 10.960.815.018 | 0.668179 | 0.030175 | 0.638003 | 2.002281 | 1.936078 | 2.005525 |
35 | 34.359.738.368 | 22.983.081.167 | 1.004.738.738 | 21.978.342.429 | 0.668896 | 0.029242 | 0.639654 | 2.002146 | 1.938128 | 2.005174 |
36 | 68.719.476.736 | 46.012.763.604 | 1.949.174.441 | 44.063.589.163 | 0.669574 | 0.028364 | 0.641210 | 2.002028 | 1.939981 | 2.004864 |
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 | 1 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 5 | 1 | 3 | 0 | 2 | 1 | 2 |
5 | 32 | 7 | 2 | 4 | 0 | 4 | 1 | 2 |
6 | 64 | 13 | 4 | 8 | 0 | 8 | 3 | 2 |
7 | 128 | 20 | 6 | 13 | 0 | 11 | 4 | 5 |
8 | 256 | 36 | 12 | 23 | 4 | 16 | 6 | 10 |
9 | 512 | 71 | 25 | 45 | 8 | 27 | 13 | 23 |
10 | 1.024 | 126 | 49 | 76 | 16 | 42 | 22 | 46 |
11 | 2.048 | 232 | 81 | 150 | 32 | 84 | 34 | 82 |
12 | 4.096 | 420 | 147 | 272 | 61 | 157 | 61 | 141 |
13 | 8.192 | 761 | 266 | 494 | 107 | 281 | 109 | 264 |
14 | 16.384 | 1.392 | 497 | 894 | 194 | 501 | 192 | 505 |
15 | 32.768 | 2.551 | 904 | 1.646 | 352 | 942 | 337 | 920 |
16 | 65.536 | 4.657 | 1.659 | 2.997 | 623 | 1.703 | 646 | 1.685 |
17 | 131.072 | 8.689 | 3.073 | 5.615 | 1.151 | 3.212 | 1.160 | 3.166 |
18 | 262.144 | 16.177 | 5.724 | 10.452 | 2.131 | 5.984 | 2.155 | 5.907 |
19 | 524.288 | 30.402 | 10.756 | 19.645 | 4.026 | 11.177 | 4.073 | 11.126 |
20 | 1.048.576 | 57.353 | 20.132 | 37.220 | 7.511 | 21.184 | 7.649 | 21.009 |
21 | 2.097.152 | 108.188 | 37.903 | 70.284 | 14.254 | 39.885 | 14.394 | 39.655 |
22 | 4.194.304 | 205.619 | 71.604 | 134.014 | 27.030 | 75.641 | 27.190 | 75.758 |
23 | 8.388.608 | 390.750 | 135.587 | 255.162 | 51.419 | 143.786 | 51.538 | 144.007 |
24 | 16.777.216 | 744.369 | 257.763 | 486.605 | 97.908 | 274.333 | 97.671 | 274.457 |
25 | 33.554.432 | 1.422.549 | 491.949 | 930.599 | 186.238 | 524.463 | 186.298 | 525.550 |
26 | 67.108.864 | 2.720.637 | 939.426 | 1.781.210 | 355.256 | 1.004.535 | 355.479 | 1.005.367 |
27 | 134.217.728 | 5.217.244 | 1.798.487 | 3.418.756 | 679.775 | 1.927.972 | 679.809 | 1.929.688 |
28 | 268.435.456 | 10.020.555 | 3.448.245 | 6.572.309 | 1.302.996 | 3.706.515 | 1.302.474 | 3.708.570 |
29 | 536.870.912 | 19.278.109 | 6.627.247 | 12.650.861 | 2.502.923 | 7.136.173 | 2.502.269 | 7.136.744 |
30 | 1.073.741.824 | 37.147.222 | 12.757.066 | 24.390.155 | 4.813.969 | 13.758.703 | 4.815.780 | 13.758.770 |
31 | 2.147.483.648 | 71.665.061 | 24.588.778 | 47.076.282 | 9.276.967 | 26.552.156 | 9.277.337 | 26.558.601 |
32 | 4.294.967.296 | 138.435.558 | 47.452.113 | 90.983.444 | 17.898.026 | 51.319.950 | 17.900.817 | 51.316.765 |
33 | 8.589.934.592 | 267.761.230 | 91.690.660 | 176.070.569 | 34.580.530 | 99.301.371 | 34.580.862 | 99.298.467 |
34 | 17.179.869.184 | 518.406.738 | 177.376.532 | 341.030.205 | 66.884.937 | 192.326.891 | 66.876.403 | 192.318.507 |
35 | 34.359.738.368 | 1.004.738.738 | 343.495.138 | 661.243.599 | 129.499.274 | 372.879.427 | 129.498.665 | 372.861.372 |
36 | 68.719.476.736 | 1.949.174.441 | 665.892.850 | 1.283.281.590 | 251.002.627 | 723.600.612 | 251.001.452 | 723.569.750 |
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 | 0 | 1 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
4 | 16 | 4 | 2 | 2 | 1 | 0 | 2 | 1 |
5 | 32 | 12 | 6 | 6 | 5 | 1 | 4 | 2 |
6 | 64 | 25 | 9 | 16 | 8 | 5 | 7 | 5 |
7 | 128 | 55 | 24 | 31 | 14 | 12 | 17 | 12 |
8 | 256 | 106 | 50 | 56 | 32 | 20 | 33 | 21 |
9 | 512 | 233 | 111 | 122 | 63 | 52 | 72 | 46 |
10 | 1.024 | 489 | 229 | 260 | 128 | 106 | 153 | 102 |
11 | 2.048 | 1.015 | 489 | 526 | 265 | 239 | 291 | 220 |
12 | 4.096 | 2.105 | 1.008 | 1.097 | 554 | 500 | 567 | 484 |
13 | 8.192 | 4.358 | 2.106 | 2.252 | 1.140 | 1.026 | 1.160 | 1.032 |
14 | 16.384 | 8.938 | 4.325 | 4.613 | 2.354 | 2.068 | 2.412 | 2.104 |
15 | 32.768 | 18.255 | 8.896 | 9.359 | 4.832 | 4.288 | 4.874 | 4.261 |
16 | 65.536 | 37.265 | 18.116 | 19.149 | 9.767 | 8.872 | 9.877 | 8.749 |
17 | 131.072 | 75.548 | 36.888 | 38.660 | 19.776 | 17.975 | 19.929 | 17.868 |
18 | 262.144 | 153.050 | 74.825 | 78.225 | 39.954 | 36.435 | 40.263 | 36.398 |
19 | 524.288 | 309.361 | 151.490 | 157.871 | 80.675 | 73.941 | 81.127 | 73.618 |
20 | 1.048.576 | 624.363 | 306.738 | 317.625 | 162.415 | 149.655 | 163.152 | 149.141 |
21 | 2.097.152 | 1.260.143 | 619.897 | 640.246 | 327.273 | 301.897 | 328.272 | 302.701 |
22 | 4.194.304 | 2.539.061 | 1.250.542 | 1.288.519 | 658.713 | 609.969 | 660.020 | 610.359 |
23 | 8.388.608 | 5.113.311 | 2.521.201 | 2.592.110 | 1.325.678 | 1.230.861 | 1.325.863 | 1.230.909 |
24 | 16.777.216 | 10.289.698 | 5.075.444 | 5.214.254 | 2.662.576 | 2.482.847 | 2.663.195 | 2.481.080 |
25 | 33.554.432 | 20.692.215 | 10.212.599 | 10.479.616 | 5.345.709 | 4.998.685 | 5.348.807 | 4.999.014 |
26 | 67.108.864 | 41.599.635 | 20.547.884 | 21.051.751 | 10.729.436 | 10.066.590 | 10.736.325 | 10.067.284 |
27 | 134.217.728 | 83.587.774 | 41.311.779 | 42.275.995 | 21.533.669 | 20.260.455 | 21.533.253 | 20.260.397 |
28 | 268.435.456 | 167.896.236 | 83.016.510 | 84.879.726 | 43.201.489 | 40.751.928 | 43.201.390 | 40.741.429 |
29 | 536.870.912 | 337.121.511 | 166.768.261 | 170.353.250 | 86.643.239 | 81.920.841 | 86.643.595 | 81.913.836 |
30 | 1.073.741.824 | 676.708.919 | 334.895.079 | 341.813.840 | 173.729.618 | 164.633.831 | 173.719.247 | 164.626.223 |
31 | 2.147.483.648 | 1.358.022.334 | 672.323.659 | 685.698.675 | 348.301.994 | 330.734.414 | 348.273.933 | 330.711.993 |
32 | 4.294.967.296 | 2.724.629.293 | 1.349.416.595 | 1.375.212.698 | 698.141.483 | 664.212.710 | 698.120.011 | 664.155.089 |
33 | 8.589.934.592 | 5.465.309.782 | 2.707.740.254 | 2.757.569.528 | 1.399.202.661 | 1.333.502.246 | 1.399.150.845 | 1.333.454.030 |
34 | 17.179.869.184 | 10.960.815.018 | 5.432.155.574 | 5.528.659.444 | 2.803.847.492 | 2.676.542.149 | 2.803.847.031 | 2.676.578.346 |
35 | 34.359.738.368 | 21.978.342.429 | 10.895.576.801 | 11.082.765.628 | 5.618.022.434 | 5.371.094.616 | 5.618.045.169 | 5.371.180.210 |
36 | 68.719.476.736 | 44.063.589.163 | 21.850.271.312 | 22.213.317.851 | 11.255.486.244 | 10.776.292.942 | 11.255.509.955 | 10.776.300.022 |