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-44x+17
f(0)=17
f(1)=13
f(2)=67
f(3)=53
f(4)=11
f(5)=89
f(6)=211
f(7)=1
f(8)=271
f(9)=149
f(10)=19
f(11)=173
f(12)=367
f(13)=193
f(14)=31
f(15)=1
f(16)=431
f(17)=1
f(18)=41
f(19)=229
f(20)=463
f(21)=233
f(22)=467
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
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)=109
f(47)=79
f(48)=1
f(49)=131
f(50)=317
f(51)=1
f(52)=433
f(53)=1
f(54)=557
f(55)=311
f(56)=1
f(57)=379
f(58)=829
f(59)=1
f(60)=977
f(61)=1
f(62)=103
f(63)=607
f(64)=1297
f(65)=691
f(66)=113
f(67)=1
f(68)=97
f(69)=1
f(70)=167
f(71)=967
f(72)=107
f(73)=1
f(74)=2237
f(75)=1171
f(76)=1
f(77)=1279
f(78)=157
f(79)=1
f(80)=2897
f(81)=137
f(82)=241
f(83)=1627
f(84)=307
f(85)=1
f(86)=191
f(87)=1879
f(88)=3889
f(89)=2011
f(90)=4157
f(91)=1
f(92)=1
f(93)=2287
f(94)=1
f(95)=1
f(96)=5009
f(97)=2579
f(98)=5309
f(99)=2731
b) Substitution of the polynom
The polynom f(x)=x^2-44x+17 could be written as f(y)= y^2-467 with x=y+22
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-22
f'(x)>2x-45 with x > 22
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 | 51 | 43 | 8 | 0.510000 | 0.430000 | 0.080000 | 5.666667 | 5.375000 | 8.000000 |
3 | 1.000 | 664 | 305 | 359 | 0.664000 | 0.305000 | 0.359000 | 13.019608 | 7.093023 | 44.875000 |
4 | 10.000 | 7.014 | 2.123 | 4.891 | 0.701400 | 0.212300 | 0.489100 | 10.563253 | 6.960656 | 13.623956 |
5 | 100.000 | 70.273 | 16.554 | 53.719 | 0.702730 | 0.165540 | 0.537190 | 10.018962 | 7.797456 | 10.983234 |
6 | 1.000.000 | 701.766 | 134.600 | 567.166 | 0.701766 | 0.134600 | 0.567166 | 9.986282 | 8.130965 | 10.558015 |
7 | 10.000.000 | 7.002.389 | 1.134.762 | 5.867.627 | 0.700239 | 0.113476 | 0.586763 | 9.978239 | 8.430624 | 10.345520 |
8 | 100.000.000 | 69.920.485 | 9.827.916 | 60.092.569 | 0.699205 | 0.098279 | 0.600926 | 9.985233 | 8.660773 | 10.241375 |
9 | 1.000.000.000 | 698.445.819 | 86.604.312 | 611.841.507 | 0.698446 | 0.086604 | 0.611842 | 9.989144 | 8.812073 | 10.181651 |
10 | 10.000.000.000 | 6.978.385.869 | 774.274.993 | 6.204.110.876 | 0.697839 | 0.077427 | 0.620411 | 9.991306 | 8.940374 | 10.140061 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 14 | 12 | 2 | 0.875000 | 0.750000 | 0.125000 | 1.750000 | 1.714286 | 2.000000 |
5 | 32 | 19 | 16 | 3 | 0.593750 | 0.500000 | 0.093750 | 1.357143 | 1.333333 | 1.500000 |
6 | 64 | 30 | 27 | 3 | 0.468750 | 0.421875 | 0.046875 | 1.578947 | 1.687500 | 1.000000 |
7 | 128 | 72 | 52 | 20 | 0.562500 | 0.406250 | 0.156250 | 2.400000 | 1.925926 | 6.666667 |
8 | 256 | 162 | 98 | 64 | 0.632812 | 0.382812 | 0.250000 | 2.250000 | 1.884615 | 3.200000 |
9 | 512 | 333 | 175 | 158 | 0.650391 | 0.341797 | 0.308594 | 2.055556 | 1.785714 | 2.468750 |
10 | 1.024 | 677 | 308 | 369 | 0.661133 | 0.300781 | 0.360352 | 2.033033 | 1.760000 | 2.335443 |
11 | 2.048 | 1.405 | 558 | 847 | 0.686035 | 0.272461 | 0.413574 | 2.075332 | 1.811688 | 2.295393 |
12 | 4.096 | 2.848 | 985 | 1.863 | 0.695312 | 0.240479 | 0.454834 | 2.027046 | 1.765233 | 2.199528 |
13 | 8.192 | 5.729 | 1.776 | 3.953 | 0.699341 | 0.216797 | 0.482544 | 2.011587 | 1.803046 | 2.121846 |
14 | 16.384 | 11.514 | 3.262 | 8.252 | 0.702759 | 0.199097 | 0.503662 | 2.009775 | 1.836712 | 2.087528 |
15 | 32.768 | 23.004 | 6.119 | 16.885 | 0.702026 | 0.186737 | 0.515289 | 1.997916 | 1.875843 | 2.046171 |
16 | 65.536 | 46.058 | 11.370 | 34.688 | 0.702789 | 0.173492 | 0.529297 | 2.002173 | 1.858147 | 2.054368 |
17 | 131.072 | 92.145 | 21.126 | 71.019 | 0.703011 | 0.161179 | 0.541832 | 2.000630 | 1.858047 | 2.047365 |
18 | 262.144 | 184.144 | 39.533 | 144.611 | 0.702454 | 0.150806 | 0.551647 | 1.998416 | 1.871296 | 2.036230 |
19 | 524.288 | 368.251 | 74.404 | 293.847 | 0.702383 | 0.141914 | 0.560469 | 1.999799 | 1.882073 | 2.031982 |
20 | 1.048.576 | 735.987 | 140.490 | 595.497 | 0.701892 | 0.133982 | 0.567910 | 1.998602 | 1.888205 | 2.026555 |
21 | 2.097.152 | 1.470.803 | 266.103 | 1.204.700 | 0.701334 | 0.126888 | 0.574446 | 1.998409 | 1.894106 | 2.023016 |
22 | 4.194.304 | 2.939.202 | 505.751 | 2.433.451 | 0.700760 | 0.120580 | 0.580180 | 1.998366 | 1.900584 | 2.019964 |
23 | 8.388.608 | 5.874.878 | 963.205 | 4.911.673 | 0.700340 | 0.114823 | 0.585517 | 1.998800 | 1.904504 | 2.018398 |
24 | 16.777.216 | 11.743.632 | 1.840.172 | 9.903.460 | 0.699975 | 0.109683 | 0.590292 | 1.998958 | 1.910468 | 2.016311 |
25 | 33.554.432 | 23.476.744 | 3.523.149 | 19.953.595 | 0.699661 | 0.104998 | 0.594664 | 1.999104 | 1.914576 | 2.014811 |
26 | 67.108.864 | 46.932.419 | 6.754.251 | 40.178.168 | 0.699348 | 0.100646 | 0.598701 | 1.999103 | 1.917106 | 2.013580 |
27 | 134.217.728 | 93.831.723 | 12.967.315 | 80.864.408 | 0.699101 | 0.096614 | 0.602487 | 1.999294 | 1.919875 | 2.012645 |
28 | 268.435.456 | 187.600.762 | 24.938.283 | 162.662.479 | 0.698867 | 0.092902 | 0.605965 | 1.999332 | 1.923165 | 2.011546 |
29 | 536.870.912 | 375.074.722 | 48.035.060 | 327.039.662 | 0.698631 | 0.089472 | 0.609159 | 1.999324 | 1.926157 | 2.010541 |
30 | 1.073.741.824 | 749.929.475 | 92.648.285 | 657.281.190 | 0.698426 | 0.086285 | 0.612141 | 1.999413 | 1.928764 | 2.009791 |
31 | 2.147.483.648 | 1.499.437.198 | 178.935.448 | 1.320.501.750 | 0.698230 | 0.083323 | 0.614907 | 1.999438 | 1.931341 | 2.009036 |
32 | 4.294.967.296 | 2.998.082.719 | 345.986.445 | 2.652.096.274 | 0.698046 | 0.080556 | 0.617489 | 1.999472 | 1.933582 | 2.008400 |
33 | 8.589.934.592 | 5.994.702.819 | 669.767.543 | 5.324.935.276 | 0.697875 | 0.077971 | 0.619904 | 1.999512 | 1.935820 | 2.007821 |
34 | 17.179.869.184 | 11.986.687.210 | 1.297.900.805 | 10.688.786.405 | 0.697717 | 0.075548 | 0.622169 | 1.999547 | 1.937838 | 2.007308 |
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 | 2 | 1 | 1 | 1 | 1 | 0 |
2 | 4 | 4 | 2 | 2 | 1 | 1 | 2 | 0 |
3 | 8 | 7 | 4 | 3 | 2 | 2 | 2 | 1 |
4 | 16 | 12 | 6 | 6 | 3 | 2 | 4 | 3 |
5 | 32 | 16 | 8 | 8 | 4 | 3 | 5 | 4 |
6 | 64 | 27 | 14 | 13 | 7 | 5 | 9 | 6 |
7 | 128 | 52 | 27 | 25 | 13 | 13 | 13 | 13 |
8 | 256 | 98 | 49 | 49 | 28 | 23 | 24 | 23 |
9 | 512 | 175 | 84 | 91 | 44 | 41 | 44 | 46 |
10 | 1.024 | 308 | 151 | 157 | 77 | 75 | 72 | 84 |
11 | 2.048 | 558 | 277 | 281 | 130 | 140 | 137 | 151 |
12 | 4.096 | 985 | 496 | 489 | 234 | 255 | 242 | 254 |
13 | 8.192 | 1.776 | 876 | 900 | 432 | 453 | 437 | 454 |
14 | 16.384 | 3.262 | 1.624 | 1.638 | 805 | 849 | 786 | 822 |
15 | 32.768 | 6.119 | 3.048 | 3.071 | 1.513 | 1.554 | 1.482 | 1.570 |
16 | 65.536 | 11.370 | 5.667 | 5.703 | 2.802 | 2.919 | 2.791 | 2.858 |
17 | 131.072 | 21.126 | 10.560 | 10.566 | 5.187 | 5.401 | 5.199 | 5.339 |
18 | 262.144 | 39.533 | 19.778 | 19.755 | 9.728 | 9.997 | 9.754 | 10.054 |
19 | 524.288 | 74.404 | 37.333 | 37.071 | 18.314 | 18.737 | 18.366 | 18.987 |
20 | 1.048.576 | 140.490 | 70.487 | 70.003 | 34.629 | 35.385 | 34.765 | 35.711 |
21 | 2.097.152 | 266.103 | 133.656 | 132.447 | 65.646 | 67.221 | 65.710 | 67.526 |
22 | 4.194.304 | 505.751 | 254.023 | 251.728 | 124.776 | 127.559 | 124.938 | 128.478 |
23 | 8.388.608 | 963.205 | 483.574 | 479.631 | 238.153 | 243.240 | 237.990 | 243.822 |
24 | 16.777.216 | 1.840.172 | 923.877 | 916.295 | 454.786 | 464.948 | 454.998 | 465.440 |
25 | 33.554.432 | 3.523.149 | 1.767.884 | 1.755.265 | 871.208 | 890.687 | 871.537 | 889.717 |
26 | 67.108.864 | 6.754.251 | 3.387.474 | 3.366.777 | 1.672.026 | 1.705.015 | 1.672.394 | 1.704.816 |
27 | 134.217.728 | 12.967.315 | 6.504.336 | 6.462.979 | 3.209.876 | 3.273.334 | 3.210.789 | 3.273.316 |
28 | 268.435.456 | 24.938.283 | 12.508.968 | 12.429.315 | 6.174.247 | 6.293.589 | 6.174.697 | 6.295.750 |
29 | 536.870.912 | 48.035.060 | 24.089.421 | 23.945.639 | 11.894.949 | 12.119.003 | 11.900.448 | 12.120.660 |
30 | 1.073.741.824 | 92.648.285 | 46.460.632 | 46.187.653 | 22.953.486 | 23.369.034 | 22.956.627 | 23.369.138 |
31 | 2.147.483.648 | 178.935.448 | 89.728.858 | 89.206.590 | 44.348.712 | 45.117.016 | 44.344.749 | 45.124.971 |
32 | 4.294.967.296 | 345.986.445 | 173.469.981 | 172.516.464 | 85.775.891 | 87.218.215 | 85.771.699 | 87.220.640 |
33 | 8.589.934.592 | 669.767.543 | 335.786.640 | 333.980.903 | 166.089.951 | 168.794.627 | 166.089.429 | 168.793.536 |
34 | 17.179.869.184 | 1.297.900.805 | 650.637.854 | 647.262.951 | 321.934.092 | 327.009.867 | 321.944.483 | 327.012.363 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
5 | 32 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
6 | 64 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
7 | 128 | 20 | 9 | 11 | 4 | 3 | 5 | 8 |
8 | 256 | 64 | 31 | 33 | 11 | 14 | 19 | 20 |
9 | 512 | 158 | 79 | 79 | 32 | 42 | 41 | 43 |
10 | 1.024 | 369 | 178 | 191 | 89 | 88 | 96 | 96 |
11 | 2.048 | 847 | 412 | 435 | 203 | 205 | 219 | 220 |
12 | 4.096 | 1.863 | 898 | 965 | 457 | 464 | 467 | 475 |
13 | 8.192 | 3.953 | 1.936 | 2.017 | 977 | 988 | 1.000 | 988 |
14 | 16.384 | 8.252 | 4.055 | 4.197 | 2.028 | 2.127 | 2.090 | 2.007 |
15 | 32.768 | 16.885 | 8.399 | 8.486 | 4.199 | 4.292 | 4.228 | 4.166 |
16 | 65.536 | 34.688 | 17.433 | 17.255 | 8.633 | 8.676 | 8.706 | 8.673 |
17 | 131.072 | 71.019 | 35.474 | 35.545 | 17.625 | 17.812 | 17.786 | 17.796 |
18 | 262.144 | 144.611 | 72.155 | 72.456 | 36.065 | 36.220 | 36.255 | 36.071 |
19 | 524.288 | 293.847 | 147.134 | 146.713 | 73.275 | 73.530 | 73.632 | 73.410 |
20 | 1.048.576 | 595.497 | 297.957 | 297.540 | 148.243 | 148.911 | 149.368 | 148.975 |
21 | 2.097.152 | 1.204.700 | 602.065 | 602.635 | 300.717 | 300.794 | 301.647 | 301.542 |
22 | 4.194.304 | 2.433.451 | 1.216.583 | 1.216.868 | 608.155 | 607.723 | 609.092 | 608.481 |
23 | 8.388.608 | 4.911.673 | 2.455.152 | 2.456.521 | 1.227.826 | 1.227.762 | 1.228.528 | 1.227.557 |
24 | 16.777.216 | 9.903.460 | 4.951.596 | 4.951.864 | 2.475.364 | 2.475.807 | 2.477.692 | 2.474.597 |
25 | 33.554.432 | 19.953.595 | 9.976.570 | 9.977.025 | 4.989.323 | 4.988.059 | 4.988.673 | 4.987.540 |
26 | 67.108.864 | 40.178.168 | 20.086.670 | 20.091.498 | 10.046.563 | 10.044.066 | 10.045.040 | 10.042.499 |
27 | 134.217.728 | 80.864.408 | 40.430.007 | 40.434.401 | 20.214.234 | 20.213.298 | 20.222.298 | 20.214.578 |
28 | 268.435.456 | 162.662.479 | 81.325.985 | 81.336.494 | 40.661.709 | 40.664.052 | 40.668.666 | 40.668.052 |
29 | 536.870.912 | 327.039.662 | 163.514.117 | 163.525.545 | 81.751.181 | 81.760.592 | 81.774.855 | 81.753.034 |
30 | 1.073.741.824 | 657.281.190 | 328.627.005 | 328.654.185 | 164.318.715 | 164.318.430 | 164.336.827 | 164.307.218 |
31 | 2.147.483.648 | 1.320.501.750 | 660.223.171 | 660.278.579 | 330.133.478 | 330.112.185 | 330.156.777 | 330.099.310 |
32 | 4.294.967.296 | 2.652.096.274 | 1.326.024.501 | 1.326.071.773 | 663.061.047 | 662.985.937 | 663.077.193 | 662.972.097 |
33 | 8.589.934.592 | 5.324.935.276 | 2.662.424.851 | 2.662.510.425 | 1.331.321.203 | 1.331.187.304 | 1.331.262.785 | 1.331.163.984 |
34 | 17.179.869.184 | 10.688.786.405 | 5.344.316.220 | 5.344.470.185 | 2.672.337.193 | 2.672.066.115 | 2.672.270.230 | 2.672.112.867 |