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-128x-7
f(0)=7
f(1)=67
f(2)=37
f(3)=191
f(4)=503
f(5)=311
f(6)=739
f(7)=61
f(8)=967
f(9)=11
f(10)=1187
f(11)=647
f(12)=1399
f(13)=751
f(14)=229
f(15)=23
f(16)=257
f(17)=947
f(18)=1987
f(19)=1039
f(20)=197
f(21)=1
f(22)=2339
f(23)=173
f(24)=2503
f(25)=1291
f(26)=2659
f(27)=1367
f(28)=401
f(29)=1439
f(30)=421
f(31)=137
f(32)=3079
f(33)=1571
f(34)=3203
f(35)=233
f(36)=3319
f(37)=241
f(38)=149
f(39)=47
f(40)=3527
f(41)=1787
f(42)=1
f(43)=1831
f(44)=1
f(45)=1871
f(46)=3779
f(47)=1907
f(48)=3847
f(49)=277
f(50)=3907
f(51)=281
f(52)=107
f(53)=181
f(54)=4003
f(55)=2011
f(56)=577
f(57)=2027
f(58)=83
f(59)=2039
f(60)=1
f(61)=89
f(62)=4099
f(63)=293
f(64)=373
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-128x-7 could be written as f(y)= y^2-4103 with x=y+64
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-64
f'(x)>2x-129 with x > 64
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 | 11 | 5 | 6 | 1.100000 | 0.500000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 19 | 38 | 0.570000 | 0.190000 | 0.570000 | 5.181818 | 3.800000 | 6.333333 |
3 | 1.000 | 709 | 167 | 542 | 0.709000 | 0.167000 | 0.709000 | 12.438597 | 8.789474 | 14.263158 |
4 | 10.000 | 7.480 | 1.254 | 6.226 | 0.748000 | 0.125400 | 0.748000 | 10.550071 | 7.508982 | 11.487085 |
5 | 100.000 | 74.352 | 9.815 | 64.537 | 0.743520 | 0.098150 | 0.743520 | 9.940107 | 7.826954 | 10.365725 |
6 | 1.000.000 | 734.157 | 80.374 | 653.783 | 0.734157 | 0.080374 | 0.734157 | 9.874072 | 8.188894 | 10.130360 |
7 | 10.000.000 | 7.278.866 | 679.440 | 6.599.426 | 0.727887 | 0.067944 | 0.727887 | 9.914591 | 8.453480 | 10.094214 |
8 | 100.000.000 | 72.325.571 | 5.887.313 | 66.438.258 | 0.723256 | 0.058873 | 0.723256 | 9.936378 | 8.664949 | 10.067278 |
9 | 1.000.000.000 | 719.711.516 | 51.945.418 | 667.766.098 | 0.719711 | 0.051945 | 0.719711 | 9.950996 | 8.823281 | 10.050927 |
10 | 10.000.000.000 | 7.169.012.676 | 464.847.971 | 6.704.164.705 | 0.716901 | 0.046485 | 0.716901 | 9.960954 | 8.948777 | 10.039691 |
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 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 9 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 2.000000 | 1.666667 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 1.777778 | 1.500000 | 2.000000 |
5 | 32 | 31 | 11 | 20 | 0.968750 | 0.343750 | 0.625000 | 1.937500 | 1.833333 | 2.000000 |
6 | 64 | 57 | 19 | 38 | 0.890625 | 0.296875 | 0.593750 | 1.838710 | 1.727273 | 1.900000 |
7 | 128 | 57 | 19 | 38 | 0.445312 | 0.148438 | 0.296875 | 1.000000 | 1.000000 | 1.000000 |
8 | 256 | 145 | 47 | 98 | 0.566406 | 0.183594 | 0.382812 | 2.543860 | 2.473684 | 2.578947 |
9 | 512 | 340 | 92 | 248 | 0.664062 | 0.179688 | 0.484375 | 2.344828 | 1.957447 | 2.530612 |
10 | 1.024 | 729 | 171 | 558 | 0.711914 | 0.166992 | 0.544922 | 2.144118 | 1.858696 | 2.250000 |
11 | 2.048 | 1.504 | 318 | 1.186 | 0.734375 | 0.155273 | 0.579102 | 2.063100 | 1.859649 | 2.125448 |
12 | 4.096 | 3.049 | 582 | 2.467 | 0.744385 | 0.142090 | 0.602295 | 2.027261 | 1.830189 | 2.080101 |
13 | 8.192 | 6.103 | 1.067 | 5.036 | 0.744995 | 0.130249 | 0.614746 | 2.001640 | 1.833333 | 2.041346 |
14 | 16.384 | 12.289 | 1.932 | 10.357 | 0.750061 | 0.117920 | 0.632141 | 2.013600 | 1.810684 | 2.056592 |
15 | 32.768 | 24.505 | 3.591 | 20.914 | 0.747833 | 0.109589 | 0.638245 | 1.994060 | 1.858696 | 2.019311 |
16 | 65.536 | 48.845 | 6.723 | 42.122 | 0.745316 | 0.102585 | 0.642731 | 1.993267 | 1.872180 | 2.014058 |
17 | 131.072 | 97.265 | 12.524 | 84.741 | 0.742073 | 0.095551 | 0.646523 | 1.991299 | 1.862859 | 2.011799 |
18 | 262.144 | 193.749 | 23.687 | 170.062 | 0.739094 | 0.090359 | 0.648735 | 1.991970 | 1.891329 | 2.006844 |
19 | 524.288 | 386.127 | 44.462 | 341.665 | 0.736479 | 0.084805 | 0.651674 | 1.992924 | 1.877063 | 2.009061 |
20 | 1.048.576 | 769.655 | 83.925 | 685.730 | 0.734000 | 0.080037 | 0.653963 | 1.993269 | 1.887567 | 2.007025 |
21 | 2.097.152 | 1.535.019 | 158.884 | 1.376.135 | 0.731954 | 0.075762 | 0.656192 | 1.994425 | 1.893167 | 2.006818 |
22 | 4.194.304 | 3.061.989 | 302.525 | 2.759.464 | 0.730035 | 0.072128 | 0.657907 | 1.994756 | 1.904062 | 2.005228 |
23 | 8.388.608 | 6.109.266 | 576.533 | 5.532.733 | 0.728281 | 0.068728 | 0.659553 | 1.995195 | 1.905737 | 2.005003 |
24 | 16.777.216 | 12.192.680 | 1.101.604 | 11.091.076 | 0.726740 | 0.065661 | 0.661080 | 1.995768 | 1.910739 | 2.004629 |
25 | 33.554.432 | 24.336.307 | 2.108.931 | 22.227.376 | 0.725278 | 0.062851 | 0.662427 | 1.995977 | 1.914418 | 2.004077 |
26 | 67.108.864 | 48.586.581 | 4.043.749 | 44.542.832 | 0.723996 | 0.060257 | 0.663740 | 1.996465 | 1.917440 | 2.003963 |
27 | 134.217.728 | 97.007.640 | 7.769.182 | 89.238.458 | 0.722763 | 0.057885 | 0.664878 | 1.996593 | 1.921282 | 2.003430 |
28 | 268.435.456 | 193.711.953 | 14.948.925 | 178.763.028 | 0.721633 | 0.055689 | 0.665944 | 1.996873 | 1.924131 | 2.003206 |
29 | 536.870.912 | 386.869.035 | 28.801.320 | 358.067.715 | 0.720600 | 0.053647 | 0.666953 | 1.997136 | 1.926648 | 2.003030 |
30 | 1.073.741.824 | 772.679.795 | 55.573.873 | 717.105.922 | 0.719614 | 0.051757 | 0.667857 | 1.997265 | 1.929560 | 2.002710 |
31 | 2.147.483.648 | 1.543.410.306 | 107.358.897 | 1.436.051.409 | 0.718706 | 0.049993 | 0.668714 | 1.997477 | 1.931823 | 2.002565 |
32 | 4.294.967.296 | 3.083.185.437 | 207.658.335 | 2.875.527.102 | 0.717860 | 0.048349 | 0.669511 | 1.997645 | 1.934244 | 2.002384 |
33 | 8.589.934.592 | 6.159.564.664 | 402.100.669 | 5.757.463.995 | 0.717068 | 0.046811 | 0.670257 | 1.997792 | 1.936357 | 2.002229 |
34 | 17.179.869.184 | 12.306.401.694 | 779.377.604 | 11.527.024.090 | 0.716327 | 0.045366 | 0.670961 | 1.997934 | 1.938265 | 2.002101 |
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 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
3 | 8 | 4 | 3 | 1 | 0 | 1 | 0 | 3 |
4 | 16 | 6 | 4 | 2 | 0 | 2 | 0 | 4 |
5 | 32 | 11 | 8 | 3 | 0 | 5 | 0 | 6 |
6 | 64 | 19 | 13 | 6 | 0 | 10 | 0 | 9 |
7 | 128 | 19 | 13 | 6 | 0 | 10 | 0 | 9 |
8 | 256 | 47 | 24 | 23 | 15 | 10 | 13 | 9 |
9 | 512 | 92 | 35 | 57 | 39 | 10 | 34 | 9 |
10 | 1.024 | 171 | 62 | 109 | 87 | 10 | 65 | 9 |
11 | 2.048 | 318 | 112 | 206 | 158 | 10 | 141 | 9 |
12 | 4.096 | 582 | 198 | 384 | 289 | 10 | 274 | 9 |
13 | 8.192 | 1.067 | 358 | 709 | 531 | 10 | 517 | 9 |
14 | 16.384 | 1.932 | 664 | 1.268 | 963 | 10 | 950 | 9 |
15 | 32.768 | 3.591 | 1.237 | 2.354 | 1.787 | 10 | 1.785 | 9 |
16 | 65.536 | 6.723 | 2.288 | 4.435 | 3.370 | 10 | 3.334 | 9 |
17 | 131.072 | 12.524 | 4.201 | 8.323 | 6.267 | 10 | 6.238 | 9 |
18 | 262.144 | 23.687 | 7.914 | 15.773 | 11.883 | 10 | 11.785 | 9 |
19 | 524.288 | 44.462 | 14.953 | 29.509 | 22.230 | 10 | 22.213 | 9 |
20 | 1.048.576 | 83.925 | 28.121 | 55.804 | 41.974 | 10 | 41.932 | 9 |
21 | 2.097.152 | 158.884 | 52.948 | 105.936 | 79.292 | 10 | 79.573 | 9 |
22 | 4.194.304 | 302.525 | 101.196 | 201.329 | 150.976 | 10 | 151.530 | 9 |
23 | 8.388.608 | 576.533 | 192.500 | 384.033 | 287.725 | 10 | 288.789 | 9 |
24 | 16.777.216 | 1.101.604 | 367.810 | 733.794 | 549.867 | 10 | 551.718 | 9 |
25 | 33.554.432 | 2.108.931 | 703.098 | 1.405.833 | 1.053.537 | 10 | 1.055.375 | 9 |
26 | 67.108.864 | 4.043.749 | 1.348.747 | 2.695.002 | 2.020.649 | 10 | 2.023.081 | 9 |
27 | 134.217.728 | 7.769.182 | 2.591.201 | 5.177.981 | 3.883.531 | 10 | 3.885.632 | 9 |
28 | 268.435.456 | 14.948.925 | 4.985.221 | 9.963.704 | 7.474.640 | 10 | 7.474.266 | 9 |
29 | 536.870.912 | 28.801.320 | 9.602.586 | 19.198.734 | 14.400.240 | 10 | 14.401.061 | 9 |
30 | 1.073.741.824 | 55.573.873 | 18.527.466 | 37.046.407 | 27.787.947 | 10 | 27.785.907 | 9 |
31 | 2.147.483.648 | 107.358.897 | 35.786.511 | 71.572.386 | 53.680.565 | 10 | 53.678.313 | 9 |
32 | 4.294.967.296 | 207.658.335 | 69.218.160 | 138.440.175 | 103.828.635 | 10 | 103.829.681 | 9 |
33 | 8.589.934.592 | 402.100.669 | 134.034.388 | 268.066.281 | 201.053.886 | 10 | 201.046.764 | 9 |
34 | 17.179.869.184 | 779.377.604 | 259.790.737 | 519.586.867 | 389.701.609 | 10 | 389.675.976 | 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 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 3 | 2 | 0 | 1 | 2 | 2 |
4 | 16 | 10 | 5 | 5 | 1 | 2 | 3 | 4 |
5 | 32 | 20 | 8 | 12 | 3 | 4 | 6 | 7 |
6 | 64 | 38 | 15 | 23 | 7 | 10 | 11 | 10 |
7 | 128 | 38 | 15 | 23 | 7 | 10 | 11 | 10 |
8 | 256 | 98 | 53 | 45 | 22 | 27 | 27 | 22 |
9 | 512 | 248 | 138 | 110 | 61 | 62 | 62 | 63 |
10 | 1.024 | 558 | 302 | 256 | 140 | 136 | 144 | 138 |
11 | 2.048 | 1.186 | 652 | 534 | 310 | 289 | 294 | 293 |
12 | 4.096 | 2.467 | 1.322 | 1.145 | 638 | 601 | 631 | 597 |
13 | 8.192 | 5.036 | 2.717 | 2.319 | 1.316 | 1.239 | 1.286 | 1.195 |
14 | 16.384 | 10.357 | 5.496 | 4.861 | 2.669 | 2.533 | 2.650 | 2.505 |
15 | 32.768 | 20.914 | 11.062 | 9.852 | 5.361 | 5.104 | 5.329 | 5.120 |
16 | 65.536 | 42.122 | 22.204 | 19.918 | 10.808 | 10.309 | 10.789 | 10.216 |
17 | 131.072 | 84.741 | 44.508 | 40.233 | 21.764 | 20.652 | 21.674 | 20.651 |
18 | 262.144 | 170.062 | 89.013 | 81.049 | 43.674 | 41.492 | 43.532 | 41.364 |
19 | 524.288 | 341.665 | 178.489 | 163.176 | 87.702 | 83.390 | 87.242 | 83.331 |
20 | 1.048.576 | 685.730 | 357.504 | 328.226 | 175.309 | 167.751 | 174.896 | 167.774 |
21 | 2.097.152 | 1.376.135 | 715.180 | 660.955 | 350.946 | 337.305 | 350.773 | 337.111 |
22 | 4.194.304 | 2.759.464 | 1.431.666 | 1.327.798 | 703.042 | 677.073 | 703.176 | 676.173 |
23 | 8.388.608 | 5.532.733 | 2.865.680 | 2.667.053 | 1.407.792 | 1.358.217 | 1.409.298 | 1.357.426 |
24 | 16.777.216 | 11.091.076 | 5.733.499 | 5.357.577 | 2.818.935 | 2.725.193 | 2.822.035 | 2.724.913 |
25 | 33.554.432 | 22.227.376 | 11.474.928 | 10.752.448 | 5.648.089 | 5.462.730 | 5.651.587 | 5.464.970 |
26 | 67.108.864 | 44.542.832 | 22.962.492 | 21.580.340 | 11.313.024 | 10.958.582 | 11.318.314 | 10.952.912 |
27 | 134.217.728 | 89.238.458 | 45.947.617 | 43.290.841 | 22.653.958 | 21.964.987 | 22.661.913 | 21.957.600 |
28 | 268.435.456 | 178.763.028 | 91.929.200 | 86.833.828 | 45.361.686 | 44.018.254 | 45.374.228 | 44.008.860 |
29 | 536.870.912 | 358.067.715 | 183.939.146 | 174.128.569 | 90.830.771 | 88.207.875 | 90.826.798 | 88.202.271 |
30 | 1.073.741.824 | 717.105.922 | 368.003.573 | 349.102.349 | 181.818.334 | 176.748.027 | 181.815.512 | 176.724.049 |
31 | 2.147.483.648 | 1.436.051.409 | 736.267.101 | 699.784.308 | 363.937.766 | 354.103.952 | 363.952.482 | 354.057.209 |
32 | 4.294.967.296 | 2.875.527.102 | 1.473.067.318 | 1.402.459.784 | 728.454.261 | 709.314.584 | 728.444.445 | 709.313.812 |
33 | 8.589.934.592 | 5.757.463.995 | 2.947.034.597 | 2.810.429.398 | 1.457.953.970 | 1.420.793.977 | 1.457.955.105 | 1.420.760.943 |
34 | 17.179.869.184 | 11.527.024.090 | 5.895.800.137 | 5.631.223.953 | 2.917.964.192 | 2.845.579.104 | 2.917.934.825 | 2.845.545.969 |