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+8x-73
f(0)=73
f(1)=1
f(2)=53
f(3)=5
f(4)=1
f(5)=1
f(6)=11
f(7)=1
f(8)=1
f(9)=1
f(10)=107
f(11)=17
f(12)=167
f(13)=1
f(14)=47
f(15)=1
f(16)=311
f(17)=1
f(18)=79
f(19)=1
f(20)=487
f(21)=67
f(22)=587
f(23)=1
f(24)=139
f(25)=1
f(26)=811
f(27)=109
f(28)=1
f(29)=1
f(30)=97
f(31)=71
f(32)=1
f(33)=1
f(34)=271
f(35)=179
f(36)=1511
f(37)=199
f(38)=1
f(39)=1
f(40)=1847
f(41)=1
f(42)=2027
f(43)=1
f(44)=443
f(45)=1
f(46)=2411
f(47)=157
f(48)=523
f(49)=1
f(50)=257
f(51)=367
f(52)=277
f(53)=1
f(54)=131
f(55)=1
f(56)=3511
f(57)=227
f(58)=751
f(59)=1
f(60)=4007
f(61)=1
f(62)=251
f(63)=1
f(64)=907
f(65)=1
f(66)=283
f(67)=619
f(68)=1019
f(69)=1
f(70)=5387
f(71)=173
f(72)=1
f(73)=1
f(74)=1
f(75)=769
f(76)=6311
f(77)=809
f(78)=1327
f(79)=1
f(80)=6967
f(81)=223
f(82)=7307
f(83)=1
f(84)=1531
f(85)=89
f(86)=8011
f(87)=1
f(88)=1
f(89)=1
f(90)=8747
f(91)=1117
f(92)=9127
f(93)=233
f(94)=1
f(95)=607
f(96)=1
f(97)=1
f(98)=2063
f(99)=263
b) Substitution of the polynom
The polynom f(x)=x^2+8x-73 could be written as f(y)= y^2-89 with x=y-4
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+4
f'(x)>2x+7
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 | 3 | 3 | 0 | 0.300000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 36 | 21 | 0.570000 | 0.360000 | 0.210000 | 19.000000 | 12.000000 | inf |
3 | 1.000 | 652 | 276 | 376 | 0.652000 | 0.276000 | 0.376000 | 11.438597 | 7.666667 | 17.904762 |
4 | 10.000 | 6.649 | 1.990 | 4.659 | 0.664900 | 0.199000 | 0.465900 | 10.197853 | 7.210145 | 12.390958 |
5 | 100.000 | 67.161 | 15.202 | 51.959 | 0.671610 | 0.152020 | 0.519590 | 10.100918 | 7.639196 | 11.152393 |
6 | 1.000.000 | 675.035 | 123.265 | 551.770 | 0.675035 | 0.123265 | 0.551770 | 10.050997 | 8.108473 | 10.619334 |
7 | 10.000.000 | 6.777.385 | 1.028.384 | 5.749.001 | 0.677738 | 0.102838 | 0.574900 | 10.040050 | 8.342871 | 10.419198 |
8 | 100.000.000 | 67.959.573 | 8.845.239 | 59.114.334 | 0.679596 | 0.088452 | 0.591143 | 10.027404 | 8.601106 | 10.282540 |
9 | 1.000.000.000 | 681.045.233 | 77.628.582 | 603.416.651 | 0.681045 | 0.077629 | 0.603417 | 10.021329 | 8.776313 | 10.207620 |
10 | 10.000.000.000 | 6.822.063.357 | 691.788.035 | 6.130.275.322 | 0.682206 | 0.069179 | 0.613028 | 10.017048 | 8.911511 | 10.159274 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 2 | 2 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 2 | 2 | 0 | 0.250000 | 0.250000 | 0.000000 | 1.000000 | 1.000000 | -nan |
4 | 16 | 6 | 5 | 1 | 0.375000 | 0.312500 | 0.062500 | 3.000000 | 2.500000 | inf |
5 | 32 | 15 | 11 | 4 | 0.468750 | 0.343750 | 0.125000 | 2.500000 | 2.200000 | 4.000000 |
6 | 64 | 35 | 22 | 13 | 0.546875 | 0.343750 | 0.203125 | 2.333333 | 2.000000 | 3.250000 |
7 | 128 | 76 | 47 | 29 | 0.593750 | 0.367188 | 0.226562 | 2.171429 | 2.136364 | 2.230769 |
8 | 256 | 156 | 87 | 69 | 0.609375 | 0.339844 | 0.269531 | 2.052632 | 1.851064 | 2.379310 |
9 | 512 | 325 | 157 | 168 | 0.634766 | 0.306641 | 0.328125 | 2.083333 | 1.804598 | 2.434783 |
10 | 1.024 | 671 | 285 | 386 | 0.655273 | 0.278320 | 0.376953 | 2.064615 | 1.815287 | 2.297619 |
11 | 2.048 | 1.348 | 507 | 841 | 0.658203 | 0.247559 | 0.410645 | 2.008942 | 1.778947 | 2.178756 |
12 | 4.096 | 2.711 | 922 | 1.789 | 0.661865 | 0.225098 | 0.436768 | 2.011128 | 1.818540 | 2.127229 |
13 | 8.192 | 5.435 | 1.687 | 3.748 | 0.663452 | 0.205933 | 0.457520 | 2.004795 | 1.829718 | 2.095025 |
14 | 16.384 | 10.928 | 3.063 | 7.865 | 0.666992 | 0.186951 | 0.480042 | 2.010672 | 1.815649 | 2.098453 |
15 | 32.768 | 21.935 | 5.614 | 16.321 | 0.669403 | 0.171326 | 0.498077 | 2.007229 | 1.832844 | 2.075143 |
16 | 65.536 | 44.005 | 10.380 | 33.625 | 0.671463 | 0.158386 | 0.513077 | 2.006155 | 1.848949 | 2.060229 |
17 | 131.072 | 88.134 | 19.372 | 68.762 | 0.672409 | 0.147797 | 0.524612 | 2.002818 | 1.866281 | 2.044966 |
18 | 262.144 | 176.421 | 36.320 | 140.101 | 0.672993 | 0.138550 | 0.534443 | 2.001736 | 1.874871 | 2.037477 |
19 | 524.288 | 353.548 | 68.202 | 285.346 | 0.674339 | 0.130085 | 0.544254 | 2.004002 | 1.877808 | 2.036716 |
20 | 1.048.576 | 708.005 | 128.722 | 579.283 | 0.675206 | 0.122759 | 0.552447 | 2.002571 | 1.887364 | 2.030107 |
21 | 2.097.152 | 1.417.987 | 242.776 | 1.175.211 | 0.676149 | 0.115765 | 0.560384 | 2.002792 | 1.886049 | 2.028734 |
22 | 4.194.304 | 2.839.341 | 460.006 | 2.379.335 | 0.676952 | 0.109674 | 0.567278 | 2.002374 | 1.894775 | 2.024602 |
23 | 8.388.608 | 5.684.024 | 873.219 | 4.810.805 | 0.677588 | 0.104096 | 0.573493 | 2.001881 | 1.898277 | 2.021912 |
24 | 16.777.216 | 11.378.549 | 1.664.378 | 9.714.171 | 0.678214 | 0.099205 | 0.579010 | 2.001848 | 1.906026 | 2.019240 |
25 | 33.554.432 | 22.775.867 | 3.179.695 | 19.596.172 | 0.678774 | 0.094762 | 0.584011 | 2.001650 | 1.910440 | 2.017277 |
26 | 67.108.864 | 45.587.317 | 6.084.007 | 39.503.310 | 0.679304 | 0.090659 | 0.588645 | 2.001562 | 1.913393 | 2.015869 |
27 | 134.217.728 | 91.240.990 | 11.664.725 | 79.576.265 | 0.679798 | 0.086909 | 0.592889 | 2.001456 | 1.917277 | 2.014420 |
28 | 268.435.456 | 182.607.060 | 22.403.102 | 160.203.958 | 0.680264 | 0.083458 | 0.596806 | 2.001371 | 1.920586 | 2.013213 |
29 | 536.870.912 | 365.439.378 | 43.101.664 | 322.337.714 | 0.680684 | 0.080283 | 0.600401 | 2.001234 | 1.923915 | 2.012046 |
30 | 1.073.741.824 | 731.306.055 | 83.040.006 | 648.266.049 | 0.681082 | 0.077337 | 0.603745 | 2.001169 | 1.926608 | 2.011139 |
31 | 2.147.483.648 | 1.463.417.804 | 160.211.074 | 1.303.206.730 | 0.681457 | 0.074604 | 0.606853 | 2.001102 | 1.929324 | 2.010296 |
32 | 4.294.967.296 | 2.928.328.123 | 309.492.085 | 2.618.836.038 | 0.681805 | 0.072059 | 0.609745 | 2.001020 | 1.931777 | 2.009532 |
33 | 8.589.934.592 | 5.859.508.293 | 598.548.563 | 5.260.959.730 | 0.682137 | 0.069680 | 0.612456 | 2.000974 | 1.933970 | 2.008893 |
34 | 17.179.869.184 | 11.724.361.369 | 1.158.869.489 | 10.565.491.880 | 0.682448 | 0.067455 | 0.614993 | 2.000912 | 1.936133 | 2.008282 |
35 | 34.359.738.368 | 23.458.795.037 | 2.246.020.767 | 21.212.774.270 | 0.682741 | 0.065368 | 0.617373 | 2.000859 | 1.938114 | 2.007741 |
36 | 68.719.476.736 | 46.936.620.714 | 4.357.319.671 | 42.579.301.043 | 0.683018 | 0.063407 | 0.619610 | 2.000811 | 1.940017 | 2.007248 |
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 | 1 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
4 | 16 | 5 | 1 | 4 | 1 | 1 | 1 | 2 |
5 | 32 | 11 | 5 | 6 | 1 | 4 | 2 | 4 |
6 | 64 | 22 | 9 | 13 | 1 | 8 | 3 | 10 |
7 | 128 | 47 | 20 | 27 | 3 | 18 | 7 | 19 |
8 | 256 | 87 | 38 | 49 | 9 | 31 | 15 | 32 |
9 | 512 | 157 | 68 | 89 | 19 | 56 | 26 | 56 |
10 | 1.024 | 285 | 125 | 160 | 37 | 101 | 41 | 106 |
11 | 2.048 | 507 | 230 | 277 | 70 | 183 | 72 | 182 |
12 | 4.096 | 922 | 413 | 509 | 124 | 326 | 136 | 336 |
13 | 8.192 | 1.687 | 743 | 944 | 226 | 601 | 242 | 618 |
14 | 16.384 | 3.063 | 1.396 | 1.667 | 423 | 1.105 | 418 | 1.117 |
15 | 32.768 | 5.614 | 2.532 | 3.082 | 767 | 2.018 | 759 | 2.070 |
16 | 65.536 | 10.380 | 4.684 | 5.696 | 1.391 | 3.749 | 1.408 | 3.832 |
17 | 131.072 | 19.372 | 8.787 | 10.585 | 2.565 | 7.040 | 2.660 | 7.107 |
18 | 262.144 | 36.320 | 16.417 | 19.903 | 4.806 | 13.252 | 4.947 | 13.315 |
19 | 524.288 | 68.202 | 30.809 | 37.393 | 9.067 | 24.944 | 9.180 | 25.011 |
20 | 1.048.576 | 128.722 | 58.046 | 70.676 | 17.028 | 47.350 | 17.090 | 47.254 |
21 | 2.097.152 | 242.776 | 109.200 | 133.576 | 32.055 | 89.172 | 32.263 | 89.286 |
22 | 4.194.304 | 460.006 | 206.754 | 253.252 | 60.380 | 169.369 | 60.861 | 169.396 |
23 | 8.388.608 | 873.219 | 392.680 | 480.539 | 114.331 | 322.029 | 114.909 | 321.950 |
24 | 16.777.216 | 1.664.378 | 747.607 | 916.771 | 217.874 | 614.354 | 218.581 | 613.569 |
25 | 33.554.432 | 3.179.695 | 1.426.785 | 1.752.910 | 414.693 | 1.174.332 | 416.412 | 1.174.258 |
26 | 67.108.864 | 6.084.007 | 2.727.996 | 3.356.011 | 792.830 | 2.248.483 | 793.999 | 2.248.695 |
27 | 134.217.728 | 11.664.725 | 5.228.489 | 6.436.236 | 1.517.947 | 4.312.706 | 1.519.674 | 4.314.398 |
28 | 268.435.456 | 22.403.102 | 10.038.015 | 12.365.087 | 2.910.561 | 8.289.072 | 2.913.720 | 8.289.749 |
29 | 536.870.912 | 43.101.664 | 19.305.302 | 23.796.362 | 5.591.768 | 15.957.211 | 5.595.161 | 15.957.524 |
30 | 1.073.741.824 | 83.040.006 | 37.186.299 | 45.853.707 | 10.761.913 | 30.756.794 | 10.764.093 | 30.757.206 |
31 | 2.147.483.648 | 160.211.074 | 71.729.942 | 88.481.132 | 20.735.784 | 59.365.530 | 20.741.288 | 59.368.472 |
32 | 4.294.967.296 | 309.492.085 | 138.524.467 | 170.967.618 | 40.012.295 | 114.725.008 | 40.017.284 | 114.737.498 |
33 | 8.589.934.592 | 598.548.563 | 267.832.656 | 330.715.907 | 77.295.792 | 221.969.405 | 77.304.749 | 221.978.617 |
34 | 17.179.869.184 | 1.158.869.489 | 518.450.710 | 640.418.779 | 149.503.108 | 429.914.367 | 149.508.265 | 429.943.749 |
35 | 34.359.738.368 | 2.246.020.767 | 1.004.591.541 | 1.241.429.226 | 289.479.067 | 833.518.753 | 289.486.002 | 833.536.945 |
36 | 68.719.476.736 | 4.357.319.671 | 1.948.576.996 | 2.408.742.675 | 561.088.625 | 1.617.537.403 | 561.095.661 | 1.617.597.982 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
5 | 32 | 4 | 3 | 1 | 1 | 1 | 0 | 2 |
6 | 64 | 13 | 8 | 5 | 2 | 6 | 1 | 4 |
7 | 128 | 29 | 15 | 14 | 4 | 11 | 4 | 10 |
8 | 256 | 69 | 35 | 34 | 15 | 24 | 12 | 18 |
9 | 512 | 168 | 88 | 80 | 33 | 52 | 36 | 47 |
10 | 1.024 | 386 | 217 | 169 | 73 | 112 | 89 | 112 |
11 | 2.048 | 841 | 450 | 391 | 180 | 236 | 195 | 230 |
12 | 4.096 | 1.789 | 934 | 855 | 396 | 487 | 415 | 491 |
13 | 8.192 | 3.748 | 1.900 | 1.848 | 852 | 1.016 | 859 | 1.021 |
14 | 16.384 | 7.865 | 4.037 | 3.828 | 1.798 | 2.100 | 1.822 | 2.145 |
15 | 32.768 | 16.321 | 8.415 | 7.906 | 3.756 | 4.341 | 3.824 | 4.400 |
16 | 65.536 | 33.625 | 17.078 | 16.547 | 7.864 | 8.972 | 7.849 | 8.940 |
17 | 131.072 | 68.762 | 35.032 | 33.730 | 16.172 | 18.286 | 16.211 | 18.093 |
18 | 262.144 | 140.101 | 71.327 | 68.774 | 33.216 | 36.715 | 33.413 | 36.757 |
19 | 524.288 | 285.346 | 144.873 | 140.473 | 67.991 | 74.483 | 68.251 | 74.621 |
20 | 1.048.576 | 579.283 | 293.961 | 285.322 | 138.451 | 150.893 | 138.969 | 150.970 |
21 | 2.097.152 | 1.175.211 | 595.308 | 579.903 | 282.489 | 305.089 | 282.495 | 305.138 |
22 | 4.194.304 | 2.379.335 | 1.204.149 | 1.175.186 | 572.770 | 616.387 | 573.520 | 616.658 |
23 | 8.388.608 | 4.810.805 | 2.433.093 | 2.377.712 | 1.160.921 | 1.243.083 | 1.162.330 | 1.244.471 |
24 | 16.777.216 | 9.714.171 | 4.910.984 | 4.803.187 | 2.349.591 | 2.506.543 | 2.350.295 | 2.507.742 |
25 | 33.554.432 | 19.596.172 | 9.903.433 | 9.692.739 | 4.749.305 | 5.047.007 | 4.748.424 | 5.051.436 |
26 | 67.108.864 | 39.503.310 | 19.951.286 | 19.552.024 | 9.591.855 | 10.160.427 | 9.587.395 | 10.163.633 |
27 | 134.217.728 | 79.576.265 | 40.172.623 | 39.403.642 | 19.346.965 | 20.446.096 | 19.343.697 | 20.439.507 |
28 | 268.435.456 | 160.203.958 | 80.846.949 | 79.357.009 | 38.995.011 | 41.112.763 | 38.989.560 | 41.106.624 |
29 | 536.870.912 | 322.337.714 | 162.600.650 | 159.737.064 | 78.540.465 | 82.623.947 | 78.539.217 | 82.634.085 |
30 | 1.073.741.824 | 648.266.049 | 326.898.296 | 321.367.753 | 158.113.856 | 166.006.871 | 158.123.464 | 166.021.858 |
31 | 2.147.483.648 | 1.303.206.730 | 656.921.913 | 646.284.817 | 318.175.957 | 333.414.826 | 318.194.835 | 333.421.112 |
32 | 4.294.967.296 | 2.618.836.038 | 1.319.715.375 | 1.299.120.663 | 639.995.639 | 669.433.577 | 639.986.540 | 669.420.282 |
33 | 8.589.934.592 | 5.260.959.730 | 2.650.440.731 | 2.610.518.999 | 1.286.740.854 | 1.343.772.463 | 1.286.706.105 | 1.343.740.308 |
34 | 17.179.869.184 | 10.565.491.880 | 5.321.344.514 | 5.244.147.366 | 2.586.139.352 | 2.696.646.738 | 2.586.099.912 | 2.696.605.878 |
35 | 34.359.738.368 | 21.212.774.270 | 10.681.183.660 | 10.531.590.610 | 5.196.044.288 | 5.410.518.011 | 5.195.986.750 | 5.410.225.221 |
36 | 68.719.476.736 | 42.579.301.043 | 21.434.848.497 | 21.144.452.546 | 10.436.757.608 | 10.853.080.748 | 10.436.651.894 | 10.852.810.793 |