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-114x+107
f(0)=107
f(1)=3
f(2)=13
f(3)=113
f(4)=37
f(5)=73
f(6)=541
f(7)=1
f(8)=19
f(9)=419
f(10)=311
f(11)=1
f(12)=1117
f(13)=67
f(14)=431
f(15)=53
f(16)=487
f(17)=257
f(18)=1621
f(19)=283
f(20)=197
f(21)=71
f(22)=1
f(23)=331
f(24)=2053
f(25)=353
f(26)=727
f(27)=59
f(28)=1
f(29)=131
f(30)=127
f(31)=137
f(32)=839
f(33)=1283
f(34)=1
f(35)=443
f(36)=1
f(37)=457
f(38)=103
f(39)=1409
f(40)=317
f(41)=1
f(42)=2917
f(43)=491
f(44)=991
f(45)=1499
f(46)=1
f(47)=1
f(48)=3061
f(49)=1
f(50)=1031
f(51)=1553
f(52)=1039
f(53)=521
f(54)=241
f(55)=523
f(56)=349
f(57)=1571
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)=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-114x+107 could be written as f(y)= y^2-3142 with x=y+57
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-57
f'(x)>2x-115 with x > 56
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 | 48 | 15 | 33 | 0.480000 | 0.150000 | 0.480000 | 4.800000 | 3.000000 | 6.600000 |
3 | 1.000 | 646 | 139 | 507 | 0.646000 | 0.139000 | 0.646000 | 13.458333 | 9.266666 | 15.363636 |
4 | 10.000 | 6.891 | 1.026 | 5.865 | 0.689100 | 0.102600 | 0.689100 | 10.667183 | 7.381295 | 11.568048 |
5 | 100.000 | 69.410 | 7.905 | 61.505 | 0.694100 | 0.079050 | 0.694100 | 10.072558 | 7.704679 | 10.486786 |
6 | 1.000.000 | 694.949 | 64.450 | 630.499 | 0.694949 | 0.064450 | 0.694949 | 10.012232 | 8.153068 | 10.251183 |
7 | 10.000.000 | 6.946.167 | 544.014 | 6.402.153 | 0.694617 | 0.054401 | 0.694617 | 9.995218 | 8.440869 | 10.154105 |
8 | 100.000.000 | 69.425.291 | 4.711.664 | 64.713.627 | 0.694253 | 0.047117 | 0.694253 | 9.994762 | 8.660924 | 10.108104 |
9 | 1.000.000.000 | 694.013.316 | 41.534.522 | 652.478.794 | 0.694013 | 0.041535 | 0.694013 | 9.996550 | 8.815255 | 10.082556 |
10 | 10.000.000.000 | 6.938.275.928 | 371.333.794 | 6.566.942.134 | 0.693828 | 0.037133 | 0.693828 | 9.997324 | 8.940366 | 10.064607 |
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 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 1.875000 | 1.500000 | 2.250000 |
5 | 32 | 29 | 8 | 21 | 0.906250 | 0.250000 | 0.656250 | 1.933333 | 1.333333 | 2.333333 |
6 | 64 | 48 | 15 | 33 | 0.750000 | 0.234375 | 0.515625 | 1.655172 | 1.875000 | 1.571429 |
7 | 128 | 53 | 18 | 35 | 0.414062 | 0.140625 | 0.273438 | 1.104167 | 1.200000 | 1.060606 |
8 | 256 | 135 | 43 | 92 | 0.527344 | 0.167969 | 0.359375 | 2.547170 | 2.388889 | 2.628572 |
9 | 512 | 314 | 82 | 232 | 0.613281 | 0.160156 | 0.453125 | 2.325926 | 1.906977 | 2.521739 |
10 | 1.024 | 660 | 141 | 519 | 0.644531 | 0.137695 | 0.506836 | 2.101911 | 1.719512 | 2.237069 |
11 | 2.048 | 1.361 | 260 | 1.101 | 0.664551 | 0.126953 | 0.537598 | 2.062121 | 1.843972 | 2.121387 |
12 | 4.096 | 2.783 | 472 | 2.311 | 0.679443 | 0.115234 | 0.564209 | 2.044820 | 1.815385 | 2.099001 |
13 | 8.192 | 5.622 | 871 | 4.751 | 0.686279 | 0.106323 | 0.579956 | 2.020122 | 1.845339 | 2.055820 |
14 | 16.384 | 11.309 | 1.597 | 9.712 | 0.690247 | 0.097473 | 0.592773 | 2.011562 | 1.833525 | 2.044201 |
15 | 32.768 | 22.697 | 2.945 | 19.752 | 0.692657 | 0.089874 | 0.602783 | 2.006986 | 1.844083 | 2.033773 |
16 | 65.536 | 45.477 | 5.424 | 40.053 | 0.693924 | 0.082764 | 0.611160 | 2.003657 | 1.841766 | 2.027795 |
17 | 131.072 | 91.003 | 10.069 | 80.934 | 0.694298 | 0.076820 | 0.617477 | 2.001077 | 1.856379 | 2.020673 |
18 | 262.144 | 182.108 | 18.844 | 163.264 | 0.694687 | 0.071884 | 0.622803 | 2.001121 | 1.871487 | 2.017249 |
19 | 524.288 | 364.448 | 35.520 | 328.928 | 0.695129 | 0.067749 | 0.627380 | 2.001274 | 1.884950 | 2.014700 |
20 | 1.048.576 | 728.717 | 67.293 | 661.424 | 0.694959 | 0.064176 | 0.630783 | 1.999509 | 1.894510 | 2.010847 |
21 | 2.097.152 | 1.457.310 | 127.659 | 1.329.651 | 0.694900 | 0.060873 | 0.634027 | 1.999830 | 1.897062 | 2.010285 |
22 | 4.194.304 | 2.913.753 | 242.440 | 2.671.313 | 0.694693 | 0.057802 | 0.636891 | 1.999405 | 1.899122 | 2.009033 |
23 | 8.388.608 | 5.826.479 | 461.667 | 5.364.812 | 0.694570 | 0.055035 | 0.639535 | 1.999647 | 1.904253 | 2.008305 |
24 | 16.777.216 | 11.652.340 | 882.239 | 10.770.101 | 0.694534 | 0.052586 | 0.641948 | 1.999894 | 1.910986 | 2.007545 |
25 | 33.554.432 | 23.300.067 | 1.688.704 | 21.611.363 | 0.694396 | 0.050327 | 0.644069 | 1.999604 | 1.914112 | 2.006607 |
26 | 67.108.864 | 46.593.827 | 3.236.948 | 43.356.879 | 0.694302 | 0.048234 | 0.646068 | 1.999729 | 1.916824 | 2.006207 |
27 | 134.217.728 | 93.175.765 | 6.217.396 | 86.958.369 | 0.694214 | 0.046323 | 0.647890 | 1.999745 | 1.920759 | 2.005642 |
28 | 268.435.456 | 186.331.795 | 11.962.415 | 174.369.380 | 0.694140 | 0.044563 | 0.649577 | 1.999788 | 1.924023 | 2.005205 |
29 | 536.870.912 | 372.627.145 | 23.038.379 | 349.588.766 | 0.694072 | 0.042912 | 0.651160 | 1.999804 | 1.925897 | 2.004875 |
30 | 1.073.741.824 | 745.181.000 | 44.432.479 | 700.748.521 | 0.694004 | 0.041381 | 0.652623 | 1.999803 | 1.928629 | 2.004494 |
31 | 2.147.483.648 | 1.490.236.311 | 85.810.004 | 1.404.426.307 | 0.693945 | 0.039958 | 0.653987 | 1.999831 | 1.931245 | 2.004180 |
32 | 4.294.967.296 | 2.980.232.696 | 165.938.137 | 2.814.294.559 | 0.693889 | 0.038635 | 0.655254 | 1.999839 | 1.933786 | 2.003875 |
33 | 8.589.934.592 | 5.960.014.616 | 321.213.112 | 5.638.801.504 | 0.693837 | 0.037394 | 0.656443 | 1.999849 | 1.935740 | 2.003629 |
34 | 17.179.869.184 | 11.919.247.354 | 622.458.623 | 11.296.788.731 | 0.693792 | 0.036232 | 0.657560 | 1.999869 | 1.937837 | 2.003402 |
35 | 34.359.738.368 | 23.837.115.199 | 1.207.386.769 | 22.629.728.430 | 0.693751 | 0.035140 | 0.658612 | 1.999884 | 1.939706 | 2.003200 |
36 | 68.719.476.736 | 47.671.757.546 | 2.344.132.760 | 45.327.624.786 | 0.693715 | 0.034112 | 0.659604 | 1.999896 | 1.941493 | 2.003012 |
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 | 2 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 2 | 0 | 0 |
3 | 8 | 4 | 1 | 2 | 1 | 2 | 1 | 0 |
4 | 16 | 6 | 2 | 3 | 1 | 3 | 2 | 0 |
5 | 32 | 8 | 4 | 3 | 1 | 3 | 4 | 0 |
6 | 64 | 15 | 6 | 8 | 3 | 6 | 6 | 0 |
7 | 128 | 18 | 7 | 10 | 3 | 8 | 6 | 1 |
8 | 256 | 43 | 21 | 21 | 3 | 19 | 12 | 9 |
9 | 512 | 82 | 43 | 38 | 3 | 36 | 21 | 22 |
10 | 1.024 | 141 | 72 | 68 | 3 | 66 | 32 | 40 |
11 | 2.048 | 260 | 133 | 126 | 3 | 124 | 62 | 71 |
12 | 4.096 | 472 | 242 | 229 | 3 | 227 | 122 | 120 |
13 | 8.192 | 871 | 443 | 427 | 3 | 425 | 213 | 230 |
14 | 16.384 | 1.597 | 808 | 788 | 3 | 786 | 399 | 409 |
15 | 32.768 | 2.945 | 1.498 | 1.446 | 3 | 1.444 | 748 | 750 |
16 | 65.536 | 5.424 | 2.750 | 2.673 | 3 | 2.671 | 1.369 | 1.381 |
17 | 131.072 | 10.069 | 5.101 | 4.967 | 3 | 4.965 | 2.550 | 2.551 |
18 | 262.144 | 18.844 | 9.506 | 9.337 | 3 | 9.335 | 4.766 | 4.740 |
19 | 524.288 | 35.520 | 17.964 | 17.555 | 3 | 17.553 | 9.025 | 8.939 |
20 | 1.048.576 | 67.293 | 34.057 | 33.235 | 3 | 33.233 | 17.081 | 16.976 |
21 | 2.097.152 | 127.659 | 64.582 | 63.076 | 3 | 63.074 | 32.370 | 32.212 |
22 | 4.194.304 | 242.440 | 122.440 | 119.999 | 3 | 119.997 | 61.453 | 60.987 |
23 | 8.388.608 | 461.667 | 233.673 | 227.993 | 3 | 227.991 | 117.072 | 116.601 |
24 | 16.777.216 | 882.239 | 446.164 | 436.074 | 3 | 436.072 | 223.189 | 222.975 |
25 | 33.554.432 | 1.688.704 | 853.620 | 835.083 | 3 | 835.081 | 426.645 | 426.975 |
26 | 67.108.864 | 3.236.948 | 1.635.550 | 1.601.397 | 3 | 1.601.395 | 817.337 | 818.213 |
27 | 134.217.728 | 6.217.396 | 3.139.507 | 3.077.888 | 3 | 3.077.886 | 1.569.370 | 1.570.137 |
28 | 268.435.456 | 11.962.415 | 6.037.369 | 5.925.045 | 3 | 5.925.043 | 3.018.446 | 3.018.923 |
29 | 536.870.912 | 23.038.379 | 11.627.245 | 11.411.133 | 3 | 11.411.131 | 5.811.913 | 5.815.332 |
30 | 1.073.741.824 | 44.432.479 | 22.416.170 | 22.016.308 | 3 | 22.016.306 | 11.207.374 | 11.208.796 |
31 | 2.147.483.648 | 85.810.004 | 43.275.086 | 42.534.917 | 3 | 42.534.915 | 21.636.091 | 21.638.995 |
32 | 4.294.967.296 | 165.938.137 | 83.653.674 | 82.284.462 | 3 | 82.284.460 | 41.827.839 | 41.825.835 |
33 | 8.589.934.592 | 321.213.112 | 161.897.067 | 159.316.044 | 3 | 159.316.042 | 80.947.349 | 80.949.718 |
34 | 17.179.869.184 | 622.458.623 | 313.642.828 | 308.815.794 | 3 | 308.815.792 | 156.818.598 | 156.824.230 |
35 | 34.359.738.368 | 1.207.386.769 | 608.238.707 | 599.148.061 | 3 | 599.148.059 | 304.122.221 | 304.116.486 |
36 | 68.719.476.736 | 2.344.132.760 | 1.180.643.639 | 1.163.489.120 | 3 | 1.163.489.118 | 590.328.413 | 590.315.226 |
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 | 2 | 0 | 0 | 0 | 2 | 0 |
3 | 8 | 4 | 4 | 0 | 1 | 1 | 2 | 0 |
4 | 16 | 9 | 6 | 3 | 1 | 2 | 3 | 3 |
5 | 32 | 21 | 10 | 11 | 4 | 6 | 4 | 7 |
6 | 64 | 33 | 17 | 16 | 7 | 9 | 6 | 11 |
7 | 128 | 35 | 17 | 18 | 8 | 9 | 7 | 11 |
8 | 256 | 92 | 48 | 44 | 33 | 15 | 18 | 26 |
9 | 512 | 232 | 111 | 121 | 71 | 43 | 53 | 65 |
10 | 1.024 | 519 | 254 | 265 | 163 | 93 | 126 | 137 |
11 | 2.048 | 1.101 | 547 | 554 | 331 | 206 | 284 | 280 |
12 | 4.096 | 2.311 | 1.161 | 1.150 | 681 | 462 | 595 | 573 |
13 | 8.192 | 4.751 | 2.367 | 2.384 | 1.398 | 993 | 1.189 | 1.171 |
14 | 16.384 | 9.712 | 4.866 | 4.846 | 2.785 | 2.047 | 2.453 | 2.427 |
15 | 32.768 | 19.752 | 9.880 | 9.872 | 5.609 | 4.207 | 5.003 | 4.933 |
16 | 65.536 | 40.053 | 20.084 | 19.969 | 11.156 | 8.700 | 10.075 | 10.122 |
17 | 131.072 | 80.934 | 40.521 | 40.413 | 22.629 | 17.567 | 20.367 | 20.371 |
18 | 262.144 | 163.264 | 81.806 | 81.458 | 45.258 | 36.012 | 40.979 | 41.015 |
19 | 524.288 | 328.928 | 164.644 | 164.284 | 90.734 | 72.978 | 82.679 | 82.537 |
20 | 1.048.576 | 661.424 | 331.086 | 330.338 | 181.446 | 147.974 | 166.201 | 165.803 |
21 | 2.097.152 | 1.329.651 | 665.190 | 664.461 | 363.465 | 299.463 | 333.664 | 333.059 |
22 | 4.194.304 | 2.671.313 | 1.336.728 | 1.334.585 | 727.438 | 605.309 | 669.516 | 669.050 |
23 | 8.388.608 | 5.364.812 | 2.684.638 | 2.680.174 | 1.455.084 | 1.221.516 | 1.344.778 | 1.343.434 |
24 | 16.777.216 | 10.770.101 | 5.387.467 | 5.382.634 | 2.910.790 | 2.463.628 | 2.699.049 | 2.696.634 |
25 | 33.554.432 | 21.611.363 | 10.807.603 | 10.803.760 | 5.822.466 | 4.967.537 | 5.413.919 | 5.407.441 |
26 | 67.108.864 | 43.356.879 | 21.684.407 | 21.672.472 | 11.643.118 | 10.003.937 | 10.859.267 | 10.850.557 |
27 | 134.217.728 | 86.958.369 | 43.493.879 | 43.464.490 | 23.283.257 | 20.139.900 | 21.775.545 | 21.759.667 |
28 | 268.435.456 | 174.369.380 | 87.207.978 | 87.161.402 | 46.563.223 | 40.517.585 | 43.660.085 | 43.628.487 |
29 | 536.870.912 | 349.588.766 | 174.832.015 | 174.756.751 | 93.115.019 | 81.486.397 | 87.519.375 | 87.467.975 |
30 | 1.073.741.824 | 700.748.521 | 350.448.507 | 350.300.014 | 186.215.947 | 163.796.845 | 175.418.567 | 175.317.162 |
31 | 2.147.483.648 | 1.404.426.307 | 702.330.528 | 702.095.779 | 372.408.114 | 329.128.727 | 351.523.411 | 351.366.055 |
32 | 4.294.967.296 | 2.814.294.559 | 1.407.394.382 | 1.406.900.177 | 744.802.898 | 661.098.368 | 704.361.660 | 704.031.633 |
33 | 8.589.934.592 | 5.638.801.504 | 2.819.833.230 | 2.818.968.274 | 1.489.547.357 | 1.327.544.650 | 1.411.178.472 | 1.410.531.025 |
34 | 17.179.869.184 | 11.296.788.731 | 5.649.229.188 | 5.647.559.543 | 2.978.931.074 | 2.665.136.987 | 2.826.985.307 | 2.825.735.363 |
35 | 34.359.738.368 | 22.629.728.430 | 11.316.386.686 | 11.313.341.744 | 5.957.680.698 | 5.349.076.444 | 5.662.592.490 | 5.660.378.798 |
36 | 68.719.476.736 | 45.327.624.786 | 22.666.730.120 | 22.660.894.666 | 11.915.051.682 | 10.733.602.719 | 11.341.534.343 | 11.337.436.042 |