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-64x-7
f(0)=7
f(1)=5
f(2)=131
f(3)=19
f(4)=13
f(5)=151
f(6)=71
f(7)=29
f(8)=1
f(9)=251
f(10)=547
f(11)=59
f(12)=631
f(13)=67
f(14)=101
f(15)=53
f(16)=31
f(17)=1
f(18)=167
f(19)=431
f(20)=887
f(21)=1
f(22)=1
f(23)=1
f(24)=967
f(25)=491
f(26)=199
f(27)=503
f(28)=1
f(29)=73
f(30)=79
f(31)=103
f(32)=1031
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)=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)=97
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=569
f(73)=1
f(74)=733
f(75)=409
f(76)=181
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=137
f(82)=113
f(83)=157
f(84)=239
f(85)=127
f(86)=1
f(87)=997
f(88)=421
f(89)=1109
f(90)=2333
f(91)=1
f(92)=367
f(93)=269
f(94)=1
f(95)=1
f(96)=613
f(97)=1597
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-64x-7 could be written as f(y)= y^2-1031 with x=y+32
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-32
f'(x)>2x-65 with x > 32
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 | 5 | 5 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 40 | 20 | 20 | 0.400000 | 0.200000 | 0.200000 | 4.000000 | 4.000000 | 4.000000 |
3 | 1.000 | 601 | 162 | 439 | 0.601000 | 0.162000 | 0.439000 | 15.025000 | 8.100000 | 21.950001 |
4 | 10.000 | 6.561 | 1.182 | 5.379 | 0.656100 | 0.118200 | 0.537900 | 10.916805 | 7.296296 | 12.252848 |
5 | 100.000 | 66.854 | 9.209 | 57.645 | 0.668540 | 0.092090 | 0.576450 | 10.189606 | 7.791032 | 10.716676 |
6 | 1.000.000 | 672.714 | 75.578 | 597.136 | 0.672714 | 0.075578 | 0.597136 | 10.062434 | 8.206971 | 10.358851 |
7 | 10.000.000 | 6.758.071 | 637.527 | 6.120.544 | 0.675807 | 0.063753 | 0.612054 | 10.045979 | 8.435351 | 10.249832 |
8 | 100.000.000 | 67.799.878 | 5.515.962 | 62.283.916 | 0.677999 | 0.055160 | 0.622839 | 10.032431 | 8.652122 | 10.176206 |
9 | 1.000.000.000 | 679.630.690 | 48.652.312 | 630.978.378 | 0.679631 | 0.048652 | 0.630978 | 10.024070 | 8.820277 | 10.130679 |
10 | 10.000.000.000 | 6.809.537.393 | 434.939.351 | 6.374.598.042 | 0.680954 | 0.043494 | 0.637460 | 10.019467 | 8.939747 | 10.102720 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 1.875000 | 2.000000 | 1.800000 |
5 | 32 | 26 | 12 | 14 | 0.812500 | 0.375000 | 0.437500 | 1.733333 | 2.000000 | 1.555556 |
6 | 64 | 26 | 12 | 14 | 0.406250 | 0.187500 | 0.218750 | 1.000000 | 1.000000 | 1.000000 |
7 | 128 | 54 | 25 | 29 | 0.421875 | 0.195312 | 0.226562 | 2.076923 | 2.083333 | 2.071429 |
8 | 256 | 128 | 51 | 77 | 0.500000 | 0.199219 | 0.300781 | 2.370370 | 2.040000 | 2.655172 |
9 | 512 | 283 | 93 | 190 | 0.552734 | 0.181641 | 0.371094 | 2.210938 | 1.823529 | 2.467532 |
10 | 1.024 | 616 | 165 | 451 | 0.601562 | 0.161133 | 0.440430 | 2.176678 | 1.774194 | 2.373684 |
11 | 2.048 | 1.281 | 304 | 977 | 0.625488 | 0.148438 | 0.477051 | 2.079545 | 1.842424 | 2.166297 |
12 | 4.096 | 2.642 | 549 | 2.093 | 0.645020 | 0.134033 | 0.510986 | 2.062451 | 1.805921 | 2.142272 |
13 | 8.192 | 5.358 | 982 | 4.376 | 0.654053 | 0.119873 | 0.534180 | 2.028009 | 1.788707 | 2.090779 |
14 | 16.384 | 10.827 | 1.825 | 9.002 | 0.660828 | 0.111389 | 0.549438 | 2.020717 | 1.858452 | 2.057130 |
15 | 32.768 | 21.775 | 3.372 | 18.403 | 0.664520 | 0.102905 | 0.561615 | 2.011176 | 1.847671 | 2.044323 |
16 | 65.536 | 43.743 | 6.274 | 37.469 | 0.667465 | 0.095734 | 0.571732 | 2.008863 | 1.860617 | 2.036027 |
17 | 131.072 | 87.701 | 11.783 | 75.918 | 0.669106 | 0.089897 | 0.579208 | 2.004915 | 1.878068 | 2.026155 |
18 | 262.144 | 175.829 | 22.174 | 153.655 | 0.670734 | 0.084587 | 0.586147 | 2.004869 | 1.881864 | 2.023960 |
19 | 524.288 | 352.168 | 41.866 | 310.302 | 0.671707 | 0.079853 | 0.591854 | 2.002901 | 1.888067 | 2.019472 |
20 | 1.048.576 | 705.502 | 78.953 | 626.549 | 0.672819 | 0.075295 | 0.597524 | 2.003311 | 1.885850 | 2.019159 |
21 | 2.097.152 | 1.412.912 | 149.672 | 1.263.240 | 0.673729 | 0.071369 | 0.602360 | 2.002704 | 1.895710 | 2.016187 |
22 | 4.194.304 | 2.830.258 | 283.966 | 2.546.292 | 0.674786 | 0.067703 | 0.607083 | 2.003138 | 1.897255 | 2.015683 |
23 | 8.388.608 | 5.667.503 | 541.030 | 5.126.473 | 0.675619 | 0.064496 | 0.611123 | 2.002469 | 1.905263 | 2.013309 |
24 | 16.777.216 | 11.347.715 | 1.033.520 | 10.314.195 | 0.676377 | 0.061603 | 0.614774 | 2.002242 | 1.910282 | 2.011948 |
25 | 33.554.432 | 22.717.107 | 1.977.276 | 20.739.831 | 0.677023 | 0.058927 | 0.618095 | 2.001910 | 1.913147 | 2.010805 |
26 | 67.108.864 | 45.476.335 | 3.790.079 | 41.686.256 | 0.677650 | 0.056477 | 0.621174 | 2.001854 | 1.916818 | 2.009961 |
27 | 134.217.728 | 91.030.497 | 7.279.079 | 83.751.418 | 0.678230 | 0.054233 | 0.623997 | 2.001711 | 1.920561 | 2.009089 |
28 | 268.435.456 | 182.199.512 | 14.005.455 | 168.194.057 | 0.678746 | 0.052174 | 0.626572 | 2.001522 | 1.924070 | 2.008253 |
29 | 536.870.912 | 364.652.727 | 26.984.196 | 337.668.531 | 0.679219 | 0.050262 | 0.628957 | 2.001392 | 1.926692 | 2.007613 |
30 | 1.073.741.824 | 729.797.197 | 52.049.256 | 677.747.941 | 0.679677 | 0.048475 | 0.631202 | 2.001348 | 1.928879 | 2.007140 |
31 | 2.147.483.648 | 1.460.492.341 | 100.525.304 | 1.359.967.037 | 0.680095 | 0.046811 | 0.633284 | 2.001230 | 1.931350 | 2.006597 |
32 | 4.294.967.296 | 2.922.719.742 | 194.366.776 | 2.728.352.966 | 0.680499 | 0.045255 | 0.635244 | 2.001188 | 1.933511 | 2.006191 |
33 | 8.589.934.592 | 5.848.672.096 | 376.237.978 | 5.472.434.118 | 0.680875 | 0.043800 | 0.637075 | 2.001106 | 1.935711 | 2.005765 |
34 | 17.179.869.184 | 11.703.412.247 | 729.083.478 | 10.974.328.769 | 0.681228 | 0.042438 | 0.638790 | 2.001038 | 1.937825 | 2.005383 |
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 | 1 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 1 | 0 | 2 |
4 | 16 | 6 | 4 | 2 | 0 | 3 | 0 | 3 |
5 | 32 | 12 | 5 | 7 | 0 | 4 | 0 | 8 |
6 | 64 | 12 | 5 | 7 | 0 | 4 | 0 | 8 |
7 | 128 | 25 | 11 | 14 | 6 | 4 | 7 | 8 |
8 | 256 | 51 | 23 | 28 | 19 | 4 | 20 | 8 |
9 | 512 | 93 | 45 | 48 | 38 | 4 | 43 | 8 |
10 | 1.024 | 165 | 79 | 86 | 68 | 4 | 85 | 8 |
11 | 2.048 | 304 | 156 | 148 | 140 | 4 | 152 | 8 |
12 | 4.096 | 549 | 269 | 280 | 260 | 4 | 277 | 8 |
13 | 8.192 | 982 | 499 | 483 | 481 | 4 | 489 | 8 |
14 | 16.384 | 1.825 | 919 | 906 | 924 | 4 | 889 | 8 |
15 | 32.768 | 3.372 | 1.671 | 1.701 | 1.682 | 4 | 1.678 | 8 |
16 | 65.536 | 6.274 | 3.151 | 3.123 | 3.119 | 4 | 3.143 | 8 |
17 | 131.072 | 11.783 | 5.958 | 5.825 | 5.899 | 4 | 5.872 | 8 |
18 | 262.144 | 22.174 | 11.190 | 10.984 | 11.095 | 4 | 11.067 | 8 |
19 | 524.288 | 41.866 | 21.110 | 20.756 | 20.903 | 4 | 20.951 | 8 |
20 | 1.048.576 | 78.953 | 39.816 | 39.137 | 39.435 | 4 | 39.506 | 8 |
21 | 2.097.152 | 149.672 | 75.517 | 74.155 | 74.876 | 4 | 74.784 | 8 |
22 | 4.194.304 | 283.966 | 142.963 | 141.003 | 141.878 | 4 | 142.076 | 8 |
23 | 8.388.608 | 541.030 | 271.907 | 269.123 | 270.220 | 4 | 270.798 | 8 |
24 | 16.777.216 | 1.033.520 | 519.349 | 514.171 | 517.004 | 4 | 516.504 | 8 |
25 | 33.554.432 | 1.977.276 | 992.516 | 984.760 | 988.830 | 4 | 988.434 | 8 |
26 | 67.108.864 | 3.790.079 | 1.901.734 | 1.888.345 | 1.895.562 | 4 | 1.894.505 | 8 |
27 | 134.217.728 | 7.279.079 | 3.650.725 | 3.628.354 | 3.640.325 | 4 | 3.638.742 | 8 |
28 | 268.435.456 | 14.005.455 | 7.025.355 | 6.980.100 | 7.005.749 | 4 | 6.999.694 | 8 |
29 | 536.870.912 | 26.984.196 | 13.533.976 | 13.450.220 | 13.495.900 | 4 | 13.488.284 | 8 |
30 | 1.073.741.824 | 52.049.256 | 26.102.117 | 25.947.139 | 26.030.025 | 4 | 26.019.219 | 8 |
31 | 2.147.483.648 | 100.525.304 | 50.406.433 | 50.118.871 | 50.266.088 | 4 | 50.259.204 | 8 |
32 | 4.294.967.296 | 194.366.776 | 97.449.722 | 96.917.054 | 97.188.350 | 4 | 97.178.414 | 8 |
33 | 8.589.934.592 | 376.237.978 | 188.613.350 | 187.624.628 | 188.121.283 | 4 | 188.116.683 | 8 |
34 | 17.179.869.184 | 729.083.478 | 365.491.594 | 363.591.884 | 364.546.477 | 4 | 364.536.989 | 8 |
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 | 0 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 0 |
3 | 8 | 5 | 2 | 3 | 0 | 1 | 3 | 1 |
4 | 16 | 9 | 3 | 6 | 0 | 3 | 5 | 1 |
5 | 32 | 14 | 7 | 7 | 1 | 3 | 5 | 5 |
6 | 64 | 14 | 7 | 7 | 1 | 3 | 5 | 5 |
7 | 128 | 29 | 15 | 14 | 4 | 6 | 12 | 7 |
8 | 256 | 77 | 38 | 39 | 16 | 16 | 28 | 17 |
9 | 512 | 190 | 92 | 98 | 43 | 39 | 62 | 46 |
10 | 1.024 | 451 | 226 | 225 | 111 | 105 | 132 | 103 |
11 | 2.048 | 977 | 484 | 493 | 234 | 232 | 274 | 237 |
12 | 4.096 | 2.093 | 1.034 | 1.059 | 527 | 477 | 555 | 534 |
13 | 8.192 | 4.376 | 2.161 | 2.215 | 1.114 | 1.042 | 1.144 | 1.076 |
14 | 16.384 | 9.002 | 4.499 | 4.503 | 2.287 | 2.174 | 2.321 | 2.220 |
15 | 32.768 | 18.403 | 9.166 | 9.237 | 4.631 | 4.468 | 4.781 | 4.523 |
16 | 65.536 | 37.469 | 18.640 | 18.829 | 9.506 | 9.065 | 9.618 | 9.280 |
17 | 131.072 | 75.918 | 37.814 | 38.104 | 19.240 | 18.449 | 19.487 | 18.742 |
18 | 262.144 | 153.655 | 76.647 | 77.008 | 39.106 | 37.447 | 39.204 | 37.898 |
19 | 524.288 | 310.302 | 155.300 | 155.002 | 78.980 | 76.091 | 78.671 | 76.560 |
20 | 1.048.576 | 626.549 | 313.587 | 312.962 | 158.875 | 154.084 | 159.134 | 154.456 |
21 | 2.097.152 | 1.263.240 | 632.174 | 631.066 | 320.195 | 311.201 | 320.397 | 311.447 |
22 | 4.194.304 | 2.546.292 | 1.273.786 | 1.272.506 | 645.498 | 628.063 | 645.137 | 627.594 |
23 | 8.388.608 | 5.126.473 | 2.563.590 | 2.562.883 | 1.298.007 | 1.265.070 | 1.298.552 | 1.264.844 |
24 | 16.777.216 | 10.314.195 | 5.157.383 | 5.156.812 | 2.611.059 | 2.547.165 | 2.609.368 | 2.546.603 |
25 | 33.554.432 | 20.739.831 | 10.369.184 | 10.370.647 | 5.245.556 | 5.124.960 | 5.244.145 | 5.125.170 |
26 | 67.108.864 | 41.686.256 | 20.842.377 | 20.843.879 | 10.539.618 | 10.302.408 | 10.537.843 | 10.306.387 |
27 | 134.217.728 | 83.751.418 | 41.871.327 | 41.880.091 | 21.164.071 | 20.711.236 | 21.163.669 | 20.712.442 |
28 | 268.435.456 | 168.194.057 | 84.098.390 | 84.095.667 | 42.488.974 | 41.607.538 | 42.490.241 | 41.607.304 |
29 | 536.870.912 | 337.668.531 | 168.827.978 | 168.840.553 | 85.271.423 | 83.563.864 | 85.266.467 | 83.566.777 |
30 | 1.073.741.824 | 677.747.941 | 338.868.776 | 338.879.165 | 171.092.688 | 167.776.995 | 171.094.207 | 167.784.051 |
31 | 2.147.483.648 | 1.359.967.037 | 679.977.647 | 679.989.390 | 343.198.636 | 336.799.449 | 343.188.119 | 336.780.833 |
32 | 4.294.967.296 | 2.728.352.966 | 1.364.160.986 | 1.364.191.980 | 688.305.817 | 675.889.429 | 688.286.661 | 675.871.059 |
33 | 8.589.934.592 | 5.472.434.118 | 2.736.211.057 | 2.736.223.061 | 1.380.194.424 | 1.356.049.951 | 1.380.164.166 | 1.356.025.577 |
34 | 17.179.869.184 | 10.974.328.769 | 5.487.161.206 | 5.487.167.563 | 2.767.045.178 | 2.720.164.743 | 2.766.983.524 | 2.720.135.324 |