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+53x-73
f(0)=73
f(1)=19
f(2)=37
f(3)=5
f(4)=31
f(5)=7
f(6)=281
f(7)=347
f(8)=83
f(9)=97
f(10)=557
f(11)=631
f(12)=101
f(13)=157
f(14)=173
f(15)=947
f(16)=1031
f(17)=1117
f(18)=241
f(19)=1
f(20)=1
f(21)=1481
f(22)=1
f(23)=67
f(24)=71
f(25)=1877
f(26)=283
f(27)=2087
f(28)=439
f(29)=461
f(30)=2417
f(31)=2531
f(32)=2647
f(33)=79
f(34)=577
f(35)=1
f(36)=1
f(37)=3257
f(38)=677
f(39)=1
f(40)=521
f(41)=199
f(42)=3917
f(43)=811
f(44)=839
f(45)=4337
f(46)=4481
f(47)=661
f(48)=191
f(49)=197
f(50)=5077
f(51)=5231
f(52)=5387
f(53)=1109
f(54)=163
f(55)=5867
f(56)=1
f(57)=6197
f(58)=1
f(59)=1307
f(60)=353
f(61)=983
f(62)=7057
f(63)=1447
f(64)=1483
f(65)=107
f(66)=251
f(67)=257
f(68)=233
f(69)=1669
f(70)=8537
f(71)=8731
f(72)=113
f(73)=1
f(74)=373
f(75)=1361
f(76)=263
f(77)=523
f(78)=2029
f(79)=109
f(80)=10567
f(81)=10781
f(82)=1571
f(83)=2243
f(84)=2287
f(85)=11657
f(86)=1
f(87)=12107
f(88)=2467
f(89)=359
f(90)=1
f(91)=1
f(92)=13267
f(93)=1
f(94)=2749
f(95)=1
f(96)=1
f(97)=467
f(98)=1
f(99)=599
b) Substitution of the polynom
The polynom f(x)=x^2+53x-73 could be written as f(y)= y^2-775.25 with x=y-26.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+26.5
f'(x)>2x+52
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 | 7 | 3 | 1.000000 | 0.700000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 35 | 46 | 0.810000 | 0.350000 | 0.810000 | 8.100000 | 5.000000 | 15.333333 |
3 | 1.000 | 735 | 241 | 494 | 0.735000 | 0.241000 | 0.735000 | 9.074074 | 6.885714 | 10.739130 |
4 | 10.000 | 7.257 | 1.695 | 5.562 | 0.725700 | 0.169500 | 0.725700 | 9.873469 | 7.033195 | 11.259109 |
5 | 100.000 | 71.861 | 13.194 | 58.667 | 0.718610 | 0.131940 | 0.718610 | 9.902301 | 7.784071 | 10.547825 |
6 | 1.000.000 | 714.351 | 108.003 | 606.348 | 0.714351 | 0.108003 | 0.714351 | 9.940733 | 8.185766 | 10.335419 |
7 | 10.000.000 | 7.112.340 | 913.630 | 6.198.710 | 0.711234 | 0.091363 | 0.711234 | 9.956366 | 8.459302 | 10.223023 |
8 | 100.000.000 | 70.874.620 | 7.914.573 | 62.960.047 | 0.708746 | 0.079146 | 0.708746 | 9.965022 | 8.662777 | 10.156960 |
9 | 1.000.000.000 | 706.871.170 | 69.813.684 | 637.057.486 | 0.706871 | 0.069814 | 0.706871 | 9.973544 | 8.820903 | 10.118440 |
10 | 10.000.000.000 | 7.053.976.927 | 624.828.918 | 6.429.148.009 | 0.705398 | 0.062483 | 0.705398 | 9.979156 | 8.949950 | 10.091944 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.000000 | inf |
3 | 8 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 2.000000 | 2.000000 | 2.000000 |
4 | 16 | 16 | 10 | 6 | 1.000000 | 0.625000 | 0.375000 | 2.000000 | 1.666667 | 3.000000 |
5 | 32 | 29 | 17 | 12 | 0.906250 | 0.531250 | 0.375000 | 1.812500 | 1.700000 | 2.000000 |
6 | 64 | 56 | 27 | 29 | 0.875000 | 0.421875 | 0.453125 | 1.931034 | 1.588235 | 2.416667 |
7 | 128 | 100 | 43 | 57 | 0.781250 | 0.335938 | 0.445312 | 1.785714 | 1.592593 | 1.965517 |
8 | 256 | 196 | 79 | 117 | 0.765625 | 0.308594 | 0.457031 | 1.960000 | 1.837209 | 2.052632 |
9 | 512 | 390 | 139 | 251 | 0.761719 | 0.271484 | 0.490234 | 1.989796 | 1.759494 | 2.145299 |
10 | 1.024 | 754 | 247 | 507 | 0.736328 | 0.241211 | 0.495117 | 1.933333 | 1.776978 | 2.019920 |
11 | 2.048 | 1.504 | 433 | 1.071 | 0.734375 | 0.211426 | 0.522949 | 1.994695 | 1.753036 | 2.112426 |
12 | 4.096 | 2.998 | 773 | 2.225 | 0.731934 | 0.188721 | 0.543213 | 1.993351 | 1.785219 | 2.077498 |
13 | 8.192 | 5.956 | 1.426 | 4.530 | 0.727051 | 0.174072 | 0.552979 | 1.986658 | 1.844761 | 2.035955 |
14 | 16.384 | 11.852 | 2.604 | 9.248 | 0.723389 | 0.158936 | 0.564453 | 1.989926 | 1.826087 | 2.041501 |
15 | 32.768 | 23.568 | 4.863 | 18.705 | 0.719238 | 0.148407 | 0.570831 | 1.988525 | 1.867512 | 2.022599 |
16 | 65.536 | 47.121 | 8.978 | 38.143 | 0.719009 | 0.136993 | 0.582016 | 1.999364 | 1.846185 | 2.039187 |
17 | 131.072 | 94.124 | 16.821 | 77.303 | 0.718109 | 0.128334 | 0.589775 | 1.997496 | 1.873580 | 2.026663 |
18 | 262.144 | 187.850 | 31.645 | 156.205 | 0.716591 | 0.120716 | 0.595875 | 1.995772 | 1.881279 | 2.020685 |
19 | 524.288 | 374.896 | 59.722 | 315.174 | 0.715057 | 0.113911 | 0.601147 | 1.995720 | 1.887249 | 2.017695 |
20 | 1.048.576 | 748.962 | 112.903 | 636.059 | 0.714266 | 0.107673 | 0.606593 | 1.997786 | 1.890476 | 2.018120 |
21 | 2.097.152 | 1.495.793 | 214.011 | 1.281.782 | 0.713250 | 0.102048 | 0.611201 | 1.997155 | 1.895530 | 2.015193 |
22 | 4.194.304 | 2.987.497 | 407.231 | 2.580.266 | 0.712275 | 0.097091 | 0.615183 | 1.997266 | 1.902851 | 2.013030 |
23 | 8.388.608 | 5.968.021 | 775.552 | 5.192.469 | 0.711444 | 0.092453 | 0.618991 | 1.997666 | 1.904452 | 2.012378 |
24 | 16.777.216 | 11.922.066 | 1.480.438 | 10.441.628 | 0.710611 | 0.088241 | 0.622370 | 1.997658 | 1.908883 | 2.010918 |
25 | 33.554.432 | 23.818.115 | 2.835.256 | 20.982.859 | 0.709835 | 0.084497 | 0.625338 | 1.997818 | 1.915147 | 2.009539 |
26 | 67.108.864 | 47.588.104 | 5.438.794 | 42.149.310 | 0.709118 | 0.081044 | 0.628074 | 1.997979 | 1.918273 | 2.008750 |
27 | 134.217.728 | 95.089.834 | 10.443.197 | 84.646.637 | 0.708474 | 0.077808 | 0.630667 | 1.998185 | 1.920131 | 2.008257 |
28 | 268.435.456 | 190.018.773 | 20.093.973 | 169.924.800 | 0.707875 | 0.074856 | 0.633019 | 1.998308 | 1.924121 | 2.007461 |
29 | 536.870.912 | 379.743.099 | 38.713.778 | 341.029.321 | 0.707327 | 0.072110 | 0.635217 | 1.998451 | 1.926636 | 2.006943 |
30 | 1.073.741.824 | 758.940.497 | 74.690.717 | 684.249.780 | 0.706818 | 0.069561 | 0.637257 | 1.998563 | 1.929306 | 2.006425 |
31 | 2.147.483.648 | 1.516.864.900 | 144.310.509 | 1.372.554.391 | 0.706345 | 0.067200 | 0.639145 | 1.998661 | 1.932108 | 2.005926 |
32 | 4.294.967.296 | 3.031.818.500 | 279.132.290 | 2.752.686.210 | 0.705900 | 0.064991 | 0.640910 | 1.998740 | 1.934248 | 2.005521 |
33 | 8.589.934.592 | 6.060.054.801 | 540.481.084 | 5.519.573.717 | 0.705483 | 0.062920 | 0.642563 | 1.998819 | 1.936290 | 2.005159 |
34 | 17.179.869.184 | 12.113.461.982 | 1.047.582.828 | 11.065.879.154 | 0.705096 | 0.060977 | 0.644119 | 1.998903 | 1.938241 | 2.004843 |
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 | 3 | 0 | 1 | 1 | 1 | 0 |
2 | 4 | 3 | 3 | 0 | 1 | 1 | 1 | 0 |
3 | 8 | 6 | 4 | 2 | 3 | 2 | 1 | 0 |
4 | 16 | 10 | 5 | 5 | 3 | 3 | 2 | 2 |
5 | 32 | 17 | 7 | 10 | 5 | 4 | 4 | 4 |
6 | 64 | 27 | 9 | 18 | 9 | 6 | 7 | 5 |
7 | 128 | 43 | 15 | 28 | 13 | 13 | 10 | 7 |
8 | 256 | 79 | 26 | 53 | 22 | 20 | 18 | 19 |
9 | 512 | 139 | 46 | 93 | 36 | 34 | 34 | 35 |
10 | 1.024 | 247 | 83 | 164 | 62 | 64 | 59 | 62 |
11 | 2.048 | 433 | 146 | 287 | 108 | 112 | 106 | 107 |
12 | 4.096 | 773 | 266 | 507 | 188 | 197 | 201 | 187 |
13 | 8.192 | 1.426 | 483 | 943 | 344 | 367 | 354 | 361 |
14 | 16.384 | 2.604 | 879 | 1.725 | 643 | 663 | 659 | 639 |
15 | 32.768 | 4.863 | 1.642 | 3.221 | 1.220 | 1.219 | 1.199 | 1.225 |
16 | 65.536 | 8.978 | 3.003 | 5.975 | 2.272 | 2.203 | 2.225 | 2.278 |
17 | 131.072 | 16.821 | 5.580 | 11.241 | 4.231 | 4.147 | 4.208 | 4.235 |
18 | 262.144 | 31.645 | 10.576 | 21.069 | 7.961 | 7.923 | 7.824 | 7.937 |
19 | 524.288 | 59.722 | 19.957 | 39.765 | 15.040 | 14.884 | 14.874 | 14.924 |
20 | 1.048.576 | 112.903 | 37.585 | 75.318 | 28.330 | 28.141 | 28.224 | 28.208 |
21 | 2.097.152 | 214.011 | 71.362 | 142.649 | 53.450 | 53.312 | 53.658 | 53.591 |
22 | 4.194.304 | 407.231 | 135.731 | 271.500 | 101.767 | 101.690 | 102.045 | 101.729 |
23 | 8.388.608 | 775.552 | 258.556 | 516.996 | 193.646 | 193.740 | 194.304 | 193.862 |
24 | 16.777.216 | 1.480.438 | 493.824 | 986.614 | 369.972 | 369.758 | 370.670 | 370.038 |
25 | 33.554.432 | 2.835.256 | 945.562 | 1.889.694 | 708.950 | 708.328 | 709.407 | 708.571 |
26 | 67.108.864 | 5.438.794 | 1.813.027 | 3.625.767 | 1.360.298 | 1.358.604 | 1.360.458 | 1.359.434 |
27 | 134.217.728 | 10.443.197 | 3.479.675 | 6.963.522 | 2.610.428 | 2.611.049 | 2.611.314 | 2.610.406 |
28 | 268.435.456 | 20.093.973 | 6.697.414 | 13.396.559 | 5.024.331 | 5.025.025 | 5.021.752 | 5.022.865 |
29 | 536.870.912 | 38.713.778 | 12.905.927 | 25.807.851 | 9.680.107 | 9.680.296 | 9.675.611 | 9.677.764 |
30 | 1.073.741.824 | 74.690.717 | 24.899.086 | 49.791.631 | 18.672.325 | 18.677.229 | 18.669.267 | 18.671.896 |
31 | 2.147.483.648 | 144.310.509 | 48.106.615 | 96.203.894 | 36.078.397 | 36.083.731 | 36.074.260 | 36.074.121 |
32 | 4.294.967.296 | 279.132.290 | 93.048.728 | 186.083.562 | 69.784.693 | 69.788.855 | 69.783.028 | 69.775.714 |
33 | 8.589.934.592 | 540.481.084 | 180.167.870 | 360.313.214 | 135.121.294 | 135.124.732 | 135.122.612 | 135.112.446 |
34 | 17.179.869.184 | 1.047.582.828 | 349.201.334 | 698.381.494 | 261.912.072 | 261.893.194 | 261.893.101 | 261.884.461 |
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 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 6 | 3 | 3 | 1 | 1 | 3 | 1 |
5 | 32 | 12 | 7 | 5 | 2 | 3 | 4 | 3 |
6 | 64 | 29 | 15 | 14 | 5 | 7 | 8 | 9 |
7 | 128 | 57 | 29 | 28 | 10 | 15 | 15 | 17 |
8 | 256 | 117 | 62 | 55 | 27 | 28 | 32 | 30 |
9 | 512 | 251 | 127 | 124 | 56 | 62 | 64 | 69 |
10 | 1.024 | 507 | 265 | 242 | 124 | 128 | 127 | 128 |
11 | 2.048 | 1.071 | 537 | 534 | 259 | 271 | 270 | 271 |
12 | 4.096 | 2.225 | 1.129 | 1.096 | 553 | 572 | 539 | 561 |
13 | 8.192 | 4.530 | 2.306 | 2.224 | 1.108 | 1.175 | 1.106 | 1.141 |
14 | 16.384 | 9.248 | 4.717 | 4.531 | 2.290 | 2.375 | 2.302 | 2.281 |
15 | 32.768 | 18.705 | 9.533 | 9.172 | 4.611 | 4.732 | 4.710 | 4.652 |
16 | 65.536 | 38.143 | 19.411 | 18.732 | 9.500 | 9.589 | 9.537 | 9.517 |
17 | 131.072 | 77.303 | 39.336 | 37.967 | 19.203 | 19.402 | 19.382 | 19.316 |
18 | 262.144 | 156.205 | 79.357 | 76.848 | 38.966 | 38.959 | 39.037 | 39.243 |
19 | 524.288 | 315.174 | 160.248 | 154.926 | 78.539 | 78.768 | 78.890 | 78.977 |
20 | 1.048.576 | 636.059 | 322.608 | 313.451 | 158.662 | 159.046 | 158.798 | 159.553 |
21 | 2.097.152 | 1.281.782 | 649.260 | 632.522 | 319.965 | 320.779 | 320.050 | 320.988 |
22 | 4.194.304 | 2.580.266 | 1.305.383 | 1.274.883 | 644.735 | 645.860 | 644.368 | 645.303 |
23 | 8.388.608 | 5.192.469 | 2.624.304 | 2.568.165 | 1.296.608 | 1.298.608 | 1.298.632 | 1.298.621 |
24 | 16.777.216 | 10.441.628 | 5.276.798 | 5.164.830 | 2.609.922 | 2.610.235 | 2.610.599 | 2.610.872 |
25 | 33.554.432 | 20.982.859 | 10.595.888 | 10.386.971 | 5.245.427 | 5.247.152 | 5.246.576 | 5.243.704 |
26 | 67.108.864 | 42.149.310 | 21.274.500 | 20.874.810 | 10.536.007 | 10.534.774 | 10.540.693 | 10.537.836 |
27 | 134.217.728 | 84.646.637 | 42.711.936 | 41.934.701 | 21.157.573 | 21.159.579 | 21.163.097 | 21.166.388 |
28 | 268.435.456 | 169.924.800 | 85.704.653 | 84.220.147 | 42.474.677 | 42.479.127 | 42.483.615 | 42.487.381 |
29 | 536.870.912 | 341.029.321 | 171.945.569 | 169.083.752 | 85.244.614 | 85.247.855 | 85.265.217 | 85.271.635 |
30 | 1.073.741.824 | 684.249.780 | 344.876.745 | 339.373.035 | 171.054.906 | 171.050.212 | 171.076.618 | 171.068.044 |
31 | 2.147.483.648 | 1.372.554.391 | 691.584.652 | 680.969.739 | 343.135.754 | 343.134.262 | 343.140.187 | 343.144.188 |
32 | 4.294.967.296 | 2.752.686.210 | 1.386.596.740 | 1.366.089.470 | 688.156.269 | 688.164.772 | 688.175.398 | 688.189.771 |
33 | 8.589.934.592 | 5.519.573.717 | 2.779.611.900 | 2.739.961.817 | 1.379.879.980 | 1.379.897.387 | 1.379.876.205 | 1.379.920.145 |
34 | 17.179.869.184 | 11.065.879.154 | 5.571.328.901 | 5.494.550.253 | 2.766.505.982 | 2.766.510.244 | 2.766.416.220 | 2.766.446.708 |