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+5
f(0)=5
f(1)=3
f(2)=1
f(3)=7
f(4)=1
f(5)=1
f(6)=41
f(7)=1
f(8)=23
f(9)=43
f(10)=1
f(11)=1
f(12)=149
f(13)=29
f(14)=67
f(15)=1
f(16)=1
f(17)=1
f(18)=47
f(19)=61
f(20)=1
f(21)=223
f(22)=163
f(23)=89
f(24)=83
f(25)=1
f(26)=227
f(27)=367
f(28)=263
f(29)=1
f(30)=181
f(31)=1
f(32)=1
f(33)=547
f(34)=1
f(35)=1
f(36)=1301
f(37)=229
f(38)=1
f(39)=109
f(40)=107
f(41)=281
f(42)=1
f(43)=103
f(44)=647
f(45)=1
f(46)=101
f(47)=1
f(48)=2309
f(49)=401
f(50)=167
f(51)=1303
f(52)=1
f(53)=1
f(54)=127
f(55)=1
f(56)=349
f(57)=1627
f(58)=1123
f(59)=1
f(60)=1
f(61)=1
f(62)=1283
f(63)=1987
f(64)=1367
f(65)=1
f(66)=1
f(67)=1
f(68)=1543
f(69)=2383
f(70)=1
f(71)=1
f(72)=5189
f(73)=1
f(74)=1
f(75)=563
f(76)=1
f(77)=1
f(78)=6089
f(79)=347
f(80)=1
f(81)=1
f(82)=2243
f(83)=383
f(84)=307
f(85)=241
f(86)=2467
f(87)=541
f(88)=1
f(89)=1321
f(90)=1621
f(91)=1381
f(92)=941
f(93)=4327
f(94)=421
f(95)=1
f(96)=9221
f(97)=523
f(98)=3203
f(99)=4903
b) Substitution of the polynom
The polynom f(x)=x^2+5 could be written as f(y)= y^2+5 with x=y+0
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+0
f'(x)>2x-1 with x > 2
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 | 6 | 5 | 1 | 0.600000 | 0.500000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 61 | 20 | 41 | 0.610000 | 0.200000 | 0.610000 | 10.166667 | 4.000000 | 41.000000 |
3 | 1.000 | 656 | 99 | 557 | 0.656000 | 0.099000 | 0.656000 | 10.754098 | 4.950000 | 13.585366 |
4 | 10.000 | 6.638 | 681 | 5.957 | 0.663800 | 0.068100 | 0.663800 | 10.118902 | 6.878788 | 10.694794 |
5 | 100.000 | 67.079 | 5.175 | 61.904 | 0.670790 | 0.051750 | 0.670790 | 10.105303 | 7.599119 | 10.391808 |
6 | 1.000.000 | 674.508 | 42.207 | 632.301 | 0.674508 | 0.042207 | 0.674508 | 10.055428 | 8.155942 | 10.214219 |
7 | 10.000.000 | 6.769.572 | 355.937 | 6.413.635 | 0.676957 | 0.035594 | 0.676957 | 10.036311 | 8.433127 | 10.143326 |
8 | 100.000.000 | 67.884.260 | 3.076.460 | 64.807.800 | 0.678843 | 0.030765 | 0.678843 | 10.027850 | 8.643271 | 10.104691 |
9 | 1.000.000.000 | 680.341.265 | 27.106.121 | 653.235.144 | 0.680341 | 0.027106 | 0.680341 | 10.022078 | 8.810815 | 10.079576 |
10 | 10.000.000.000 | 6.815.530.703 | 242.312.628 | 6.573.218.075 | 0.681553 | 0.024231 | 0.681553 | 10.017812 | 8.939406 | 10.062561 |
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 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 5 | 4 | 1 | 0.625000 | 0.500000 | 0.125000 | 1.666667 | 1.333333 | inf |
4 | 16 | 9 | 6 | 3 | 0.562500 | 0.375000 | 0.187500 | 1.800000 | 1.500000 | 3.000000 |
5 | 32 | 19 | 8 | 11 | 0.593750 | 0.250000 | 0.343750 | 2.111111 | 1.333333 | 3.666667 |
6 | 64 | 39 | 14 | 25 | 0.609375 | 0.218750 | 0.390625 | 2.052632 | 1.750000 | 2.272727 |
7 | 128 | 81 | 23 | 58 | 0.632812 | 0.179688 | 0.453125 | 2.076923 | 1.642857 | 2.320000 |
8 | 256 | 162 | 34 | 128 | 0.632812 | 0.132812 | 0.500000 | 2.000000 | 1.478261 | 2.206897 |
9 | 512 | 332 | 55 | 277 | 0.648438 | 0.107422 | 0.541016 | 2.049383 | 1.617647 | 2.164062 |
10 | 1.024 | 671 | 101 | 570 | 0.655273 | 0.098633 | 0.556641 | 2.021084 | 1.836364 | 2.057762 |
11 | 2.048 | 1.335 | 182 | 1.153 | 0.651855 | 0.088867 | 0.562988 | 1.989568 | 1.801980 | 2.022807 |
12 | 4.096 | 2.694 | 332 | 2.362 | 0.657715 | 0.081055 | 0.576660 | 2.017977 | 1.824176 | 2.048569 |
13 | 8.192 | 5.448 | 577 | 4.871 | 0.665039 | 0.070435 | 0.594604 | 2.022272 | 1.737952 | 2.062235 |
14 | 16.384 | 10.916 | 1.045 | 9.871 | 0.666260 | 0.063782 | 0.602478 | 2.003671 | 1.811092 | 2.026483 |
15 | 32.768 | 21.872 | 1.937 | 19.935 | 0.667480 | 0.059113 | 0.608368 | 2.003664 | 1.853588 | 2.019552 |
16 | 65.536 | 43.889 | 3.523 | 40.366 | 0.669693 | 0.053757 | 0.615936 | 2.006629 | 1.818792 | 2.024881 |
17 | 131.072 | 87.991 | 6.610 | 81.381 | 0.671318 | 0.050430 | 0.620888 | 2.004853 | 1.876242 | 2.016078 |
18 | 262.144 | 176.332 | 12.421 | 163.911 | 0.672653 | 0.047382 | 0.625271 | 2.003978 | 1.879122 | 2.014119 |
19 | 524.288 | 353.123 | 23.480 | 329.643 | 0.673529 | 0.044785 | 0.628744 | 2.002603 | 1.890347 | 2.011110 |
20 | 1.048.576 | 707.318 | 44.093 | 663.225 | 0.674551 | 0.042050 | 0.632501 | 2.003036 | 1.877896 | 2.011949 |
21 | 2.097.152 | 1.416.754 | 83.593 | 1.333.161 | 0.675561 | 0.039860 | 0.635701 | 2.002994 | 1.895834 | 2.010119 |
22 | 4.194.304 | 2.835.577 | 158.970 | 2.676.607 | 0.676054 | 0.037901 | 0.638153 | 2.001460 | 1.901714 | 2.007715 |
23 | 8.388.608 | 5.677.026 | 302.338 | 5.374.688 | 0.676754 | 0.036041 | 0.640713 | 2.002071 | 1.901856 | 2.008023 |
24 | 16.777.216 | 11.364.401 | 576.732 | 10.787.669 | 0.677371 | 0.034376 | 0.642995 | 2.001823 | 1.907574 | 2.007125 |
25 | 33.554.432 | 22.749.491 | 1.103.239 | 21.646.252 | 0.677988 | 0.032879 | 0.645109 | 2.001821 | 1.912915 | 2.006574 |
26 | 67.108.864 | 45.536.142 | 2.114.142 | 43.422.000 | 0.678541 | 0.031503 | 0.647038 | 2.001633 | 1.916305 | 2.005982 |
27 | 134.217.728 | 91.141.267 | 4.059.617 | 87.081.650 | 0.679055 | 0.030247 | 0.648809 | 2.001515 | 1.920220 | 2.005473 |
28 | 268.435.456 | 182.409.796 | 7.805.392 | 174.604.404 | 0.679529 | 0.029077 | 0.650452 | 2.001396 | 1.922692 | 2.005065 |
29 | 536.870.912 | 365.054.541 | 15.034.462 | 350.020.079 | 0.679967 | 0.028004 | 0.651963 | 2.001288 | 1.926164 | 2.004646 |
30 | 1.073.741.824 | 730.558.250 | 28.997.095 | 701.561.155 | 0.680385 | 0.027006 | 0.653380 | 2.001230 | 1.928709 | 2.004345 |
31 | 2.147.483.648 | 1.461.951.657 | 55.998.599 | 1.405.953.058 | 0.680774 | 0.026076 | 0.654698 | 2.001143 | 1.931180 | 2.004035 |
32 | 4.294.967.296 | 2.925.471.888 | 108.278.982 | 2.817.192.906 | 0.681140 | 0.025211 | 0.655929 | 2.001073 | 1.933602 | 2.003760 |
33 | 8.589.934.592 | 5.853.854.280 | 209.606.663 | 5.644.247.617 | 0.681478 | 0.024401 | 0.657077 | 2.000995 | 1.935802 | 2.003500 |
34 | 17.179.869.184 | 11.713.298.670 | 406.176.170 | 11.307.122.500 | 0.681804 | 0.023643 | 0.658161 | 2.000955 | 1.937802 | 2.003300 |
35 | 34.359.738.368 | 23.437.159.276 | 787.860.134 | 22.649.299.142 | 0.682111 | 0.022930 | 0.659181 | 2.000902 | 1.939701 | 2.003100 |
36 | 68.719.476.736 | 46.894.297.743 | 1.529.563.809 | 45.364.733.934 | 0.682402 | 0.022258 | 0.660144 | 2.000853 | 1.941415 | 2.002920 |
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 | 0 | 1 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 4 | 1 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 6 | 2 | 3 | 1 | 2 | 2 | 1 |
5 | 32 | 8 | 4 | 3 | 1 | 2 | 2 | 3 |
6 | 64 | 14 | 8 | 5 | 1 | 5 | 4 | 4 |
7 | 128 | 23 | 12 | 10 | 4 | 6 | 6 | 7 |
8 | 256 | 34 | 18 | 15 | 7 | 9 | 8 | 10 |
9 | 512 | 55 | 28 | 26 | 12 | 14 | 14 | 15 |
10 | 1.024 | 101 | 49 | 51 | 23 | 24 | 28 | 26 |
11 | 2.048 | 182 | 89 | 92 | 42 | 42 | 50 | 48 |
12 | 4.096 | 332 | 166 | 165 | 74 | 83 | 91 | 84 |
13 | 8.192 | 577 | 288 | 288 | 131 | 140 | 157 | 149 |
14 | 16.384 | 1.045 | 523 | 521 | 258 | 262 | 263 | 262 |
15 | 32.768 | 1.937 | 991 | 945 | 472 | 495 | 473 | 497 |
16 | 65.536 | 3.523 | 1.791 | 1.731 | 880 | 917 | 851 | 875 |
17 | 131.072 | 6.610 | 3.322 | 3.287 | 1.659 | 1.698 | 1.628 | 1.625 |
18 | 262.144 | 12.421 | 6.223 | 6.197 | 3.097 | 3.160 | 3.100 | 3.064 |
19 | 524.288 | 23.480 | 11.805 | 11.674 | 5.846 | 5.965 | 5.828 | 5.841 |
20 | 1.048.576 | 44.093 | 22.311 | 21.781 | 10.871 | 11.208 | 10.910 | 11.104 |
21 | 2.097.152 | 83.593 | 42.242 | 41.350 | 20.610 | 21.148 | 20.740 | 21.095 |
22 | 4.194.304 | 158.970 | 80.367 | 78.602 | 39.259 | 40.178 | 39.343 | 40.190 |
23 | 8.388.608 | 302.338 | 152.864 | 149.473 | 74.644 | 76.367 | 74.829 | 76.498 |
24 | 16.777.216 | 576.732 | 291.348 | 285.383 | 142.591 | 145.634 | 142.792 | 145.715 |
25 | 33.554.432 | 1.103.239 | 557.100 | 546.138 | 272.918 | 278.371 | 273.220 | 278.730 |
26 | 67.108.864 | 2.114.142 | 1.068.119 | 1.046.022 | 522.827 | 533.784 | 523.195 | 534.336 |
27 | 134.217.728 | 4.059.617 | 2.050.371 | 2.009.245 | 1.004.686 | 1.024.889 | 1.004.559 | 1.025.483 |
28 | 268.435.456 | 7.805.392 | 3.939.579 | 3.865.812 | 1.932.550 | 1.969.469 | 1.933.262 | 1.970.111 |
29 | 536.870.912 | 15.034.462 | 7.586.433 | 7.448.028 | 3.722.574 | 3.794.257 | 3.725.454 | 3.792.177 |
30 | 1.073.741.824 | 28.997.095 | 14.626.512 | 14.370.582 | 7.183.855 | 7.314.231 | 7.186.727 | 7.312.282 |
31 | 2.147.483.648 | 55.998.599 | 28.235.330 | 27.763.268 | 13.879.812 | 14.119.182 | 13.883.456 | 14.116.149 |
32 | 4.294.967.296 | 108.278.982 | 54.587.221 | 53.691.760 | 26.844.089 | 27.298.988 | 26.847.671 | 27.288.234 |
33 | 8.589.934.592 | 209.606.663 | 105.643.923 | 103.962.739 | 51.978.483 | 52.831.192 | 51.984.256 | 52.812.732 |
34 | 17.179.869.184 | 406.176.170 | 204.665.117 | 201.511.052 | 100.753.359 | 102.341.040 | 100.757.693 | 102.324.078 |
35 | 34.359.738.368 | 787.860.134 | 396.895.312 | 390.964.821 | 195.483.289 | 198.456.442 | 195.481.532 | 198.438.871 |
36 | 68.719.476.736 | 1.529.563.809 | 770.384.334 | 759.179.474 | 379.596.995 | 385.206.391 | 379.582.479 | 385.177.944 |
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 | 1 | 2 | 0 | 1 | 1 | 1 |
5 | 32 | 11 | 4 | 7 | 1 | 4 | 3 | 3 |
6 | 64 | 25 | 10 | 15 | 3 | 7 | 7 | 8 |
7 | 128 | 58 | 27 | 31 | 11 | 18 | 15 | 14 |
8 | 256 | 128 | 52 | 76 | 28 | 33 | 34 | 33 |
9 | 512 | 277 | 128 | 149 | 69 | 71 | 70 | 67 |
10 | 1.024 | 570 | 278 | 292 | 143 | 141 | 144 | 142 |
11 | 2.048 | 1.153 | 581 | 572 | 283 | 297 | 282 | 291 |
12 | 4.096 | 2.362 | 1.148 | 1.214 | 604 | 583 | 577 | 598 |
13 | 8.192 | 4.871 | 2.396 | 2.475 | 1.202 | 1.227 | 1.225 | 1.217 |
14 | 16.384 | 9.871 | 4.906 | 4.965 | 2.374 | 2.517 | 2.511 | 2.469 |
15 | 32.768 | 19.935 | 9.943 | 9.992 | 4.875 | 4.997 | 5.053 | 5.010 |
16 | 65.536 | 40.366 | 20.236 | 20.130 | 9.957 | 10.105 | 10.176 | 10.128 |
17 | 131.072 | 81.381 | 40.670 | 40.711 | 20.277 | 20.407 | 20.369 | 20.328 |
18 | 262.144 | 163.911 | 81.858 | 82.053 | 40.815 | 41.085 | 41.137 | 40.874 |
19 | 524.288 | 329.643 | 164.637 | 165.006 | 82.106 | 82.755 | 82.626 | 82.156 |
20 | 1.048.576 | 663.225 | 331.376 | 331.849 | 165.642 | 165.735 | 166.306 | 165.542 |
21 | 2.097.152 | 1.333.161 | 666.214 | 666.947 | 333.632 | 332.583 | 333.826 | 333.120 |
22 | 4.194.304 | 2.676.607 | 1.338.892 | 1.337.715 | 670.327 | 667.764 | 669.230 | 669.286 |
23 | 8.388.608 | 5.374.688 | 2.687.518 | 2.687.170 | 1.344.759 | 1.342.323 | 1.344.242 | 1.343.364 |
24 | 16.777.216 | 10.787.669 | 5.392.978 | 5.394.691 | 2.697.683 | 2.694.746 | 2.700.089 | 2.695.151 |
25 | 33.554.432 | 21.646.252 | 10.823.065 | 10.823.187 | 5.413.965 | 5.406.979 | 5.414.737 | 5.410.571 |
26 | 67.108.864 | 43.422.000 | 21.711.450 | 21.710.550 | 10.860.031 | 10.849.804 | 10.858.783 | 10.853.382 |
27 | 134.217.728 | 87.081.650 | 43.540.468 | 43.541.182 | 21.781.202 | 21.754.905 | 21.780.761 | 21.764.782 |
28 | 268.435.456 | 174.604.404 | 87.302.208 | 87.302.196 | 43.670.046 | 43.624.194 | 43.673.485 | 43.636.679 |
29 | 536.870.912 | 350.020.079 | 175.002.391 | 175.017.688 | 87.539.555 | 87.461.356 | 87.542.488 | 87.476.680 |
30 | 1.073.741.824 | 701.561.155 | 350.775.801 | 350.785.354 | 175.466.136 | 175.314.235 | 175.451.683 | 175.329.101 |
31 | 2.147.483.648 | 1.405.953.058 | 702.947.616 | 703.005.442 | 351.619.115 | 351.348.471 | 351.619.549 | 351.365.923 |
32 | 4.294.967.296 | 2.817.192.906 | 1.408.530.508 | 1.408.662.398 | 704.526.010 | 704.064.468 | 704.525.027 | 704.077.401 |
33 | 8.589.934.592 | 5.644.247.617 | 2.821.976.472 | 2.822.271.145 | 1.411.475.009 | 1.410.617.598 | 1.411.517.204 | 1.410.637.806 |
34 | 17.179.869.184 | 11.307.122.500 | 5.653.292.836 | 5.653.829.664 | 2.827.572.517 | 2.825.964.972 | 2.827.588.653 | 2.825.996.358 |
35 | 34.359.738.368 | 22.649.299.142 | 11.324.189.781 | 11.325.109.361 | 5.663.811.396 | 5.660.758.113 | 5.663.951.757 | 5.660.777.876 |
36 | 68.719.476.736 | 45.364.733.934 | 22.681.456.797 | 22.683.277.137 | 11.343.999.710 | 11.338.356.474 | 11.344.052.525 | 11.338.325.225 |