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-68x-37
f(0)=37
f(1)=13
f(2)=1
f(3)=29
f(4)=293
f(5)=11
f(6)=409
f(7)=1
f(8)=47
f(9)=71
f(10)=617
f(11)=83
f(12)=709
f(13)=1
f(14)=61
f(15)=1
f(16)=79
f(17)=113
f(18)=937
f(19)=1
f(20)=997
f(21)=1
f(22)=1049
f(23)=67
f(24)=1093
f(25)=139
f(26)=1129
f(27)=1
f(28)=89
f(29)=73
f(30)=107
f(31)=1
f(32)=41
f(33)=149
f(34)=1193
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)=1
f(68)=1
f(69)=1
f(70)=103
f(71)=1
f(72)=251
f(73)=1
f(74)=1
f(75)=1
f(76)=571
f(77)=1
f(78)=743
f(79)=1
f(80)=1
f(81)=127
f(82)=101
f(83)=151
f(84)=1307
f(85)=1
f(86)=1511
f(87)=1
f(88)=1723
f(89)=229
f(90)=1
f(91)=257
f(92)=167
f(93)=1
f(94)=1
f(95)=1
f(96)=241
f(97)=347
f(98)=2903
f(99)=379
b) Substitution of the polynom
The polynom f(x)=x^2-68x-37 could be written as f(y)= y^2-1193 with x=y+34
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-34
f'(x)>2x-69 with x > 35
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 | 9 | 8 | 1 | 0.900000 | 0.800000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 39 | 33 | 6 | 0.390000 | 0.330000 | 0.060000 | 4.333333 | 4.125000 | 6.000000 |
3 | 1.000 | 602 | 353 | 249 | 0.602000 | 0.353000 | 0.249000 | 15.435898 | 10.696970 | 41.500000 |
4 | 10.000 | 6.578 | 2.614 | 3.964 | 0.657800 | 0.261400 | 0.396400 | 10.926910 | 7.405099 | 15.919679 |
5 | 100.000 | 67.127 | 19.936 | 47.191 | 0.671270 | 0.199360 | 0.471910 | 10.204774 | 7.626626 | 11.904894 |
6 | 1.000.000 | 675.173 | 160.325 | 514.848 | 0.675173 | 0.160325 | 0.514848 | 10.058144 | 8.041985 | 10.909877 |
7 | 10.000.000 | 6.779.371 | 1.343.880 | 5.435.491 | 0.677937 | 0.134388 | 0.543549 | 10.040939 | 8.382224 | 10.557467 |
8 | 100.000.000 | 67.986.428 | 11.565.863 | 56.420.565 | 0.679864 | 0.115659 | 0.564206 | 10.028428 | 8.606321 | 10.380031 |
9 | 1.000.000.000 | 681.300.868 | 101.497.924 | 579.802.944 | 0.681301 | 0.101498 | 0.579803 | 10.021130 | 8.775646 | 10.276447 |
10 | 10.000.000.000 | 6.824.695.436 | 904.399.560 | 5.920.295.876 | 0.682470 | 0.090440 | 0.592030 | 10.017154 | 8.910523 | 10.210876 |
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 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 2.000000 | 2.000000 | -nan |
3 | 8 | 7 | 6 | 1 | 0.875000 | 0.750000 | 0.125000 | 1.750000 | 1.500000 | inf |
4 | 16 | 13 | 10 | 3 | 0.812500 | 0.625000 | 0.187500 | 1.857143 | 1.666667 | 3.000000 |
5 | 32 | 24 | 19 | 5 | 0.750000 | 0.593750 | 0.156250 | 1.846154 | 1.900000 | 1.666667 |
6 | 64 | 26 | 21 | 5 | 0.406250 | 0.328125 | 0.078125 | 1.083333 | 1.105263 | 1.000000 |
7 | 128 | 54 | 45 | 9 | 0.421875 | 0.351562 | 0.070312 | 2.076923 | 2.142857 | 1.800000 |
8 | 256 | 122 | 100 | 22 | 0.476562 | 0.390625 | 0.085938 | 2.259259 | 2.222222 | 2.444444 |
9 | 512 | 287 | 193 | 94 | 0.560547 | 0.376953 | 0.183594 | 2.352459 | 1.930000 | 4.272727 |
10 | 1.024 | 617 | 360 | 257 | 0.602539 | 0.351562 | 0.250977 | 2.149826 | 1.865285 | 2.734043 |
11 | 2.048 | 1.278 | 662 | 616 | 0.624023 | 0.323242 | 0.300781 | 2.071313 | 1.838889 | 2.396887 |
12 | 4.096 | 2.641 | 1.203 | 1.438 | 0.644775 | 0.293701 | 0.351074 | 2.066510 | 1.817221 | 2.334416 |
13 | 8.192 | 5.368 | 2.199 | 3.169 | 0.655273 | 0.268433 | 0.386841 | 2.032563 | 1.827930 | 2.203755 |
14 | 16.384 | 10.864 | 4.058 | 6.806 | 0.663086 | 0.247681 | 0.415405 | 2.023845 | 1.845384 | 2.147681 |
15 | 32.768 | 21.851 | 7.434 | 14.417 | 0.666840 | 0.226868 | 0.439972 | 2.011322 | 1.831937 | 2.118278 |
16 | 65.536 | 43.901 | 13.698 | 30.203 | 0.669876 | 0.209015 | 0.460861 | 2.009107 | 1.842615 | 2.094957 |
17 | 131.072 | 88.053 | 25.492 | 62.561 | 0.671791 | 0.194489 | 0.477303 | 2.005718 | 1.861002 | 2.071351 |
18 | 262.144 | 176.480 | 47.567 | 128.913 | 0.673218 | 0.181454 | 0.491764 | 2.004247 | 1.865958 | 2.060597 |
19 | 524.288 | 353.486 | 89.093 | 264.393 | 0.674221 | 0.169931 | 0.504290 | 2.002980 | 1.873000 | 2.050941 |
20 | 1.048.576 | 707.955 | 167.478 | 540.477 | 0.675159 | 0.159719 | 0.515439 | 2.002781 | 1.879811 | 2.044218 |
21 | 2.097.152 | 1.417.860 | 316.928 | 1.100.932 | 0.676088 | 0.151123 | 0.524965 | 2.002754 | 1.892356 | 2.036964 |
22 | 4.194.304 | 2.839.530 | 600.731 | 2.238.799 | 0.676997 | 0.143225 | 0.533771 | 2.002687 | 1.895481 | 2.033549 |
23 | 8.388.608 | 5.685.309 | 1.141.701 | 4.543.608 | 0.677742 | 0.136101 | 0.541640 | 2.002201 | 1.900519 | 2.029485 |
24 | 16.777.216 | 11.381.509 | 2.175.385 | 9.206.124 | 0.678391 | 0.129663 | 0.548728 | 2.001916 | 1.905389 | 2.026170 |
25 | 33.554.432 | 22.783.143 | 4.156.310 | 18.626.833 | 0.678991 | 0.123868 | 0.555123 | 2.001768 | 1.910609 | 2.023309 |
26 | 67.108.864 | 45.603.856 | 7.953.955 | 37.649.901 | 0.679550 | 0.118523 | 0.561027 | 2.001649 | 1.913706 | 2.021272 |
27 | 134.217.728 | 91.275.695 | 15.249.951 | 76.025.744 | 0.680057 | 0.113621 | 0.566436 | 2.001491 | 1.917279 | 2.019281 |
28 | 268.435.456 | 182.675.115 | 29.290.033 | 153.385.082 | 0.680518 | 0.109114 | 0.571404 | 2.001356 | 1.920664 | 2.017541 |
29 | 536.870.912 | 365.576.778 | 56.351.400 | 309.225.378 | 0.680940 | 0.104963 | 0.575977 | 2.001240 | 1.923910 | 2.016007 |
30 | 1.073.741.824 | 731.586.096 | 108.572.180 | 623.013.916 | 0.681343 | 0.101116 | 0.580227 | 2.001183 | 1.926699 | 2.014757 |
31 | 2.147.483.648 | 1.463.972.708 | 209.454.783 | 1.254.517.925 | 0.681715 | 0.097535 | 0.584180 | 2.001094 | 1.929175 | 2.013628 |
32 | 4.294.967.296 | 2.929.472.776 | 404.594.923 | 2.524.877.853 | 0.682071 | 0.094202 | 0.587869 | 2.001043 | 1.931658 | 2.012628 |
33 | 8.589.934.592 | 5.861.769.273 | 782.491.333 | 5.079.277.940 | 0.682400 | 0.091094 | 0.591306 | 2.000964 | 1.934012 | 2.011693 |
34 | 17.179.869.184 | 11.728.909.064 | 1.514.989.721 | 10.213.919.343 | 0.682712 | 0.088184 | 0.594528 | 2.000916 | 1.936110 | 2.010900 |
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 | 2 | 0 | 0 | 0 | 2 | 0 |
2 | 4 | 4 | 2 | 2 | 0 | 0 | 4 | 0 |
3 | 8 | 6 | 3 | 3 | 1 | 1 | 4 | 0 |
4 | 16 | 10 | 4 | 6 | 2 | 2 | 5 | 1 |
5 | 32 | 19 | 11 | 8 | 7 | 4 | 7 | 1 |
6 | 64 | 21 | 11 | 10 | 8 | 4 | 8 | 1 |
7 | 128 | 45 | 20 | 25 | 9 | 17 | 11 | 8 |
8 | 256 | 100 | 43 | 57 | 18 | 35 | 17 | 30 |
9 | 512 | 193 | 83 | 110 | 35 | 71 | 30 | 57 |
10 | 1.024 | 360 | 161 | 199 | 52 | 138 | 52 | 118 |
11 | 2.048 | 662 | 291 | 371 | 96 | 236 | 94 | 236 |
12 | 4.096 | 1.203 | 536 | 667 | 169 | 435 | 183 | 416 |
13 | 8.192 | 2.199 | 975 | 1.224 | 319 | 791 | 305 | 784 |
14 | 16.384 | 4.058 | 1.819 | 2.239 | 556 | 1.485 | 550 | 1.467 |
15 | 32.768 | 7.434 | 3.341 | 4.093 | 1.025 | 2.729 | 996 | 2.684 |
16 | 65.536 | 13.698 | 6.146 | 7.552 | 1.841 | 4.990 | 1.836 | 5.031 |
17 | 131.072 | 25.492 | 11.501 | 13.991 | 3.421 | 9.314 | 3.438 | 9.319 |
18 | 262.144 | 47.567 | 21.430 | 26.137 | 6.387 | 17.454 | 6.286 | 17.440 |
19 | 524.288 | 89.093 | 40.027 | 49.066 | 11.796 | 32.757 | 11.758 | 32.782 |
20 | 1.048.576 | 167.478 | 75.319 | 92.159 | 22.204 | 61.644 | 22.041 | 61.589 |
21 | 2.097.152 | 316.928 | 142.596 | 174.332 | 41.777 | 116.933 | 41.731 | 116.487 |
22 | 4.194.304 | 600.731 | 270.080 | 330.651 | 79.017 | 221.311 | 78.982 | 221.421 |
23 | 8.388.608 | 1.141.701 | 513.249 | 628.452 | 149.903 | 420.718 | 150.068 | 421.012 |
24 | 16.777.216 | 2.175.385 | 977.004 | 1.198.381 | 285.078 | 802.158 | 285.505 | 802.644 |
25 | 33.554.432 | 4.156.310 | 1.865.201 | 2.291.109 | 543.111 | 1.534.436 | 544.190 | 1.534.573 |
26 | 67.108.864 | 7.953.955 | 3.567.445 | 4.386.510 | 1.037.393 | 2.939.091 | 1.037.786 | 2.939.685 |
27 | 134.217.728 | 15.249.951 | 6.835.883 | 8.414.068 | 1.985.579 | 5.638.938 | 1.985.145 | 5.640.289 |
28 | 268.435.456 | 29.290.033 | 13.123.117 | 16.166.916 | 3.806.845 | 10.837.665 | 3.806.719 | 10.838.804 |
29 | 536.870.912 | 56.351.400 | 25.240.930 | 31.110.470 | 7.314.058 | 20.861.778 | 7.312.754 | 20.862.810 |
30 | 1.073.741.824 | 108.572.180 | 48.615.205 | 59.956.975 | 14.071.354 | 40.217.393 | 14.072.024 | 40.211.409 |
31 | 2.147.483.648 | 209.454.783 | 93.766.592 | 115.688.191 | 27.112.244 | 77.618.256 | 27.115.066 | 77.609.217 |
32 | 4.294.967.296 | 404.594.923 | 181.077.903 | 223.517.020 | 52.309.916 | 149.991.407 | 52.309.697 | 149.983.903 |
33 | 8.589.934.592 | 782.491.333 | 350.133.183 | 432.358.150 | 101.056.122 | 290.193.686 | 101.056.353 | 290.185.172 |
34 | 17.179.869.184 | 1.514.989.721 | 677.764.987 | 837.224.734 | 195.450.753 | 562.040.740 | 195.468.863 | 562.029.365 |
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 | 3 | 2 | 1 | 0 | 0 | 1 | 2 |
5 | 32 | 5 | 2 | 3 | 1 | 1 | 1 | 2 |
6 | 64 | 5 | 2 | 3 | 1 | 1 | 1 | 2 |
7 | 128 | 9 | 6 | 3 | 3 | 2 | 2 | 2 |
8 | 256 | 22 | 11 | 11 | 6 | 4 | 6 | 6 |
9 | 512 | 94 | 54 | 40 | 21 | 23 | 24 | 26 |
10 | 1.024 | 257 | 139 | 118 | 56 | 68 | 63 | 70 |
11 | 2.048 | 616 | 322 | 294 | 149 | 151 | 154 | 162 |
12 | 4.096 | 1.438 | 732 | 706 | 353 | 364 | 344 | 377 |
13 | 8.192 | 3.169 | 1.587 | 1.582 | 776 | 830 | 768 | 795 |
14 | 16.384 | 6.806 | 3.430 | 3.376 | 1.646 | 1.753 | 1.695 | 1.712 |
15 | 32.768 | 14.417 | 7.264 | 7.153 | 3.564 | 3.649 | 3.574 | 3.630 |
16 | 65.536 | 30.203 | 15.103 | 15.100 | 7.451 | 7.585 | 7.511 | 7.656 |
17 | 131.072 | 62.561 | 31.412 | 31.149 | 15.512 | 15.777 | 15.415 | 15.857 |
18 | 262.144 | 128.913 | 64.637 | 64.276 | 31.930 | 32.451 | 32.000 | 32.532 |
19 | 524.288 | 264.393 | 132.518 | 131.875 | 65.624 | 66.435 | 65.553 | 66.781 |
20 | 1.048.576 | 540.477 | 270.980 | 269.497 | 134.393 | 135.760 | 134.222 | 136.102 |
21 | 2.097.152 | 1.100.932 | 551.852 | 549.080 | 274.052 | 276.411 | 273.567 | 276.902 |
22 | 4.194.304 | 2.238.799 | 1.122.109 | 1.116.690 | 557.089 | 561.861 | 557.323 | 562.526 |
23 | 8.388.608 | 4.543.608 | 2.278.006 | 2.265.602 | 1.130.479 | 1.140.995 | 1.131.695 | 1.140.439 |
24 | 16.777.216 | 9.206.124 | 4.614.901 | 4.591.223 | 2.291.865 | 2.310.795 | 2.292.361 | 2.311.103 |
25 | 33.554.432 | 18.626.833 | 9.334.637 | 9.292.196 | 4.637.661 | 4.676.214 | 4.638.791 | 4.674.167 |
26 | 67.108.864 | 37.649.901 | 18.869.536 | 18.780.365 | 9.376.023 | 9.447.894 | 9.380.773 | 9.445.211 |
27 | 134.217.728 | 76.025.744 | 38.098.585 | 37.927.159 | 18.932.758 | 19.076.617 | 18.945.632 | 19.070.737 |
28 | 268.435.456 | 153.385.082 | 76.856.882 | 76.528.200 | 38.216.378 | 38.476.336 | 38.219.421 | 38.472.947 |
29 | 536.870.912 | 309.225.378 | 154.931.984 | 154.293.394 | 77.057.951 | 77.565.575 | 77.045.134 | 77.556.718 |
30 | 1.073.741.824 | 623.013.916 | 312.113.480 | 310.900.436 | 155.259.390 | 156.244.490 | 155.266.662 | 156.243.374 |
31 | 2.147.483.648 | 1.254.517.925 | 628.404.807 | 626.113.118 | 312.672.410 | 314.561.915 | 312.707.755 | 314.575.845 |
32 | 4.294.967.296 | 2.524.877.853 | 1.264.671.300 | 1.260.206.553 | 629.371.773 | 633.040.781 | 629.420.997 | 633.044.302 |
33 | 8.589.934.592 | 5.079.277.940 | 2.543.950.805 | 2.535.327.135 | 1.266.256.391 | 1.273.351.406 | 1.266.312.737 | 1.273.357.406 |
34 | 17.179.869.184 | 10.213.919.343 | 5.115.310.190 | 5.098.609.153 | 2.546.655.712 | 2.560.325.726 | 2.546.653.233 | 2.560.284.672 |