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-78x+19
f(0)=19
f(1)=29
f(2)=7
f(3)=103
f(4)=277
f(5)=173
f(6)=59
f(7)=239
f(8)=541
f(9)=43
f(10)=661
f(11)=359
f(12)=773
f(13)=1
f(14)=877
f(15)=463
f(16)=139
f(17)=509
f(18)=1061
f(19)=1
f(20)=163
f(21)=31
f(22)=1213
f(23)=89
f(24)=1277
f(25)=653
f(26)=1
f(27)=97
f(28)=1381
f(29)=701
f(30)=1
f(31)=719
f(32)=1453
f(33)=733
f(34)=211
f(35)=743
f(36)=1493
f(37)=107
f(38)=79
f(39)=751
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)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=179
f(81)=131
f(82)=347
f(83)=1
f(84)=523
f(85)=307
f(86)=101
f(87)=401
f(88)=1
f(89)=499
f(90)=157
f(91)=601
f(92)=1307
f(93)=1
f(94)=1523
f(95)=1
f(96)=1747
f(97)=1
f(98)=1979
f(99)=1049
b) Substitution of the polynom
The polynom f(x)=x^2-78x+19 could be written as f(y)= y^2-1502 with x=y+39
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-39
f'(x)>2x-79 with x > 39
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 | 11 | 8 | 3 | 1.100000 | 0.800000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 48 | 37 | 11 | 0.480000 | 0.370000 | 0.480000 | 4.363636 | 4.625000 | 3.666667 |
3 | 1.000 | 716 | 344 | 372 | 0.716000 | 0.344000 | 0.716000 | 14.916667 | 9.297297 | 33.818180 |
4 | 10.000 | 7.313 | 2.460 | 4.853 | 0.731300 | 0.246000 | 0.731300 | 10.213687 | 7.151163 | 13.045699 |
5 | 100.000 | 72.683 | 18.993 | 53.690 | 0.726830 | 0.189930 | 0.726830 | 9.938876 | 7.720732 | 11.063260 |
6 | 1.000.000 | 721.343 | 154.061 | 567.282 | 0.721343 | 0.154061 | 0.721343 | 9.924508 | 8.111463 | 10.565878 |
7 | 10.000.000 | 7.171.774 | 1.300.360 | 5.871.414 | 0.717177 | 0.130036 | 0.717177 | 9.942252 | 8.440553 | 10.350080 |
8 | 100.000.000 | 71.399.376 | 11.256.281 | 60.143.095 | 0.713994 | 0.112563 | 0.713994 | 9.955608 | 8.656281 | 10.243375 |
9 | 1.000.000.000 | 711.524.240 | 99.209.253 | 612.314.987 | 0.711524 | 0.099209 | 0.711524 | 9.965412 | 8.813680 | 10.180969 |
10 | 10.000.000.000 | 7.095.689.525 | 886.948.486 | 6.208.741.039 | 0.709569 | 0.088695 | 0.709569 | 9.972520 | 8.940179 | 10.139782 |
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 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 2.000000 | 1.000000 |
3 | 8 | 9 | 7 | 2 | 1.125000 | 0.875000 | 0.250000 | 1.800000 | 1.750000 | 2.000000 |
4 | 16 | 16 | 12 | 4 | 1.000000 | 0.750000 | 0.250000 | 1.777778 | 1.714286 | 2.000000 |
5 | 32 | 28 | 21 | 7 | 0.875000 | 0.656250 | 0.218750 | 1.750000 | 1.750000 | 1.750000 |
6 | 64 | 35 | 25 | 10 | 0.546875 | 0.390625 | 0.156250 | 1.250000 | 1.190476 | 1.428571 |
7 | 128 | 69 | 51 | 18 | 0.539062 | 0.398438 | 0.140625 | 1.971429 | 2.040000 | 1.800000 |
8 | 256 | 163 | 104 | 59 | 0.636719 | 0.406250 | 0.230469 | 2.362319 | 2.039216 | 3.277778 |
9 | 512 | 355 | 194 | 161 | 0.693359 | 0.378906 | 0.314453 | 2.177914 | 1.865385 | 2.728814 |
10 | 1.024 | 734 | 350 | 384 | 0.716797 | 0.341797 | 0.375000 | 2.067606 | 1.804124 | 2.385093 |
11 | 2.048 | 1.490 | 637 | 853 | 0.727539 | 0.311035 | 0.416504 | 2.029973 | 1.820000 | 2.221354 |
12 | 4.096 | 2.988 | 1.134 | 1.854 | 0.729492 | 0.276855 | 0.452637 | 2.005369 | 1.780220 | 2.173505 |
13 | 8.192 | 5.982 | 2.068 | 3.914 | 0.730225 | 0.252441 | 0.477783 | 2.002008 | 1.823633 | 2.111111 |
14 | 16.384 | 11.999 | 3.801 | 8.198 | 0.732361 | 0.231995 | 0.500366 | 2.005851 | 1.838008 | 2.094532 |
15 | 32.768 | 23.927 | 6.957 | 16.970 | 0.730194 | 0.212311 | 0.517883 | 1.994083 | 1.830308 | 2.070017 |
16 | 65.536 | 47.691 | 12.939 | 34.752 | 0.727707 | 0.197433 | 0.530273 | 1.993188 | 1.859853 | 2.047849 |
17 | 131.072 | 95.126 | 24.229 | 70.897 | 0.725754 | 0.184853 | 0.540901 | 1.994632 | 1.872556 | 2.040084 |
18 | 262.144 | 189.817 | 45.443 | 144.374 | 0.724094 | 0.173351 | 0.550743 | 1.995427 | 1.875562 | 2.036391 |
19 | 524.288 | 378.837 | 85.210 | 293.627 | 0.722574 | 0.162525 | 0.560049 | 1.995801 | 1.875096 | 2.033794 |
20 | 1.048.576 | 756.310 | 160.910 | 595.400 | 0.721273 | 0.153456 | 0.567818 | 1.996400 | 1.888393 | 2.027743 |
21 | 2.097.152 | 1.509.818 | 304.877 | 1.204.941 | 0.719937 | 0.145377 | 0.574561 | 1.996295 | 1.894705 | 2.023750 |
22 | 4.194.304 | 3.014.171 | 579.387 | 2.434.784 | 0.718634 | 0.138137 | 0.580498 | 1.996380 | 1.900396 | 2.020667 |
23 | 8.388.608 | 6.018.520 | 1.104.080 | 4.914.440 | 0.717463 | 0.131617 | 0.585847 | 1.996741 | 1.905600 | 2.018430 |
24 | 16.777.216 | 12.019.353 | 2.107.579 | 9.911.774 | 0.716409 | 0.125621 | 0.590788 | 1.997061 | 1.908901 | 2.016867 |
25 | 33.554.432 | 24.004.099 | 4.033.625 | 19.970.474 | 0.715378 | 0.120211 | 0.595167 | 1.997121 | 1.913867 | 2.014823 |
26 | 67.108.864 | 47.947.608 | 7.735.421 | 40.212.187 | 0.714475 | 0.115267 | 0.599208 | 1.997476 | 1.917734 | 2.013582 |
27 | 134.217.728 | 95.785.131 | 14.852.098 | 80.933.033 | 0.713655 | 0.110657 | 0.602998 | 1.997704 | 1.920012 | 2.012649 |
28 | 268.435.456 | 191.360.126 | 28.565.934 | 162.794.192 | 0.712872 | 0.106416 | 0.606456 | 1.997806 | 1.923360 | 2.011468 |
29 | 536.870.912 | 382.329.554 | 55.023.056 | 327.306.498 | 0.712144 | 0.102488 | 0.609656 | 1.997958 | 1.926177 | 2.010554 |
30 | 1.073.741.824 | 763.923.489 | 106.137.732 | 657.785.757 | 0.711459 | 0.098848 | 0.612611 | 1.998076 | 1.928968 | 2.009693 |
31 | 2.147.483.648 | 1.526.491.712 | 204.983.008 | 1.321.508.704 | 0.710828 | 0.095453 | 0.615375 | 1.998226 | 1.931293 | 2.009026 |
32 | 4.294.967.296 | 3.050.436.676 | 396.368.691 | 2.654.067.985 | 0.710235 | 0.092287 | 0.617948 | 1.998332 | 1.933666 | 2.008362 |
33 | 8.589.934.592 | 6.096.160.128 | 767.245.785 | 5.328.914.343 | 0.709686 | 0.089319 | 0.620367 | 1.998455 | 1.935687 | 2.007829 |
34 | 17.179.869.184 | 12.183.393.457 | 1.486.799.473 | 10.696.593.984 | 0.709167 | 0.086543 | 0.622624 | 1.998536 | 1.937840 | 2.007275 |
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 | 1 | 1 | 0 | 1 | 1 | 0 |
2 | 4 | 4 | 3 | 1 | 0 | 1 | 2 | 1 |
3 | 8 | 7 | 4 | 3 | 0 | 1 | 4 | 2 |
4 | 16 | 12 | 7 | 5 | 0 | 1 | 7 | 4 |
5 | 32 | 21 | 10 | 11 | 0 | 1 | 15 | 5 |
6 | 64 | 25 | 12 | 13 | 0 | 1 | 17 | 7 |
7 | 128 | 51 | 27 | 24 | 7 | 20 | 17 | 7 |
8 | 256 | 104 | 52 | 52 | 19 | 61 | 17 | 7 |
9 | 512 | 194 | 98 | 96 | 43 | 127 | 17 | 7 |
10 | 1.024 | 350 | 180 | 170 | 86 | 240 | 17 | 7 |
11 | 2.048 | 637 | 322 | 315 | 153 | 460 | 17 | 7 |
12 | 4.096 | 1.134 | 579 | 555 | 290 | 820 | 17 | 7 |
13 | 8.192 | 2.068 | 1.043 | 1.025 | 531 | 1.513 | 17 | 7 |
14 | 16.384 | 3.801 | 1.904 | 1.897 | 974 | 2.803 | 17 | 7 |
15 | 32.768 | 6.957 | 3.506 | 3.451 | 1.782 | 5.151 | 17 | 7 |
16 | 65.536 | 12.939 | 6.508 | 6.431 | 3.318 | 9.597 | 17 | 7 |
17 | 131.072 | 24.229 | 12.215 | 12.014 | 6.202 | 18.003 | 17 | 7 |
18 | 262.144 | 45.443 | 22.893 | 22.550 | 11.541 | 33.878 | 17 | 7 |
19 | 524.288 | 85.210 | 42.892 | 42.318 | 21.583 | 63.603 | 17 | 7 |
20 | 1.048.576 | 160.910 | 80.966 | 79.944 | 40.791 | 120.095 | 17 | 7 |
21 | 2.097.152 | 304.877 | 153.329 | 151.548 | 77.264 | 227.589 | 17 | 7 |
22 | 4.194.304 | 579.387 | 291.072 | 288.315 | 146.620 | 432.743 | 17 | 7 |
23 | 8.388.608 | 1.104.080 | 554.077 | 550.003 | 279.320 | 824.736 | 17 | 7 |
24 | 16.777.216 | 2.107.579 | 1.058.131 | 1.049.448 | 533.364 | 1.574.191 | 17 | 7 |
25 | 33.554.432 | 4.033.625 | 2.024.409 | 2.009.216 | 1.020.124 | 3.013.477 | 17 | 7 |
26 | 67.108.864 | 7.735.421 | 3.882.517 | 3.852.904 | 1.955.197 | 5.780.200 | 17 | 7 |
27 | 134.217.728 | 14.852.098 | 7.453.071 | 7.399.027 | 3.750.741 | 11.101.333 | 17 | 7 |
28 | 268.435.456 | 28.565.934 | 14.330.349 | 14.235.585 | 7.211.717 | 21.354.193 | 17 | 7 |
29 | 536.870.912 | 55.023.056 | 27.597.373 | 27.425.683 | 13.883.903 | 41.139.129 | 17 | 7 |
30 | 1.073.741.824 | 106.137.732 | 53.225.359 | 52.912.373 | 26.769.981 | 79.367.727 | 17 | 7 |
31 | 2.147.483.648 | 204.983.008 | 102.788.086 | 102.194.922 | 51.685.415 | 153.297.569 | 17 | 7 |
32 | 4.294.967.296 | 396.368.691 | 198.732.289 | 197.636.402 | 99.904.312 | 296.464.355 | 17 | 7 |
33 | 8.589.934.592 | 767.245.785 | 384.645.511 | 382.600.274 | 193.332.733 | 573.913.028 | 17 | 7 |
34 | 17.179.869.184 | 1.486.799.473 | 745.321.739 | 741.477.734 | 374.571.417 | 1.112.228.032 | 17 | 7 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 4 | 3 | 1 | 0 | 3 | 0 | 1 |
5 | 32 | 7 | 5 | 2 | 2 | 4 | 0 | 1 |
6 | 64 | 10 | 7 | 3 | 2 | 6 | 0 | 2 |
7 | 128 | 18 | 10 | 8 | 3 | 6 | 5 | 4 |
8 | 256 | 59 | 29 | 30 | 10 | 10 | 24 | 15 |
9 | 512 | 161 | 81 | 80 | 34 | 24 | 64 | 39 |
10 | 1.024 | 384 | 186 | 198 | 89 | 62 | 149 | 84 |
11 | 2.048 | 853 | 424 | 429 | 195 | 153 | 302 | 203 |
12 | 4.096 | 1.854 | 912 | 942 | 422 | 332 | 640 | 460 |
13 | 8.192 | 3.914 | 1.920 | 1.994 | 895 | 764 | 1.288 | 967 |
14 | 16.384 | 8.198 | 4.033 | 4.165 | 1.923 | 1.616 | 2.617 | 2.042 |
15 | 32.768 | 16.970 | 8.436 | 8.534 | 4.032 | 3.406 | 5.242 | 4.290 |
16 | 65.536 | 34.752 | 17.377 | 17.375 | 8.309 | 7.089 | 10.615 | 8.739 |
17 | 131.072 | 70.897 | 35.415 | 35.482 | 17.019 | 14.766 | 21.254 | 17.858 |
18 | 262.144 | 144.374 | 72.021 | 72.353 | 34.590 | 30.592 | 42.702 | 36.490 |
19 | 524.288 | 293.627 | 146.869 | 146.758 | 70.567 | 63.181 | 85.701 | 74.178 |
20 | 1.048.576 | 595.400 | 297.867 | 297.533 | 143.691 | 129.523 | 172.326 | 149.860 |
21 | 2.097.152 | 1.204.941 | 602.387 | 602.554 | 291.730 | 265.302 | 344.869 | 303.040 |
22 | 4.194.304 | 2.434.784 | 1.218.233 | 1.216.551 | 590.505 | 540.428 | 691.577 | 612.274 |
23 | 8.388.608 | 4.914.440 | 2.457.840 | 2.456.600 | 1.194.873 | 1.098.420 | 1.386.806 | 1.234.341 |
24 | 16.777.216 | 9.911.774 | 4.958.219 | 4.953.555 | 2.412.972 | 2.231.442 | 2.779.259 | 2.488.101 |
25 | 33.554.432 | 19.970.474 | 9.990.977 | 9.979.497 | 4.868.374 | 4.522.796 | 5.566.760 | 5.012.544 |
26 | 67.108.864 | 40.212.187 | 20.115.968 | 20.096.219 | 9.816.427 | 9.152.754 | 11.151.665 | 10.091.341 |
27 | 134.217.728 | 80.933.033 | 40.483.747 | 40.449.286 | 19.786.019 | 18.510.805 | 22.334.776 | 20.301.433 |
28 | 268.435.456 | 162.794.192 | 81.430.324 | 81.363.868 | 39.843.227 | 37.393.351 | 44.732.979 | 40.824.635 |
29 | 536.870.912 | 327.306.498 | 163.712.134 | 163.594.364 | 80.183.389 | 75.481.167 | 89.576.302 | 82.065.640 |
30 | 1.073.741.824 | 657.785.757 | 329.001.454 | 328.784.303 | 161.284.392 | 152.219.652 | 179.377.676 | 164.904.037 |
31 | 2.147.483.648 | 1.321.508.704 | 660.950.644 | 660.558.060 | 324.271.513 | 306.814.926 | 359.181.360 | 331.240.905 |
32 | 4.294.967.296 | 2.654.067.985 | 1.327.374.252 | 1.326.693.733 | 651.686.023 | 618.057.496 | 719.205.093 | 665.119.373 |
33 | 8.589.934.592 | 5.328.914.343 | 2.665.111.051 | 2.663.803.292 | 1.309.348.414 | 1.244.383.938 | 1.439.888.433 | 1.335.293.558 |
34 | 17.179.869.184 | 10.696.593.984 | 5.349.468.434 | 5.347.125.550 | 2.629.823.309 | 2.504.241.778 | 2.882.598.217 | 2.679.930.680 |