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-37x+5
f(0)=5
f(1)=31
f(2)=13
f(3)=97
f(4)=127
f(5)=1
f(6)=181
f(7)=41
f(8)=227
f(9)=19
f(10)=53
f(11)=281
f(12)=59
f(13)=307
f(14)=317
f(15)=1
f(16)=331
f(17)=67
f(18)=337
f(19)=1
f(20)=1
f(21)=1
f(22)=1
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)=43
f(39)=83
f(40)=1
f(41)=1
f(42)=1
f(43)=263
f(44)=313
f(45)=73
f(46)=419
f(47)=1
f(48)=1
f(49)=593
f(50)=131
f(51)=719
f(52)=157
f(53)=853
f(54)=71
f(55)=199
f(56)=1069
f(57)=229
f(58)=1223
f(59)=1303
f(60)=277
f(61)=113
f(62)=311
f(63)=1
f(64)=1733
f(65)=1
f(66)=101
f(67)=1
f(68)=2113
f(69)=2213
f(70)=463
f(71)=1
f(72)=1
f(73)=2633
f(74)=211
f(75)=571
f(76)=2969
f(77)=617
f(78)=3203
f(79)=3323
f(80)=1
f(81)=1
f(82)=739
f(83)=3823
f(84)=1
f(85)=1
f(86)=4219
f(87)=1
f(88)=4493
f(89)=1
f(90)=191
f(91)=4919
f(92)=1013
f(93)=401
f(94)=173
f(95)=1103
f(96)=5669
f(97)=233
f(98)=193
f(99)=6143
b) Substitution of the polynom
The polynom f(x)=x^2-37x+5 could be written as f(y)= y^2-337.25 with x=y+18.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-18.5
f'(x)>2x-38 with x > 18
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 | 57 | 36 | 21 | 0.570000 | 0.360000 | 0.570000 | 5.700000 | 5.142857 | 7.000000 |
3 | 1.000 | 693 | 243 | 450 | 0.693000 | 0.243000 | 0.693000 | 12.157895 | 6.750000 | 21.428572 |
4 | 10.000 | 7.106 | 1.763 | 5.343 | 0.710600 | 0.176300 | 0.710600 | 10.253968 | 7.255144 | 11.873333 |
5 | 100.000 | 71.346 | 13.173 | 58.173 | 0.713460 | 0.131730 | 0.713460 | 10.040248 | 7.471923 | 10.887704 |
6 | 1.000.000 | 710.247 | 107.757 | 602.490 | 0.710247 | 0.107757 | 0.710247 | 9.954966 | 8.180141 | 10.356867 |
7 | 10.000.000 | 7.077.012 | 911.978 | 6.165.034 | 0.707701 | 0.091198 | 0.707701 | 9.964156 | 8.463284 | 10.232592 |
8 | 100.000.000 | 70.567.288 | 7.893.586 | 62.673.702 | 0.705673 | 0.078936 | 0.705673 | 9.971339 | 8.655457 | 10.165995 |
9 | 1.000.000.000 | 704.160.912 | 69.665.265 | 634.495.647 | 0.704161 | 0.069665 | 0.704161 | 9.978574 | 8.825553 | 10.123794 |
10 | 10.000.000.000 | 7.029.723.480 | 623.400.249 | 6.406.323.231 | 0.702972 | 0.062340 | 0.702972 | 9.983121 | 8.948509 | 10.096718 |
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 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 1.600000 | 1.500000 | 2.000000 |
4 | 16 | 15 | 11 | 4 | 0.937500 | 0.687500 | 0.250000 | 1.875000 | 1.833333 | 2.000000 |
5 | 32 | 17 | 12 | 5 | 0.531250 | 0.375000 | 0.156250 | 1.133333 | 1.090909 | 1.250000 |
6 | 64 | 35 | 24 | 11 | 0.546875 | 0.375000 | 0.171875 | 2.058824 | 2.000000 | 2.200000 |
7 | 128 | 80 | 43 | 37 | 0.625000 | 0.335938 | 0.289062 | 2.285714 | 1.791667 | 3.363636 |
8 | 256 | 171 | 78 | 93 | 0.667969 | 0.304688 | 0.363281 | 2.137500 | 1.813954 | 2.513514 |
9 | 512 | 346 | 137 | 209 | 0.675781 | 0.267578 | 0.408203 | 2.023392 | 1.756410 | 2.247312 |
10 | 1.024 | 712 | 248 | 464 | 0.695312 | 0.242188 | 0.453125 | 2.057803 | 1.810219 | 2.220096 |
11 | 2.048 | 1.443 | 458 | 985 | 0.704590 | 0.223633 | 0.480957 | 2.026685 | 1.846774 | 2.122845 |
12 | 4.096 | 2.910 | 822 | 2.088 | 0.710449 | 0.200684 | 0.509766 | 2.016632 | 1.794760 | 2.119797 |
13 | 8.192 | 5.823 | 1.489 | 4.334 | 0.710815 | 0.181763 | 0.529053 | 2.001031 | 1.811436 | 2.075670 |
14 | 16.384 | 11.682 | 2.678 | 9.004 | 0.713013 | 0.163452 | 0.549561 | 2.006182 | 1.798522 | 2.077527 |
15 | 32.768 | 23.407 | 4.841 | 18.566 | 0.714325 | 0.147736 | 0.566589 | 2.003681 | 1.807692 | 2.061972 |
16 | 65.536 | 46.814 | 9.044 | 37.770 | 0.714325 | 0.138000 | 0.576324 | 2.000000 | 1.868209 | 2.034364 |
17 | 131.072 | 93.544 | 16.870 | 76.674 | 0.713684 | 0.128708 | 0.584976 | 1.998206 | 1.865325 | 2.030024 |
18 | 262.144 | 186.685 | 31.523 | 155.162 | 0.712147 | 0.120251 | 0.591896 | 1.995692 | 1.868583 | 2.023659 |
19 | 524.288 | 373.052 | 59.356 | 313.696 | 0.711540 | 0.113213 | 0.598328 | 1.998297 | 1.882943 | 2.021732 |
20 | 1.048.576 | 744.788 | 112.597 | 632.191 | 0.710285 | 0.107381 | 0.602904 | 1.996472 | 1.896978 | 2.015298 |
21 | 2.097.152 | 1.488.033 | 213.227 | 1.274.806 | 0.709549 | 0.101675 | 0.607875 | 1.997928 | 1.893718 | 2.016489 |
22 | 4.194.304 | 2.972.459 | 405.568 | 2.566.891 | 0.708689 | 0.096695 | 0.611995 | 1.997576 | 1.902048 | 2.013554 |
23 | 8.388.608 | 5.938.318 | 773.524 | 5.164.794 | 0.707903 | 0.092211 | 0.615691 | 1.997780 | 1.907261 | 2.012082 |
24 | 16.777.216 | 11.864.381 | 1.477.413 | 10.386.968 | 0.707172 | 0.088061 | 0.619112 | 1.997936 | 1.909977 | 2.011110 |
25 | 33.554.432 | 23.707.664 | 2.827.118 | 20.880.546 | 0.706543 | 0.084255 | 0.622289 | 1.998222 | 1.913560 | 2.010264 |
26 | 67.108.864 | 47.376.758 | 5.421.386 | 41.955.372 | 0.705969 | 0.080785 | 0.625184 | 1.998373 | 1.917637 | 2.009304 |
27 | 134.217.728 | 94.688.637 | 10.416.496 | 84.272.141 | 0.705485 | 0.077609 | 0.627876 | 1.998631 | 1.921371 | 2.008614 |
28 | 268.435.456 | 189.243.382 | 20.046.727 | 169.196.655 | 0.704987 | 0.074680 | 0.630307 | 1.998586 | 1.924517 | 2.007741 |
29 | 536.870.912 | 378.239.748 | 38.629.391 | 339.610.357 | 0.704526 | 0.071953 | 0.632574 | 1.998695 | 1.926967 | 2.007193 |
30 | 1.073.741.824 | 756.043.186 | 74.529.722 | 681.513.464 | 0.704120 | 0.069411 | 0.634709 | 1.998847 | 1.929353 | 2.006751 |
31 | 2.147.483.648 | 1.511.269.540 | 143.991.672 | 1.367.277.868 | 0.703740 | 0.067051 | 0.636688 | 1.998919 | 1.932003 | 2.006238 |
32 | 4.294.967.296 | 3.020.998.443 | 278.488.201 | 2.742.510.242 | 0.703381 | 0.064841 | 0.638540 | 1.998981 | 1.934057 | 2.005818 |
33 | 8.589.934.592 | 6.039.114.894 | 539.234.728 | 5.499.880.166 | 0.703045 | 0.062775 | 0.640270 | 1.999046 | 1.936293 | 2.005418 |
34 | 17.179.869.184 | 12.072.827.490 | 1.045.200.643 | 11.027.626.847 | 0.702731 | 0.060839 | 0.641892 | 1.999106 | 1.938304 | 2.005067 |
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 | 0 | 1 | 1 |
2 | 4 | 4 | 3 | 1 | 1 | 0 | 1 | 2 |
3 | 8 | 6 | 4 | 2 | 1 | 1 | 2 | 2 |
4 | 16 | 11 | 7 | 4 | 2 | 3 | 3 | 3 |
5 | 32 | 12 | 8 | 4 | 3 | 3 | 3 | 3 |
6 | 64 | 24 | 12 | 12 | 5 | 6 | 6 | 7 |
7 | 128 | 43 | 16 | 27 | 10 | 11 | 11 | 11 |
8 | 256 | 78 | 27 | 51 | 17 | 20 | 22 | 19 |
9 | 512 | 137 | 45 | 92 | 32 | 33 | 37 | 35 |
10 | 1.024 | 248 | 80 | 168 | 57 | 65 | 64 | 62 |
11 | 2.048 | 458 | 152 | 306 | 106 | 113 | 124 | 115 |
12 | 4.096 | 822 | 271 | 551 | 199 | 210 | 203 | 210 |
13 | 8.192 | 1.489 | 493 | 996 | 358 | 383 | 376 | 372 |
14 | 16.384 | 2.678 | 906 | 1.772 | 657 | 686 | 680 | 655 |
15 | 32.768 | 4.841 | 1.611 | 3.230 | 1.188 | 1.221 | 1.228 | 1.204 |
16 | 65.536 | 9.044 | 2.979 | 6.065 | 2.262 | 2.277 | 2.245 | 2.260 |
17 | 131.072 | 16.870 | 5.605 | 11.265 | 4.245 | 4.266 | 4.211 | 4.148 |
18 | 262.144 | 31.523 | 10.476 | 21.047 | 7.919 | 7.926 | 7.886 | 7.792 |
19 | 524.288 | 59.356 | 19.770 | 39.586 | 14.881 | 14.958 | 14.789 | 14.728 |
20 | 1.048.576 | 112.597 | 37.638 | 74.959 | 28.198 | 28.282 | 28.088 | 28.029 |
21 | 2.097.152 | 213.227 | 71.181 | 142.046 | 53.512 | 53.491 | 53.124 | 53.100 |
22 | 4.194.304 | 405.568 | 135.028 | 270.540 | 101.901 | 101.386 | 101.216 | 101.065 |
23 | 8.388.608 | 773.524 | 257.968 | 515.556 | 194.025 | 193.434 | 193.033 | 193.032 |
24 | 16.777.216 | 1.477.413 | 492.257 | 985.156 | 370.094 | 369.202 | 369.311 | 368.806 |
25 | 33.554.432 | 2.827.118 | 942.033 | 1.885.085 | 707.321 | 706.632 | 707.155 | 706.010 |
26 | 67.108.864 | 5.421.386 | 1.806.105 | 3.615.281 | 1.356.920 | 1.354.731 | 1.355.433 | 1.354.302 |
27 | 134.217.728 | 10.416.496 | 3.471.337 | 6.945.159 | 2.606.512 | 2.603.362 | 2.603.857 | 2.602.765 |
28 | 268.435.456 | 20.046.727 | 6.679.624 | 13.367.103 | 5.014.441 | 5.010.406 | 5.011.117 | 5.010.763 |
29 | 536.870.912 | 38.629.391 | 12.874.791 | 25.754.600 | 9.659.839 | 9.656.060 | 9.657.392 | 9.656.100 |
30 | 1.073.741.824 | 74.529.722 | 24.842.816 | 49.686.906 | 18.630.775 | 18.634.276 | 18.632.678 | 18.631.993 |
31 | 2.147.483.648 | 143.991.672 | 47.999.768 | 95.991.904 | 35.999.792 | 36.001.014 | 35.997.159 | 35.993.707 |
32 | 4.294.967.296 | 278.488.201 | 92.835.896 | 185.652.305 | 69.619.367 | 69.628.539 | 69.619.998 | 69.620.297 |
33 | 8.589.934.592 | 539.234.728 | 179.751.819 | 359.482.909 | 134.810.874 | 134.812.742 | 134.803.798 | 134.807.314 |
34 | 17.179.869.184 | 1.045.200.643 | 348.408.544 | 696.792.099 | 261.297.544 | 261.305.325 | 261.306.354 | 261.291.420 |
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 | 1 | 0 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
4 | 16 | 4 | 1 | 3 | 1 | 1 | 2 | 0 |
5 | 32 | 5 | 2 | 3 | 1 | 2 | 2 | 0 |
6 | 64 | 11 | 6 | 5 | 1 | 3 | 5 | 2 |
7 | 128 | 37 | 19 | 18 | 6 | 9 | 9 | 13 |
8 | 256 | 93 | 47 | 46 | 18 | 25 | 19 | 31 |
9 | 512 | 209 | 109 | 100 | 48 | 53 | 53 | 55 |
10 | 1.024 | 464 | 236 | 228 | 105 | 129 | 119 | 111 |
11 | 2.048 | 985 | 497 | 488 | 223 | 271 | 252 | 239 |
12 | 4.096 | 2.088 | 1.072 | 1.016 | 503 | 529 | 553 | 503 |
13 | 8.192 | 4.334 | 2.236 | 2.098 | 1.082 | 1.120 | 1.071 | 1.061 |
14 | 16.384 | 9.004 | 4.692 | 4.312 | 2.188 | 2.269 | 2.292 | 2.255 |
15 | 32.768 | 18.566 | 9.576 | 8.990 | 4.547 | 4.640 | 4.698 | 4.681 |
16 | 65.536 | 37.770 | 19.430 | 18.340 | 9.377 | 9.455 | 9.494 | 9.444 |
17 | 131.072 | 76.674 | 39.265 | 37.409 | 19.030 | 19.191 | 19.226 | 19.227 |
18 | 262.144 | 155.162 | 79.348 | 75.814 | 38.649 | 39.028 | 38.734 | 38.751 |
19 | 524.288 | 313.696 | 160.148 | 153.548 | 78.273 | 78.453 | 78.325 | 78.645 |
20 | 1.048.576 | 632.191 | 322.355 | 309.836 | 157.757 | 158.286 | 157.848 | 158.300 |
21 | 2.097.152 | 1.274.806 | 648.946 | 625.860 | 318.609 | 318.990 | 318.722 | 318.485 |
22 | 4.194.304 | 2.566.891 | 1.304.651 | 1.262.240 | 641.698 | 641.472 | 641.390 | 642.331 |
23 | 8.388.608 | 5.164.794 | 2.624.097 | 2.540.697 | 1.291.475 | 1.290.778 | 1.290.457 | 1.292.084 |
24 | 16.777.216 | 10.386.968 | 5.273.138 | 5.113.830 | 2.596.548 | 2.596.167 | 2.596.700 | 2.597.553 |
25 | 33.554.432 | 20.880.546 | 10.591.907 | 10.288.639 | 5.219.847 | 5.219.462 | 5.219.444 | 5.221.793 |
26 | 67.108.864 | 41.955.372 | 21.266.437 | 20.688.935 | 10.490.245 | 10.488.831 | 10.487.628 | 10.488.668 |
27 | 134.217.728 | 84.272.141 | 42.690.887 | 41.581.254 | 21.070.893 | 21.067.160 | 21.066.452 | 21.067.636 |
28 | 268.435.456 | 169.196.655 | 85.664.579 | 83.532.076 | 42.293.825 | 42.302.991 | 42.302.060 | 42.297.779 |
29 | 536.870.912 | 339.610.357 | 171.859.315 | 167.751.042 | 84.905.022 | 84.908.028 | 84.896.233 | 84.901.074 |
30 | 1.073.741.824 | 681.513.464 | 344.707.505 | 336.805.959 | 170.374.028 | 170.393.846 | 170.371.536 | 170.374.054 |
31 | 2.147.483.648 | 1.367.277.868 | 691.267.976 | 676.009.892 | 341.828.675 | 341.835.949 | 341.814.021 | 341.799.223 |
32 | 4.294.967.296 | 2.742.510.242 | 1.386.021.423 | 1.356.488.819 | 685.656.871 | 685.631.983 | 685.613.049 | 685.608.339 |
33 | 8.589.934.592 | 5.499.880.166 | 2.778.506.776 | 2.721.373.390 | 1.375.007.949 | 1.374.968.430 | 1.374.964.385 | 1.374.939.402 |
34 | 17.179.869.184 | 11.027.626.847 | 5.569.087.320 | 5.458.539.527 | 2.756.955.050 | 2.756.945.368 | 2.756.864.748 | 2.756.861.681 |