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+79
f(0)=79
f(1)=5
f(2)=83
f(3)=11
f(4)=19
f(5)=13
f(6)=23
f(7)=1
f(8)=1
f(9)=1
f(10)=179
f(11)=1
f(12)=223
f(13)=31
f(14)=1
f(15)=1
f(16)=67
f(17)=1
f(18)=1
f(19)=1
f(20)=479
f(21)=1
f(22)=563
f(23)=1
f(24)=131
f(25)=1
f(26)=151
f(27)=101
f(28)=863
f(29)=1
f(30)=89
f(31)=1
f(32)=1103
f(33)=73
f(34)=1
f(35)=163
f(36)=1
f(37)=181
f(38)=1523
f(39)=1
f(40)=1
f(41)=1
f(42)=97
f(43)=241
f(44)=1
f(45)=263
f(46)=439
f(47)=1
f(48)=2383
f(49)=1
f(50)=2579
f(51)=1
f(52)=1
f(53)=1
f(54)=599
f(55)=1
f(56)=643
f(57)=1
f(58)=313
f(59)=1
f(60)=283
f(61)=1
f(62)=3923
f(63)=1
f(64)=167
f(65)=269
f(66)=887
f(67)=571
f(68)=4703
f(69)=1
f(70)=383
f(71)=1
f(72)=277
f(73)=1
f(74)=1
f(75)=1
f(76)=1171
f(77)=751
f(78)=6163
f(79)=1
f(80)=1
f(81)=1
f(82)=6803
f(83)=1
f(84)=1427
f(85)=1
f(86)=1
f(87)=239
f(88)=7823
f(89)=1
f(90)=8179
f(91)=1
f(92)=8543
f(93)=1091
f(94)=1783
f(95)=569
f(96)=1
f(97)=593
f(98)=421
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+79 could be written as f(y)= y^2+79 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 > 9
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 | 8 | 6 | 2 | 0.800000 | 0.600000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 56 | 36 | 20 | 0.560000 | 0.360000 | 0.560000 | 7.000000 | 6.000000 | 10.000000 |
3 | 1.000 | 610 | 241 | 369 | 0.610000 | 0.241000 | 0.610000 | 10.892858 | 6.694445 | 18.450001 |
4 | 10.000 | 6.328 | 1.657 | 4.671 | 0.632800 | 0.165700 | 0.632800 | 10.373771 | 6.875519 | 12.658537 |
5 | 100.000 | 64.752 | 12.435 | 52.317 | 0.647520 | 0.124350 | 0.647520 | 10.232617 | 7.504526 | 11.200385 |
6 | 1.000.000 | 655.343 | 100.100 | 555.243 | 0.655343 | 0.100100 | 0.655343 | 10.120815 | 8.049859 | 10.613051 |
7 | 10.000.000 | 6.609.936 | 838.412 | 5.771.524 | 0.660994 | 0.083841 | 0.660994 | 10.086224 | 8.375744 | 10.394591 |
8 | 100.000.000 | 66.510.074 | 7.216.171 | 59.293.903 | 0.665101 | 0.072162 | 0.665101 | 10.062136 | 8.606951 | 10.273526 |
9 | 1.000.000.000 | 668.234.498 | 63.345.429 | 604.889.069 | 0.668234 | 0.063345 | 0.668234 | 10.047117 | 8.778260 | 10.201539 |
10 | 10.000.000.000 | 6.707.575.513 | 564.452.922 | 6.143.122.591 | 0.670758 | 0.056445 | 0.670758 | 10.037757 | 8.910713 | 10.155784 |
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 | 7 | 5 | 2 | 0.875000 | 0.625000 | 0.250000 | 1.400000 | 1.250000 | 2.000000 |
4 | 16 | 11 | 8 | 3 | 0.687500 | 0.500000 | 0.187500 | 1.571429 | 1.600000 | 1.500000 |
5 | 32 | 19 | 13 | 6 | 0.593750 | 0.406250 | 0.187500 | 1.727273 | 1.625000 | 2.000000 |
6 | 64 | 35 | 22 | 13 | 0.546875 | 0.343750 | 0.203125 | 1.842105 | 1.692308 | 2.166667 |
7 | 128 | 73 | 43 | 30 | 0.570312 | 0.335938 | 0.234375 | 2.085714 | 1.954545 | 2.307692 |
8 | 256 | 148 | 73 | 75 | 0.578125 | 0.285156 | 0.292969 | 2.027397 | 1.697674 | 2.500000 |
9 | 512 | 304 | 137 | 167 | 0.593750 | 0.267578 | 0.326172 | 2.054054 | 1.876712 | 2.226667 |
10 | 1.024 | 625 | 244 | 381 | 0.610352 | 0.238281 | 0.372070 | 2.055921 | 1.781022 | 2.281437 |
11 | 2.048 | 1.258 | 440 | 818 | 0.614258 | 0.214844 | 0.399414 | 2.012800 | 1.803279 | 2.146982 |
12 | 4.096 | 2.551 | 792 | 1.759 | 0.622803 | 0.193359 | 0.429443 | 2.027822 | 1.800000 | 2.150367 |
13 | 8.192 | 5.180 | 1.415 | 3.765 | 0.632324 | 0.172729 | 0.459595 | 2.030576 | 1.786616 | 2.140421 |
14 | 16.384 | 10.458 | 2.533 | 7.925 | 0.638306 | 0.154602 | 0.483704 | 2.018919 | 1.790106 | 2.104914 |
15 | 32.768 | 21.042 | 4.603 | 16.439 | 0.642151 | 0.140472 | 0.501678 | 2.012048 | 1.817213 | 2.074322 |
16 | 65.536 | 42.328 | 8.517 | 33.811 | 0.645874 | 0.129959 | 0.515915 | 2.011596 | 1.850315 | 2.056755 |
17 | 131.072 | 85.028 | 15.870 | 69.158 | 0.648712 | 0.121078 | 0.527634 | 2.008789 | 1.863332 | 2.045429 |
18 | 262.144 | 170.667 | 29.641 | 141.026 | 0.651043 | 0.113071 | 0.537971 | 2.007186 | 1.867738 | 2.039186 |
19 | 524.288 | 342.623 | 55.467 | 287.156 | 0.653502 | 0.105795 | 0.547707 | 2.007553 | 1.871293 | 2.036192 |
20 | 1.048.576 | 687.323 | 104.525 | 582.798 | 0.655482 | 0.099683 | 0.555799 | 2.006062 | 1.884454 | 2.029552 |
21 | 2.097.152 | 1.378.852 | 197.569 | 1.181.283 | 0.657488 | 0.094208 | 0.563280 | 2.006119 | 1.890160 | 2.026917 |
22 | 4.194.304 | 2.764.591 | 374.636 | 2.389.955 | 0.659130 | 0.089320 | 0.569810 | 2.004995 | 1.896229 | 2.023186 |
23 | 8.388.608 | 5.540.926 | 712.494 | 4.828.432 | 0.660530 | 0.084936 | 0.575594 | 2.004248 | 1.901830 | 2.020303 |
24 | 16.777.216 | 11.106.485 | 1.357.206 | 9.749.279 | 0.661998 | 0.080896 | 0.581102 | 2.004446 | 1.904867 | 2.019140 |
25 | 33.554.432 | 22.256.588 | 2.592.909 | 19.663.679 | 0.663298 | 0.077275 | 0.586023 | 2.003927 | 1.910476 | 2.016937 |
26 | 67.108.864 | 44.589.784 | 4.962.747 | 39.627.037 | 0.664440 | 0.073951 | 0.590489 | 2.003442 | 1.913969 | 2.015240 |
27 | 134.217.728 | 89.326.216 | 9.515.346 | 79.810.870 | 0.665532 | 0.070895 | 0.594637 | 2.003289 | 1.917355 | 2.014051 |
28 | 268.435.456 | 178.919.994 | 18.277.030 | 160.642.964 | 0.666529 | 0.068087 | 0.598442 | 2.002995 | 1.920795 | 2.012795 |
29 | 536.870.912 | 358.335.755 | 35.165.559 | 323.170.196 | 0.667452 | 0.065501 | 0.601951 | 2.002771 | 1.924030 | 2.011730 |
30 | 1.073.741.824 | 717.604.726 | 67.760.732 | 649.843.994 | 0.668321 | 0.063107 | 0.605214 | 2.002604 | 1.926906 | 2.010841 |
31 | 2.147.483.648 | 1.436.952.802 | 130.718.111 | 1.306.234.691 | 0.669133 | 0.060870 | 0.608263 | 2.002429 | 1.929113 | 2.010074 |
32 | 4.294.967.296 | 2.877.169.934 | 252.524.628 | 2.624.645.306 | 0.669893 | 0.058795 | 0.611098 | 2.002272 | 1.931826 | 2.009321 |
33 | 8.589.934.592 | 5.760.465.472 | 488.371.788 | 5.272.093.684 | 0.670606 | 0.056854 | 0.613752 | 2.002129 | 1.933957 | 2.008688 |
34 | 17.179.869.184 | 11.532.449.206 | 945.549.732 | 10.586.899.474 | 0.671277 | 0.055038 | 0.616239 | 2.001999 | 1.936127 | 2.008101 |
35 | 34.359.738.368 | 23.086.587.034 | 1.832.568.246 | 21.254.018.788 | 0.671908 | 0.053335 | 0.618573 | 2.001881 | 1.938098 | 2.007577 |
36 | 68.719.476.736 | 46.214.149.227 | 3.555.153.936 | 42.658.995.291 | 0.672504 | 0.051734 | 0.620770 | 2.001775 | 1.939985 | 2.007102 |
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 | 1 | 2 | 0 | 1 | 1 | 1 |
2 | 4 | 4 | 1 | 3 | 0 | 2 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 2 | 1 |
4 | 16 | 8 | 4 | 4 | 0 | 3 | 2 | 3 |
5 | 32 | 13 | 4 | 9 | 0 | 4 | 3 | 6 |
6 | 64 | 22 | 9 | 13 | 2 | 8 | 4 | 8 |
7 | 128 | 43 | 16 | 27 | 5 | 14 | 7 | 17 |
8 | 256 | 73 | 31 | 42 | 7 | 26 | 11 | 29 |
9 | 512 | 137 | 59 | 78 | 15 | 46 | 20 | 56 |
10 | 1.024 | 244 | 114 | 130 | 31 | 93 | 32 | 88 |
11 | 2.048 | 440 | 195 | 245 | 49 | 161 | 60 | 170 |
12 | 4.096 | 792 | 360 | 432 | 97 | 287 | 105 | 303 |
13 | 8.192 | 1.415 | 643 | 772 | 194 | 515 | 191 | 515 |
14 | 16.384 | 2.533 | 1.159 | 1.374 | 346 | 911 | 341 | 935 |
15 | 32.768 | 4.603 | 2.085 | 2.518 | 613 | 1.687 | 624 | 1.679 |
16 | 65.536 | 8.517 | 3.893 | 4.624 | 1.134 | 3.106 | 1.149 | 3.128 |
17 | 131.072 | 15.870 | 7.130 | 8.740 | 2.158 | 5.792 | 2.116 | 5.804 |
18 | 262.144 | 29.641 | 13.362 | 16.279 | 3.994 | 10.867 | 3.917 | 10.863 |
19 | 524.288 | 55.467 | 25.100 | 30.367 | 7.386 | 20.402 | 7.342 | 20.337 |
20 | 1.048.576 | 104.525 | 47.330 | 57.195 | 13.886 | 38.407 | 13.794 | 38.438 |
21 | 2.097.152 | 197.569 | 88.956 | 108.613 | 26.176 | 72.692 | 25.975 | 72.726 |
22 | 4.194.304 | 374.636 | 168.547 | 206.089 | 49.178 | 138.136 | 49.101 | 138.221 |
23 | 8.388.608 | 712.494 | 320.430 | 392.064 | 93.235 | 262.657 | 93.508 | 263.094 |
24 | 16.777.216 | 1.357.206 | 610.126 | 747.080 | 177.468 | 500.930 | 177.607 | 501.201 |
25 | 33.554.432 | 2.592.909 | 1.163.118 | 1.429.791 | 338.348 | 957.861 | 338.549 | 958.151 |
26 | 67.108.864 | 4.962.747 | 2.225.607 | 2.737.140 | 647.099 | 1.835.262 | 646.592 | 1.833.794 |
27 | 134.217.728 | 9.515.346 | 4.265.937 | 5.249.409 | 1.238.382 | 3.520.035 | 1.239.393 | 3.517.536 |
28 | 268.435.456 | 18.277.030 | 8.192.020 | 10.085.010 | 2.375.323 | 6.763.762 | 2.376.224 | 6.761.721 |
29 | 536.870.912 | 35.165.559 | 15.755.223 | 19.410.336 | 4.562.414 | 13.019.464 | 4.565.176 | 13.018.505 |
30 | 1.073.741.824 | 67.760.732 | 30.346.178 | 37.414.554 | 8.782.155 | 25.098.176 | 8.781.475 | 25.098.926 |
31 | 2.147.483.648 | 130.718.111 | 58.530.424 | 72.187.687 | 16.922.485 | 48.433.985 | 16.922.770 | 48.438.871 |
32 | 4.294.967.296 | 252.524.628 | 113.033.797 | 139.490.831 | 32.646.660 | 93.610.433 | 32.654.635 | 93.612.900 |
33 | 8.589.934.592 | 488.371.788 | 218.547.028 | 269.824.760 | 63.063.616 | 181.116.372 | 63.079.896 | 181.111.904 |
34 | 17.179.869.184 | 945.549.732 | 423.036.380 | 522.513.352 | 121.978.782 | 350.791.460 | 122.003.029 | 350.776.461 |
35 | 34.359.738.368 | 1.832.568.246 | 819.701.075 | 1.012.867.171 | 236.194.704 | 680.091.048 | 236.208.155 | 680.074.339 |
36 | 68.719.476.736 | 3.555.153.936 | 1.589.900.747 | 1.965.253.189 | 457.793.200 | 1.319.786.001 | 457.827.769 | 1.319.746.966 |
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 | 1 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 3 | 2 | 1 | 0 | 2 | 0 | 1 |
5 | 32 | 6 | 3 | 3 | 1 | 3 | 0 | 2 |
6 | 64 | 13 | 8 | 5 | 3 | 5 | 0 | 5 |
7 | 128 | 30 | 15 | 15 | 7 | 11 | 2 | 10 |
8 | 256 | 75 | 39 | 36 | 16 | 20 | 17 | 22 |
9 | 512 | 167 | 83 | 84 | 37 | 39 | 43 | 48 |
10 | 1.024 | 381 | 194 | 187 | 80 | 95 | 96 | 110 |
11 | 2.048 | 818 | 414 | 404 | 186 | 218 | 192 | 222 |
12 | 4.096 | 1.759 | 906 | 853 | 410 | 478 | 413 | 458 |
13 | 8.192 | 3.765 | 1.913 | 1.852 | 884 | 989 | 921 | 971 |
14 | 16.384 | 7.925 | 4.008 | 3.917 | 1.894 | 2.035 | 1.955 | 2.041 |
15 | 32.768 | 16.439 | 8.336 | 8.103 | 3.956 | 4.259 | 4.033 | 4.191 |
16 | 65.536 | 33.811 | 17.087 | 16.724 | 8.333 | 8.636 | 8.321 | 8.521 |
17 | 131.072 | 69.158 | 34.868 | 34.290 | 17.077 | 17.682 | 17.102 | 17.297 |
18 | 262.144 | 141.026 | 71.242 | 69.784 | 34.755 | 35.955 | 34.768 | 35.548 |
19 | 524.288 | 287.156 | 144.672 | 142.484 | 70.787 | 73.060 | 70.523 | 72.786 |
20 | 1.048.576 | 582.798 | 293.677 | 289.121 | 143.943 | 147.652 | 143.251 | 147.952 |
21 | 2.097.152 | 1.181.283 | 594.851 | 586.432 | 291.808 | 299.438 | 290.913 | 299.124 |
22 | 4.194.304 | 2.389.955 | 1.203.497 | 1.186.458 | 590.474 | 604.982 | 589.945 | 604.554 |
23 | 8.388.608 | 4.828.432 | 2.430.504 | 2.397.928 | 1.193.486 | 1.221.313 | 1.192.242 | 1.221.391 |
24 | 16.777.216 | 9.749.279 | 4.906.138 | 4.843.141 | 2.409.478 | 2.465.285 | 2.409.282 | 2.465.234 |
25 | 33.554.432 | 19.663.679 | 9.892.587 | 9.771.092 | 4.864.918 | 4.966.930 | 4.863.291 | 4.968.540 |
26 | 67.108.864 | 39.627.037 | 19.925.385 | 19.701.652 | 9.807.700 | 10.004.889 | 9.805.470 | 10.008.978 |
27 | 134.217.728 | 79.810.870 | 40.119.670 | 39.691.200 | 19.761.810 | 20.143.727 | 19.755.946 | 20.149.387 |
28 | 268.435.456 | 160.642.964 | 80.731.199 | 79.911.765 | 39.787.867 | 40.534.715 | 39.782.735 | 40.537.647 |
29 | 536.870.912 | 323.170.196 | 162.372.463 | 160.797.733 | 80.065.244 | 81.522.121 | 80.059.833 | 81.522.998 |
30 | 1.073.741.824 | 649.843.994 | 326.451.670 | 323.392.324 | 161.058.963 | 163.864.116 | 161.049.024 | 163.871.891 |
31 | 2.147.483.648 | 1.306.234.691 | 656.083.333 | 650.151.358 | 323.845.585 | 329.275.740 | 323.829.261 | 329.284.105 |
32 | 4.294.967.296 | 2.624.645.306 | 1.318.060.231 | 1.306.585.075 | 650.871.671 | 661.464.229 | 650.880.467 | 661.428.939 |
33 | 8.589.934.592 | 5.272.093.684 | 2.647.148.605 | 2.624.945.079 | 1.307.741.382 | 1.328.278.010 | 1.307.822.366 | 1.328.251.926 |
34 | 17.179.869.184 | 10.586.899.474 | 5.315.020.098 | 5.271.879.376 | 2.626.765.483 | 2.666.656.772 | 2.626.824.129 | 2.666.653.090 |
35 | 34.359.738.368 | 21.254.018.788 | 10.668.840.447 | 10.585.178.341 | 5.274.728.245 | 5.352.282.901 | 5.274.815.145 | 5.352.192.497 |
36 | 68.719.476.736 | 42.658.995.291 | 21.410.597.604 | 21.248.397.687 | 10.589.337.453 | 10.740.126.032 | 10.589.501.838 | 10.740.029.968 |