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-66x+5
f(0)=5
f(1)=3
f(2)=41
f(3)=23
f(4)=1
f(5)=1
f(6)=71
f(7)=17
f(8)=1
f(9)=127
f(10)=37
f(11)=1
f(12)=643
f(13)=19
f(14)=241
f(15)=1
f(16)=53
f(17)=1
f(18)=859
f(19)=1
f(20)=61
f(21)=47
f(22)=107
f(23)=1
f(24)=59
f(25)=1
f(26)=1
f(27)=131
f(28)=353
f(29)=89
f(30)=43
f(31)=1
f(32)=1
f(33)=271
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)=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)=199
f(75)=1
f(76)=1
f(77)=1
f(78)=941
f(79)=1
f(80)=1
f(81)=1
f(82)=439
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=229
f(88)=647
f(89)=1
f(90)=433
f(91)=1
f(92)=1
f(93)=1
f(94)=293
f(95)=1
f(96)=577
f(97)=251
f(98)=349
f(99)=409
b) Substitution of the polynom
The polynom f(x)=x^2-66x+5 could be written as f(y)= y^2-1084 with x=y+33
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-33
f'(x)>2x-67 with x > 33
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 | 3 | 5 | 0.800000 | 0.300000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 32 | 10 | 22 | 0.320000 | 0.100000 | 0.220000 | 4.000000 | 3.333333 | 4.400000 |
3 | 1.000 | 537 | 86 | 451 | 0.537000 | 0.086000 | 0.451000 | 16.781250 | 8.600000 | 20.500000 |
4 | 10.000 | 6.063 | 604 | 5.459 | 0.606300 | 0.060400 | 0.545900 | 11.290503 | 7.023256 | 12.104213 |
5 | 100.000 | 62.840 | 4.589 | 58.251 | 0.628400 | 0.045890 | 0.582510 | 10.364506 | 7.597682 | 10.670635 |
6 | 1.000.000 | 640.423 | 36.803 | 603.620 | 0.640423 | 0.036803 | 0.603620 | 10.191327 | 8.019830 | 10.362397 |
7 | 10.000.000 | 6.481.212 | 311.163 | 6.170.049 | 0.648121 | 0.031116 | 0.617005 | 10.120205 | 8.454827 | 10.221744 |
8 | 100.000.000 | 65.384.056 | 2.683.498 | 62.700.558 | 0.653841 | 0.026835 | 0.627006 | 10.088245 | 8.624091 | 10.162085 |
9 | 1.000.000.000 | 658.285.078 | 23.608.183 | 634.676.895 | 0.658285 | 0.023608 | 0.634677 | 10.067975 | 8.797541 | 10.122348 |
10 | 10.000.000.000 | 6.618.255.483 | 210.761.831 | 6.407.493.652 | 0.661826 | 0.021076 | 0.640749 | 10.053783 | 8.927490 | 10.095678 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 2.000000 | 1.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 1.000000 | 2.000000 |
4 | 16 | 11 | 4 | 7 | 0.687500 | 0.250000 | 0.437500 | 1.833333 | 2.000000 | 1.750000 |
5 | 32 | 19 | 6 | 13 | 0.593750 | 0.187500 | 0.406250 | 1.727273 | 1.500000 | 1.857143 |
6 | 64 | 20 | 7 | 13 | 0.312500 | 0.109375 | 0.203125 | 1.052632 | 1.166667 | 1.000000 |
7 | 128 | 44 | 14 | 30 | 0.343750 | 0.109375 | 0.234375 | 2.200000 | 2.000000 | 2.307692 |
8 | 256 | 107 | 27 | 80 | 0.417969 | 0.105469 | 0.312500 | 2.431818 | 1.928571 | 2.666667 |
9 | 512 | 248 | 48 | 200 | 0.484375 | 0.093750 | 0.390625 | 2.317757 | 1.777778 | 2.500000 |
10 | 1.024 | 552 | 89 | 463 | 0.539062 | 0.086914 | 0.452148 | 2.225806 | 1.854167 | 2.315000 |
11 | 2.048 | 1.162 | 157 | 1.005 | 0.567383 | 0.076660 | 0.490723 | 2.105072 | 1.764045 | 2.170626 |
12 | 4.096 | 2.424 | 287 | 2.137 | 0.591797 | 0.070068 | 0.521729 | 2.086059 | 1.828025 | 2.126368 |
13 | 8.192 | 4.930 | 516 | 4.414 | 0.601807 | 0.062988 | 0.538818 | 2.033828 | 1.797909 | 2.065512 |
14 | 16.384 | 10.045 | 924 | 9.121 | 0.613098 | 0.056396 | 0.556702 | 2.037525 | 1.790698 | 2.066380 |
15 | 32.768 | 20.313 | 1.679 | 18.634 | 0.619904 | 0.051239 | 0.568665 | 2.022200 | 1.817100 | 2.042978 |
16 | 65.536 | 40.986 | 3.156 | 37.830 | 0.625397 | 0.048157 | 0.577240 | 2.017723 | 1.879690 | 2.030160 |
17 | 131.072 | 82.581 | 5.849 | 76.732 | 0.630043 | 0.044624 | 0.585419 | 2.014859 | 1.853295 | 2.028337 |
18 | 262.144 | 166.090 | 11.007 | 155.083 | 0.633583 | 0.041988 | 0.591595 | 2.011237 | 1.881860 | 2.021099 |
19 | 524.288 | 334.163 | 20.515 | 313.648 | 0.637365 | 0.039129 | 0.598236 | 2.011939 | 1.863814 | 2.022453 |
20 | 1.048.576 | 671.568 | 38.518 | 633.050 | 0.640457 | 0.036734 | 0.603724 | 2.009702 | 1.877553 | 2.018345 |
21 | 2.097.152 | 1.348.745 | 72.936 | 1.275.809 | 0.643132 | 0.034779 | 0.608353 | 2.008352 | 1.893556 | 2.015337 |
22 | 4.194.304 | 2.707.140 | 138.837 | 2.568.303 | 0.645432 | 0.033101 | 0.612331 | 2.007155 | 1.903546 | 2.013078 |
23 | 8.388.608 | 5.431.953 | 264.067 | 5.167.886 | 0.647539 | 0.031479 | 0.616060 | 2.006528 | 1.901993 | 2.012179 |
24 | 16.777.216 | 10.896.884 | 503.689 | 10.393.195 | 0.649505 | 0.030022 | 0.619483 | 2.006071 | 1.907429 | 2.011111 |
25 | 33.554.432 | 21.854.568 | 962.510 | 20.892.058 | 0.651317 | 0.028685 | 0.622632 | 2.005579 | 1.910921 | 2.010167 |
26 | 67.108.864 | 43.819.461 | 1.844.454 | 41.975.007 | 0.652961 | 0.027485 | 0.625476 | 2.005048 | 1.916296 | 2.009137 |
27 | 134.217.728 | 87.842.680 | 3.540.793 | 84.301.887 | 0.654479 | 0.026381 | 0.628098 | 2.004650 | 1.919697 | 2.008383 |
28 | 268.435.456 | 176.063.092 | 6.805.913 | 169.257.179 | 0.655886 | 0.025354 | 0.630532 | 2.004300 | 1.922144 | 2.007751 |
29 | 536.870.912 | 352.828.083 | 13.099.567 | 339.728.516 | 0.657194 | 0.024400 | 0.632794 | 2.003987 | 1.924733 | 2.007173 |
30 | 1.073.741.824 | 706.959.499 | 25.254.900 | 681.704.599 | 0.658407 | 0.023520 | 0.634887 | 2.003694 | 1.927919 | 2.006616 |
31 | 2.147.483.648 | 1.416.363.330 | 48.750.727 | 1.367.612.603 | 0.659546 | 0.022701 | 0.636844 | 2.003458 | 1.930347 | 2.006166 |
32 | 4.294.967.296 | 2.837.305.022 | 94.226.796 | 2.743.078.226 | 0.660612 | 0.021939 | 0.638673 | 2.003232 | 1.932829 | 2.005742 |
33 | 8.589.934.592 | 5.683.219.177 | 182.327.845 | 5.500.891.332 | 0.661614 | 0.021226 | 0.640388 | 2.003034 | 1.934989 | 2.005372 |
34 | 17.179.869.184 | 11.382.624.134 | 353.174.842 | 11.029.449.292 | 0.662556 | 0.020557 | 0.641998 | 2.002848 | 1.937032 | 2.005030 |
35 | 34.359.738.368 | 22.795.714.961 | 684.790.412 | 22.110.924.549 | 0.663443 | 0.019930 | 0.643513 | 2.002676 | 1.938956 | 2.004717 |
36 | 68.719.476.736 | 45.648.889.911 | 1.328.987.061 | 44.319.902.850 | 0.664279 | 0.019339 | 0.644939 | 2.002521 | 1.940721 | 2.004435 |
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 | 0 | 2 | 0 | 0 | 1 | 1 |
3 | 8 | 2 | 0 | 2 | 0 | 0 | 1 | 1 |
4 | 16 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
5 | 32 | 6 | 3 | 3 | 0 | 3 | 1 | 2 |
6 | 64 | 7 | 4 | 3 | 0 | 3 | 1 | 3 |
7 | 128 | 14 | 7 | 7 | 1 | 3 | 7 | 3 |
8 | 256 | 27 | 9 | 18 | 4 | 3 | 17 | 3 |
9 | 512 | 48 | 12 | 36 | 6 | 3 | 36 | 3 |
10 | 1.024 | 89 | 22 | 67 | 17 | 3 | 66 | 3 |
11 | 2.048 | 157 | 45 | 112 | 32 | 3 | 119 | 3 |
12 | 4.096 | 287 | 78 | 209 | 64 | 3 | 217 | 3 |
13 | 8.192 | 516 | 147 | 369 | 122 | 3 | 388 | 3 |
14 | 16.384 | 924 | 258 | 666 | 228 | 3 | 690 | 3 |
15 | 32.768 | 1.679 | 439 | 1.240 | 421 | 3 | 1.252 | 3 |
16 | 65.536 | 3.156 | 828 | 2.328 | 817 | 3 | 2.333 | 3 |
17 | 131.072 | 5.849 | 1.550 | 4.299 | 1.514 | 3 | 4.329 | 3 |
18 | 262.144 | 11.007 | 2.877 | 8.130 | 2.868 | 3 | 8.133 | 3 |
19 | 524.288 | 20.515 | 5.403 | 15.112 | 5.368 | 3 | 15.141 | 3 |
20 | 1.048.576 | 38.518 | 10.135 | 28.383 | 10.039 | 3 | 28.473 | 3 |
21 | 2.097.152 | 72.936 | 19.089 | 53.847 | 18.890 | 3 | 54.040 | 3 |
22 | 4.194.304 | 138.837 | 36.406 | 102.431 | 35.968 | 3 | 102.863 | 3 |
23 | 8.388.608 | 264.067 | 68.949 | 195.118 | 68.297 | 3 | 195.764 | 3 |
24 | 16.777.216 | 503.689 | 130.715 | 372.974 | 129.806 | 3 | 373.877 | 3 |
25 | 33.554.432 | 962.510 | 249.975 | 712.535 | 247.938 | 3 | 714.566 | 3 |
26 | 67.108.864 | 1.844.454 | 478.259 | 1.366.195 | 474.067 | 3 | 1.370.381 | 3 |
27 | 134.217.728 | 3.540.793 | 916.693 | 2.624.100 | 908.112 | 3 | 2.632.675 | 3 |
28 | 268.435.456 | 6.805.913 | 1.759.322 | 5.046.591 | 1.742.414 | 3 | 5.063.493 | 3 |
29 | 536.870.912 | 13.099.567 | 3.383.419 | 9.716.148 | 3.351.184 | 3 | 9.748.377 | 3 |
30 | 1.073.741.824 | 25.254.900 | 6.513.889 | 18.741.011 | 6.455.214 | 3 | 18.799.680 | 3 |
31 | 2.147.483.648 | 48.750.727 | 12.561.938 | 36.188.789 | 12.453.045 | 3 | 36.297.676 | 3 |
32 | 4.294.967.296 | 94.226.796 | 24.256.460 | 69.970.336 | 24.045.197 | 3 | 70.181.593 | 3 |
33 | 8.589.934.592 | 182.327.845 | 46.896.564 | 135.431.281 | 46.504.073 | 3 | 135.823.766 | 3 |
34 | 17.179.869.184 | 353.174.842 | 90.768.898 | 262.405.944 | 90.019.957 | 3 | 263.154.879 | 3 |
35 | 34.359.738.368 | 684.790.412 | 175.840.247 | 508.950.165 | 174.458.443 | 3 | 510.331.963 | 3 |
36 | 68.719.476.736 | 1.328.987.061 | 340.963.139 | 988.023.922 | 338.388.883 | 3 | 990.598.172 | 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 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 4 | 0 | 3 | 2 | 1 | 0 | 1 |
4 | 16 | 7 | 2 | 4 | 3 | 1 | 2 | 1 |
5 | 32 | 13 | 3 | 9 | 5 | 3 | 3 | 2 |
6 | 64 | 13 | 3 | 9 | 5 | 3 | 3 | 2 |
7 | 128 | 30 | 11 | 18 | 8 | 7 | 5 | 10 |
8 | 256 | 80 | 40 | 39 | 16 | 24 | 14 | 26 |
9 | 512 | 200 | 101 | 98 | 39 | 55 | 39 | 67 |
10 | 1.024 | 463 | 224 | 238 | 92 | 121 | 101 | 149 |
11 | 2.048 | 1.005 | 522 | 482 | 213 | 256 | 209 | 327 |
12 | 4.096 | 2.137 | 1.116 | 1.020 | 465 | 541 | 466 | 665 |
13 | 8.192 | 4.414 | 2.290 | 2.123 | 967 | 1.120 | 990 | 1.337 |
14 | 16.384 | 9.121 | 4.715 | 4.405 | 2.004 | 2.344 | 2.035 | 2.738 |
15 | 32.768 | 18.634 | 9.555 | 9.078 | 4.225 | 4.736 | 4.210 | 5.463 |
16 | 65.536 | 37.830 | 19.286 | 18.543 | 8.619 | 9.684 | 8.625 | 10.902 |
17 | 131.072 | 76.732 | 38.992 | 37.739 | 17.743 | 19.409 | 17.584 | 21.996 |
18 | 262.144 | 155.083 | 78.905 | 76.177 | 36.063 | 39.292 | 35.586 | 44.142 |
19 | 524.288 | 313.648 | 159.379 | 154.268 | 73.011 | 79.370 | 72.612 | 88.655 |
20 | 1.048.576 | 633.050 | 321.713 | 311.336 | 148.452 | 160.049 | 147.448 | 177.101 |
21 | 2.097.152 | 1.275.809 | 647.857 | 627.951 | 300.827 | 321.998 | 298.767 | 354.217 |
22 | 4.194.304 | 2.568.303 | 1.303.212 | 1.265.090 | 608.580 | 647.455 | 603.021 | 709.247 |
23 | 8.388.608 | 5.167.886 | 2.620.426 | 2.547.459 | 1.228.378 | 1.301.812 | 1.218.044 | 1.419.652 |
24 | 16.777.216 | 10.393.195 | 5.267.237 | 5.125.957 | 2.476.802 | 2.615.793 | 2.457.858 | 2.842.742 |
25 | 33.554.432 | 20.892.058 | 10.579.337 | 10.312.720 | 4.992.019 | 5.255.908 | 4.953.292 | 5.690.839 |
26 | 67.108.864 | 41.975.007 | 21.243.349 | 20.731.657 | 10.050.576 | 10.556.493 | 9.976.567 | 11.391.371 |
27 | 134.217.728 | 84.301.887 | 42.639.134 | 41.662.752 | 20.231.356 | 21.194.043 | 20.085.079 | 22.791.409 |
28 | 268.435.456 | 169.257.179 | 85.569.405 | 83.687.773 | 40.699.672 | 42.533.281 | 40.412.624 | 45.611.602 |
29 | 536.870.912 | 339.728.516 | 171.668.533 | 168.059.982 | 81.824.501 | 85.352.244 | 81.273.618 | 91.278.153 |
30 | 1.073.741.824 | 681.704.599 | 344.327.584 | 337.377.014 | 164.440.359 | 171.219.772 | 163.380.452 | 182.664.016 |
31 | 2.147.483.648 | 1.367.612.603 | 690.526.069 | 677.086.533 | 330.342.155 | 343.435.633 | 328.306.980 | 365.527.835 |
32 | 4.294.967.296 | 2.743.078.226 | 1.384.509.759 | 1.358.568.466 | 663.461.409 | 688.687.573 | 659.515.998 | 731.413.246 |
33 | 8.589.934.592 | 5.500.891.332 | 2.775.533.091 | 2.725.358.240 | 1.332.057.667 | 1.380.786.882 | 1.324.512.479 | 1.463.534.304 |
34 | 17.179.869.184 | 11.029.449.292 | 5.563.345.195 | 5.466.104.096 | 2.673.839.038 | 2.767.983.074 | 2.659.262.347 | 2.928.364.833 |
35 | 34.359.738.368 | 22.110.924.549 | 11.149.788.649 | 10.961.135.899 | 5.365.994.894 | 5.548.139.270 | 5.337.703.013 | 5.859.087.372 |
36 | 68.719.476.736 | 44.319.902.850 | 22.343.012.865 | 21.976.889.984 | 10.766.418.597 | 11.119.108.729 | 10.711.506.856 | 11.722.868.668 |