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-80x-113
f(0)=113
f(1)=3
f(2)=269
f(3)=43
f(4)=139
f(5)=61
f(6)=557
f(7)=13
f(8)=53
f(9)=47
f(10)=271
f(11)=109
f(12)=929
f(13)=41
f(14)=17
f(15)=1
f(16)=379
f(17)=37
f(18)=1229
f(19)=1
f(20)=101
f(21)=1
f(22)=463
f(23)=89
f(24)=31
f(25)=1
f(26)=1
f(27)=193
f(28)=523
f(29)=199
f(30)=1613
f(31)=1
f(32)=97
f(33)=1
f(34)=1
f(35)=211
f(36)=1697
f(37)=71
f(38)=1709
f(39)=107
f(40)=571
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=223
f(85)=1
f(86)=1
f(87)=1
f(88)=197
f(89)=1
f(90)=787
f(91)=1
f(92)=991
f(93)=137
f(94)=401
f(95)=1
f(96)=1423
f(97)=1
f(98)=127
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-80x-113 could be written as f(y)= y^2-1713 with x=y+40
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-40
f'(x)>2x-81 with x > 41
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 35 | 12 | 23 | 0.350000 | 0.120000 | 0.350000 | 3.500000 | 4.000000 | 3.285714 |
3 | 1.000 | 584 | 107 | 477 | 0.584000 | 0.107000 | 0.584000 | 16.685715 | 8.916667 | 20.739130 |
4 | 10.000 | 6.450 | 838 | 5.612 | 0.645000 | 0.083800 | 0.645000 | 11.044520 | 7.831776 | 11.765199 |
5 | 100.000 | 66.046 | 6.553 | 59.493 | 0.660460 | 0.065530 | 0.660460 | 10.239690 | 7.819809 | 10.601033 |
6 | 1.000.000 | 665.941 | 53.995 | 611.946 | 0.665941 | 0.053995 | 0.665941 | 10.082988 | 8.239738 | 10.286016 |
7 | 10.000.000 | 6.700.190 | 456.998 | 6.243.192 | 0.670019 | 0.045700 | 0.670019 | 10.061236 | 8.463710 | 10.202194 |
8 | 100.000.000 | 67.293.498 | 3.964.141 | 63.329.357 | 0.672935 | 0.039641 | 0.672935 | 10.043521 | 8.674307 | 10.143746 |
9 | 1.000.000.000 | 675.202.419 | 34.967.111 | 640.235.308 | 0.675202 | 0.034967 | 0.675202 | 10.033695 | 8.820855 | 10.109613 |
10 | 10.000.000.000 | 6.770.031.257 | 312.965.616 | 6.457.065.641 | 0.677003 | 0.031297 | 0.677003 | 10.026669 | 8.950285 | 10.085457 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 14 | 4 | 10 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 1.333333 | 2.000000 |
5 | 32 | 24 | 6 | 18 | 0.750000 | 0.187500 | 0.562500 | 1.714286 | 1.500000 | 1.800000 |
6 | 64 | 29 | 8 | 21 | 0.453125 | 0.125000 | 0.328125 | 1.208333 | 1.333333 | 1.166667 |
7 | 128 | 46 | 17 | 29 | 0.359375 | 0.132812 | 0.226562 | 1.586207 | 2.125000 | 1.380952 |
8 | 256 | 118 | 34 | 84 | 0.460938 | 0.132812 | 0.328125 | 2.565217 | 2.000000 | 2.896552 |
9 | 512 | 281 | 66 | 215 | 0.548828 | 0.128906 | 0.419922 | 2.381356 | 1.941176 | 2.559524 |
10 | 1.024 | 599 | 108 | 491 | 0.584961 | 0.105469 | 0.479492 | 2.131673 | 1.636364 | 2.283721 |
11 | 2.048 | 1.255 | 210 | 1.045 | 0.612793 | 0.102539 | 0.510254 | 2.095159 | 1.944444 | 2.128309 |
12 | 4.096 | 2.586 | 377 | 2.209 | 0.631348 | 0.092041 | 0.539307 | 2.060558 | 1.795238 | 2.113876 |
13 | 8.192 | 5.269 | 712 | 4.557 | 0.643188 | 0.086914 | 0.556274 | 2.037510 | 1.888594 | 2.062924 |
14 | 16.384 | 10.646 | 1.292 | 9.354 | 0.649780 | 0.078857 | 0.570923 | 2.020497 | 1.814607 | 2.052666 |
15 | 32.768 | 21.457 | 2.370 | 19.087 | 0.654816 | 0.072327 | 0.582489 | 2.015499 | 1.834365 | 2.040517 |
16 | 65.536 | 43.169 | 4.482 | 38.687 | 0.658707 | 0.068390 | 0.590317 | 2.011884 | 1.891139 | 2.026877 |
17 | 131.072 | 86.582 | 8.372 | 78.210 | 0.660568 | 0.063873 | 0.596695 | 2.005652 | 1.867916 | 2.021609 |
18 | 262.144 | 173.738 | 15.804 | 157.934 | 0.662758 | 0.060287 | 0.602470 | 2.006629 | 1.887721 | 2.019358 |
19 | 524.288 | 348.374 | 29.860 | 318.514 | 0.664471 | 0.056953 | 0.607517 | 2.005169 | 1.889395 | 2.016754 |
20 | 1.048.576 | 698.314 | 56.364 | 641.950 | 0.665964 | 0.053753 | 0.612211 | 2.004495 | 1.887609 | 2.015453 |
21 | 2.097.152 | 1.399.528 | 106.751 | 1.292.777 | 0.667347 | 0.050903 | 0.616444 | 2.004153 | 1.893957 | 2.013828 |
22 | 4.194.304 | 2.804.208 | 203.283 | 2.600.925 | 0.668575 | 0.048466 | 0.620109 | 2.003681 | 1.904273 | 2.011890 |
23 | 8.388.608 | 5.617.888 | 387.916 | 5.229.972 | 0.669704 | 0.046243 | 0.623461 | 2.003378 | 1.908256 | 2.010812 |
24 | 16.777.216 | 11.253.611 | 741.676 | 10.511.935 | 0.670767 | 0.044207 | 0.626560 | 2.003175 | 1.911950 | 2.009941 |
25 | 33.554.432 | 22.536.590 | 1.420.395 | 21.116.195 | 0.671643 | 0.042331 | 0.629312 | 2.002610 | 1.915115 | 2.008783 |
26 | 67.108.864 | 45.130.056 | 2.722.702 | 42.407.354 | 0.672490 | 0.040571 | 0.631919 | 2.002524 | 1.916863 | 2.008286 |
27 | 134.217.728 | 90.364.759 | 5.231.279 | 85.133.480 | 0.673270 | 0.038976 | 0.634294 | 2.002319 | 1.921356 | 2.007517 |
28 | 268.435.456 | 180.921.995 | 10.061.563 | 170.860.432 | 0.673987 | 0.037482 | 0.636505 | 2.002130 | 1.923347 | 2.006971 |
29 | 536.870.912 | 362.199.455 | 19.387.085 | 342.812.370 | 0.674649 | 0.036111 | 0.638538 | 2.001965 | 1.926846 | 2.006388 |
30 | 1.073.741.824 | 725.062.380 | 37.408.196 | 687.654.184 | 0.675267 | 0.034839 | 0.640428 | 2.001832 | 1.929542 | 2.005920 |
31 | 2.147.483.648 | 1.451.364.572 | 72.275.486 | 1.379.089.086 | 0.675844 | 0.033656 | 0.642188 | 2.001710 | 1.932076 | 2.005498 |
32 | 4.294.967.296 | 2.905.054.424 | 139.810.523 | 2.765.243.901 | 0.676386 | 0.032552 | 0.643834 | 2.001602 | 1.934411 | 2.005124 |
33 | 8.589.934.592 | 5.814.489.426 | 270.712.581 | 5.543.776.845 | 0.676896 | 0.031515 | 0.645381 | 2.001508 | 1.936282 | 2.004806 |
34 | 17.179.869.184 | 11.637.199.241 | 524.716.243 | 11.112.482.998 | 0.677374 | 0.030543 | 0.646832 | 2.001414 | 1.938278 | 2.004497 |
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 | 2 | 1 | 0 | 1 | 0 |
2 | 4 | 2 | 0 | 2 | 1 | 0 | 1 | 0 |
3 | 8 | 3 | 0 | 3 | 1 | 0 | 2 | 0 |
4 | 16 | 4 | 0 | 4 | 2 | 0 | 2 | 0 |
5 | 32 | 6 | 0 | 6 | 2 | 0 | 4 | 0 |
6 | 64 | 8 | 0 | 8 | 3 | 0 | 5 | 0 |
7 | 128 | 17 | 9 | 8 | 3 | 5 | 5 | 4 |
8 | 256 | 34 | 26 | 8 | 3 | 13 | 5 | 13 |
9 | 512 | 66 | 58 | 8 | 3 | 27 | 5 | 31 |
10 | 1.024 | 108 | 100 | 8 | 3 | 47 | 5 | 53 |
11 | 2.048 | 210 | 202 | 8 | 3 | 97 | 5 | 105 |
12 | 4.096 | 377 | 369 | 8 | 3 | 183 | 5 | 186 |
13 | 8.192 | 712 | 704 | 8 | 3 | 355 | 5 | 349 |
14 | 16.384 | 1.292 | 1.284 | 8 | 3 | 638 | 5 | 646 |
15 | 32.768 | 2.370 | 2.362 | 8 | 3 | 1.180 | 5 | 1.182 |
16 | 65.536 | 4.482 | 4.474 | 8 | 3 | 2.248 | 5 | 2.226 |
17 | 131.072 | 8.372 | 8.364 | 8 | 3 | 4.208 | 5 | 4.156 |
18 | 262.144 | 15.804 | 15.796 | 8 | 3 | 7.940 | 5 | 7.856 |
19 | 524.288 | 29.860 | 29.852 | 8 | 3 | 14.932 | 5 | 14.920 |
20 | 1.048.576 | 56.364 | 56.356 | 8 | 3 | 28.153 | 5 | 28.203 |
21 | 2.097.152 | 106.751 | 106.743 | 8 | 3 | 53.240 | 5 | 53.503 |
22 | 4.194.304 | 203.283 | 203.275 | 8 | 3 | 101.536 | 5 | 101.739 |
23 | 8.388.608 | 387.916 | 387.908 | 8 | 3 | 193.908 | 5 | 194.000 |
24 | 16.777.216 | 741.676 | 741.668 | 8 | 3 | 370.826 | 5 | 370.842 |
25 | 33.554.432 | 1.420.395 | 1.420.387 | 8 | 3 | 710.065 | 5 | 710.322 |
26 | 67.108.864 | 2.722.702 | 2.722.694 | 8 | 3 | 1.361.573 | 5 | 1.361.121 |
27 | 134.217.728 | 5.231.279 | 5.231.271 | 8 | 3 | 2.615.899 | 5 | 2.615.372 |
28 | 268.435.456 | 10.061.563 | 10.061.555 | 8 | 3 | 5.030.828 | 5 | 5.030.727 |
29 | 536.870.912 | 19.387.085 | 19.387.077 | 8 | 3 | 9.694.654 | 5 | 9.692.423 |
30 | 1.073.741.824 | 37.408.196 | 37.408.188 | 8 | 3 | 18.705.079 | 5 | 18.703.109 |
31 | 2.147.483.648 | 72.275.486 | 72.275.478 | 8 | 3 | 36.140.849 | 5 | 36.134.629 |
32 | 4.294.967.296 | 139.810.523 | 139.810.515 | 8 | 3 | 69.907.633 | 5 | 69.902.882 |
33 | 8.589.934.592 | 270.712.581 | 270.712.573 | 8 | 3 | 135.359.260 | 5 | 135.353.313 |
34 | 17.179.869.184 | 524.716.243 | 524.716.235 | 8 | 3 | 262.345.692 | 5 | 262.370.543 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 3 | 2 | 0 | 0 | 3 | 0 | 0 |
3 | 8 | 5 | 3 | 1 | 0 | 3 | 2 | 0 |
4 | 16 | 10 | 6 | 3 | 1 | 4 | 3 | 2 |
5 | 32 | 18 | 12 | 5 | 4 | 5 | 5 | 4 |
6 | 64 | 21 | 14 | 6 | 4 | 8 | 5 | 4 |
7 | 128 | 29 | 15 | 13 | 6 | 11 | 6 | 6 |
8 | 256 | 84 | 35 | 48 | 22 | 22 | 23 | 17 |
9 | 512 | 215 | 92 | 122 | 57 | 51 | 54 | 53 |
10 | 1.024 | 491 | 210 | 280 | 132 | 119 | 124 | 116 |
11 | 2.048 | 1.045 | 462 | 582 | 264 | 263 | 280 | 238 |
12 | 4.096 | 2.209 | 981 | 1.227 | 566 | 537 | 585 | 521 |
13 | 8.192 | 4.557 | 2.035 | 2.521 | 1.184 | 1.097 | 1.222 | 1.054 |
14 | 16.384 | 9.354 | 4.180 | 5.173 | 2.454 | 2.244 | 2.481 | 2.175 |
15 | 32.768 | 19.087 | 8.651 | 10.435 | 4.936 | 4.576 | 5.033 | 4.542 |
16 | 65.536 | 38.687 | 17.705 | 20.981 | 9.981 | 9.257 | 10.079 | 9.370 |
17 | 131.072 | 78.210 | 36.198 | 42.011 | 20.170 | 18.769 | 20.384 | 18.887 |
18 | 262.144 | 157.934 | 73.731 | 84.202 | 40.719 | 38.066 | 40.857 | 38.292 |
19 | 524.288 | 318.514 | 149.523 | 168.990 | 82.244 | 76.847 | 82.318 | 77.105 |
20 | 1.048.576 | 641.950 | 302.117 | 339.832 | 165.244 | 155.494 | 165.475 | 155.737 |
21 | 2.097.152 | 1.292.777 | 611.134 | 681.642 | 332.908 | 313.967 | 332.286 | 313.616 |
22 | 4.194.304 | 2.600.925 | 1.232.786 | 1.368.138 | 667.685 | 632.744 | 667.143 | 633.353 |
23 | 8.388.608 | 5.229.972 | 2.486.084 | 2.743.887 | 1.340.003 | 1.274.610 | 1.340.157 | 1.275.202 |
24 | 16.777.216 | 10.511.935 | 5.012.737 | 5.499.197 | 2.689.964 | 2.564.765 | 2.691.473 | 2.565.733 |
25 | 33.554.432 | 21.116.195 | 10.094.552 | 11.021.642 | 5.399.242 | 5.157.029 | 5.398.810 | 5.161.114 |
26 | 67.108.864 | 42.407.354 | 20.313.403 | 22.093.950 | 10.833.780 | 10.367.144 | 10.834.314 | 10.372.116 |
27 | 134.217.728 | 85.133.480 | 40.855.611 | 44.277.868 | 21.728.951 | 20.833.892 | 21.734.958 | 20.835.679 |
28 | 268.435.456 | 170.860.432 | 82.142.364 | 88.718.067 | 43.571.525 | 41.851.703 | 43.580.563 | 41.856.641 |
29 | 536.870.912 | 342.812.370 | 165.075.278 | 177.737.091 | 87.350.099 | 84.034.779 | 87.376.037 | 84.051.455 |
30 | 1.073.741.824 | 687.654.184 | 331.628.997 | 356.025.186 | 175.092.719 | 168.706.934 | 175.131.167 | 168.723.364 |
31 | 2.147.483.648 | 1.379.089.086 | 665.978.522 | 713.110.563 | 350.934.338 | 338.578.593 | 350.964.230 | 338.611.925 |
32 | 4.294.967.296 | 2.765.243.901 | 1.337.056.503 | 1.428.187.397 | 703.208.459 | 679.366.138 | 703.273.662 | 679.395.642 |
33 | 8.589.934.592 | 5.543.776.845 | 2.683.717.362 | 2.860.059.482 | 1.409.014.066 | 1.362.798.903 | 1.409.097.765 | 1.362.866.111 |
34 | 17.179.869.184 | 11.112.482.998 | 5.385.509.211 | 5.726.973.786 | 2.822.861.742 | 2.733.309.759 | 2.822.925.192 | 2.733.386.305 |