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-16x+191
f(0)=191
f(1)=11
f(2)=163
f(3)=19
f(4)=13
f(5)=17
f(6)=131
f(7)=1
f(8)=127
f(9)=1
f(10)=1
f(11)=1
f(12)=1
f(13)=1
f(14)=1
f(15)=1
f(16)=1
f(17)=1
f(18)=227
f(19)=31
f(20)=271
f(21)=37
f(22)=1
f(23)=1
f(24)=383
f(25)=1
f(26)=41
f(27)=61
f(28)=1
f(29)=71
f(30)=47
f(31)=1
f(32)=1
f(33)=1
f(34)=73
f(35)=107
f(36)=911
f(37)=1
f(38)=79
f(39)=1
f(40)=1151
f(41)=1
f(42)=1283
f(43)=1
f(44)=1423
f(45)=1
f(46)=1571
f(47)=103
f(48)=157
f(49)=113
f(50)=1
f(51)=1
f(52)=2063
f(53)=269
f(54)=2243
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=149
f(61)=367
f(62)=179
f(63)=197
f(64)=251
f(65)=211
f(66)=3491
f(67)=1
f(68)=3727
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=4483
f(75)=577
f(76)=4751
f(77)=1
f(78)=457
f(79)=1
f(80)=1
f(81)=1
f(82)=431
f(83)=719
f(84)=5903
f(85)=757
f(86)=6211
f(87)=199
f(88)=1
f(89)=1
f(90)=1
f(91)=877
f(92)=653
f(93)=919
f(94)=7523
f(95)=1
f(96)=463
f(97)=503
f(98)=433
f(99)=1051
b) Substitution of the polynom
The polynom f(x)=x^2-16x+191 could be written as f(y)= y^2+127 with x=y+8
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-8
f'(x)>2x-17 with x > 11
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 | 7 | 1 | 0.800000 | 0.700000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 53 | 41 | 12 | 0.530000 | 0.410000 | 0.120000 | 6.625000 | 5.857143 | 12.000000 |
3 | 1.000 | 613 | 323 | 290 | 0.613000 | 0.323000 | 0.290000 | 11.566038 | 7.878049 | 24.166666 |
4 | 10.000 | 6.484 | 2.279 | 4.205 | 0.648400 | 0.227900 | 0.420500 | 10.577488 | 7.055727 | 14.500000 |
5 | 100.000 | 65.817 | 17.372 | 48.445 | 0.658170 | 0.173720 | 0.484450 | 10.150679 | 7.622642 | 11.520808 |
6 | 1.000.000 | 665.225 | 140.124 | 525.101 | 0.665225 | 0.140124 | 0.525101 | 10.107191 | 8.066083 | 10.839116 |
7 | 10.000.000 | 6.692.649 | 1.172.919 | 5.519.730 | 0.669265 | 0.117292 | 0.551973 | 10.060730 | 8.370579 | 10.511749 |
8 | 100.000.000 | 67.232.050 | 10.092.286 | 57.139.764 | 0.672320 | 0.100923 | 0.571398 | 10.045656 | 8.604419 | 10.351912 |
9 | 1.000.000.000 | 674.657.844 | 88.587.669 | 586.070.175 | 0.674658 | 0.088588 | 0.586070 | 10.034766 | 8.777761 | 10.256783 |
10 | 10.000.000.000 | 6.765.197.079 | 789.404.249 | 5.975.792.830 | 0.676520 | 0.078940 | 0.597579 | 10.027597 | 8.910995 | 10.196378 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 8 | 7 | 1 | 0.500000 | 0.437500 | 0.062500 | 1.000000 | 1.000000 | 1.000000 |
5 | 32 | 13 | 12 | 1 | 0.406250 | 0.375000 | 0.031250 | 1.625000 | 1.714286 | 1.000000 |
6 | 64 | 32 | 25 | 7 | 0.500000 | 0.390625 | 0.109375 | 2.461539 | 2.083333 | 7.000000 |
7 | 128 | 69 | 52 | 17 | 0.539062 | 0.406250 | 0.132812 | 2.156250 | 2.080000 | 2.428571 |
8 | 256 | 147 | 95 | 52 | 0.574219 | 0.371094 | 0.203125 | 2.130435 | 1.826923 | 3.058824 |
9 | 512 | 301 | 179 | 122 | 0.587891 | 0.349609 | 0.238281 | 2.047619 | 1.884210 | 2.346154 |
10 | 1.024 | 627 | 327 | 300 | 0.612305 | 0.319336 | 0.292969 | 2.083056 | 1.826816 | 2.459016 |
11 | 2.048 | 1.295 | 580 | 715 | 0.632324 | 0.283203 | 0.349121 | 2.065391 | 1.773700 | 2.383333 |
12 | 4.096 | 2.628 | 1.035 | 1.593 | 0.641602 | 0.252686 | 0.388916 | 2.029344 | 1.784483 | 2.227972 |
13 | 8.192 | 5.315 | 1.925 | 3.390 | 0.648804 | 0.234985 | 0.413818 | 2.022450 | 1.859903 | 2.128060 |
14 | 16.384 | 10.655 | 3.513 | 7.142 | 0.650330 | 0.214417 | 0.435913 | 2.004704 | 1.824935 | 2.106785 |
15 | 32.768 | 21.420 | 6.493 | 14.927 | 0.653687 | 0.198151 | 0.455536 | 2.010324 | 1.848278 | 2.090031 |
16 | 65.536 | 43.052 | 11.925 | 31.127 | 0.656921 | 0.181961 | 0.474960 | 2.009897 | 1.836593 | 2.085282 |
17 | 131.072 | 86.457 | 22.147 | 64.310 | 0.659615 | 0.168968 | 0.490646 | 2.008199 | 1.857191 | 2.066052 |
18 | 262.144 | 173.517 | 41.388 | 132.129 | 0.661915 | 0.157883 | 0.504032 | 2.006974 | 1.868786 | 2.054564 |
19 | 524.288 | 348.124 | 77.398 | 270.726 | 0.663994 | 0.147625 | 0.516369 | 2.006282 | 1.870059 | 2.048952 |
20 | 1.048.576 | 697.488 | 146.332 | 551.156 | 0.665176 | 0.139553 | 0.525623 | 2.003562 | 1.890643 | 2.035844 |
21 | 2.097.152 | 1.398.008 | 276.350 | 1.121.658 | 0.666622 | 0.131774 | 0.534848 | 2.004347 | 1.888514 | 2.035101 |
22 | 4.194.304 | 2.801.560 | 523.855 | 2.277.705 | 0.667944 | 0.124897 | 0.543047 | 2.003966 | 1.895622 | 2.030659 |
23 | 8.388.608 | 5.611.975 | 996.230 | 4.615.745 | 0.669000 | 0.118760 | 0.550240 | 2.003161 | 1.901729 | 2.026489 |
24 | 16.777.216 | 11.241.404 | 1.898.227 | 9.343.177 | 0.670040 | 0.113143 | 0.556897 | 2.003110 | 1.905410 | 2.024197 |
25 | 33.554.432 | 22.515.142 | 3.625.436 | 18.889.706 | 0.671004 | 0.108046 | 0.562957 | 2.002876 | 1.909907 | 2.021765 |
26 | 67.108.864 | 45.087.850 | 6.939.801 | 38.148.049 | 0.671861 | 0.103411 | 0.568450 | 2.002557 | 1.914198 | 2.019515 |
27 | 134.217.728 | 90.281.836 | 13.308.015 | 76.973.821 | 0.672652 | 0.099152 | 0.573500 | 2.002354 | 1.917636 | 2.017766 |
28 | 268.435.456 | 180.763.674 | 25.561.156 | 155.202.518 | 0.673397 | 0.095223 | 0.578174 | 2.002215 | 1.920734 | 2.016303 |
29 | 536.870.912 | 361.895.301 | 49.180.206 | 312.715.095 | 0.674083 | 0.091605 | 0.582477 | 2.002035 | 1.924021 | 2.014884 |
30 | 1.073.741.824 | 724.474.944 | 94.761.116 | 629.713.828 | 0.674720 | 0.088253 | 0.586467 | 2.001891 | 1.926814 | 2.013698 |
31 | 2.147.483.648 | 1.450.239.690 | 182.823.219 | 1.267.416.471 | 0.675321 | 0.085134 | 0.590187 | 2.001781 | 1.929306 | 2.012686 |
32 | 4.294.967.296 | 2.902.890.624 | 353.157.478 | 2.549.733.146 | 0.675882 | 0.082226 | 0.593656 | 2.001662 | 1.931688 | 2.011756 |
33 | 8.589.934.592 | 5.810.301.898 | 683.005.685 | 5.127.296.213 | 0.676408 | 0.079512 | 0.596896 | 2.001557 | 1.933998 | 2.010915 |
34 | 17.179.869.184 | 11.629.117.496 | 1.322.381.242 | 10.306.736.254 | 0.676904 | 0.076973 | 0.599931 | 2.001465 | 1.936120 | 2.010170 |
35 | 34.359.738.368 | 23.274.285.821 | 2.562.928.714 | 20.711.357.107 | 0.677371 | 0.074591 | 0.602780 | 2.001380 | 1.938116 | 2.009497 |
36 | 68.719.476.736 | 46.578.882.389 | 4.972.074.788 | 41.606.807.601 | 0.677812 | 0.072353 | 0.605459 | 2.001302 | 1.939997 | 2.008888 |
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 | 3 | 1 | 2 | 0 | 2 | 0 | 1 |
2 | 4 | 4 | 2 | 2 | 0 | 3 | 0 | 1 |
3 | 8 | 7 | 3 | 4 | 1 | 4 | 0 | 2 |
4 | 16 | 7 | 3 | 4 | 1 | 4 | 0 | 2 |
5 | 32 | 12 | 5 | 7 | 1 | 5 | 1 | 5 |
6 | 64 | 25 | 8 | 17 | 2 | 9 | 3 | 11 |
7 | 128 | 52 | 23 | 29 | 4 | 20 | 7 | 21 |
8 | 256 | 95 | 44 | 51 | 9 | 31 | 14 | 41 |
9 | 512 | 179 | 80 | 99 | 20 | 63 | 25 | 71 |
10 | 1.024 | 327 | 145 | 182 | 42 | 114 | 46 | 125 |
11 | 2.048 | 580 | 265 | 315 | 82 | 209 | 78 | 211 |
12 | 4.096 | 1.035 | 458 | 577 | 152 | 378 | 132 | 373 |
13 | 8.192 | 1.925 | 841 | 1.084 | 269 | 707 | 264 | 685 |
14 | 16.384 | 3.513 | 1.538 | 1.975 | 470 | 1.309 | 474 | 1.260 |
15 | 32.768 | 6.493 | 2.886 | 3.607 | 876 | 2.394 | 877 | 2.346 |
16 | 65.536 | 11.925 | 5.341 | 6.584 | 1.599 | 4.384 | 1.609 | 4.333 |
17 | 131.072 | 22.147 | 9.944 | 12.203 | 2.989 | 8.094 | 2.944 | 8.120 |
18 | 262.144 | 41.388 | 18.640 | 22.748 | 5.542 | 15.137 | 5.484 | 15.225 |
19 | 524.288 | 77.398 | 34.874 | 42.524 | 10.294 | 28.393 | 10.210 | 28.501 |
20 | 1.048.576 | 146.332 | 65.889 | 80.443 | 19.443 | 53.837 | 19.223 | 53.829 |
21 | 2.097.152 | 276.350 | 124.250 | 152.100 | 36.552 | 101.756 | 36.157 | 101.885 |
22 | 4.194.304 | 523.855 | 235.275 | 288.580 | 69.086 | 193.116 | 68.542 | 193.111 |
23 | 8.388.608 | 996.230 | 447.179 | 549.051 | 130.727 | 367.585 | 130.276 | 367.642 |
24 | 16.777.216 | 1.898.227 | 851.762 | 1.046.465 | 248.435 | 700.732 | 248.019 | 701.041 |
25 | 33.554.432 | 3.625.436 | 1.626.812 | 1.998.624 | 473.445 | 1.338.817 | 473.494 | 1.339.680 |
26 | 67.108.864 | 6.939.801 | 3.112.990 | 3.826.811 | 904.156 | 2.565.110 | 904.524 | 2.566.011 |
27 | 134.217.728 | 13.308.015 | 5.964.603 | 7.343.412 | 1.732.329 | 4.920.656 | 1.731.971 | 4.923.059 |
28 | 268.435.456 | 25.561.156 | 11.454.088 | 14.107.068 | 3.322.718 | 9.457.210 | 3.321.650 | 9.459.578 |
29 | 536.870.912 | 49.180.206 | 22.031.257 | 27.148.949 | 6.383.790 | 18.205.026 | 6.384.927 | 18.206.463 |
30 | 1.073.741.824 | 94.761.116 | 42.437.428 | 52.323.688 | 12.282.003 | 35.096.910 | 12.285.697 | 35.096.506 |
31 | 2.147.483.648 | 182.823.219 | 81.854.373 | 100.968.846 | 23.664.192 | 67.748.316 | 23.668.684 | 67.742.027 |
32 | 4.294.967.296 | 353.157.478 | 158.073.400 | 195.084.078 | 45.657.905 | 130.922.090 | 45.663.939 | 130.913.544 |
33 | 8.589.934.592 | 683.005.685 | 305.629.223 | 377.376.462 | 88.208.264 | 253.305.966 | 88.209.388 | 253.282.067 |
34 | 17.179.869.184 | 1.322.381.242 | 591.611.241 | 730.770.001 | 170.592.968 | 490.591.738 | 170.609.944 | 490.586.592 |
35 | 34.359.738.368 | 2.562.928.714 | 1.146.369.280 | 1.416.559.434 | 330.321.424 | 951.151.510 | 330.342.211 | 951.113.569 |
36 | 68.719.476.736 | 4.972.074.788 | 2.223.517.509 | 2.748.557.279 | 640.228.423 | 1.845.827.526 | 640.277.198 | 1.845.741.641 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
5 | 32 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
6 | 64 | 7 | 4 | 3 | 1 | 2 | 3 | 1 |
7 | 128 | 17 | 9 | 8 | 6 | 3 | 4 | 4 |
8 | 256 | 52 | 23 | 29 | 15 | 14 | 11 | 12 |
9 | 512 | 122 | 58 | 64 | 34 | 31 | 27 | 30 |
10 | 1.024 | 300 | 135 | 165 | 81 | 74 | 78 | 67 |
11 | 2.048 | 715 | 342 | 373 | 181 | 170 | 197 | 167 |
12 | 4.096 | 1.593 | 795 | 798 | 407 | 393 | 421 | 372 |
13 | 8.192 | 3.390 | 1.701 | 1.689 | 877 | 828 | 881 | 804 |
14 | 16.384 | 7.142 | 3.558 | 3.584 | 1.789 | 1.755 | 1.842 | 1.756 |
15 | 32.768 | 14.927 | 7.483 | 7.444 | 3.803 | 3.651 | 3.840 | 3.633 |
16 | 65.536 | 31.127 | 15.653 | 15.474 | 7.953 | 7.569 | 7.960 | 7.645 |
17 | 131.072 | 64.310 | 32.173 | 32.137 | 16.464 | 15.722 | 16.287 | 15.837 |
18 | 262.144 | 132.129 | 66.029 | 66.100 | 33.672 | 32.453 | 33.529 | 32.475 |
19 | 524.288 | 270.726 | 135.478 | 135.248 | 68.802 | 66.567 | 68.903 | 66.454 |
20 | 1.048.576 | 551.156 | 275.732 | 275.424 | 139.992 | 135.538 | 140.013 | 135.613 |
21 | 2.097.152 | 1.121.658 | 561.243 | 560.415 | 284.784 | 275.873 | 284.176 | 276.825 |
22 | 4.194.304 | 2.277.705 | 1.139.217 | 1.138.488 | 577.328 | 561.730 | 577.083 | 561.564 |
23 | 8.388.608 | 4.615.745 | 2.310.439 | 2.305.306 | 1.167.196 | 1.140.607 | 1.168.798 | 1.139.144 |
24 | 16.777.216 | 9.343.177 | 4.677.506 | 4.665.671 | 2.361.027 | 2.310.397 | 2.363.286 | 2.308.467 |
25 | 33.554.432 | 18.889.706 | 9.456.398 | 9.433.308 | 4.773.509 | 4.673.857 | 4.771.872 | 4.670.468 |
26 | 67.108.864 | 38.148.049 | 19.092.847 | 19.055.202 | 9.633.407 | 9.441.150 | 9.634.502 | 9.438.990 |
27 | 134.217.728 | 76.973.821 | 38.524.618 | 38.449.203 | 19.428.656 | 19.061.254 | 19.424.851 | 19.059.060 |
28 | 268.435.456 | 155.202.518 | 77.671.782 | 77.530.736 | 39.151.901 | 38.453.099 | 39.153.205 | 38.444.313 |
29 | 536.870.912 | 312.715.095 | 156.481.473 | 156.233.622 | 78.847.990 | 77.510.666 | 78.850.568 | 77.505.871 |
30 | 1.073.741.824 | 629.713.828 | 315.097.883 | 314.615.945 | 158.723.997 | 156.126.483 | 158.737.547 | 156.125.801 |
31 | 2.147.483.648 | 1.267.416.471 | 634.155.783 | 633.260.688 | 319.351.878 | 314.345.913 | 319.368.339 | 314.350.341 |
32 | 4.294.967.296 | 2.549.733.146 | 1.275.752.854 | 1.273.980.292 | 642.251.934 | 632.575.273 | 642.274.021 | 632.631.918 |
33 | 8.589.934.592 | 5.127.296.213 | 2.565.390.073 | 2.561.906.140 | 1.291.130.228 | 1.272.495.581 | 1.291.141.725 | 1.272.528.679 |
34 | 17.179.869.184 | 10.306.736.254 | 5.156.700.787 | 5.150.035.467 | 2.594.626.482 | 2.558.737.953 | 2.594.628.437 | 2.558.743.382 |
35 | 34.359.738.368 | 20.711.357.107 | 10.362.045.433 | 10.349.311.674 | 5.212.528.132 | 5.143.158.898 | 5.212.506.274 | 5.143.163.803 |
36 | 68.719.476.736 | 41.606.807.601 | 20.815.727.520 | 20.791.080.081 | 10.468.834.861 | 10.334.519.204 | 10.468.805.424 | 10.334.648.112 |