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+43x-3
f(0)=3
f(1)=41
f(2)=29
f(3)=5
f(4)=37
f(5)=79
f(6)=97
f(7)=347
f(8)=1
f(9)=31
f(10)=17
f(11)=197
f(12)=73
f(13)=1
f(14)=53
f(15)=1
f(16)=941
f(17)=113
f(18)=1
f(19)=47
f(20)=419
f(21)=149
f(22)=1427
f(23)=101
f(24)=107
f(25)=1697
f(26)=199
f(27)=1
f(28)=397
f(29)=139
f(30)=1
f(31)=1
f(32)=1
f(33)=167
f(34)=523
f(35)=1
f(36)=947
f(37)=2957
f(38)=1
f(39)=71
f(40)=1
f(41)=1
f(42)=1
f(43)=739
f(44)=1
f(45)=1319
f(46)=4091
f(47)=1409
f(48)=1
f(49)=1
f(50)=1549
f(51)=1597
f(52)=4937
f(53)=1
f(54)=349
f(55)=5387
f(56)=1847
f(57)=211
f(58)=1171
f(59)=401
f(60)=1
f(61)=373
f(62)=241
f(63)=89
f(64)=1
f(65)=2339
f(66)=1
f(67)=1
f(68)=503
f(69)=103
f(70)=7907
f(71)=1
f(72)=1
f(73)=1693
f(74)=577
f(75)=983
f(76)=9041
f(77)=3079
f(78)=1
f(79)=1
f(80)=1093
f(81)=3347
f(82)=10247
f(83)=1
f(84)=1
f(85)=1
f(86)=3697
f(87)=3769
f(88)=461
f(89)=1
f(90)=3989
f(91)=1
f(92)=4139
f(93)=281
f(94)=1
f(95)=257
f(96)=4447
f(97)=13577
f(98)=307
f(99)=937
b) Substitution of the polynom
The polynom f(x)=x^2+43x-3 could be written as f(y)= y^2-465.25 with x=y-21.5
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+21.5
f'(x)>2x+42
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 | 8 | 3 | 5 | 0.800000 | 0.300000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 14 | 50 | 0.640000 | 0.140000 | 0.500000 | 8.000000 | 4.666667 | 10.000000 |
3 | 1.000 | 644 | 78 | 566 | 0.644000 | 0.078000 | 0.566000 | 10.062500 | 5.571429 | 11.320000 |
4 | 10.000 | 6.641 | 581 | 6.060 | 0.664100 | 0.058100 | 0.606000 | 10.312112 | 7.448718 | 10.706714 |
5 | 100.000 | 66.958 | 4.577 | 62.381 | 0.669580 | 0.045770 | 0.623810 | 10.082518 | 7.877797 | 10.293895 |
6 | 1.000.000 | 674.165 | 37.183 | 636.982 | 0.674165 | 0.037183 | 0.636982 | 10.068476 | 8.123880 | 10.211154 |
7 | 10.000.000 | 6.768.472 | 314.949 | 6.453.523 | 0.676847 | 0.031495 | 0.645352 | 10.039785 | 8.470242 | 10.131406 |
8 | 100.000.000 | 67.881.515 | 2.727.137 | 65.154.378 | 0.678815 | 0.027271 | 0.651544 | 10.029075 | 8.658979 | 10.095940 |
9 | 1.000.000.000 | 680.337.771 | 24.061.390 | 656.276.381 | 0.680338 | 0.024061 | 0.656276 | 10.022431 | 8.822948 | 10.072637 |
10 | 10.000.000.000 | 6.815.864.031 | 215.343.865 | 6.600.520.166 | 0.681586 | 0.021534 | 0.660052 | 10.018353 | 8.949769 | 10.057531 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
4 | 16 | 12 | 4 | 8 | 0.750000 | 0.250000 | 0.500000 | 1.714286 | 1.333333 | 2.000000 |
5 | 32 | 23 | 6 | 17 | 0.718750 | 0.187500 | 0.531250 | 1.916667 | 1.500000 | 2.125000 |
6 | 64 | 42 | 10 | 32 | 0.656250 | 0.156250 | 0.500000 | 1.826087 | 1.666667 | 1.882353 |
7 | 128 | 81 | 17 | 64 | 0.632812 | 0.132812 | 0.500000 | 1.928571 | 1.700000 | 2.000000 |
8 | 256 | 164 | 24 | 140 | 0.640625 | 0.093750 | 0.546875 | 2.024691 | 1.411765 | 2.187500 |
9 | 512 | 326 | 39 | 287 | 0.636719 | 0.076172 | 0.560547 | 1.987805 | 1.625000 | 2.050000 |
10 | 1.024 | 659 | 78 | 581 | 0.643555 | 0.076172 | 0.567383 | 2.021472 | 2.000000 | 2.024390 |
11 | 2.048 | 1.330 | 142 | 1.188 | 0.649414 | 0.069336 | 0.580078 | 2.018209 | 1.820513 | 2.044750 |
12 | 4.096 | 2.693 | 260 | 2.433 | 0.657471 | 0.063477 | 0.593994 | 2.024812 | 1.830986 | 2.047980 |
13 | 8.192 | 5.438 | 487 | 4.951 | 0.663818 | 0.059448 | 0.604370 | 2.019309 | 1.873077 | 2.034936 |
14 | 16.384 | 10.915 | 905 | 10.010 | 0.666199 | 0.055237 | 0.610962 | 2.007172 | 1.858316 | 2.021814 |
15 | 32.768 | 21.893 | 1.682 | 20.211 | 0.668121 | 0.051331 | 0.616791 | 2.005772 | 1.858564 | 2.019081 |
16 | 65.536 | 43.872 | 3.155 | 40.717 | 0.669434 | 0.048141 | 0.621292 | 2.003928 | 1.875743 | 2.014596 |
17 | 131.072 | 87.967 | 5.838 | 82.129 | 0.671135 | 0.044540 | 0.626595 | 2.005083 | 1.850396 | 2.017069 |
18 | 262.144 | 176.167 | 10.891 | 165.276 | 0.672024 | 0.041546 | 0.630478 | 2.002649 | 1.865536 | 2.012395 |
19 | 524.288 | 353.033 | 20.587 | 332.446 | 0.673357 | 0.039267 | 0.634090 | 2.003968 | 1.890276 | 2.011460 |
20 | 1.048.576 | 706.841 | 38.897 | 667.944 | 0.674096 | 0.037095 | 0.637001 | 2.002195 | 1.889396 | 2.009181 |
21 | 2.097.152 | 1.415.851 | 73.698 | 1.342.153 | 0.675130 | 0.035142 | 0.639988 | 2.003069 | 1.894696 | 2.009380 |
22 | 4.194.304 | 2.834.838 | 140.270 | 2.694.568 | 0.675878 | 0.033443 | 0.642435 | 2.002215 | 1.903308 | 2.007646 |
23 | 8.388.608 | 5.676.607 | 267.241 | 5.409.366 | 0.676704 | 0.031858 | 0.644847 | 2.002445 | 1.905190 | 2.007508 |
24 | 16.777.216 | 11.363.784 | 510.150 | 10.853.634 | 0.677334 | 0.030407 | 0.646927 | 2.001862 | 1.908951 | 2.006452 |
25 | 33.554.432 | 22.748.567 | 976.412 | 21.772.155 | 0.677960 | 0.029099 | 0.648861 | 2.001848 | 1.913970 | 2.005978 |
26 | 67.108.864 | 45.534.486 | 1.873.400 | 43.661.086 | 0.678517 | 0.027916 | 0.650601 | 2.001642 | 1.918657 | 2.005363 |
27 | 134.217.728 | 91.137.824 | 3.598.296 | 87.539.528 | 0.679030 | 0.026809 | 0.652220 | 2.001512 | 1.920730 | 2.004978 |
28 | 268.435.456 | 182.405.809 | 6.925.377 | 175.480.432 | 0.679515 | 0.025799 | 0.653716 | 2.001428 | 1.924627 | 2.004585 |
29 | 536.870.912 | 365.048.751 | 13.341.526 | 351.707.225 | 0.679956 | 0.024851 | 0.655106 | 2.001300 | 1.926469 | 2.004253 |
30 | 1.073.741.824 | 730.556.214 | 25.741.333 | 704.814.881 | 0.680384 | 0.023973 | 0.656410 | 2.001257 | 1.929414 | 2.003982 |
31 | 2.147.483.648 | 1.461.974.355 | 49.730.470 | 1.412.243.885 | 0.680785 | 0.023158 | 0.657627 | 2.001180 | 1.931931 | 2.003709 |
32 | 4.294.967.296 | 2.925.550.715 | 96.195.922 | 2.829.354.793 | 0.681158 | 0.022397 | 0.658760 | 2.001096 | 1.934346 | 2.003446 |
33 | 8.589.934.592 | 5.854.138.469 | 186.270.692 | 5.667.867.777 | 0.681511 | 0.021685 | 0.659827 | 2.001038 | 1.936368 | 2.003237 |
34 | 17.179.869.184 | 11.713.986.451 | 361.046.148 | 11.352.940.303 | 0.681844 | 0.021016 | 0.660828 | 2.000975 | 1.938287 | 2.003036 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 3 | 0 | 2 | 1 | 2 | 0 | 0 |
4 | 16 | 4 | 0 | 3 | 1 | 2 | 1 | 0 |
5 | 32 | 6 | 0 | 5 | 2 | 3 | 1 | 0 |
6 | 64 | 10 | 0 | 9 | 3 | 5 | 2 | 0 |
7 | 128 | 17 | 0 | 16 | 6 | 7 | 2 | 2 |
8 | 256 | 24 | 0 | 23 | 7 | 9 | 4 | 4 |
9 | 512 | 39 | 0 | 38 | 7 | 15 | 9 | 8 |
10 | 1.024 | 78 | 0 | 76 | 17 | 22 | 18 | 21 |
11 | 2.048 | 142 | 0 | 140 | 35 | 35 | 36 | 36 |
12 | 4.096 | 260 | 0 | 258 | 63 | 64 | 72 | 61 |
13 | 8.192 | 487 | 0 | 485 | 112 | 113 | 136 | 126 |
14 | 16.384 | 905 | 0 | 903 | 218 | 211 | 240 | 236 |
15 | 32.768 | 1.682 | 0 | 1.680 | 402 | 419 | 439 | 422 |
16 | 65.536 | 3.155 | 0 | 3.153 | 770 | 797 | 808 | 780 |
17 | 131.072 | 5.838 | 0 | 5.836 | 1.453 | 1.468 | 1.466 | 1.451 |
18 | 262.144 | 10.891 | 0 | 10.889 | 2.711 | 2.727 | 2.722 | 2.731 |
19 | 524.288 | 20.587 | 0 | 20.585 | 5.154 | 5.127 | 5.135 | 5.171 |
20 | 1.048.576 | 38.897 | 0 | 38.895 | 9.711 | 9.753 | 9.736 | 9.697 |
21 | 2.097.152 | 73.698 | 0 | 73.696 | 18.403 | 18.581 | 18.403 | 18.311 |
22 | 4.194.304 | 140.270 | 0 | 140.268 | 35.036 | 35.358 | 34.945 | 34.931 |
23 | 8.388.608 | 267.241 | 0 | 267.239 | 66.671 | 67.328 | 66.589 | 66.653 |
24 | 16.777.216 | 510.150 | 0 | 510.148 | 127.305 | 127.920 | 127.318 | 127.607 |
25 | 33.554.432 | 976.412 | 0 | 976.410 | 244.006 | 244.760 | 243.673 | 243.973 |
26 | 67.108.864 | 1.873.400 | 0 | 1.873.398 | 468.354 | 468.792 | 468.058 | 468.196 |
27 | 134.217.728 | 3.598.296 | 0 | 3.598.294 | 899.302 | 900.313 | 898.889 | 899.792 |
28 | 268.435.456 | 6.925.377 | 0 | 6.925.375 | 1.730.541 | 1.731.467 | 1.732.305 | 1.731.064 |
29 | 536.870.912 | 13.341.526 | 0 | 13.341.524 | 3.333.865 | 3.335.663 | 3.336.822 | 3.335.176 |
30 | 1.073.741.824 | 25.741.333 | 0 | 25.741.331 | 6.432.765 | 6.436.182 | 6.435.966 | 6.436.420 |
31 | 2.147.483.648 | 49.730.470 | 0 | 49.730.468 | 12.433.416 | 12.433.413 | 12.431.353 | 12.432.288 |
32 | 4.294.967.296 | 96.195.922 | 0 | 96.195.920 | 24.048.988 | 24.046.274 | 24.049.016 | 24.051.644 |
33 | 8.589.934.592 | 186.270.692 | 0 | 186.270.690 | 46.569.355 | 46.562.687 | 46.571.419 | 46.567.231 |
34 | 17.179.869.184 | 361.046.148 | 0 | 361.046.146 | 90.261.460 | 90.259.490 | 90.261.893 | 90.263.305 |
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 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 4 | 3 | 1 | 1 | 0 | 2 | 1 |
4 | 16 | 8 | 5 | 3 | 2 | 0 | 4 | 2 |
5 | 32 | 17 | 8 | 9 | 3 | 3 | 7 | 4 |
6 | 64 | 32 | 17 | 15 | 6 | 8 | 11 | 7 |
7 | 128 | 64 | 34 | 30 | 15 | 17 | 18 | 14 |
8 | 256 | 140 | 82 | 58 | 34 | 41 | 31 | 34 |
9 | 512 | 287 | 164 | 123 | 73 | 77 | 69 | 68 |
10 | 1.024 | 581 | 316 | 265 | 150 | 141 | 149 | 141 |
11 | 2.048 | 1.188 | 635 | 553 | 301 | 303 | 294 | 290 |
12 | 4.096 | 2.433 | 1.298 | 1.135 | 605 | 602 | 595 | 631 |
13 | 8.192 | 4.951 | 2.593 | 2.358 | 1.221 | 1.244 | 1.242 | 1.244 |
14 | 16.384 | 10.010 | 5.274 | 4.736 | 2.482 | 2.471 | 2.531 | 2.526 |
15 | 32.768 | 20.211 | 10.535 | 9.676 | 4.984 | 5.078 | 5.084 | 5.065 |
16 | 65.536 | 40.717 | 21.201 | 19.516 | 10.073 | 10.239 | 10.188 | 10.217 |
17 | 131.072 | 82.129 | 42.728 | 39.401 | 20.434 | 20.567 | 20.532 | 20.596 |
18 | 262.144 | 165.276 | 85.699 | 79.577 | 41.121 | 41.462 | 41.334 | 41.359 |
19 | 524.288 | 332.446 | 171.847 | 160.599 | 82.717 | 83.516 | 83.092 | 83.121 |
20 | 1.048.576 | 667.944 | 344.404 | 323.540 | 166.792 | 167.184 | 166.844 | 167.124 |
21 | 2.097.152 | 1.342.153 | 691.385 | 650.768 | 335.176 | 335.783 | 335.237 | 335.957 |
22 | 4.194.304 | 2.694.568 | 1.386.015 | 1.308.553 | 672.585 | 673.947 | 673.873 | 674.163 |
23 | 8.388.608 | 5.409.366 | 2.779.892 | 2.629.474 | 1.351.330 | 1.353.180 | 1.351.979 | 1.352.877 |
24 | 16.777.216 | 10.853.634 | 5.571.217 | 5.282.417 | 2.714.047 | 2.713.729 | 2.711.977 | 2.713.881 |
25 | 33.554.432 | 21.772.155 | 11.159.745 | 10.612.410 | 5.446.807 | 5.442.560 | 5.440.098 | 5.442.690 |
26 | 67.108.864 | 43.661.086 | 22.357.264 | 21.303.822 | 10.916.980 | 10.915.629 | 10.912.663 | 10.915.814 |
27 | 134.217.728 | 87.539.528 | 44.778.948 | 42.760.580 | 21.891.554 | 21.885.457 | 21.880.487 | 21.882.030 |
28 | 268.435.456 | 175.480.432 | 89.683.324 | 85.797.108 | 43.881.450 | 43.863.475 | 43.865.655 | 43.869.852 |
29 | 536.870.912 | 351.707.225 | 179.601.689 | 172.105.536 | 87.936.111 | 87.923.659 | 87.921.267 | 87.926.188 |
30 | 1.073.741.824 | 704.814.881 | 359.639.476 | 345.175.405 | 176.207.926 | 176.215.902 | 176.191.993 | 176.199.060 |
31 | 2.147.483.648 | 1.412.243.885 | 720.055.518 | 692.188.367 | 353.060.112 | 353.079.010 | 353.048.636 | 353.056.127 |
32 | 4.294.967.296 | 2.829.354.793 | 1.441.586.631 | 1.387.768.162 | 707.330.283 | 707.334.383 | 707.354.981 | 707.335.146 |
33 | 8.589.934.592 | 5.667.867.777 | 2.885.985.277 | 2.781.882.500 | 1.416.947.528 | 1.416.988.341 | 1.416.955.850 | 1.416.976.058 |
34 | 17.179.869.184 | 11.352.940.303 | 5.777.311.024 | 5.575.629.279 | 2.838.245.928 | 2.838.169.993 | 2.838.278.060 | 2.838.246.322 |