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-136x+5
f(0)=5
f(1)=13
f(2)=263
f(3)=197
f(4)=523
f(5)=1
f(6)=31
f(7)=449
f(8)=1019
f(9)=569
f(10)=251
f(11)=137
f(12)=1483
f(13)=797
f(14)=131
f(15)=181
f(16)=383
f(17)=1009
f(18)=163
f(19)=1109
f(20)=463
f(21)=241
f(22)=2503
f(23)=1297
f(24)=2683
f(25)=277
f(26)=571
f(27)=113
f(28)=3019
f(29)=1549
f(30)=127
f(31)=1
f(32)=3323
f(33)=1697
f(34)=3463
f(35)=353
f(36)=719
f(37)=59
f(38)=3719
f(39)=1889
f(40)=1
f(41)=389
f(42)=3943
f(43)=1997
f(44)=311
f(45)=409
f(46)=827
f(47)=2089
f(48)=4219
f(49)=2129
f(50)=859
f(51)=433
f(52)=4363
f(53)=1
f(54)=4423
f(55)=89
f(56)=179
f(57)=173
f(58)=4519
f(59)=2269
f(60)=911
f(61)=457
f(62)=4583
f(63)=2297
f(64)=4603
f(65)=461
f(66)=71
f(67)=2309
f(68)=149
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)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-136x+5 could be written as f(y)= y^2-4619 with x=y+68
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-68
f'(x)>2x-137 with x > 68
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 | 5 | 5 | 1.000000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 62 | 19 | 43 | 0.620000 | 0.190000 | 0.620000 | 6.200000 | 3.800000 | 8.600000 |
3 | 1.000 | 717 | 161 | 556 | 0.717000 | 0.161000 | 0.717000 | 11.564516 | 8.473684 | 12.930233 |
4 | 10.000 | 7.640 | 1.177 | 6.463 | 0.764000 | 0.117700 | 0.764000 | 10.655509 | 7.310559 | 11.624101 |
5 | 100.000 | 75.749 | 9.036 | 66.713 | 0.757490 | 0.090360 | 0.757490 | 9.914790 | 7.677145 | 10.322296 |
6 | 1.000.000 | 746.214 | 74.857 | 671.357 | 0.746214 | 0.074857 | 0.746214 | 9.851140 | 8.284307 | 10.063361 |
7 | 10.000.000 | 7.378.075 | 632.405 | 6.745.670 | 0.737808 | 0.063240 | 0.737808 | 9.887344 | 8.448174 | 10.047813 |
8 | 100.000.000 | 73.178.377 | 5.479.061 | 67.699.316 | 0.731784 | 0.054791 | 0.731784 | 9.918356 | 8.663848 | 10.035966 |
9 | 1.000.000.000 | 727.197.285 | 48.346.074 | 678.851.211 | 0.727197 | 0.048346 | 0.727197 | 9.937325 | 8.823788 | 10.027446 |
10 | 10.000.000.000 | 7.235.816.951 | 432.621.532 | 6.803.195.419 | 0.723582 | 0.043262 | 0.723582 | 9.950280 | 8.948432 | 10.021629 |
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 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 1.600000 | 1.666667 | 1.500000 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.200000 | 3.333333 |
5 | 32 | 31 | 10 | 21 | 0.968750 | 0.312500 | 0.656250 | 1.937500 | 1.666667 | 2.100000 |
6 | 64 | 59 | 19 | 40 | 0.921875 | 0.296875 | 0.625000 | 1.903226 | 1.900000 | 1.904762 |
7 | 128 | 62 | 19 | 43 | 0.484375 | 0.148438 | 0.335938 | 1.050847 | 1.000000 | 1.075000 |
8 | 256 | 147 | 43 | 104 | 0.574219 | 0.167969 | 0.406250 | 2.370968 | 2.263158 | 2.418605 |
9 | 512 | 344 | 87 | 257 | 0.671875 | 0.169922 | 0.501953 | 2.340136 | 2.023256 | 2.471154 |
10 | 1.024 | 740 | 166 | 574 | 0.722656 | 0.162109 | 0.560547 | 2.151163 | 1.908046 | 2.233463 |
11 | 2.048 | 1.525 | 307 | 1.218 | 0.744629 | 0.149902 | 0.594727 | 2.060811 | 1.849398 | 2.121951 |
12 | 4.096 | 3.121 | 556 | 2.565 | 0.761963 | 0.135742 | 0.626221 | 2.046557 | 1.811075 | 2.105911 |
13 | 8.192 | 6.271 | 991 | 5.280 | 0.765503 | 0.120972 | 0.644531 | 2.009292 | 1.782374 | 2.058480 |
14 | 16.384 | 12.539 | 1.815 | 10.724 | 0.765320 | 0.110779 | 0.654541 | 1.999522 | 1.831483 | 2.031061 |
15 | 32.768 | 24.976 | 3.356 | 21.620 | 0.762207 | 0.102417 | 0.659790 | 1.991865 | 1.849036 | 2.016039 |
16 | 65.536 | 49.782 | 6.236 | 43.546 | 0.759613 | 0.095154 | 0.664459 | 1.993194 | 1.858164 | 2.014153 |
17 | 131.072 | 99.146 | 11.520 | 87.626 | 0.756424 | 0.087891 | 0.668533 | 1.991603 | 1.847338 | 2.012263 |
18 | 262.144 | 197.206 | 21.784 | 175.422 | 0.752281 | 0.083099 | 0.669182 | 1.989046 | 1.890972 | 2.001940 |
19 | 524.288 | 392.711 | 41.254 | 351.457 | 0.749037 | 0.078686 | 0.670351 | 1.991374 | 1.893775 | 2.003495 |
20 | 1.048.576 | 782.264 | 78.142 | 704.122 | 0.746025 | 0.074522 | 0.671503 | 1.991958 | 1.894168 | 2.003437 |
21 | 2.097.152 | 1.558.700 | 147.814 | 1.410.886 | 0.743246 | 0.070483 | 0.672763 | 1.992550 | 1.891608 | 2.003752 |
22 | 4.194.304 | 3.106.608 | 281.566 | 2.825.042 | 0.740673 | 0.067131 | 0.673542 | 1.993076 | 1.904867 | 2.002318 |
23 | 8.388.608 | 6.193.392 | 536.657 | 5.656.735 | 0.738310 | 0.063974 | 0.674335 | 1.993619 | 1.905972 | 2.002354 |
24 | 16.777.216 | 12.353.104 | 1.025.577 | 11.327.527 | 0.736302 | 0.061129 | 0.675173 | 1.994562 | 1.911047 | 2.002485 |
25 | 33.554.432 | 24.643.395 | 1.963.123 | 22.680.272 | 0.734430 | 0.058506 | 0.675925 | 1.994915 | 1.914164 | 2.002226 |
26 | 67.108.864 | 49.171.334 | 3.764.455 | 45.406.879 | 0.732710 | 0.056095 | 0.676615 | 1.995315 | 1.917585 | 2.002043 |
27 | 134.217.728 | 98.132.616 | 7.230.040 | 90.902.576 | 0.731145 | 0.053868 | 0.677277 | 1.995728 | 1.920607 | 2.001956 |
28 | 268.435.456 | 195.867.390 | 13.912.441 | 181.954.949 | 0.729663 | 0.051828 | 0.677835 | 1.995946 | 1.924255 | 2.001648 |
29 | 536.870.912 | 391.014.635 | 26.806.265 | 364.208.370 | 0.728321 | 0.049931 | 0.678391 | 1.996323 | 1.926784 | 2.001641 |
30 | 1.073.741.824 | 780.686.590 | 51.724.174 | 728.962.416 | 0.727071 | 0.048172 | 0.678899 | 1.996566 | 1.929556 | 2.001498 |
31 | 2.147.483.648 | 1.558.873.722 | 99.927.001 | 1.458.946.721 | 0.725907 | 0.046532 | 0.679375 | 1.996798 | 1.931921 | 2.001402 |
32 | 4.294.967.296 | 3.113.057.781 | 193.260.052 | 2.919.797.729 | 0.724815 | 0.044997 | 0.679818 | 1.996992 | 1.934012 | 2.001305 |
33 | 8.589.934.592 | 6.217.365.343 | 374.218.695 | 5.843.146.648 | 0.723797 | 0.043565 | 0.680232 | 1.997189 | 1.936348 | 2.001216 |
34 | 17.179.869.184 | 12.418.319.961 | 725.337.842 | 11.692.982.119 | 0.722841 | 0.042220 | 0.680621 | 1.997360 | 1.938273 | 2.001145 |
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 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 1 | 2 |
4 | 16 | 6 | 3 | 3 | 0 | 3 | 1 | 2 |
5 | 32 | 10 | 6 | 4 | 0 | 6 | 1 | 3 |
6 | 64 | 19 | 13 | 6 | 0 | 9 | 1 | 9 |
7 | 128 | 19 | 13 | 6 | 0 | 9 | 1 | 9 |
8 | 256 | 43 | 21 | 22 | 13 | 9 | 12 | 9 |
9 | 512 | 87 | 35 | 52 | 35 | 9 | 34 | 9 |
10 | 1.024 | 166 | 65 | 101 | 74 | 9 | 74 | 9 |
11 | 2.048 | 307 | 107 | 200 | 144 | 9 | 145 | 9 |
12 | 4.096 | 556 | 191 | 365 | 261 | 9 | 277 | 9 |
13 | 8.192 | 991 | 347 | 644 | 475 | 9 | 498 | 9 |
14 | 16.384 | 1.815 | 617 | 1.198 | 881 | 9 | 916 | 9 |
15 | 32.768 | 3.356 | 1.121 | 2.235 | 1.633 | 9 | 1.705 | 9 |
16 | 65.536 | 6.236 | 2.091 | 4.145 | 3.092 | 9 | 3.126 | 9 |
17 | 131.072 | 11.520 | 3.850 | 7.670 | 5.738 | 9 | 5.764 | 9 |
18 | 262.144 | 21.784 | 7.308 | 14.476 | 10.885 | 9 | 10.881 | 9 |
19 | 524.288 | 41.254 | 13.743 | 27.511 | 20.638 | 9 | 20.598 | 9 |
20 | 1.048.576 | 78.142 | 26.078 | 52.064 | 39.074 | 9 | 39.050 | 9 |
21 | 2.097.152 | 147.814 | 49.338 | 98.476 | 73.833 | 9 | 73.963 | 9 |
22 | 4.194.304 | 281.566 | 94.030 | 187.536 | 140.801 | 9 | 140.747 | 9 |
23 | 8.388.608 | 536.657 | 178.827 | 357.830 | 268.147 | 9 | 268.492 | 9 |
24 | 16.777.216 | 1.025.577 | 341.521 | 684.056 | 512.823 | 9 | 512.736 | 9 |
25 | 33.554.432 | 1.963.123 | 654.022 | 1.309.101 | 981.817 | 9 | 981.288 | 9 |
26 | 67.108.864 | 3.764.455 | 1.254.206 | 2.510.249 | 1.882.524 | 9 | 1.881.913 | 9 |
27 | 134.217.728 | 7.230.040 | 2.408.819 | 4.821.221 | 3.616.188 | 9 | 3.613.834 | 9 |
28 | 268.435.456 | 13.912.441 | 4.636.120 | 9.276.321 | 6.958.586 | 9 | 6.953.837 | 9 |
29 | 536.870.912 | 26.806.265 | 8.934.725 | 17.871.540 | 13.405.488 | 9 | 13.400.759 | 9 |
30 | 1.073.741.824 | 51.724.174 | 17.238.315 | 34.485.859 | 25.865.460 | 9 | 25.858.696 | 9 |
31 | 2.147.483.648 | 99.927.001 | 33.304.519 | 66.622.482 | 49.970.326 | 9 | 49.956.657 | 9 |
32 | 4.294.967.296 | 193.260.052 | 64.415.320 | 128.844.732 | 96.642.704 | 9 | 96.617.330 | 9 |
33 | 8.589.934.592 | 374.218.695 | 124.732.861 | 249.485.834 | 187.125.172 | 9 | 187.093.505 | 9 |
34 | 17.179.869.184 | 725.337.842 | 241.777.933 | 483.559.909 | 362.690.962 | 9 | 362.646.862 | 9 |
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 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 3 | 1 | 2 | 1 | 0 | 2 | 0 |
4 | 16 | 10 | 2 | 8 | 3 | 2 | 4 | 1 |
5 | 32 | 21 | 11 | 10 | 7 | 4 | 7 | 3 |
6 | 64 | 40 | 17 | 23 | 16 | 7 | 11 | 6 |
7 | 128 | 43 | 17 | 26 | 16 | 7 | 14 | 6 |
8 | 256 | 104 | 55 | 49 | 24 | 29 | 24 | 27 |
9 | 512 | 257 | 141 | 116 | 51 | 78 | 53 | 75 |
10 | 1.024 | 574 | 319 | 255 | 112 | 169 | 115 | 178 |
11 | 2.048 | 1.218 | 646 | 572 | 244 | 353 | 242 | 379 |
12 | 4.096 | 2.565 | 1.372 | 1.193 | 508 | 778 | 524 | 755 |
13 | 8.192 | 5.280 | 2.826 | 2.454 | 1.064 | 1.568 | 1.081 | 1.567 |
14 | 16.384 | 10.724 | 5.681 | 5.043 | 2.204 | 3.149 | 2.212 | 3.159 |
15 | 32.768 | 21.620 | 11.311 | 10.309 | 4.502 | 6.364 | 4.536 | 6.218 |
16 | 65.536 | 43.546 | 22.814 | 20.732 | 9.217 | 12.585 | 9.237 | 12.507 |
17 | 131.072 | 87.626 | 45.812 | 41.814 | 18.805 | 25.033 | 18.823 | 24.965 |
18 | 262.144 | 175.422 | 91.566 | 83.856 | 38.019 | 49.651 | 38.118 | 49.634 |
19 | 524.288 | 351.457 | 182.914 | 168.543 | 76.804 | 98.890 | 77.137 | 98.626 |
20 | 1.048.576 | 704.122 | 365.215 | 338.907 | 155.191 | 196.878 | 155.565 | 196.488 |
21 | 2.097.152 | 1.410.886 | 730.541 | 680.345 | 313.468 | 392.141 | 314.126 | 391.151 |
22 | 4.194.304 | 2.825.042 | 1.460.161 | 1.364.881 | 631.824 | 781.099 | 632.816 | 779.303 |
23 | 8.388.608 | 5.656.735 | 2.919.123 | 2.737.612 | 1.273.441 | 1.555.460 | 1.274.428 | 1.553.406 |
24 | 16.777.216 | 11.327.527 | 5.836.786 | 5.490.741 | 2.564.048 | 3.100.375 | 2.564.184 | 3.098.920 |
25 | 33.554.432 | 22.680.272 | 11.670.223 | 11.010.049 | 5.158.159 | 6.180.232 | 5.159.768 | 6.182.113 |
26 | 67.108.864 | 45.406.879 | 23.338.141 | 22.068.738 | 10.374.653 | 12.328.547 | 10.372.825 | 12.330.854 |
27 | 134.217.728 | 90.902.576 | 46.666.902 | 44.235.674 | 20.847.074 | 24.601.705 | 20.851.653 | 24.602.144 |
28 | 268.435.456 | 181.954.949 | 93.318.435 | 88.636.514 | 41.882.878 | 49.088.472 | 41.892.812 | 49.090.787 |
29 | 536.870.912 | 364.208.370 | 186.618.510 | 177.589.860 | 84.114.027 | 97.981.494 | 84.127.389 | 97.985.460 |
30 | 1.073.741.824 | 728.962.416 | 373.193.448 | 355.768.968 | 168.880.294 | 195.600.247 | 168.880.324 | 195.601.551 |
31 | 2.147.483.648 | 1.458.946.721 | 746.280.984 | 712.665.737 | 338.964.338 | 390.516.403 | 338.966.135 | 390.499.845 |
32 | 4.294.967.296 | 2.919.797.729 | 1.492.397.068 | 1.427.400.661 | 680.145.304 | 779.766.192 | 680.146.223 | 779.740.010 |
33 | 8.589.934.592 | 5.843.146.648 | 2.984.471.500 | 2.858.675.148 | 1.364.423.518 | 1.557.167.631 | 1.364.433.768 | 1.557.121.731 |
34 | 17.179.869.184 | 11.692.982.119 | 5.968.372.671 | 5.724.609.448 | 2.736.684.781 | 3.109.843.349 | 2.736.617.522 | 3.109.836.467 |