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+23
f(0)=23
f(1)=3
f(2)=1
f(3)=1
f(4)=13
f(5)=1
f(6)=59
f(7)=1
f(8)=29
f(9)=1
f(10)=41
f(11)=1
f(12)=167
f(13)=1
f(14)=73
f(15)=31
f(16)=1
f(17)=1
f(18)=347
f(19)=1
f(20)=47
f(21)=1
f(22)=1
f(23)=1
f(24)=599
f(25)=1
f(26)=233
f(27)=1
f(28)=269
f(29)=1
f(30)=71
f(31)=1
f(32)=349
f(33)=139
f(34)=131
f(35)=1
f(36)=1319
f(37)=1
f(38)=163
f(39)=193
f(40)=541
f(41)=1
f(42)=1787
f(43)=1
f(44)=653
f(45)=1
f(46)=1
f(47)=1
f(48)=179
f(49)=101
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=2939
f(55)=127
f(56)=1
f(57)=409
f(58)=1129
f(59)=1
f(60)=3623
f(61)=1
f(62)=1289
f(63)=499
f(64)=1373
f(65)=1
f(66)=151
f(67)=1
f(68)=1549
f(69)=1
f(70)=547
f(71)=211
f(72)=1
f(73)=223
f(74)=1
f(75)=353
f(76)=1933
f(77)=1
f(78)=197
f(79)=1
f(80)=2141
f(81)=823
f(82)=173
f(83)=1
f(84)=7079
f(85)=1
f(86)=2473
f(87)=1
f(88)=863
f(89)=331
f(90)=8123
f(91)=1
f(92)=1
f(93)=271
f(94)=2953
f(95)=1
f(96)=9239
f(97)=1
f(98)=3209
f(99)=307
b) Substitution of the polynom
The polynom f(x)=x^2+23 could be written as f(y)= y^2+23 with x=y+0
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+0
f'(x)>2x-1 with x > 5
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.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 56 | 22 | 34 | 0.560000 | 0.220000 | 0.560000 | 9.333333 | 7.333333 | 11.333333 |
3 | 1.000 | 617 | 162 | 455 | 0.617000 | 0.162000 | 0.617000 | 11.017858 | 7.363636 | 13.382353 |
4 | 10.000 | 6.414 | 1.100 | 5.314 | 0.641400 | 0.110000 | 0.641400 | 10.395462 | 6.790123 | 11.679121 |
5 | 100.000 | 65.297 | 8.516 | 56.781 | 0.652970 | 0.085160 | 0.652970 | 10.180387 | 7.741818 | 10.685171 |
6 | 1.000.000 | 660.434 | 68.153 | 592.281 | 0.660434 | 0.068153 | 0.660434 | 10.114308 | 8.002935 | 10.430972 |
7 | 10.000.000 | 6.652.372 | 570.360 | 6.082.012 | 0.665237 | 0.057036 | 0.665237 | 10.072728 | 8.368817 | 10.268795 |
8 | 100.000.000 | 66.872.063 | 4.913.430 | 61.958.633 | 0.668721 | 0.049134 | 0.668721 | 10.052364 | 8.614612 | 10.187193 |
9 | 1.000.000.000 | 671.424.332 | 43.127.669 | 628.296.663 | 0.671424 | 0.043128 | 0.671424 | 10.040431 | 8.777508 | 10.140583 |
10 | 10.000.000.000 | 6.735.904.494 | 384.271.119 | 6.351.633.375 | 0.673590 | 0.038427 | 0.673590 | 10.032261 | 8.910083 | 10.109291 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.500000 | 1.000000 | inf |
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 | 16 | 7 | 9 | 0.500000 | 0.218750 | 0.281250 | 1.777778 | 1.400000 | 2.250000 |
6 | 64 | 34 | 15 | 19 | 0.531250 | 0.234375 | 0.296875 | 2.125000 | 2.142857 | 2.111111 |
7 | 128 | 73 | 28 | 45 | 0.570312 | 0.218750 | 0.351562 | 2.147059 | 1.866667 | 2.368421 |
8 | 256 | 149 | 50 | 99 | 0.582031 | 0.195312 | 0.386719 | 2.041096 | 1.785714 | 2.200000 |
9 | 512 | 308 | 92 | 216 | 0.601562 | 0.179688 | 0.421875 | 2.067114 | 1.840000 | 2.181818 |
10 | 1.024 | 630 | 165 | 465 | 0.615234 | 0.161133 | 0.454102 | 2.045455 | 1.793478 | 2.152778 |
11 | 2.048 | 1.287 | 288 | 999 | 0.628418 | 0.140625 | 0.487793 | 2.042857 | 1.745455 | 2.148387 |
12 | 4.096 | 2.598 | 515 | 2.083 | 0.634277 | 0.125732 | 0.508545 | 2.018648 | 1.788194 | 2.085085 |
13 | 8.192 | 5.254 | 928 | 4.326 | 0.641357 | 0.113281 | 0.528076 | 2.022325 | 1.801942 | 2.076812 |
14 | 16.384 | 10.588 | 1.691 | 8.897 | 0.646240 | 0.103210 | 0.543030 | 2.015227 | 1.822198 | 2.056634 |
15 | 32.768 | 21.260 | 3.128 | 18.132 | 0.648804 | 0.095459 | 0.553345 | 2.007934 | 1.849793 | 2.037990 |
16 | 65.536 | 42.714 | 5.850 | 36.864 | 0.651764 | 0.089264 | 0.562500 | 2.009125 | 1.870205 | 2.033091 |
17 | 131.072 | 85.857 | 10.863 | 74.994 | 0.655037 | 0.082878 | 0.572159 | 2.010044 | 1.856923 | 2.034343 |
18 | 262.144 | 172.230 | 20.261 | 151.969 | 0.657005 | 0.077290 | 0.579716 | 2.006010 | 1.865139 | 2.026415 |
19 | 524.288 | 345.327 | 37.937 | 307.390 | 0.658659 | 0.072359 | 0.586300 | 2.005034 | 1.872415 | 2.022715 |
20 | 1.048.576 | 692.566 | 71.198 | 621.368 | 0.660482 | 0.067900 | 0.592583 | 2.005537 | 1.876743 | 2.021432 |
21 | 2.097.152 | 1.388.801 | 134.435 | 1.254.366 | 0.662232 | 0.064104 | 0.598128 | 2.005298 | 1.888185 | 2.018717 |
22 | 4.194.304 | 2.783.579 | 254.865 | 2.528.714 | 0.663657 | 0.060765 | 0.602892 | 2.004304 | 1.895823 | 2.015930 |
23 | 8.388.608 | 5.578.149 | 484.572 | 5.093.577 | 0.664967 | 0.057765 | 0.607202 | 2.003948 | 1.901289 | 2.014295 |
24 | 16.777.216 | 11.175.797 | 923.571 | 10.252.226 | 0.666129 | 0.055049 | 0.611080 | 2.003496 | 1.905952 | 2.012775 |
25 | 33.554.432 | 22.387.362 | 1.764.739 | 20.622.623 | 0.667195 | 0.052593 | 0.614602 | 2.003201 | 1.910778 | 2.011527 |
26 | 67.108.864 | 44.840.400 | 3.378.769 | 41.461.631 | 0.668174 | 0.050348 | 0.617826 | 2.002934 | 1.914600 | 2.010493 |
27 | 134.217.728 | 89.805.079 | 6.479.301 | 83.325.778 | 0.669100 | 0.048275 | 0.620825 | 2.002772 | 1.917651 | 2.009708 |
28 | 268.435.456 | 179.839.553 | 12.445.781 | 167.393.772 | 0.669955 | 0.046364 | 0.623590 | 2.002554 | 1.920852 | 2.008908 |
29 | 536.870.912 | 360.108.606 | 23.944.541 | 336.164.065 | 0.670755 | 0.044600 | 0.626154 | 2.002388 | 1.923908 | 2.008223 |
30 | 1.073.741.824 | 721.020.355 | 46.134.848 | 674.885.507 | 0.671503 | 0.042966 | 0.628536 | 2.002230 | 1.926738 | 2.007607 |
31 | 2.147.483.648 | 1.443.527.989 | 88.999.216 | 1.354.528.773 | 0.672195 | 0.041443 | 0.630752 | 2.002063 | 1.929110 | 2.007050 |
32 | 4.294.967.296 | 2.889.874.837 | 171.906.851 | 2.717.967.986 | 0.672851 | 0.040025 | 0.632826 | 2.001953 | 1.931555 | 2.006578 |
33 | 8.589.934.592 | 5.784.984.861 | 332.469.526 | 5.452.515.335 | 0.673461 | 0.038705 | 0.634756 | 2.001812 | 1.934010 | 2.006100 |
34 | 17.179.869.184 | 11.579.861.632 | 643.691.617 | 10.936.170.015 | 0.674037 | 0.037468 | 0.636569 | 2.001710 | 1.936092 | 2.005711 |
35 | 34.359.738.368 | 23.178.413.014 | 1.247.566.330 | 21.930.846.684 | 0.674581 | 0.036309 | 0.638272 | 2.001614 | 1.938143 | 2.005350 |
36 | 68.719.476.736 | 46.392.174.744 | 2.420.274.299 | 43.971.900.445 | 0.675095 | 0.035220 | 0.639875 | 2.001525 | 1.939996 | 2.005025 |
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 | 0 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 0 | 2 | 0 | 2 | 0 | 1 |
4 | 16 | 5 | 1 | 3 | 0 | 2 | 0 | 3 |
5 | 32 | 7 | 1 | 5 | 0 | 3 | 0 | 4 |
6 | 64 | 15 | 5 | 9 | 2 | 7 | 0 | 6 |
7 | 128 | 28 | 10 | 17 | 4 | 11 | 1 | 12 |
8 | 256 | 50 | 17 | 32 | 7 | 19 | 3 | 21 |
9 | 512 | 92 | 29 | 62 | 9 | 37 | 11 | 35 |
10 | 1.024 | 165 | 54 | 110 | 19 | 63 | 22 | 61 |
11 | 2.048 | 288 | 97 | 190 | 38 | 109 | 38 | 103 |
12 | 4.096 | 515 | 176 | 338 | 68 | 188 | 70 | 189 |
13 | 8.192 | 928 | 329 | 598 | 116 | 348 | 125 | 339 |
14 | 16.384 | 1.691 | 616 | 1.074 | 227 | 628 | 226 | 610 |
15 | 32.768 | 3.128 | 1.137 | 1.990 | 421 | 1.175 | 410 | 1.122 |
16 | 65.536 | 5.850 | 2.095 | 3.754 | 782 | 2.193 | 767 | 2.108 |
17 | 131.072 | 10.863 | 3.856 | 7.006 | 1.429 | 4.034 | 1.418 | 3.982 |
18 | 262.144 | 20.261 | 7.133 | 13.127 | 2.697 | 7.483 | 2.654 | 7.427 |
19 | 524.288 | 37.937 | 13.227 | 24.709 | 5.013 | 14.068 | 4.923 | 13.933 |
20 | 1.048.576 | 71.198 | 24.889 | 46.308 | 9.433 | 26.265 | 9.228 | 26.272 |
21 | 2.097.152 | 134.435 | 46.863 | 87.571 | 17.733 | 49.598 | 17.569 | 49.535 |
22 | 4.194.304 | 254.865 | 88.707 | 166.157 | 33.455 | 94.025 | 33.355 | 94.030 |
23 | 8.388.608 | 484.572 | 168.111 | 316.460 | 63.633 | 178.921 | 63.410 | 178.608 |
24 | 16.777.216 | 923.571 | 319.745 | 603.825 | 120.770 | 341.217 | 120.813 | 340.771 |
25 | 33.554.432 | 1.764.739 | 610.001 | 1.154.737 | 230.555 | 652.156 | 230.597 | 651.431 |
26 | 67.108.864 | 3.378.769 | 1.166.405 | 2.212.363 | 440.615 | 1.249.284 | 440.654 | 1.248.216 |
27 | 134.217.728 | 6.479.301 | 2.233.208 | 4.246.092 | 844.148 | 2.396.721 | 843.010 | 2.395.422 |
28 | 268.435.456 | 12.445.781 | 4.283.565 | 8.162.215 | 1.618.260 | 4.607.130 | 1.616.451 | 4.603.940 |
29 | 536.870.912 | 23.944.541 | 8.230.745 | 15.713.795 | 3.107.771 | 8.867.426 | 3.107.059 | 8.862.285 |
30 | 1.073.741.824 | 46.134.848 | 15.841.770 | 30.293.077 | 5.978.866 | 17.088.757 | 5.979.742 | 17.087.483 |
31 | 2.147.483.648 | 88.999.216 | 30.530.718 | 58.468.497 | 11.522.456 | 32.979.867 | 11.521.622 | 32.975.271 |
32 | 4.294.967.296 | 171.906.851 | 58.917.671 | 112.989.179 | 22.229.301 | 63.728.241 | 22.227.481 | 63.721.828 |
33 | 8.589.934.592 | 332.469.526 | 113.852.391 | 218.617.134 | 42.942.835 | 123.299.958 | 42.937.782 | 123.288.951 |
34 | 17.179.869.184 | 643.691.617 | 220.237.653 | 423.453.963 | 83.042.726 | 238.808.646 | 83.047.348 | 238.792.897 |
35 | 34.359.738.368 | 1.247.566.330 | 426.513.313 | 821.053.016 | 160.803.594 | 463.000.871 | 160.793.137 | 462.968.728 |
36 | 68.719.476.736 | 2.420.274.299 | 826.814.376 | 1.593.459.922 | 311.674.809 | 898.490.969 | 311.658.332 | 898.450.189 |
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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
4 | 16 | 4 | 2 | 2 | 2 | 0 | 2 | 0 |
5 | 32 | 9 | 3 | 6 | 3 | 0 | 4 | 2 |
6 | 64 | 19 | 7 | 12 | 5 | 3 | 8 | 3 |
7 | 128 | 45 | 20 | 25 | 13 | 7 | 16 | 9 |
8 | 256 | 99 | 47 | 52 | 26 | 20 | 35 | 18 |
9 | 512 | 216 | 106 | 110 | 54 | 44 | 72 | 46 |
10 | 1.024 | 465 | 231 | 234 | 129 | 105 | 135 | 96 |
11 | 2.048 | 999 | 510 | 489 | 276 | 221 | 277 | 225 |
12 | 4.096 | 2.083 | 1.065 | 1.018 | 574 | 463 | 586 | 460 |
13 | 8.192 | 4.326 | 2.179 | 2.147 | 1.174 | 967 | 1.205 | 980 |
14 | 16.384 | 8.897 | 4.442 | 4.455 | 2.427 | 2.007 | 2.477 | 1.986 |
15 | 32.768 | 18.132 | 9.017 | 9.115 | 4.899 | 4.181 | 4.938 | 4.114 |
16 | 65.536 | 36.864 | 18.419 | 18.445 | 9.925 | 8.588 | 9.880 | 8.471 |
17 | 131.072 | 74.994 | 37.563 | 37.431 | 19.964 | 17.413 | 20.211 | 17.406 |
18 | 262.144 | 151.969 | 76.112 | 75.857 | 40.368 | 35.592 | 40.613 | 35.396 |
19 | 524.288 | 307.390 | 153.906 | 153.484 | 81.590 | 72.179 | 81.491 | 72.130 |
20 | 1.048.576 | 621.368 | 311.380 | 309.988 | 164.213 | 146.646 | 163.922 | 146.587 |
21 | 2.097.152 | 1.254.366 | 628.164 | 626.202 | 329.826 | 297.158 | 330.061 | 297.321 |
22 | 4.194.304 | 2.528.714 | 1.266.041 | 1.262.673 | 663.186 | 600.804 | 663.536 | 601.188 |
23 | 8.388.608 | 5.093.577 | 2.551.382 | 2.542.195 | 1.332.560 | 1.214.116 | 1.332.685 | 1.214.216 |
24 | 16.777.216 | 10.252.226 | 5.133.914 | 5.118.312 | 2.675.567 | 2.451.225 | 2.675.519 | 2.449.915 |
25 | 33.554.432 | 20.622.623 | 10.323.947 | 10.298.676 | 5.371.864 | 4.940.942 | 5.370.635 | 4.939.182 |
26 | 67.108.864 | 41.461.631 | 20.754.210 | 20.707.421 | 10.781.494 | 9.954.618 | 10.777.210 | 9.948.309 |
27 | 134.217.728 | 83.325.778 | 41.705.580 | 41.620.198 | 21.626.694 | 20.038.053 | 21.626.366 | 20.034.665 |
28 | 268.435.456 | 167.393.772 | 83.781.747 | 83.612.025 | 43.374.311 | 40.319.471 | 43.375.864 | 40.324.126 |
29 | 536.870.912 | 336.164.065 | 168.230.372 | 167.933.693 | 86.979.281 | 81.095.684 | 86.985.307 | 81.103.793 |
30 | 1.073.741.824 | 674.885.507 | 337.726.076 | 337.159.431 | 174.372.235 | 163.037.197 | 174.407.119 | 163.068.956 |
31 | 2.147.483.648 | 1.354.528.773 | 677.842.563 | 676.686.210 | 349.565.202 | 327.668.831 | 349.597.453 | 327.697.287 |
32 | 4.294.967.296 | 2.717.967.986 | 1.360.087.891 | 1.357.880.095 | 700.646.384 | 658.331.897 | 700.637.821 | 658.351.884 |
33 | 8.589.934.592 | 5.452.515.335 | 2.728.391.470 | 2.724.123.865 | 1.404.090.427 | 1.322.167.316 | 1.404.058.857 | 1.322.198.735 |
34 | 17.179.869.184 | 10.936.170.015 | 5.472.159.021 | 5.464.010.994 | 2.813.391.569 | 2.654.710.911 | 2.813.360.278 | 2.654.707.257 |
35 | 34.359.738.368 | 21.930.846.684 | 10.973.367.454 | 10.957.479.230 | 5.636.610.945 | 5.328.808.428 | 5.636.593.112 | 5.328.834.199 |
36 | 68.719.476.736 | 43.971.900.445 | 22.001.429.477 | 21.970.470.968 | 11.291.635.379 | 10.694.244.491 | 11.291.669.085 | 10.694.351.490 |