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-62x+83
f(0)=83
f(1)=11
f(2)=37
f(3)=47
f(4)=149
f(5)=101
f(6)=23
f(7)=151
f(8)=349
f(9)=197
f(10)=19
f(11)=239
f(12)=1
f(13)=277
f(14)=31
f(15)=311
f(16)=653
f(17)=1
f(18)=709
f(19)=367
f(20)=757
f(21)=389
f(22)=797
f(23)=1
f(24)=829
f(25)=421
f(26)=853
f(27)=431
f(28)=79
f(29)=1
f(30)=877
f(31)=439
f(32)=1
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)=73
f(64)=211
f(65)=139
f(66)=347
f(67)=1
f(68)=491
f(69)=283
f(70)=643
f(71)=1
f(72)=1
f(73)=443
f(74)=971
f(75)=1
f(76)=1
f(77)=619
f(78)=1
f(79)=1
f(80)=1523
f(81)=811
f(82)=1723
f(83)=1
f(84)=1931
f(85)=1019
f(86)=113
f(87)=1129
f(88)=2371
f(89)=1
f(90)=137
f(91)=1361
f(92)=2843
f(93)=1483
f(94)=281
f(95)=1609
f(96)=3347
f(97)=1
f(98)=157
f(99)=1873
b) Substitution of the polynom
The polynom f(x)=x^2-62x+83 could be written as f(y)= y^2-878 with x=y+31
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-31
f'(x)>2x-63 with x > 30
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 | 9 | 1 | 1.000000 | 0.900000 | 1.000000 | |||
2 | 100 | 51 | 46 | 5 | 0.510000 | 0.460000 | 0.510000 | 5.100000 | 5.111111 | 5.000000 |
3 | 1.000 | 712 | 379 | 333 | 0.712000 | 0.379000 | 0.712000 | 13.960784 | 8.239130 | 66.599998 |
4 | 10.000 | 7.328 | 2.661 | 4.667 | 0.732800 | 0.266100 | 0.732800 | 10.292135 | 7.021108 | 14.015015 |
5 | 100.000 | 72.724 | 20.666 | 52.058 | 0.727240 | 0.206660 | 0.727240 | 9.924127 | 7.766253 | 11.154489 |
6 | 1.000.000 | 721.828 | 168.038 | 553.790 | 0.721828 | 0.168038 | 0.721828 | 9.925582 | 8.131133 | 10.637942 |
7 | 10.000.000 | 7.176.740 | 1.416.924 | 5.759.816 | 0.717674 | 0.141692 | 0.717674 | 9.942451 | 8.432164 | 10.400723 |
8 | 100.000.000 | 71.441.639 | 12.265.665 | 59.175.974 | 0.714416 | 0.122657 | 0.714416 | 9.954609 | 8.656544 | 10.273935 |
9 | 1.000.000.000 | 711.894.230 | 108.127.172 | 603.767.058 | 0.711894 | 0.108127 | 0.711894 | 9.964696 | 8.815434 | 10.202908 |
10 | 10.000.000.000 | 7.099.087.275 | 966.664.776 | 6.132.422.499 | 0.709909 | 0.096666 | 0.709909 | 9.972110 | 8.940073 | 10.156935 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | |||
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 15 | 13 | 2 | 0.937500 | 0.812500 | 0.125000 | 1.666667 | 1.625000 | 2.000000 |
5 | 32 | 27 | 24 | 3 | 0.843750 | 0.750000 | 0.093750 | 1.800000 | 1.846154 | 1.500000 |
6 | 64 | 28 | 25 | 3 | 0.437500 | 0.390625 | 0.046875 | 1.037037 | 1.041667 | 1.000000 |
7 | 128 | 70 | 59 | 11 | 0.546875 | 0.460938 | 0.085938 | 2.500000 | 2.360000 | 3.666667 |
8 | 256 | 168 | 115 | 53 | 0.656250 | 0.449219 | 0.207031 | 2.400000 | 1.949153 | 4.818182 |
9 | 512 | 352 | 216 | 136 | 0.687500 | 0.421875 | 0.265625 | 2.095238 | 1.878261 | 2.566038 |
10 | 1.024 | 731 | 388 | 343 | 0.713867 | 0.378906 | 0.334961 | 2.076705 | 1.796296 | 2.522059 |
11 | 2.048 | 1.478 | 686 | 792 | 0.721680 | 0.334961 | 0.386719 | 2.021888 | 1.768041 | 2.309038 |
12 | 4.096 | 2.999 | 1.209 | 1.790 | 0.732178 | 0.295166 | 0.437012 | 2.029093 | 1.762391 | 2.260101 |
13 | 8.192 | 6.003 | 2.247 | 3.756 | 0.732788 | 0.274292 | 0.458496 | 2.001667 | 1.858561 | 2.098324 |
14 | 16.384 | 11.981 | 4.134 | 7.847 | 0.731262 | 0.252319 | 0.478943 | 1.995835 | 1.839786 | 2.089191 |
15 | 32.768 | 23.952 | 7.593 | 16.359 | 0.730957 | 0.231720 | 0.499237 | 1.999165 | 1.836720 | 2.084746 |
16 | 65.536 | 47.713 | 14.158 | 33.555 | 0.728043 | 0.216034 | 0.512009 | 1.992026 | 1.864612 | 2.051164 |
17 | 131.072 | 95.183 | 26.408 | 68.775 | 0.726189 | 0.201477 | 0.524712 | 1.994907 | 1.865235 | 2.049620 |
18 | 262.144 | 190.090 | 49.298 | 140.792 | 0.725136 | 0.188057 | 0.537079 | 1.997100 | 1.866783 | 2.047139 |
19 | 524.288 | 379.207 | 92.857 | 286.350 | 0.723280 | 0.177111 | 0.546169 | 1.994881 | 1.883586 | 2.033851 |
20 | 1.048.576 | 756.765 | 175.614 | 581.151 | 0.721707 | 0.167479 | 0.554229 | 1.995651 | 1.891231 | 2.029513 |
21 | 2.097.152 | 1.510.592 | 332.721 | 1.177.871 | 0.720306 | 0.158654 | 0.561653 | 1.996118 | 1.894615 | 2.026790 |
22 | 4.194.304 | 3.016.006 | 631.623 | 2.384.383 | 0.719072 | 0.150591 | 0.568481 | 1.996572 | 1.898356 | 2.024316 |
23 | 8.388.608 | 6.022.903 | 1.203.057 | 4.819.846 | 0.717986 | 0.143416 | 0.574570 | 1.996980 | 1.904707 | 2.021423 |
24 | 16.777.216 | 12.026.887 | 2.297.203 | 9.729.684 | 0.716858 | 0.136924 | 0.579934 | 1.996859 | 1.909472 | 2.018671 |
25 | 33.554.432 | 24.019.273 | 4.395.323 | 19.623.950 | 0.715830 | 0.130991 | 0.584839 | 1.997131 | 1.913337 | 2.016916 |
26 | 67.108.864 | 47.978.808 | 8.427.160 | 39.551.648 | 0.714940 | 0.125574 | 0.589365 | 1.997513 | 1.917302 | 2.015478 |
27 | 134.217.728 | 95.842.289 | 16.184.778 | 79.657.511 | 0.714081 | 0.120586 | 0.593495 | 1.997596 | 1.920550 | 2.014013 |
28 | 268.435.456 | 191.464.561 | 31.134.861 | 160.329.700 | 0.713261 | 0.115986 | 0.597275 | 1.997704 | 1.923712 | 2.012738 |
29 | 536.870.912 | 382.530.745 | 59.976.294 | 322.554.451 | 0.712519 | 0.111715 | 0.600805 | 1.997919 | 1.926339 | 2.011820 |
30 | 1.073.741.824 | 764.317.075 | 115.678.862 | 648.638.213 | 0.711826 | 0.107734 | 0.604091 | 1.998054 | 1.928743 | 2.010942 |
31 | 2.147.483.648 | 1.527.259.922 | 223.402.436 | 1.303.857.486 | 0.711186 | 0.104030 | 0.607156 | 1.998202 | 1.931229 | 2.010146 |
32 | 4.294.967.296 | 3.051.948.512 | 431.972.626 | 2.619.975.886 | 0.710587 | 0.100576 | 0.610011 | 1.998316 | 1.933608 | 2.009403 |
33 | 8.589.934.592 | 6.099.081.306 | 836.213.665 | 5.262.867.641 | 0.710027 | 0.097348 | 0.612678 | 1.998422 | 1.935802 | 2.008746 |
34 | 17.179.869.184 | 12.189.157.940 | 1.620.400.504 | 10.568.757.436 | 0.709502 | 0.094320 | 0.615183 | 1.998524 | 1.937783 | 2.008175 |
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 | 3 | 1 | 2 | 0 | 2 | 1 | 0 |
2 | 4 | 5 | 1 | 4 | 0 | 2 | 2 | 1 |
3 | 8 | 8 | 3 | 5 | 0 | 2 | 4 | 2 |
4 | 16 | 13 | 4 | 9 | 0 | 2 | 7 | 4 |
5 | 32 | 24 | 12 | 12 | 0 | 2 | 15 | 7 |
6 | 64 | 25 | 13 | 12 | 0 | 3 | 15 | 7 |
7 | 128 | 59 | 30 | 29 | 8 | 29 | 15 | 7 |
8 | 256 | 115 | 58 | 57 | 22 | 71 | 15 | 7 |
9 | 512 | 216 | 106 | 110 | 46 | 148 | 15 | 7 |
10 | 1.024 | 388 | 195 | 193 | 90 | 276 | 15 | 7 |
11 | 2.048 | 686 | 335 | 351 | 153 | 511 | 15 | 7 |
12 | 4.096 | 1.209 | 593 | 616 | 301 | 886 | 15 | 7 |
13 | 8.192 | 2.247 | 1.127 | 1.120 | 574 | 1.651 | 15 | 7 |
14 | 16.384 | 4.134 | 2.058 | 2.076 | 1.039 | 3.073 | 15 | 7 |
15 | 32.768 | 7.593 | 3.851 | 3.742 | 1.917 | 5.654 | 15 | 7 |
16 | 65.536 | 14.158 | 7.161 | 6.997 | 3.625 | 10.511 | 15 | 7 |
17 | 131.072 | 26.408 | 13.283 | 13.125 | 6.730 | 19.656 | 15 | 7 |
18 | 262.144 | 49.298 | 24.806 | 24.492 | 12.436 | 36.840 | 15 | 7 |
19 | 524.288 | 92.857 | 46.696 | 46.161 | 23.527 | 69.308 | 15 | 7 |
20 | 1.048.576 | 175.614 | 88.067 | 87.547 | 44.498 | 131.094 | 15 | 7 |
21 | 2.097.152 | 332.721 | 166.852 | 165.869 | 84.258 | 248.441 | 15 | 7 |
22 | 4.194.304 | 631.623 | 316.819 | 314.804 | 160.171 | 471.430 | 15 | 7 |
23 | 8.388.608 | 1.203.057 | 603.489 | 599.568 | 304.843 | 898.192 | 15 | 7 |
24 | 16.777.216 | 2.297.203 | 1.152.322 | 1.144.881 | 581.479 | 1.715.702 | 15 | 7 |
25 | 33.554.432 | 4.395.323 | 2.205.078 | 2.190.245 | 1.111.032 | 3.284.269 | 15 | 7 |
26 | 67.108.864 | 8.427.160 | 4.228.057 | 4.199.103 | 2.129.490 | 6.297.648 | 15 | 7 |
27 | 134.217.728 | 16.184.778 | 8.118.326 | 8.066.452 | 4.086.726 | 12.098.030 | 15 | 7 |
28 | 268.435.456 | 31.134.861 | 15.617.310 | 15.517.551 | 7.860.143 | 23.274.696 | 15 | 7 |
29 | 536.870.912 | 59.976.294 | 30.081.110 | 29.895.184 | 15.135.185 | 44.841.087 | 15 | 7 |
30 | 1.073.741.824 | 115.678.862 | 58.013.459 | 57.665.403 | 29.179.964 | 86.498.876 | 15 | 7 |
31 | 2.147.483.648 | 223.402.436 | 112.025.749 | 111.376.687 | 56.332.165 | 167.070.249 | 15 | 7 |
32 | 4.294.967.296 | 431.972.626 | 216.596.285 | 215.376.341 | 108.887.437 | 323.085.167 | 15 | 7 |
33 | 8.589.934.592 | 836.213.665 | 419.237.784 | 416.975.881 | 210.728.250 | 625.485.393 | 15 | 7 |
34 | 17.179.869.184 | 1.620.400.504 | 812.295.482 | 808.105.022 | 408.227.516 | 1.212.172.966 | 15 | 7 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
4 | 16 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
5 | 32 | 3 | 2 | 1 | 0 | 0 | 0 | 3 |
6 | 64 | 3 | 2 | 1 | 0 | 0 | 0 | 3 |
7 | 128 | 11 | 6 | 5 | 6 | 2 | 0 | 3 |
8 | 256 | 53 | 27 | 26 | 24 | 10 | 9 | 10 |
9 | 512 | 136 | 73 | 63 | 50 | 25 | 38 | 23 |
10 | 1.024 | 343 | 176 | 167 | 117 | 71 | 95 | 60 |
11 | 2.048 | 792 | 398 | 394 | 262 | 159 | 209 | 162 |
12 | 4.096 | 1.790 | 905 | 885 | 554 | 351 | 481 | 404 |
13 | 8.192 | 3.756 | 1.864 | 1.892 | 1.113 | 760 | 993 | 890 |
14 | 16.384 | 7.847 | 3.891 | 3.956 | 2.276 | 1.667 | 2.055 | 1.849 |
15 | 32.768 | 16.359 | 8.079 | 8.280 | 4.693 | 3.513 | 4.238 | 3.915 |
16 | 65.536 | 33.555 | 16.660 | 16.895 | 9.502 | 7.315 | 8.693 | 8.045 |
17 | 131.072 | 68.775 | 34.413 | 34.362 | 19.173 | 15.296 | 17.710 | 16.596 |
18 | 262.144 | 140.792 | 70.329 | 70.463 | 38.834 | 31.627 | 36.085 | 34.246 |
19 | 524.288 | 286.350 | 143.054 | 143.296 | 78.462 | 65.081 | 73.053 | 69.754 |
20 | 1.048.576 | 581.151 | 290.337 | 290.814 | 158.560 | 132.882 | 148.186 | 141.523 |
21 | 2.097.152 | 1.177.871 | 588.482 | 589.389 | 319.823 | 271.122 | 299.578 | 287.348 |
22 | 4.194.304 | 2.384.383 | 1.191.854 | 1.192.529 | 644.764 | 551.729 | 605.777 | 582.113 |
23 | 8.388.608 | 4.819.846 | 2.409.487 | 2.410.359 | 1.298.087 | 1.120.804 | 1.223.031 | 1.177.924 |
24 | 16.777.216 | 9.729.684 | 4.864.440 | 4.865.244 | 2.610.466 | 2.272.054 | 2.466.088 | 2.381.076 |
25 | 33.554.432 | 19.623.950 | 9.813.437 | 9.810.513 | 5.246.435 | 4.603.102 | 4.969.125 | 4.805.288 |
26 | 67.108.864 | 39.551.648 | 19.775.335 | 19.776.313 | 10.539.266 | 9.309.716 | 10.007.460 | 9.695.206 |
27 | 134.217.728 | 79.657.511 | 39.824.400 | 39.833.111 | 21.161.343 | 18.809.528 | 20.145.129 | 19.541.511 |
28 | 268.435.456 | 160.329.700 | 80.157.888 | 80.171.812 | 42.485.375 | 37.965.917 | 40.518.558 | 39.359.850 |
29 | 536.870.912 | 322.554.451 | 161.263.479 | 161.290.972 | 85.272.294 | 76.570.095 | 81.464.083 | 79.247.979 |
30 | 1.073.741.824 | 648.638.213 | 324.283.795 | 324.354.418 | 171.085.466 | 154.337.616 | 163.756.077 | 159.459.054 |
31 | 2.147.483.648 | 1.303.857.486 | 651.881.401 | 651.976.085 | 343.192.815 | 310.899.708 | 329.041.033 | 320.723.930 |
32 | 4.294.967.296 | 2.619.975.886 | 1.309.916.812 | 1.310.059.074 | 688.293.094 | 625.951.393 | 660.906.457 | 644.824.942 |
33 | 8.589.934.592 | 5.262.867.641 | 2.631.252.929 | 2.631.614.712 | 1.380.177.678 | 1.259.647.228 | 1.327.089.393 | 1.295.953.342 |
34 | 17.179.869.184 | 10.568.757.436 | 5.284.054.243 | 5.284.703.193 | 2.767.091.694 | 2.533.802.826 | 2.664.137.722 | 2.603.725.194 |