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+32x-127
f(0)=127
f(1)=47
f(2)=59
f(3)=11
f(4)=17
f(5)=29
f(6)=101
f(7)=73
f(8)=193
f(9)=1
f(10)=293
f(11)=173
f(12)=401
f(13)=229
f(14)=1
f(15)=1
f(16)=641
f(17)=353
f(18)=773
f(19)=421
f(20)=83
f(21)=1
f(22)=1061
f(23)=569
f(24)=1217
f(25)=1
f(26)=1381
f(27)=733
f(28)=1553
f(29)=821
f(30)=1733
f(31)=1
f(32)=113
f(33)=1009
f(34)=1
f(35)=1109
f(36)=211
f(37)=1213
f(38)=149
f(39)=1321
f(40)=2753
f(41)=1433
f(42)=271
f(43)=1549
f(44)=3217
f(45)=1669
f(46)=3461
f(47)=163
f(48)=79
f(49)=1
f(50)=137
f(51)=2053
f(52)=4241
f(53)=199
f(54)=4517
f(55)=1
f(56)=4801
f(57)=2473
f(58)=463
f(59)=2621
f(60)=5393
f(61)=1
f(62)=5701
f(63)=1
f(64)=547
f(65)=3089
f(66)=373
f(67)=3253
f(68)=6673
f(69)=311
f(70)=7013
f(71)=3593
f(72)=433
f(73)=3769
f(74)=7717
f(75)=359
f(76)=8081
f(77)=4133
f(78)=107
f(79)=1
f(80)=1
f(81)=4513
f(82)=9221
f(83)=277
f(84)=1
f(85)=4909
f(86)=911
f(87)=5113
f(88)=10433
f(89)=313
f(90)=10853
f(91)=503
f(92)=389
f(93)=5749
f(94)=11717
f(95)=1
f(96)=12161
f(97)=563
f(98)=12613
f(99)=6421
b) Substitution of the polynom
The polynom f(x)=x^2+32x-127 could be written as f(y)= y^2-383 with x=y-16
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+16
f'(x)>2x+31
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 | 10 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 84 | 63 | 21 | 0.840000 | 0.630000 | 0.210000 | 8.400000 | 6.300000 | inf |
3 | 1.000 | 766 | 388 | 378 | 0.766000 | 0.388000 | 0.378000 | 9.119047 | 6.158730 | 18.000000 |
4 | 10.000 | 7.435 | 2.827 | 4.608 | 0.743500 | 0.282700 | 0.460800 | 9.706266 | 7.286082 | 12.190476 |
5 | 100.000 | 73.354 | 21.683 | 51.671 | 0.733540 | 0.216830 | 0.516710 | 9.866039 | 7.669968 | 11.213325 |
6 | 1.000.000 | 726.678 | 176.498 | 550.180 | 0.726678 | 0.176498 | 0.550180 | 9.906454 | 8.139925 | 10.647752 |
7 | 10.000.000 | 7.217.562 | 1.491.674 | 5.725.888 | 0.721756 | 0.149167 | 0.572589 | 9.932270 | 8.451507 | 10.407299 |
8 | 100.000.000 | 71.793.130 | 12.909.530 | 58.883.600 | 0.717931 | 0.129095 | 0.588836 | 9.947005 | 8.654391 | 10.283750 |
9 | 1.000.000.000 | 715.005.975 | 113.781.837 | 601.224.138 | 0.715006 | 0.113782 | 0.601224 | 9.959253 | 8.813787 | 10.210383 |
10 | 10.000.000.000 | 7.126.971.478 | 1.017.343.654 | 6.109.627.824 | 0.712697 | 0.101734 | 0.610963 | 9.967710 | 8.941178 | 10.161981 |
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 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 14 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.555556 | 1.555556 | -nan |
5 | 32 | 27 | 25 | 2 | 0.843750 | 0.781250 | 0.062500 | 1.928571 | 1.785714 | inf |
6 | 64 | 53 | 43 | 10 | 0.828125 | 0.671875 | 0.156250 | 1.962963 | 1.720000 | 5.000000 |
7 | 128 | 105 | 75 | 30 | 0.820312 | 0.585938 | 0.234375 | 1.981132 | 1.744186 | 3.000000 |
8 | 256 | 200 | 133 | 67 | 0.781250 | 0.519531 | 0.261719 | 1.904762 | 1.773333 | 2.233333 |
9 | 512 | 393 | 229 | 164 | 0.767578 | 0.447266 | 0.320312 | 1.965000 | 1.721804 | 2.447761 |
10 | 1.024 | 782 | 394 | 388 | 0.763672 | 0.384766 | 0.378906 | 1.989822 | 1.720524 | 2.365854 |
11 | 2.048 | 1.556 | 732 | 824 | 0.759766 | 0.357422 | 0.402344 | 1.989770 | 1.857868 | 2.123711 |
12 | 4.096 | 3.079 | 1.305 | 1.774 | 0.751709 | 0.318604 | 0.433105 | 1.978792 | 1.782787 | 2.152913 |
13 | 8.192 | 6.090 | 2.370 | 3.720 | 0.743408 | 0.289307 | 0.454102 | 1.977915 | 1.816092 | 2.096956 |
14 | 16.384 | 12.130 | 4.326 | 7.804 | 0.740356 | 0.264038 | 0.476318 | 1.991790 | 1.825316 | 2.097849 |
15 | 32.768 | 24.128 | 8.022 | 16.106 | 0.736328 | 0.244812 | 0.491516 | 1.989118 | 1.854369 | 2.063813 |
16 | 65.536 | 48.170 | 14.768 | 33.402 | 0.735016 | 0.225342 | 0.509674 | 1.996436 | 1.840937 | 2.073885 |
17 | 131.072 | 95.972 | 27.710 | 68.262 | 0.732208 | 0.211411 | 0.520798 | 1.992360 | 1.876354 | 2.043650 |
18 | 262.144 | 191.384 | 51.915 | 139.469 | 0.730072 | 0.198040 | 0.532032 | 1.994165 | 1.873511 | 2.043143 |
19 | 524.288 | 381.809 | 97.702 | 284.107 | 0.728243 | 0.186352 | 0.541891 | 1.994989 | 1.881961 | 2.037062 |
20 | 1.048.576 | 761.898 | 184.477 | 577.421 | 0.726603 | 0.175931 | 0.550672 | 1.995495 | 1.888160 | 2.032407 |
21 | 2.097.152 | 1.520.342 | 349.821 | 1.170.521 | 0.724956 | 0.166808 | 0.558148 | 1.995467 | 1.896285 | 2.027153 |
22 | 4.194.304 | 3.034.563 | 664.294 | 2.370.269 | 0.723496 | 0.158380 | 0.565116 | 1.995974 | 1.898954 | 2.024969 |
23 | 8.388.608 | 6.057.442 | 1.266.068 | 4.791.374 | 0.722103 | 0.150927 | 0.571176 | 1.996150 | 1.905885 | 2.021447 |
24 | 16.777.216 | 12.091.664 | 2.417.978 | 9.673.686 | 0.720719 | 0.144123 | 0.576597 | 1.996167 | 1.909833 | 2.018980 |
25 | 33.554.432 | 24.145.996 | 4.626.571 | 19.519.425 | 0.719607 | 0.137883 | 0.581724 | 1.996913 | 1.913405 | 2.017786 |
26 | 67.108.864 | 48.218.831 | 8.868.870 | 39.349.961 | 0.718517 | 0.132156 | 0.586360 | 1.996970 | 1.916942 | 2.015939 |
27 | 134.217.728 | 96.302.732 | 17.034.716 | 79.268.016 | 0.717511 | 0.126919 | 0.590593 | 1.997202 | 1.920731 | 2.014437 |
28 | 268.435.456 | 192.355.874 | 32.765.362 | 159.590.512 | 0.716581 | 0.122060 | 0.594521 | 1.997408 | 1.923446 | 2.013303 |
29 | 536.870.912 | 384.249.552 | 63.110.879 | 321.138.673 | 0.715721 | 0.117553 | 0.598167 | 1.997597 | 1.926146 | 2.012267 |
30 | 1.073.741.824 | 767.648.731 | 121.727.998 | 645.920.733 | 0.714929 | 0.113368 | 0.601561 | 1.997787 | 1.928796 | 2.011345 |
31 | 2.147.483.648 | 1.533.690.018 | 235.112.886 | 1.298.577.132 | 0.714180 | 0.109483 | 0.604697 | 1.997906 | 1.931461 | 2.010428 |
32 | 4.294.967.296 | 3.064.389.642 | 454.621.752 | 2.609.767.890 | 0.713484 | 0.105850 | 0.607634 | 1.998050 | 1.933632 | 2.009713 |
33 | 8.589.934.592 | 6.123.183.659 | 880.050.056 | 5.243.133.603 | 0.712832 | 0.102451 | 0.610381 | 1.998174 | 1.935785 | 2.009042 |
34 | 17.179.869.184 | 12.235.885.316 | 1.705.375.873 | 10.530.509.443 | 0.712222 | 0.099266 | 0.612956 | 1.998288 | 1.937817 | 2.008438 |
35 | 34.359.738.368 | 24.452.137.578 | 3.307.872.455 | 21.144.265.123 | 0.711651 | 0.096272 | 0.615379 | 1.998395 | 1.939674 | 2.007905 |
36 | 68.719.476.736 | 48.867.181.206 | 6.422.090.684 | 42.445.090.522 | 0.711111 | 0.093454 | 0.617657 | 1.998483 | 1.941457 | 2.007404 |
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 | 1 | 0 | 2 |
2 | 4 | 5 | 1 | 4 | 1 | 2 | 0 | 2 |
3 | 8 | 9 | 3 | 6 | 3 | 2 | 2 | 2 |
4 | 16 | 14 | 4 | 10 | 5 | 2 | 5 | 2 |
5 | 32 | 25 | 7 | 18 | 9 | 2 | 12 | 2 |
6 | 64 | 43 | 17 | 26 | 18 | 2 | 21 | 2 |
7 | 128 | 75 | 35 | 40 | 32 | 2 | 39 | 2 |
8 | 256 | 133 | 63 | 70 | 64 | 2 | 65 | 2 |
9 | 512 | 229 | 113 | 116 | 118 | 2 | 107 | 2 |
10 | 1.024 | 394 | 203 | 191 | 195 | 2 | 195 | 2 |
11 | 2.048 | 732 | 361 | 371 | 368 | 2 | 360 | 2 |
12 | 4.096 | 1.305 | 656 | 649 | 655 | 2 | 646 | 2 |
13 | 8.192 | 2.370 | 1.188 | 1.182 | 1.191 | 2 | 1.175 | 2 |
14 | 16.384 | 4.326 | 2.160 | 2.166 | 2.148 | 2 | 2.174 | 2 |
15 | 32.768 | 8.022 | 4.036 | 3.986 | 3.987 | 2 | 4.031 | 2 |
16 | 65.536 | 14.768 | 7.396 | 7.372 | 7.339 | 2 | 7.425 | 2 |
17 | 131.072 | 27.710 | 13.846 | 13.864 | 13.824 | 2 | 13.882 | 2 |
18 | 262.144 | 51.915 | 26.068 | 25.847 | 25.957 | 2 | 25.954 | 2 |
19 | 524.288 | 97.702 | 48.957 | 48.745 | 48.888 | 2 | 48.810 | 2 |
20 | 1.048.576 | 184.477 | 92.400 | 92.077 | 92.295 | 2 | 92.178 | 2 |
21 | 2.097.152 | 349.821 | 175.609 | 174.212 | 174.926 | 2 | 174.891 | 2 |
22 | 4.194.304 | 664.294 | 333.433 | 330.861 | 331.967 | 2 | 332.323 | 2 |
23 | 8.388.608 | 1.266.068 | 635.805 | 630.263 | 632.567 | 2 | 633.497 | 2 |
24 | 16.777.216 | 2.417.978 | 1.213.317 | 1.204.661 | 1.208.513 | 2 | 1.209.461 | 2 |
25 | 33.554.432 | 4.626.571 | 2.321.636 | 2.304.935 | 2.312.595 | 2 | 2.313.972 | 2 |
26 | 67.108.864 | 8.868.870 | 4.450.065 | 4.418.805 | 4.434.389 | 2 | 4.434.477 | 2 |
27 | 134.217.728 | 17.034.716 | 8.546.782 | 8.487.934 | 8.514.913 | 2 | 8.519.799 | 2 |
28 | 268.435.456 | 32.765.362 | 16.436.265 | 16.329.097 | 16.380.140 | 2 | 16.385.218 | 2 |
29 | 536.870.912 | 63.110.879 | 31.654.213 | 31.456.666 | 31.553.206 | 2 | 31.557.669 | 2 |
30 | 1.073.741.824 | 121.727.998 | 61.046.650 | 60.681.348 | 60.862.550 | 2 | 60.865.444 | 2 |
31 | 2.147.483.648 | 235.112.886 | 117.896.514 | 117.216.372 | 117.558.194 | 2 | 117.554.688 | 2 |
32 | 4.294.967.296 | 454.621.752 | 227.949.430 | 226.672.322 | 227.305.276 | 2 | 227.316.472 | 2 |
33 | 8.589.934.592 | 880.050.056 | 441.214.780 | 438.835.276 | 440.019.778 | 2 | 440.030.274 | 2 |
34 | 17.179.869.184 | 1.705.375.873 | 854.912.144 | 850.463.729 | 852.675.117 | 2 | 852.700.752 | 2 |
35 | 34.359.738.368 | 3.307.872.455 | 1.658.100.975 | 1.649.771.480 | 1.653.937.251 | 2 | 1.653.935.200 | 2 |
36 | 68.719.476.736 | 6.422.090.684 | 3.218.871.345 | 3.203.219.339 | 3.211.011.891 | 2 | 3.211.078.789 | 2 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 2 | 0 | 2 | 1 | 1 | 0 | 0 |
6 | 64 | 10 | 6 | 4 | 2 | 4 | 1 | 3 |
7 | 128 | 30 | 17 | 13 | 5 | 9 | 8 | 8 |
8 | 256 | 67 | 32 | 35 | 14 | 21 | 13 | 19 |
9 | 512 | 164 | 83 | 81 | 31 | 48 | 38 | 47 |
10 | 1.024 | 388 | 199 | 189 | 79 | 115 | 88 | 106 |
11 | 2.048 | 824 | 404 | 420 | 168 | 234 | 179 | 243 |
12 | 4.096 | 1.774 | 887 | 887 | 381 | 503 | 383 | 507 |
13 | 8.192 | 3.720 | 1.829 | 1.891 | 804 | 1.042 | 816 | 1.058 |
14 | 16.384 | 7.804 | 3.929 | 3.875 | 1.745 | 2.160 | 1.742 | 2.157 |
15 | 32.768 | 16.106 | 8.063 | 8.043 | 3.658 | 4.390 | 3.656 | 4.402 |
16 | 65.536 | 33.402 | 16.708 | 16.694 | 7.628 | 9.096 | 7.731 | 8.947 |
17 | 131.072 | 68.262 | 34.142 | 34.120 | 15.872 | 18.328 | 15.920 | 18.142 |
18 | 262.144 | 139.469 | 69.874 | 69.595 | 32.555 | 37.171 | 32.686 | 37.057 |
19 | 524.288 | 284.107 | 142.010 | 142.097 | 66.844 | 75.224 | 66.875 | 75.164 |
20 | 1.048.576 | 577.421 | 288.502 | 288.919 | 136.605 | 152.089 | 136.442 | 152.285 |
21 | 2.097.152 | 1.170.521 | 584.712 | 585.809 | 278.588 | 307.249 | 277.369 | 307.315 |
22 | 4.194.304 | 2.370.269 | 1.184.777 | 1.185.492 | 566.062 | 619.682 | 564.953 | 619.572 |
23 | 8.388.608 | 4.791.374 | 2.394.373 | 2.397.001 | 1.146.550 | 1.249.830 | 1.145.561 | 1.249.433 |
24 | 16.777.216 | 9.673.686 | 4.834.356 | 4.839.330 | 2.319.828 | 2.518.092 | 2.318.618 | 2.517.148 |
25 | 33.554.432 | 19.519.425 | 9.755.046 | 9.764.379 | 4.694.424 | 5.067.265 | 4.690.534 | 5.067.202 |
26 | 67.108.864 | 39.349.961 | 19.665.610 | 19.684.351 | 9.480.223 | 10.195.802 | 9.477.044 | 10.196.892 |
27 | 134.217.728 | 79.268.016 | 39.622.696 | 39.645.320 | 19.135.170 | 20.502.500 | 19.130.427 | 20.499.919 |
28 | 268.435.456 | 159.590.512 | 79.770.452 | 79.820.060 | 38.591.656 | 41.208.565 | 38.588.507 | 41.201.784 |
29 | 536.870.912 | 321.138.673 | 160.527.881 | 160.610.792 | 77.775.629 | 82.798.909 | 77.766.210 | 82.797.925 |
30 | 1.073.741.824 | 645.920.733 | 322.880.440 | 323.040.293 | 156.649.907 | 166.304.285 | 156.666.825 | 166.299.716 |
31 | 2.147.483.648 | 1.298.577.132 | 649.137.659 | 649.439.473 | 315.360.534 | 333.933.535 | 315.376.987 | 333.906.076 |
32 | 4.294.967.296 | 2.609.767.890 | 1.304.604.937 | 1.305.162.953 | 634.567.290 | 670.332.672 | 634.566.933 | 670.300.995 |
33 | 8.589.934.592 | 5.243.133.603 | 2.621.023.232 | 2.622.110.371 | 1.276.286.485 | 1.345.290.373 | 1.276.309.817 | 1.345.246.928 |
34 | 17.179.869.184 | 10.530.509.443 | 5.264.276.659 | 5.266.232.784 | 2.565.976.752 | 2.699.324.282 | 2.566.006.312 | 2.699.202.097 |
35 | 34.359.738.368 | 21.144.265.123 | 10.570.314.234 | 10.573.950.889 | 5.157.107.528 | 5.415.128.450 | 5.157.072.748 | 5.414.956.397 |
36 | 68.719.476.736 | 42.445.090.522 | 21.219.070.842 | 21.226.019.680 | 10.361.506.645 | 10.861.070.025 | 10.361.535.832 | 10.860.978.020 |