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-3
f(0)=3
f(1)=23
f(2)=29
f(3)=7
f(4)=163
f(5)=11
f(6)=1
f(7)=131
f(8)=97
f(9)=53
f(10)=1
f(11)=61
f(12)=43
f(13)=1
f(14)=47
f(15)=73
f(16)=41
f(17)=1
f(18)=157
f(19)=239
f(20)=1
f(21)=1
f(22)=487
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)=89
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=59
f(52)=1
f(53)=79
f(54)=179
f(55)=1
f(56)=223
f(57)=1
f(58)=809
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=199
f(64)=1277
f(65)=227
f(66)=1
f(67)=769
f(68)=181
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=151
f(74)=739
f(75)=1
f(76)=347
f(77)=1
f(78)=883
f(79)=1381
f(80)=137
f(81)=499
f(82)=283
f(83)=1
f(84)=373
f(85)=1741
f(86)=401
f(87)=1
f(88)=1
f(89)=1
f(90)=197
f(91)=2137
f(92)=1471
f(93)=1
f(94)=1
f(95)=269
f(96)=1663
f(97)=367
f(98)=1
f(99)=907
b) Substitution of the polynom
The polynom f(x)=x^2-44x-3 could be written as f(y)= y^2-487 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 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 42 | 12 | 30 | 0.420000 | 0.120000 | 0.300000 | 4.666667 | 3.000000 | 6.000000 |
3 | 1.000 | 589 | 83 | 506 | 0.589000 | 0.083000 | 0.506000 | 14.023809 | 6.916667 | 16.866667 |
4 | 10.000 | 6.437 | 658 | 5.779 | 0.643700 | 0.065800 | 0.577900 | 10.928693 | 7.927711 | 11.420949 |
5 | 100.000 | 65.612 | 5.063 | 60.549 | 0.656120 | 0.050630 | 0.605490 | 10.192947 | 7.694529 | 10.477418 |
6 | 1.000.000 | 663.084 | 41.381 | 621.703 | 0.663084 | 0.041381 | 0.621703 | 10.106139 | 8.173218 | 10.267767 |
7 | 10.000.000 | 6.673.559 | 348.814 | 6.324.745 | 0.667356 | 0.034881 | 0.632474 | 10.064425 | 8.429327 | 10.173258 |
8 | 100.000.000 | 67.049.305 | 3.018.765 | 64.030.540 | 0.670493 | 0.030188 | 0.640305 | 10.047009 | 8.654368 | 10.123814 |
9 | 1.000.000.000 | 672.995.423 | 26.598.928 | 646.396.495 | 0.672995 | 0.026599 | 0.646396 | 10.037321 | 8.811195 | 10.095128 |
10 | 10.000.000.000 | 6.749.971.545 | 237.804.146 | 6.512.167.399 | 0.674997 | 0.023780 | 0.651217 | 10.029744 | 8.940366 | 10.074572 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 14 | 4 | 10 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 1.000000 | 2.500000 |
5 | 32 | 17 | 6 | 11 | 0.531250 | 0.187500 | 0.343750 | 1.214286 | 1.500000 | 1.100000 |
6 | 64 | 22 | 8 | 14 | 0.343750 | 0.125000 | 0.218750 | 1.294118 | 1.333333 | 1.272727 |
7 | 128 | 57 | 16 | 41 | 0.445312 | 0.125000 | 0.320312 | 2.590909 | 2.000000 | 2.928571 |
8 | 256 | 129 | 29 | 100 | 0.503906 | 0.113281 | 0.390625 | 2.263158 | 1.812500 | 2.439024 |
9 | 512 | 281 | 51 | 230 | 0.548828 | 0.099609 | 0.449219 | 2.178295 | 1.758621 | 2.300000 |
10 | 1.024 | 607 | 86 | 521 | 0.592773 | 0.083984 | 0.508789 | 2.160142 | 1.686275 | 2.265217 |
11 | 2.048 | 1.264 | 162 | 1.102 | 0.617188 | 0.079102 | 0.538086 | 2.082372 | 1.883721 | 2.115163 |
12 | 4.096 | 2.597 | 291 | 2.306 | 0.634033 | 0.071045 | 0.562988 | 2.054589 | 1.796296 | 2.092559 |
13 | 8.192 | 5.262 | 548 | 4.714 | 0.642334 | 0.066895 | 0.575439 | 2.026184 | 1.883162 | 2.044232 |
14 | 16.384 | 10.629 | 1.014 | 9.615 | 0.648743 | 0.061890 | 0.586853 | 2.019954 | 1.850365 | 2.039669 |
15 | 32.768 | 21.348 | 1.840 | 19.508 | 0.651489 | 0.056152 | 0.595337 | 2.008467 | 1.814596 | 2.028913 |
16 | 65.536 | 42.950 | 3.453 | 39.497 | 0.655365 | 0.052689 | 0.602676 | 2.011898 | 1.876630 | 2.024657 |
17 | 131.072 | 86.098 | 6.488 | 79.610 | 0.656876 | 0.049500 | 0.607376 | 2.004610 | 1.878946 | 2.015596 |
18 | 262.144 | 172.830 | 12.125 | 160.705 | 0.659294 | 0.046253 | 0.613041 | 2.007364 | 1.868835 | 2.018653 |
19 | 524.288 | 346.826 | 22.918 | 323.908 | 0.661518 | 0.043713 | 0.617805 | 2.006747 | 1.890144 | 2.015544 |
20 | 1.048.576 | 695.271 | 43.277 | 651.994 | 0.663062 | 0.041272 | 0.621790 | 2.004668 | 1.888341 | 2.012899 |
21 | 2.097.152 | 1.393.394 | 81.888 | 1.311.506 | 0.664422 | 0.039047 | 0.625375 | 2.004102 | 1.892183 | 2.011531 |
22 | 4.194.304 | 2.792.672 | 155.433 | 2.637.239 | 0.665825 | 0.037058 | 0.628767 | 2.004223 | 1.898117 | 2.010848 |
23 | 8.388.608 | 5.595.764 | 296.061 | 5.299.703 | 0.667067 | 0.035293 | 0.631774 | 2.003731 | 1.904750 | 2.009565 |
24 | 16.777.216 | 11.209.372 | 565.531 | 10.643.841 | 0.668131 | 0.033708 | 0.634422 | 2.003189 | 1.910184 | 2.008384 |
25 | 33.554.432 | 22.450.369 | 1.082.107 | 21.368.262 | 0.669073 | 0.032249 | 0.636824 | 2.002821 | 1.913435 | 2.007571 |
26 | 67.108.864 | 44.963.219 | 2.073.985 | 42.889.234 | 0.670004 | 0.030905 | 0.639099 | 2.002783 | 1.916617 | 2.007147 |
27 | 134.217.728 | 90.040.144 | 3.984.149 | 86.055.995 | 0.670851 | 0.029684 | 0.641167 | 2.002529 | 1.921011 | 2.006471 |
28 | 268.435.456 | 180.291.228 | 7.659.642 | 172.631.586 | 0.671637 | 0.028534 | 0.643103 | 2.002343 | 1.922529 | 2.006038 |
29 | 536.870.912 | 360.980.370 | 14.749.916 | 346.230.454 | 0.672378 | 0.027474 | 0.644904 | 2.002207 | 1.925666 | 2.005603 |
30 | 1.073.741.824 | 722.701.110 | 28.457.070 | 694.244.040 | 0.673068 | 0.026503 | 0.646565 | 2.002051 | 1.929304 | 2.005150 |
31 | 2.147.483.648 | 1.446.781.397 | 54.961.198 | 1.391.820.199 | 0.673710 | 0.025593 | 0.648117 | 2.001908 | 1.931372 | 2.004800 |
32 | 4.294.967.296 | 2.896.145.603 | 106.273.113 | 2.789.872.490 | 0.674311 | 0.024744 | 0.649568 | 2.001785 | 1.933602 | 2.004478 |
33 | 8.589.934.592 | 5.797.146.313 | 205.713.289 | 5.591.433.024 | 0.674877 | 0.023948 | 0.650928 | 2.001676 | 1.935704 | 2.004189 |
34 | 17.179.869.184 | 11.603.435.989 | 398.640.437 | 11.204.795.552 | 0.675409 | 0.023204 | 0.652205 | 2.001577 | 1.937845 | 2.003922 |
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 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 1 | 2 | 0 | 3 | 0 | 1 |
4 | 16 | 4 | 1 | 2 | 0 | 3 | 0 | 1 |
5 | 32 | 6 | 2 | 3 | 0 | 3 | 0 | 3 |
6 | 64 | 8 | 2 | 5 | 1 | 3 | 1 | 3 |
7 | 128 | 16 | 9 | 6 | 5 | 3 | 5 | 3 |
8 | 256 | 29 | 13 | 15 | 13 | 3 | 10 | 3 |
9 | 512 | 51 | 27 | 23 | 26 | 3 | 19 | 3 |
10 | 1.024 | 86 | 38 | 47 | 45 | 3 | 35 | 3 |
11 | 2.048 | 162 | 78 | 83 | 79 | 3 | 77 | 3 |
12 | 4.096 | 291 | 142 | 148 | 145 | 3 | 140 | 3 |
13 | 8.192 | 548 | 279 | 268 | 269 | 3 | 273 | 3 |
14 | 16.384 | 1.014 | 510 | 503 | 505 | 3 | 503 | 3 |
15 | 32.768 | 1.840 | 946 | 893 | 929 | 3 | 905 | 3 |
16 | 65.536 | 3.453 | 1.753 | 1.699 | 1.747 | 3 | 1.700 | 3 |
17 | 131.072 | 6.488 | 3.274 | 3.213 | 3.243 | 3 | 3.239 | 3 |
18 | 262.144 | 12.125 | 6.114 | 6.010 | 6.062 | 3 | 6.057 | 3 |
19 | 524.288 | 22.918 | 11.600 | 11.317 | 11.439 | 3 | 11.473 | 3 |
20 | 1.048.576 | 43.277 | 21.886 | 21.390 | 21.559 | 3 | 21.712 | 3 |
21 | 2.097.152 | 81.888 | 41.438 | 40.449 | 40.934 | 3 | 40.948 | 3 |
22 | 4.194.304 | 155.433 | 78.686 | 76.746 | 77.696 | 3 | 77.731 | 3 |
23 | 8.388.608 | 296.061 | 149.702 | 146.358 | 148.027 | 3 | 148.028 | 3 |
24 | 16.777.216 | 565.531 | 285.674 | 279.856 | 282.807 | 3 | 282.718 | 3 |
25 | 33.554.432 | 1.082.107 | 546.939 | 535.167 | 541.031 | 3 | 541.070 | 3 |
26 | 67.108.864 | 2.073.985 | 1.047.806 | 1.026.178 | 1.036.701 | 3 | 1.037.278 | 3 |
27 | 134.217.728 | 3.984.149 | 2.011.649 | 1.972.499 | 1.991.402 | 3 | 1.992.741 | 3 |
28 | 268.435.456 | 7.659.642 | 3.864.782 | 3.794.859 | 3.829.864 | 3 | 3.829.772 | 3 |
29 | 536.870.912 | 14.749.916 | 7.442.672 | 7.307.243 | 7.374.561 | 3 | 7.375.349 | 3 |
30 | 1.073.741.824 | 28.457.070 | 14.352.882 | 14.104.187 | 14.227.192 | 3 | 14.229.872 | 3 |
31 | 2.147.483.648 | 54.961.198 | 27.711.171 | 27.250.026 | 27.480.430 | 3 | 27.480.762 | 3 |
32 | 4.294.967.296 | 106.273.113 | 53.570.953 | 52.702.159 | 53.131.022 | 3 | 53.142.085 | 3 |
33 | 8.589.934.592 | 205.713.289 | 103.673.444 | 102.039.844 | 102.850.384 | 3 | 102.862.899 | 3 |
34 | 17.179.869.184 | 398.640.437 | 200.862.299 | 197.778.137 | 199.310.612 | 3 | 199.329.819 | 3 |
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 | 0 | 1 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 10 | 5 | 5 | 3 | 2 | 3 | 2 |
5 | 32 | 11 | 6 | 5 | 3 | 2 | 4 | 2 |
6 | 64 | 14 | 8 | 6 | 3 | 3 | 4 | 4 |
7 | 128 | 41 | 26 | 15 | 6 | 14 | 9 | 12 |
8 | 256 | 100 | 52 | 48 | 16 | 32 | 21 | 31 |
9 | 512 | 230 | 115 | 115 | 40 | 72 | 49 | 69 |
10 | 1.024 | 521 | 268 | 253 | 97 | 157 | 110 | 157 |
11 | 2.048 | 1.102 | 546 | 556 | 222 | 329 | 243 | 308 |
12 | 4.096 | 2.306 | 1.130 | 1.176 | 473 | 655 | 518 | 660 |
13 | 8.192 | 4.714 | 2.320 | 2.394 | 1.024 | 1.313 | 1.041 | 1.336 |
14 | 16.384 | 9.615 | 4.731 | 4.884 | 2.136 | 2.655 | 2.121 | 2.703 |
15 | 32.768 | 19.508 | 9.719 | 9.789 | 4.367 | 5.338 | 4.389 | 5.414 |
16 | 65.536 | 39.497 | 19.814 | 19.683 | 8.914 | 10.735 | 8.983 | 10.865 |
17 | 131.072 | 79.610 | 39.634 | 39.976 | 18.175 | 21.592 | 18.221 | 21.622 |
18 | 262.144 | 160.705 | 80.248 | 80.457 | 36.958 | 43.418 | 37.131 | 43.198 |
19 | 524.288 | 323.908 | 161.652 | 162.256 | 74.850 | 86.810 | 75.191 | 87.057 |
20 | 1.048.576 | 651.994 | 325.795 | 326.199 | 151.648 | 174.164 | 152.226 | 173.956 |
21 | 2.097.152 | 1.311.506 | 655.496 | 656.010 | 306.667 | 349.069 | 306.902 | 348.868 |
22 | 4.194.304 | 2.637.239 | 1.317.876 | 1.319.363 | 619.105 | 699.605 | 619.412 | 699.117 |
23 | 8.388.608 | 5.299.703 | 2.648.204 | 2.651.499 | 1.249.321 | 1.401.306 | 1.249.331 | 1.399.745 |
24 | 16.777.216 | 10.643.841 | 5.321.099 | 5.322.742 | 2.516.754 | 2.805.940 | 2.516.905 | 2.804.242 |
25 | 33.554.432 | 21.368.262 | 10.682.200 | 10.686.062 | 5.067.329 | 5.617.272 | 5.067.478 | 5.616.183 |
26 | 67.108.864 | 42.889.234 | 21.441.164 | 21.448.070 | 10.197.285 | 11.249.163 | 10.194.465 | 11.248.321 |
27 | 134.217.728 | 86.055.995 | 43.025.096 | 43.030.899 | 20.511.046 | 22.523.420 | 20.501.979 | 22.519.550 |
28 | 268.435.456 | 172.631.586 | 86.316.001 | 86.315.585 | 41.228.951 | 45.096.735 | 41.210.321 | 45.095.579 |
29 | 536.870.912 | 346.230.454 | 173.111.960 | 173.118.494 | 82.827.729 | 90.293.489 | 82.818.398 | 90.290.838 |
30 | 1.073.741.824 | 694.244.040 | 347.122.381 | 347.121.659 | 166.364.489 | 180.759.412 | 166.350.968 | 180.769.171 |
31 | 2.147.483.648 | 1.391.820.199 | 695.891.092 | 695.929.107 | 334.058.092 | 361.856.208 | 334.038.654 | 361.867.245 |
32 | 4.294.967.296 | 2.789.872.490 | 1.394.904.049 | 1.394.968.441 | 670.596.095 | 724.343.552 | 670.595.574 | 724.337.269 |
33 | 8.589.934.592 | 5.591.433.024 | 2.795.649.468 | 2.795.783.556 | 1.345.859.425 | 1.449.832.879 | 1.345.902.042 | 1.449.838.678 |
34 | 17.179.869.184 | 11.204.795.552 | 5.602.305.085 | 5.602.490.467 | 2.700.514.385 | 2.901.882.506 | 2.700.516.874 | 2.901.881.787 |