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+150x-47
f(0)=47
f(1)=13
f(2)=257
f(3)=103
f(4)=569
f(5)=7
f(6)=127
f(7)=263
f(8)=1217
f(9)=173
f(10)=1553
f(11)=431
f(12)=271
f(13)=37
f(14)=1
f(15)=607
f(16)=2609
f(17)=349
f(18)=229
f(19)=113
f(20)=479
f(21)=443
f(22)=101
f(23)=983
f(24)=4129
f(25)=541
f(26)=647
f(27)=1
f(28)=4937
f(29)=643
f(30)=53
f(31)=107
f(32)=109
f(33)=1
f(34)=887
f(35)=1607
f(36)=61
f(37)=859
f(38)=151
f(39)=1831
f(40)=83
f(41)=139
f(42)=8017
f(43)=2063
f(44)=653
f(45)=1091
f(46)=8969
f(47)=1
f(48)=193
f(49)=1213
f(50)=269
f(51)=2551
f(52)=10457
f(53)=1
f(54)=1567
f(55)=401
f(56)=11489
f(57)=1
f(58)=197
f(59)=1
f(60)=12553
f(61)=1
f(62)=1871
f(63)=3343
f(64)=13649
f(65)=1741
f(66)=1093
f(67)=3623
f(68)=2111
f(69)=1
f(70)=1181
f(71)=3911
f(72)=15937
f(73)=2029
f(74)=16529
f(75)=601
f(76)=2447
f(77)=2179
f(78)=17737
f(79)=347
f(80)=18353
f(81)=2333
f(82)=2711
f(83)=1
f(84)=19609
f(85)=1
f(86)=20249
f(87)=1
f(88)=20897
f(89)=379
f(90)=3079
f(91)=5471
f(92)=1709
f(93)=2819
f(94)=487
f(95)=5807
f(96)=1
f(97)=1
f(98)=191
f(99)=6151
b) Substitution of the polynom
The polynom f(x)=x^2+150x-47 could be written as f(y)= y^2-5672 with x=y-75
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+75
f'(x)>2x+149
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 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 83 | 51 | 32 | 0.830000 | 0.510000 | 0.830000 | 8.300000 | 5.666667 | 32.000000 |
3 | 1.000 | 730 | 351 | 379 | 0.730000 | 0.351000 | 0.730000 | 8.795180 | 6.882353 | 11.843750 |
4 | 10.000 | 7.111 | 2.501 | 4.610 | 0.711100 | 0.250100 | 0.711100 | 9.741096 | 7.125356 | 12.163589 |
5 | 100.000 | 70.638 | 19.325 | 51.313 | 0.706380 | 0.193250 | 0.706380 | 9.933624 | 7.726909 | 11.130802 |
6 | 1.000.000 | 703.663 | 157.159 | 546.504 | 0.703663 | 0.157159 | 0.703663 | 9.961536 | 8.132420 | 10.650400 |
7 | 10.000.000 | 7.020.984 | 1.321.043 | 5.699.941 | 0.702098 | 0.132104 | 0.702098 | 9.977765 | 8.405774 | 10.429825 |
8 | 100.000.000 | 70.077.396 | 11.396.867 | 58.680.529 | 0.700774 | 0.113969 | 0.700774 | 9.981135 | 8.627173 | 10.294936 |
9 | 1.000.000.000 | 699.799.799 | 100.255.556 | 599.544.243 | 0.699800 | 0.100256 | 0.699800 | 9.986099 | 8.796764 | 10.217091 |
10 | 10.000.000.000 | 6.990.356.908 | 894.919.164 | 6.095.437.744 | 0.699036 | 0.089492 | 0.699036 | 9.989081 | 8.926380 | 10.166785 |
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 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 15 | 12 | 3 | 0.937500 | 0.750000 | 0.187500 | 1.875000 | 1.714286 | 3.000000 |
5 | 32 | 29 | 19 | 10 | 0.906250 | 0.593750 | 0.312500 | 1.933333 | 1.583333 | 3.333333 |
6 | 64 | 54 | 33 | 21 | 0.843750 | 0.515625 | 0.328125 | 1.862069 | 1.736842 | 2.100000 |
7 | 128 | 103 | 64 | 39 | 0.804688 | 0.500000 | 0.304688 | 1.907407 | 1.939394 | 1.857143 |
8 | 256 | 197 | 115 | 82 | 0.769531 | 0.449219 | 0.320312 | 1.912621 | 1.796875 | 2.102564 |
9 | 512 | 383 | 194 | 189 | 0.748047 | 0.378906 | 0.369141 | 1.944162 | 1.686957 | 2.304878 |
10 | 1.024 | 747 | 363 | 384 | 0.729492 | 0.354492 | 0.375000 | 1.950392 | 1.871134 | 2.031746 |
11 | 2.048 | 1.467 | 645 | 822 | 0.716309 | 0.314941 | 0.401367 | 1.963855 | 1.776860 | 2.140625 |
12 | 4.096 | 2.936 | 1.159 | 1.777 | 0.716797 | 0.282959 | 0.433838 | 2.001363 | 1.796899 | 2.161800 |
13 | 8.192 | 5.837 | 2.098 | 3.739 | 0.712524 | 0.256104 | 0.456421 | 1.988079 | 1.810181 | 2.104108 |
14 | 16.384 | 11.655 | 3.884 | 7.771 | 0.711365 | 0.237061 | 0.474304 | 1.996745 | 1.851287 | 2.078363 |
15 | 32.768 | 23.237 | 7.090 | 16.147 | 0.709137 | 0.216370 | 0.492767 | 1.993737 | 1.825438 | 2.077853 |
16 | 65.536 | 46.321 | 13.185 | 33.136 | 0.706802 | 0.201187 | 0.505615 | 1.993416 | 1.859661 | 2.052146 |
17 | 131.072 | 92.542 | 24.630 | 67.912 | 0.706039 | 0.187912 | 0.518127 | 1.997841 | 1.868032 | 2.049493 |
18 | 262.144 | 184.809 | 46.173 | 138.636 | 0.704990 | 0.176136 | 0.528854 | 1.997028 | 1.874665 | 2.041407 |
19 | 524.288 | 369.197 | 86.889 | 282.308 | 0.704187 | 0.165728 | 0.538460 | 1.997722 | 1.881814 | 2.036325 |
20 | 1.048.576 | 737.801 | 164.143 | 573.658 | 0.703622 | 0.156539 | 0.547083 | 1.998394 | 1.889111 | 2.032029 |
21 | 2.097.152 | 1.474.648 | 310.517 | 1.164.131 | 0.703167 | 0.148066 | 0.555101 | 1.998707 | 1.891747 | 2.029312 |
22 | 4.194.304 | 2.946.636 | 589.563 | 2.357.073 | 0.702533 | 0.140563 | 0.561970 | 1.998196 | 1.898650 | 2.024749 |
23 | 8.388.608 | 5.890.742 | 1.121.670 | 4.769.072 | 0.702231 | 0.133713 | 0.568518 | 1.999141 | 1.902545 | 2.023303 |
24 | 16.777.216 | 11.772.765 | 2.140.095 | 9.632.670 | 0.701711 | 0.127560 | 0.574152 | 1.998520 | 1.907954 | 2.019821 |
25 | 33.554.432 | 23.532.325 | 4.090.886 | 19.441.439 | 0.701318 | 0.121918 | 0.579400 | 1.998878 | 1.911544 | 2.018281 |
26 | 67.108.864 | 47.041.245 | 7.834.012 | 39.207.233 | 0.700969 | 0.116736 | 0.584233 | 1.999005 | 1.914991 | 2.016684 |
27 | 134.217.728 | 94.036.863 | 15.035.066 | 79.001.797 | 0.700629 | 0.112020 | 0.588609 | 1.999030 | 1.919204 | 2.014980 |
28 | 268.435.456 | 187.989.957 | 28.896.081 | 159.093.876 | 0.700317 | 0.107646 | 0.592671 | 1.999109 | 1.921912 | 2.013801 |
29 | 536.870.912 | 375.829.008 | 55.631.554 | 320.197.454 | 0.700036 | 0.103622 | 0.596414 | 1.999197 | 1.925228 | 2.012632 |
30 | 1.073.741.824 | 751.378.641 | 107.248.253 | 644.130.388 | 0.699776 | 0.099883 | 0.599893 | 1.999257 | 1.927831 | 2.011666 |
31 | 2.147.483.648 | 1.502.230.003 | 207.026.636 | 1.295.203.367 | 0.699530 | 0.096404 | 0.603126 | 1.999298 | 1.930350 | 2.010778 |
32 | 4.294.967.296 | 3.003.456.767 | 400.134.384 | 2.603.322.383 | 0.699297 | 0.093164 | 0.606133 | 1.999332 | 1.932768 | 2.009972 |
33 | 8.589.934.592 | 6.005.067.363 | 774.212.170 | 5.230.855.193 | 0.699082 | 0.090130 | 0.608952 | 1.999385 | 1.934880 | 2.009300 |
34 | 17.179.869.184 | 12.006.682.560 | 1.499.684.373 | 10.506.998.187 | 0.698881 | 0.087293 | 0.611588 | 1.999425 | 1.937046 | 2.008658 |
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 | 1 | 0 | 1 | 1 |
2 | 4 | 5 | 2 | 3 | 2 | 0 | 1 | 2 |
3 | 8 | 7 | 2 | 5 | 3 | 0 | 1 | 3 |
4 | 16 | 12 | 3 | 9 | 5 | 0 | 2 | 5 |
5 | 32 | 19 | 7 | 12 | 7 | 2 | 4 | 6 |
6 | 64 | 33 | 14 | 19 | 13 | 4 | 5 | 11 |
7 | 128 | 64 | 28 | 36 | 28 | 7 | 10 | 19 |
8 | 256 | 115 | 52 | 63 | 52 | 13 | 19 | 31 |
9 | 512 | 194 | 86 | 108 | 85 | 25 | 31 | 53 |
10 | 1.024 | 363 | 155 | 208 | 168 | 48 | 53 | 94 |
11 | 2.048 | 645 | 275 | 370 | 298 | 83 | 92 | 172 |
12 | 4.096 | 1.159 | 476 | 683 | 531 | 153 | 163 | 312 |
13 | 8.192 | 2.098 | 885 | 1.213 | 976 | 279 | 287 | 556 |
14 | 16.384 | 3.884 | 1.641 | 2.243 | 1.827 | 531 | 521 | 1.005 |
15 | 32.768 | 7.090 | 2.979 | 4.111 | 3.340 | 978 | 944 | 1.828 |
16 | 65.536 | 13.185 | 5.547 | 7.638 | 6.289 | 1.764 | 1.746 | 3.386 |
17 | 131.072 | 24.630 | 10.383 | 14.247 | 11.797 | 3.255 | 3.212 | 6.366 |
18 | 262.144 | 46.173 | 19.438 | 26.735 | 22.113 | 6.082 | 6.116 | 11.862 |
19 | 524.288 | 86.889 | 36.574 | 50.315 | 41.763 | 11.416 | 11.418 | 22.292 |
20 | 1.048.576 | 164.143 | 69.108 | 95.035 | 79.171 | 21.566 | 21.538 | 41.868 |
21 | 2.097.152 | 310.517 | 130.616 | 179.901 | 150.115 | 40.733 | 40.839 | 78.830 |
22 | 4.194.304 | 589.563 | 247.666 | 341.897 | 285.574 | 76.974 | 77.063 | 149.952 |
23 | 8.388.608 | 1.121.670 | 471.149 | 650.521 | 543.855 | 146.337 | 146.093 | 285.385 |
24 | 16.777.216 | 2.140.095 | 898.726 | 1.241.369 | 1.039.623 | 278.880 | 277.963 | 543.629 |
25 | 33.554.432 | 4.090.886 | 1.718.011 | 2.372.875 | 1.990.092 | 531.748 | 530.647 | 1.038.399 |
26 | 67.108.864 | 7.834.012 | 3.289.340 | 4.544.672 | 3.813.267 | 1.015.927 | 1.016.105 | 1.988.713 |
27 | 134.217.728 | 15.035.066 | 6.308.973 | 8.726.093 | 7.325.101 | 1.946.256 | 1.947.933 | 3.815.776 |
28 | 268.435.456 | 28.896.081 | 12.120.212 | 16.775.869 | 14.094.827 | 3.736.020 | 3.737.528 | 7.327.706 |
29 | 536.870.912 | 55.631.554 | 23.329.402 | 32.302.152 | 27.162.772 | 7.184.569 | 7.185.864 | 14.098.349 |
30 | 1.073.741.824 | 107.248.253 | 44.969.690 | 62.278.563 | 52.414.208 | 13.835.290 | 13.834.835 | 27.163.920 |
31 | 2.147.483.648 | 207.026.636 | 86.793.674 | 120.232.962 | 101.262.266 | 26.675.480 | 26.678.019 | 52.410.871 |
32 | 4.294.967.296 | 400.134.384 | 167.714.832 | 232.419.552 | 195.854.932 | 51.505.328 | 51.511.259 | 101.262.865 |
33 | 8.589.934.592 | 774.212.170 | 324.446.680 | 449.765.490 | 379.227.149 | 99.558.758 | 99.570.821 | 195.855.442 |
34 | 17.179.869.184 | 1.499.684.373 | 628.356.227 | 871.328.146 | 735.076.499 | 192.681.502 | 192.682.193 | 379.244.179 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
4 | 16 | 3 | 3 | 0 | 0 | 0 | 1 | 2 |
5 | 32 | 10 | 5 | 5 | 1 | 1 | 4 | 4 |
6 | 64 | 21 | 9 | 12 | 3 | 3 | 7 | 8 |
7 | 128 | 39 | 16 | 23 | 6 | 5 | 13 | 15 |
8 | 256 | 82 | 35 | 47 | 14 | 14 | 29 | 25 |
9 | 512 | 189 | 77 | 112 | 36 | 41 | 57 | 55 |
10 | 1.024 | 384 | 168 | 216 | 71 | 87 | 109 | 117 |
11 | 2.048 | 822 | 367 | 455 | 167 | 202 | 219 | 234 |
12 | 4.096 | 1.777 | 818 | 959 | 387 | 443 | 461 | 486 |
13 | 8.192 | 3.739 | 1.750 | 1.989 | 823 | 928 | 989 | 999 |
14 | 16.384 | 7.771 | 3.650 | 4.121 | 1.742 | 1.915 | 2.011 | 2.103 |
15 | 32.768 | 16.147 | 7.633 | 8.514 | 3.744 | 3.948 | 4.154 | 4.301 |
16 | 65.536 | 33.136 | 15.877 | 17.259 | 7.774 | 7.991 | 8.583 | 8.788 |
17 | 131.072 | 67.912 | 32.597 | 35.315 | 16.089 | 16.330 | 17.593 | 17.900 |
18 | 262.144 | 138.636 | 66.957 | 71.679 | 32.944 | 33.665 | 35.596 | 36.431 |
19 | 524.288 | 282.308 | 136.473 | 145.835 | 67.277 | 68.565 | 72.269 | 74.197 |
20 | 1.048.576 | 573.658 | 277.958 | 295.700 | 136.847 | 139.501 | 147.261 | 150.049 |
21 | 2.097.152 | 1.164.131 | 565.204 | 598.927 | 278.898 | 283.929 | 297.701 | 303.603 |
22 | 4.194.304 | 2.357.073 | 1.147.020 | 1.210.053 | 565.731 | 575.339 | 602.575 | 613.428 |
23 | 8.388.608 | 4.769.072 | 2.324.820 | 2.444.252 | 1.146.307 | 1.166.679 | 1.217.863 | 1.238.223 |
24 | 16.777.216 | 9.632.670 | 4.701.411 | 4.931.259 | 2.323.509 | 2.357.754 | 2.454.904 | 2.496.503 |
25 | 33.554.432 | 19.441.439 | 9.503.396 | 9.938.043 | 4.698.053 | 4.764.908 | 4.949.607 | 5.028.871 |
26 | 67.108.864 | 39.207.233 | 19.188.815 | 20.018.418 | 9.488.648 | 9.615.830 | 9.974.418 | 10.128.337 |
27 | 134.217.728 | 79.001.797 | 38.706.428 | 40.295.369 | 19.153.254 | 19.391.674 | 20.079.144 | 20.377.725 |
28 | 268.435.456 | 159.093.876 | 78.033.538 | 81.060.338 | 38.627.188 | 39.085.696 | 40.405.416 | 40.975.576 |
29 | 536.870.912 | 320.197.454 | 157.188.930 | 163.008.524 | 77.842.460 | 78.732.763 | 81.258.301 | 82.363.930 |
30 | 1.073.741.824 | 644.130.388 | 316.467.104 | 327.663.284 | 156.795.077 | 158.471.134 | 163.357.370 | 165.506.807 |
31 | 2.147.483.648 | 1.295.203.367 | 636.806.312 | 658.397.055 | 315.637.707 | 318.844.419 | 328.273.263 | 332.447.978 |
32 | 4.294.967.296 | 2.603.322.383 | 1.280.796.014 | 1.322.526.369 | 635.067.575 | 641.214.515 | 659.477.059 | 667.563.234 |
33 | 8.589.934.592 | 5.230.855.193 | 2.575.046.770 | 2.655.808.423 | 1.277.235.001 | 1.289.079.817 | 1.324.394.514 | 1.340.145.861 |
34 | 17.179.869.184 | 10.506.998.187 | 5.175.345.225 | 5.331.652.962 | 2.567.774.953 | 2.590.599.977 | 2.658.941.062 | 2.689.682.195 |