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+72x-113
f(0)=113
f(1)=5
f(2)=7
f(3)=1
f(4)=191
f(5)=17
f(6)=71
f(7)=11
f(8)=31
f(9)=1
f(10)=101
f(11)=1
f(12)=179
f(13)=1
f(14)=1091
f(15)=149
f(16)=37
f(17)=1
f(18)=137
f(19)=1
f(20)=157
f(21)=23
f(22)=1
f(23)=1
f(24)=313
f(25)=1
f(26)=487
f(27)=1
f(28)=2687
f(29)=1
f(30)=421
f(31)=1
f(32)=643
f(33)=419
f(34)=3491
f(35)=227
f(36)=151
f(37)=1
f(38)=83
f(39)=1
f(40)=397
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1063
f(47)=1
f(48)=5647
f(49)=727
f(50)=5987
f(51)=1
f(52)=181
f(53)=1
f(54)=6691
f(55)=859
f(56)=1
f(57)=1
f(58)=1061
f(59)=1
f(60)=211
f(61)=1
f(62)=1
f(63)=1049
f(64)=1
f(65)=1
f(66)=257
f(67)=1
f(68)=409
f(69)=601
f(70)=317
f(71)=251
f(72)=293
f(73)=1
f(74)=10691
f(75)=1
f(76)=131
f(77)=1
f(78)=11587
f(79)=1
f(80)=1721
f(81)=307
f(82)=2503
f(83)=797
f(84)=1181
f(85)=827
f(86)=1
f(87)=1
f(88)=13967
f(89)=1777
f(90)=1
f(91)=1
f(92)=599
f(93)=1
f(94)=2213
f(95)=1
f(96)=3203
f(97)=1
f(98)=16547
f(99)=1051
b) Substitution of the polynom
The polynom f(x)=x^2+72x-113 could be written as f(y)= y^2-1409 with x=y-36
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+36
f'(x)>2x+71
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 | 4 | 4 | 0.800000 | 0.400000 | 0.400000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 25 | 32 | 0.570000 | 0.250000 | 0.320000 | 7.125000 | 6.250000 | 8.000000 |
3 | 1.000 | 592 | 182 | 410 | 0.592000 | 0.182000 | 0.410000 | 10.385965 | 7.280000 | 12.812500 |
4 | 10.000 | 6.164 | 1.358 | 4.806 | 0.616400 | 0.135800 | 0.480600 | 10.412162 | 7.461538 | 11.721951 |
5 | 100.000 | 63.521 | 10.251 | 53.270 | 0.635210 | 0.102510 | 0.532700 | 10.305159 | 7.548601 | 11.084062 |
6 | 1.000.000 | 644.936 | 82.356 | 562.580 | 0.644936 | 0.082356 | 0.562580 | 10.153114 | 8.033948 | 10.560916 |
7 | 10.000.000 | 6.521.960 | 691.374 | 5.830.586 | 0.652196 | 0.069137 | 0.583059 | 10.112569 | 8.394944 | 10.364012 |
8 | 100.000.000 | 65.749.148 | 5.939.481 | 59.809.667 | 0.657492 | 0.059395 | 0.598097 | 10.081195 | 8.590837 | 10.257917 |
9 | 1.000.000.000 | 661.542.284 | 52.110.965 | 609.431.319 | 0.661542 | 0.052111 | 0.609431 | 10.061610 | 8.773656 | 10.189511 |
10 | 10.000.000.000 | 6.647.595.487 | 464.436.438 | 6.183.159.049 | 0.664760 | 0.046444 | 0.618316 | 10.048633 | 8.912452 | 10.145785 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.750000 | 1.333333 | 3.000000 |
4 | 16 | 12 | 6 | 6 | 0.750000 | 0.375000 | 0.375000 | 1.714286 | 1.500000 | 2.000000 |
5 | 32 | 19 | 7 | 12 | 0.593750 | 0.218750 | 0.375000 | 1.583333 | 1.166667 | 2.000000 |
6 | 64 | 35 | 16 | 19 | 0.546875 | 0.250000 | 0.296875 | 1.842105 | 2.285714 | 1.583333 |
7 | 128 | 72 | 32 | 40 | 0.562500 | 0.250000 | 0.312500 | 2.057143 | 2.000000 | 2.105263 |
8 | 256 | 144 | 58 | 86 | 0.562500 | 0.226562 | 0.335938 | 2.000000 | 1.812500 | 2.150000 |
9 | 512 | 293 | 105 | 188 | 0.572266 | 0.205078 | 0.367188 | 2.034722 | 1.810345 | 2.186047 |
10 | 1.024 | 606 | 186 | 420 | 0.591797 | 0.181641 | 0.410156 | 2.068259 | 1.771429 | 2.234043 |
11 | 2.048 | 1.228 | 343 | 885 | 0.599609 | 0.167480 | 0.432129 | 2.026403 | 1.844086 | 2.107143 |
12 | 4.096 | 2.484 | 625 | 1.859 | 0.606445 | 0.152588 | 0.453857 | 2.022801 | 1.822157 | 2.100565 |
13 | 8.192 | 5.026 | 1.141 | 3.885 | 0.613525 | 0.139282 | 0.474243 | 2.023350 | 1.825600 | 2.089833 |
14 | 16.384 | 10.175 | 2.093 | 8.082 | 0.621033 | 0.127747 | 0.493286 | 2.024473 | 1.834356 | 2.080309 |
15 | 32.768 | 20.588 | 3.847 | 16.741 | 0.628296 | 0.117401 | 0.510895 | 2.023391 | 1.838032 | 2.071393 |
16 | 65.536 | 41.478 | 7.011 | 34.467 | 0.632904 | 0.106979 | 0.525925 | 2.014669 | 1.822459 | 2.058838 |
17 | 131.072 | 83.462 | 13.083 | 70.379 | 0.636765 | 0.099815 | 0.536949 | 2.012199 | 1.866068 | 2.041924 |
18 | 262.144 | 167.594 | 24.367 | 143.227 | 0.639320 | 0.092953 | 0.546368 | 2.008028 | 1.862493 | 2.035081 |
19 | 524.288 | 336.760 | 45.696 | 291.064 | 0.642319 | 0.087158 | 0.555161 | 2.009380 | 1.875323 | 2.032187 |
20 | 1.048.576 | 676.615 | 86.016 | 590.599 | 0.645270 | 0.082031 | 0.563239 | 2.009191 | 1.882353 | 2.029104 |
21 | 2.097.152 | 1.358.394 | 162.735 | 1.195.659 | 0.647733 | 0.077598 | 0.570135 | 2.007632 | 1.891915 | 2.024485 |
22 | 4.194.304 | 2.725.506 | 308.386 | 2.417.120 | 0.649811 | 0.073525 | 0.576286 | 2.006418 | 1.895020 | 2.021580 |
23 | 8.388.608 | 5.466.946 | 587.117 | 4.879.829 | 0.651711 | 0.069990 | 0.581721 | 2.005846 | 1.903838 | 2.018861 |
24 | 16.777.216 | 10.964.427 | 1.117.665 | 9.846.762 | 0.653531 | 0.066618 | 0.586913 | 2.005585 | 1.903650 | 2.017850 |
25 | 33.554.432 | 21.984.382 | 2.133.660 | 19.850.722 | 0.655186 | 0.063588 | 0.591598 | 2.005064 | 1.909034 | 2.015965 |
26 | 67.108.864 | 44.068.027 | 4.085.350 | 39.982.677 | 0.656665 | 0.060876 | 0.595788 | 2.004515 | 1.914715 | 2.014167 |
27 | 134.217.728 | 88.322.933 | 7.831.893 | 80.491.040 | 0.658057 | 0.058352 | 0.599705 | 2.004241 | 1.917068 | 2.013148 |
28 | 268.435.456 | 176.992.298 | 15.042.530 | 161.949.768 | 0.659348 | 0.056038 | 0.603310 | 2.003922 | 1.920676 | 2.012022 |
29 | 536.870.912 | 354.623.016 | 28.933.311 | 325.689.705 | 0.660537 | 0.053892 | 0.606644 | 2.003607 | 1.923434 | 2.011054 |
30 | 1.073.741.824 | 710.444.558 | 55.742.273 | 654.702.285 | 0.661653 | 0.051914 | 0.609739 | 2.003380 | 1.926578 | 2.010203 |
31 | 2.147.483.648 | 1.423.106.223 | 107.545.277 | 1.315.560.946 | 0.662685 | 0.050080 | 0.612606 | 2.003121 | 1.929331 | 2.009403 |
32 | 4.294.967.296 | 2.850.405.260 | 207.759.640 | 2.642.645.620 | 0.663662 | 0.048373 | 0.615289 | 2.002946 | 1.931834 | 2.008759 |
33 | 8.589.934.592 | 5.708.604.572 | 401.831.857 | 5.306.772.715 | 0.664569 | 0.046779 | 0.617790 | 2.002734 | 1.934119 | 2.008129 |
34 | 17.179.869.184 | 11.431.883.684 | 778.001.414 | 10.653.882.270 | 0.665423 | 0.045286 | 0.620138 | 2.002571 | 1.936137 | 2.007601 |
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 | 3 | 0 | 3 | 1 | 0 | 1 | 1 |
3 | 8 | 4 | 0 | 4 | 2 | 0 | 1 | 1 |
4 | 16 | 6 | 0 | 6 | 2 | 1 | 2 | 1 |
5 | 32 | 7 | 0 | 7 | 2 | 1 | 2 | 2 |
6 | 64 | 16 | 4 | 12 | 3 | 7 | 2 | 4 |
7 | 128 | 32 | 11 | 21 | 5 | 13 | 6 | 8 |
8 | 256 | 58 | 25 | 33 | 11 | 22 | 10 | 15 |
9 | 512 | 105 | 46 | 59 | 12 | 41 | 16 | 36 |
10 | 1.024 | 186 | 86 | 100 | 20 | 70 | 26 | 70 |
11 | 2.048 | 343 | 156 | 187 | 41 | 115 | 49 | 138 |
12 | 4.096 | 625 | 287 | 338 | 73 | 215 | 89 | 248 |
13 | 8.192 | 1.141 | 521 | 620 | 145 | 407 | 155 | 434 |
14 | 16.384 | 2.093 | 945 | 1.148 | 279 | 755 | 291 | 768 |
15 | 32.768 | 3.847 | 1.728 | 2.119 | 528 | 1.383 | 533 | 1.403 |
16 | 65.536 | 7.011 | 3.126 | 3.885 | 921 | 2.516 | 973 | 2.601 |
17 | 131.072 | 13.083 | 5.879 | 7.204 | 1.773 | 4.727 | 1.754 | 4.829 |
18 | 262.144 | 24.367 | 10.998 | 13.369 | 3.248 | 8.918 | 3.244 | 8.957 |
19 | 524.288 | 45.696 | 20.631 | 25.065 | 5.984 | 16.765 | 6.106 | 16.841 |
20 | 1.048.576 | 86.016 | 38.770 | 47.246 | 11.360 | 31.580 | 11.505 | 31.571 |
21 | 2.097.152 | 162.735 | 73.248 | 89.487 | 21.369 | 59.963 | 21.639 | 59.764 |
22 | 4.194.304 | 308.386 | 138.901 | 169.485 | 40.401 | 113.715 | 40.698 | 113.572 |
23 | 8.388.608 | 587.117 | 263.938 | 323.179 | 76.726 | 216.877 | 77.316 | 216.198 |
24 | 16.777.216 | 1.117.665 | 501.815 | 615.850 | 146.072 | 413.094 | 146.641 | 411.858 |
25 | 33.554.432 | 2.133.660 | 957.613 | 1.176.047 | 278.558 | 788.593 | 279.377 | 787.132 |
26 | 67.108.864 | 4.085.350 | 1.833.364 | 2.251.986 | 532.226 | 1.510.250 | 533.828 | 1.509.046 |
27 | 134.217.728 | 7.831.893 | 3.512.564 | 4.319.329 | 1.018.192 | 2.896.399 | 1.020.529 | 2.896.773 |
28 | 268.435.456 | 15.042.530 | 6.740.980 | 8.301.550 | 1.954.165 | 5.565.602 | 1.955.065 | 5.567.698 |
29 | 536.870.912 | 28.933.311 | 12.962.785 | 15.970.526 | 3.754.434 | 10.710.767 | 3.753.918 | 10.714.192 |
30 | 1.073.741.824 | 55.742.273 | 24.961.900 | 30.780.373 | 7.222.062 | 20.647.732 | 7.224.223 | 20.648.256 |
31 | 2.147.483.648 | 107.545.277 | 48.154.871 | 59.390.406 | 13.918.657 | 39.855.336 | 13.919.018 | 39.852.266 |
32 | 4.294.967.296 | 207.759.640 | 92.998.840 | 114.760.800 | 26.854.796 | 77.026.210 | 26.859.819 | 77.018.815 |
33 | 8.589.934.592 | 401.831.857 | 179.821.771 | 222.010.086 | 51.889.078 | 149.019.831 | 51.896.835 | 149.026.113 |
34 | 17.179.869.184 | 778.001.414 | 348.072.031 | 429.929.383 | 100.367.775 | 288.624.425 | 100.374.140 | 288.635.074 |
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 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 0 | 0 | 3 |
4 | 16 | 6 | 3 | 3 | 0 | 1 | 2 | 3 |
5 | 32 | 12 | 8 | 4 | 2 | 2 | 4 | 4 |
6 | 64 | 19 | 13 | 6 | 2 | 4 | 7 | 6 |
7 | 128 | 40 | 22 | 18 | 7 | 11 | 11 | 11 |
8 | 256 | 86 | 45 | 41 | 21 | 21 | 21 | 23 |
9 | 512 | 188 | 98 | 90 | 44 | 41 | 51 | 52 |
10 | 1.024 | 420 | 217 | 203 | 101 | 98 | 109 | 112 |
11 | 2.048 | 885 | 463 | 422 | 211 | 224 | 229 | 221 |
12 | 4.096 | 1.859 | 971 | 888 | 462 | 471 | 466 | 460 |
13 | 8.192 | 3.885 | 1.986 | 1.899 | 960 | 978 | 971 | 976 |
14 | 16.384 | 8.082 | 4.104 | 3.978 | 2.021 | 2.015 | 1.998 | 2.048 |
15 | 32.768 | 16.741 | 8.503 | 8.238 | 4.220 | 4.168 | 4.149 | 4.204 |
16 | 65.536 | 34.467 | 17.500 | 16.967 | 8.634 | 8.596 | 8.693 | 8.544 |
17 | 131.072 | 70.379 | 35.570 | 34.809 | 17.709 | 17.525 | 17.599 | 17.546 |
18 | 262.144 | 143.227 | 72.114 | 71.113 | 35.922 | 35.619 | 35.878 | 35.808 |
19 | 524.288 | 291.064 | 146.661 | 144.403 | 72.923 | 72.480 | 73.151 | 72.510 |
20 | 1.048.576 | 590.599 | 297.368 | 293.231 | 147.974 | 147.319 | 148.166 | 147.140 |
21 | 2.097.152 | 1.195.659 | 601.851 | 593.808 | 299.883 | 298.688 | 299.351 | 297.737 |
22 | 4.194.304 | 2.417.120 | 1.216.947 | 1.200.173 | 605.437 | 603.592 | 605.560 | 602.531 |
23 | 8.388.608 | 4.879.829 | 2.455.968 | 2.423.861 | 1.221.821 | 1.217.947 | 1.223.106 | 1.216.955 |
24 | 16.777.216 | 9.846.762 | 4.953.279 | 4.893.483 | 2.466.260 | 2.456.335 | 2.466.478 | 2.457.689 |
25 | 33.554.432 | 19.850.722 | 9.980.109 | 9.870.613 | 4.971.070 | 4.952.235 | 4.972.518 | 4.954.899 |
26 | 67.108.864 | 39.982.677 | 20.098.688 | 19.883.989 | 10.012.813 | 9.976.796 | 10.013.277 | 9.979.791 |
27 | 134.217.728 | 80.491.040 | 40.453.853 | 40.037.187 | 20.153.091 | 20.089.226 | 20.155.896 | 20.092.827 |
28 | 268.435.456 | 161.949.768 | 81.373.246 | 80.576.522 | 40.556.576 | 40.421.232 | 40.548.396 | 40.423.564 |
29 | 536.870.912 | 325.689.705 | 163.605.097 | 162.084.608 | 81.547.453 | 81.296.687 | 81.539.758 | 81.305.807 |
30 | 1.073.741.824 | 654.702.285 | 328.833.918 | 325.868.367 | 163.910.053 | 163.436.345 | 163.911.106 | 163.444.781 |
31 | 2.147.483.648 | 1.315.560.946 | 660.664.342 | 654.896.604 | 329.338.353 | 328.414.694 | 329.350.485 | 328.457.414 |
32 | 4.294.967.296 | 2.642.645.620 | 1.326.884.005 | 1.315.761.615 | 661.515.774 | 659.773.292 | 661.555.965 | 659.800.589 |
33 | 8.589.934.592 | 5.306.772.715 | 2.664.201.223 | 2.642.571.492 | 1.328.334.082 | 1.325.021.698 | 1.328.401.897 | 1.325.015.038 |
34 | 17.179.869.184 | 10.653.882.270 | 5.347.881.955 | 5.306.000.315 | 2.666.683.691 | 2.660.236.870 | 2.666.730.665 | 2.660.231.044 |