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+25x-97
f(0)=97
f(1)=71
f(2)=43
f(3)=13
f(4)=19
f(5)=53
f(6)=89
f(7)=127
f(8)=167
f(9)=11
f(10)=23
f(11)=1
f(12)=347
f(13)=397
f(14)=449
f(15)=503
f(16)=1
f(17)=617
f(18)=677
f(19)=739
f(20)=73
f(21)=79
f(22)=937
f(23)=1
f(24)=83
f(25)=1153
f(26)=1229
f(27)=1307
f(28)=1
f(29)=113
f(30)=1553
f(31)=149
f(32)=157
f(33)=1
f(34)=1
f(35)=2003
f(36)=2099
f(37)=1
f(38)=2297
f(39)=2399
f(40)=2503
f(41)=2609
f(42)=1
f(43)=257
f(44)=2939
f(45)=1
f(46)=3169
f(47)=173
f(48)=3407
f(49)=3529
f(50)=281
f(51)=3779
f(52)=3907
f(53)=367
f(54)=379
f(55)=331
f(56)=193
f(57)=199
f(58)=1
f(59)=1
f(60)=5003
f(61)=271
f(62)=5297
f(63)=419
f(64)=509
f(65)=523
f(66)=311
f(67)=6067
f(68)=479
f(69)=6389
f(70)=6553
f(71)=6719
f(72)=1
f(73)=7057
f(74)=7229
f(75)=673
f(76)=1
f(77)=7757
f(78)=7937
f(79)=353
f(80)=1
f(81)=653
f(82)=8677
f(83)=8867
f(84)=9059
f(85)=487
f(86)=859
f(87)=877
f(88)=229
f(89)=773
f(90)=10253
f(91)=10459
f(92)=10667
f(93)=1
f(94)=853
f(95)=1
f(96)=11519
f(97)=1
f(98)=1087
f(99)=641
b) Substitution of the polynom
The polynom f(x)=x^2+25x-97 could be written as f(y)= y^2-253.25 with x=y-12.5
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+12.5
f'(x)>2x+24
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 | 9 | 1 | 1.000000 | 0.900000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 82 | 50 | 32 | 0.820000 | 0.500000 | 0.320000 | 8.200000 | 5.555555 | 32.000000 |
3 | 1.000 | 744 | 326 | 418 | 0.744000 | 0.326000 | 0.418000 | 9.073171 | 6.520000 | 13.062500 |
4 | 10.000 | 7.339 | 2.282 | 5.057 | 0.733900 | 0.228200 | 0.505700 | 9.864247 | 7.000000 | 12.098086 |
5 | 100.000 | 72.690 | 17.535 | 55.155 | 0.726900 | 0.175350 | 0.551550 | 9.904619 | 7.684049 | 10.906664 |
6 | 1.000.000 | 721.673 | 143.395 | 578.278 | 0.721673 | 0.143395 | 0.578278 | 9.928092 | 8.177645 | 10.484598 |
7 | 10.000.000 | 7.172.758 | 1.215.668 | 5.957.090 | 0.717276 | 0.121567 | 0.595709 | 9.939070 | 8.477757 | 10.301430 |
8 | 100.000.000 | 71.396.374 | 10.542.555 | 60.853.819 | 0.713964 | 0.105426 | 0.608538 | 9.953825 | 8.672232 | 10.215361 |
9 | 1.000.000.000 | 711.548.365 | 93.040.016 | 618.508.349 | 0.711548 | 0.093040 | 0.618508 | 9.966169 | 8.825187 | 10.163837 |
10 | 10.000.000.000 | 7.096.118.402 | 832.685.429 | 6.263.432.973 | 0.709612 | 0.083269 | 0.626343 | 9.972784 | 8.949756 | 10.126676 |
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 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 13 | 1 | 0.875000 | 0.812500 | 0.062500 | 1.555556 | 1.444444 | inf |
5 | 32 | 28 | 21 | 7 | 0.875000 | 0.656250 | 0.218750 | 2.000000 | 1.615385 | 7.000000 |
6 | 64 | 53 | 35 | 18 | 0.828125 | 0.546875 | 0.281250 | 1.892857 | 1.666667 | 2.571429 |
7 | 128 | 103 | 59 | 44 | 0.804688 | 0.460938 | 0.343750 | 1.943396 | 1.685714 | 2.444444 |
8 | 256 | 197 | 102 | 95 | 0.769531 | 0.398438 | 0.371094 | 1.912621 | 1.728814 | 2.159091 |
9 | 512 | 385 | 182 | 203 | 0.751953 | 0.355469 | 0.396484 | 1.954315 | 1.784314 | 2.136842 |
10 | 1.024 | 762 | 338 | 424 | 0.744141 | 0.330078 | 0.414062 | 1.979221 | 1.857143 | 2.088670 |
11 | 2.048 | 1.510 | 595 | 915 | 0.737305 | 0.290527 | 0.446777 | 1.981627 | 1.760355 | 2.158019 |
12 | 4.096 | 3.021 | 1.057 | 1.964 | 0.737549 | 0.258057 | 0.479492 | 2.000662 | 1.776471 | 2.146448 |
13 | 8.192 | 6.010 | 1.903 | 4.107 | 0.733643 | 0.232300 | 0.501343 | 1.989408 | 1.800378 | 2.091141 |
14 | 16.384 | 11.978 | 3.512 | 8.466 | 0.731079 | 0.214355 | 0.516724 | 1.993012 | 1.845507 | 2.061359 |
15 | 32.768 | 23.908 | 6.437 | 17.471 | 0.729614 | 0.196442 | 0.533173 | 1.995993 | 1.832859 | 2.063666 |
16 | 65.536 | 47.705 | 11.969 | 35.736 | 0.727921 | 0.182632 | 0.545288 | 1.995357 | 1.859407 | 2.045447 |
17 | 131.072 | 95.211 | 22.405 | 72.806 | 0.726402 | 0.170937 | 0.555466 | 1.995829 | 1.871919 | 2.037329 |
18 | 262.144 | 190.015 | 42.003 | 148.012 | 0.724850 | 0.160229 | 0.564621 | 1.995725 | 1.874715 | 2.032964 |
19 | 524.288 | 379.168 | 79.223 | 299.945 | 0.723206 | 0.151106 | 0.572100 | 1.995463 | 1.886127 | 2.026491 |
20 | 1.048.576 | 756.623 | 149.738 | 606.885 | 0.721572 | 0.142801 | 0.578771 | 1.995482 | 1.890082 | 2.023321 |
21 | 2.097.152 | 1.510.150 | 284.693 | 1.225.457 | 0.720096 | 0.135752 | 0.584343 | 1.995908 | 1.901274 | 2.019257 |
22 | 4.194.304 | 3.014.839 | 541.226 | 2.473.613 | 0.718794 | 0.129038 | 0.589755 | 1.996384 | 1.901086 | 2.018523 |
23 | 8.388.608 | 6.019.387 | 1.031.853 | 4.987.534 | 0.717567 | 0.123006 | 0.594560 | 1.996587 | 1.906510 | 2.016295 |
24 | 16.777.216 | 12.020.142 | 1.971.048 | 10.049.094 | 0.716456 | 0.117484 | 0.598973 | 1.996905 | 1.910202 | 2.014842 |
25 | 33.554.432 | 24.005.425 | 3.775.589 | 20.229.836 | 0.715417 | 0.112521 | 0.602896 | 1.997100 | 1.915524 | 2.013100 |
26 | 67.108.864 | 47.946.975 | 7.241.284 | 40.705.691 | 0.714466 | 0.107904 | 0.606562 | 1.997339 | 1.917922 | 2.012161 |
27 | 134.217.728 | 95.782.051 | 13.913.293 | 81.868.758 | 0.713632 | 0.103662 | 0.609970 | 1.997666 | 1.921385 | 2.011236 |
28 | 268.435.456 | 191.356.629 | 26.769.884 | 164.586.745 | 0.712859 | 0.099726 | 0.613133 | 1.997834 | 1.924051 | 2.010373 |
29 | 536.870.912 | 382.332.325 | 51.586.599 | 330.745.726 | 0.712149 | 0.096088 | 0.616062 | 1.998009 | 1.927039 | 2.009552 |
30 | 1.073.741.824 | 763.945.144 | 99.538.909 | 664.406.235 | 0.711479 | 0.092703 | 0.618777 | 1.998118 | 1.929550 | 2.008813 |
31 | 2.147.483.648 | 1.526.558.216 | 192.300.167 | 1.334.258.049 | 0.710859 | 0.089547 | 0.621312 | 1.998256 | 1.931909 | 2.008196 |
32 | 4.294.967.296 | 3.050.598.389 | 371.967.080 | 2.678.631.309 | 0.710273 | 0.086605 | 0.623667 | 1.998351 | 1.934305 | 2.007581 |
33 | 8.589.934.592 | 6.096.519.806 | 720.255.992 | 5.376.263.814 | 0.709728 | 0.083849 | 0.625879 | 1.998467 | 1.936343 | 2.007093 |
34 | 17.179.869.184 | 12.184.215.465 | 1.396.086.009 | 10.788.129.456 | 0.709215 | 0.081263 | 0.627952 | 1.998553 | 1.938319 | 2.006622 |
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 | 2 | 1 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 4 | 1 | 1 | 2 | 1 | 1 |
3 | 8 | 9 | 5 | 4 | 2 | 2 | 2 | 3 |
4 | 16 | 13 | 6 | 7 | 3 | 3 | 3 | 4 |
5 | 32 | 21 | 9 | 12 | 7 | 5 | 5 | 4 |
6 | 64 | 35 | 13 | 22 | 12 | 11 | 5 | 7 |
7 | 128 | 59 | 22 | 37 | 19 | 17 | 13 | 10 |
8 | 256 | 102 | 34 | 68 | 27 | 28 | 27 | 20 |
9 | 512 | 182 | 62 | 120 | 42 | 51 | 51 | 38 |
10 | 1.024 | 338 | 119 | 219 | 81 | 85 | 91 | 81 |
11 | 2.048 | 595 | 205 | 390 | 143 | 144 | 154 | 154 |
12 | 4.096 | 1.057 | 349 | 708 | 256 | 260 | 271 | 270 |
13 | 8.192 | 1.903 | 641 | 1.262 | 476 | 469 | 476 | 482 |
14 | 16.384 | 3.512 | 1.187 | 2.325 | 896 | 873 | 871 | 872 |
15 | 32.768 | 6.437 | 2.169 | 4.268 | 1.650 | 1.602 | 1.596 | 1.589 |
16 | 65.536 | 11.969 | 3.977 | 7.992 | 3.043 | 2.983 | 2.975 | 2.968 |
17 | 131.072 | 22.405 | 7.431 | 14.974 | 5.707 | 5.623 | 5.536 | 5.539 |
18 | 262.144 | 42.003 | 13.968 | 28.035 | 10.652 | 10.463 | 10.388 | 10.500 |
19 | 524.288 | 79.223 | 26.346 | 52.877 | 19.888 | 19.796 | 19.670 | 19.869 |
20 | 1.048.576 | 149.738 | 49.787 | 99.951 | 37.574 | 37.381 | 37.372 | 37.411 |
21 | 2.097.152 | 284.693 | 94.628 | 190.065 | 71.386 | 71.003 | 71.110 | 71.194 |
22 | 4.194.304 | 541.226 | 180.003 | 361.223 | 135.605 | 135.109 | 135.026 | 135.486 |
23 | 8.388.608 | 1.031.853 | 343.588 | 688.265 | 258.527 | 257.770 | 257.608 | 257.948 |
24 | 16.777.216 | 1.971.048 | 656.867 | 1.314.181 | 493.198 | 492.367 | 492.553 | 492.930 |
25 | 33.554.432 | 3.775.589 | 1.258.606 | 2.516.983 | 943.904 | 943.392 | 943.668 | 944.625 |
26 | 67.108.864 | 7.241.284 | 2.414.929 | 4.826.355 | 1.809.875 | 1.809.708 | 1.810.636 | 1.811.065 |
27 | 134.217.728 | 13.913.293 | 4.641.211 | 9.272.082 | 3.477.252 | 3.478.978 | 3.479.055 | 3.478.008 |
28 | 268.435.456 | 26.769.884 | 8.927.586 | 17.842.298 | 6.692.030 | 6.691.469 | 6.694.050 | 6.692.335 |
29 | 536.870.912 | 51.586.599 | 17.196.390 | 34.390.209 | 12.894.605 | 12.896.745 | 12.899.560 | 12.895.689 |
30 | 1.073.741.824 | 99.538.909 | 33.179.952 | 66.358.957 | 24.886.429 | 24.885.866 | 24.887.539 | 24.879.075 |
31 | 2.147.483.648 | 192.300.167 | 64.099.484 | 128.200.683 | 48.075.676 | 48.077.190 | 48.080.183 | 48.067.118 |
32 | 4.294.967.296 | 371.967.080 | 123.991.889 | 247.975.191 | 92.996.519 | 92.993.333 | 92.989.849 | 92.987.379 |
33 | 8.589.934.592 | 720.255.992 | 240.089.996 | 480.165.996 | 180.069.817 | 180.062.327 | 180.065.491 | 180.058.357 |
34 | 17.179.869.184 | 1.396.086.009 | 465.387.412 | 930.698.597 | 349.028.903 | 349.032.020 | 349.028.654 | 348.996.432 |
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 | 7 | 3 | 4 | 2 | 1 | 2 | 2 |
6 | 64 | 18 | 9 | 9 | 5 | 4 | 4 | 5 |
7 | 128 | 44 | 24 | 20 | 11 | 10 | 11 | 12 |
8 | 256 | 95 | 49 | 46 | 24 | 21 | 26 | 24 |
9 | 512 | 203 | 92 | 111 | 50 | 52 | 53 | 48 |
10 | 1.024 | 424 | 204 | 220 | 104 | 102 | 112 | 106 |
11 | 2.048 | 915 | 445 | 470 | 213 | 218 | 241 | 243 |
12 | 4.096 | 1.964 | 985 | 979 | 477 | 478 | 529 | 480 |
13 | 8.192 | 4.107 | 2.033 | 2.074 | 1.015 | 1.035 | 1.051 | 1.006 |
14 | 16.384 | 8.466 | 4.206 | 4.260 | 2.061 | 2.137 | 2.152 | 2.116 |
15 | 32.768 | 17.471 | 8.717 | 8.754 | 4.318 | 4.440 | 4.299 | 4.414 |
16 | 65.536 | 35.736 | 17.983 | 17.753 | 9.009 | 8.978 | 8.830 | 8.919 |
17 | 131.072 | 72.806 | 36.539 | 36.267 | 18.260 | 18.169 | 18.158 | 18.219 |
18 | 262.144 | 148.012 | 74.420 | 73.592 | 36.890 | 36.994 | 36.953 | 37.175 |
19 | 524.288 | 299.945 | 150.407 | 149.538 | 74.710 | 75.331 | 74.638 | 75.266 |
20 | 1.048.576 | 606.885 | 304.340 | 302.545 | 151.425 | 151.948 | 151.701 | 151.811 |
21 | 2.097.152 | 1.225.457 | 613.816 | 611.641 | 306.352 | 306.255 | 306.341 | 306.509 |
22 | 4.194.304 | 2.473.613 | 1.238.485 | 1.235.128 | 618.384 | 618.243 | 618.193 | 618.793 |
23 | 8.388.608 | 4.987.534 | 2.496.636 | 2.490.898 | 1.246.096 | 1.247.174 | 1.247.468 | 1.246.796 |
24 | 16.777.216 | 10.049.094 | 5.029.744 | 5.019.350 | 2.511.847 | 2.512.550 | 2.513.737 | 2.510.960 |
25 | 33.554.432 | 20.229.836 | 10.127.294 | 10.102.542 | 5.055.178 | 5.057.940 | 5.061.208 | 5.055.510 |
26 | 67.108.864 | 40.705.691 | 20.380.479 | 20.325.212 | 10.174.691 | 10.175.329 | 10.182.294 | 10.173.377 |
27 | 134.217.728 | 81.868.758 | 40.985.167 | 40.883.591 | 20.468.699 | 20.465.622 | 20.472.016 | 20.462.421 |
28 | 268.435.456 | 164.586.745 | 82.395.442 | 82.191.303 | 41.140.611 | 41.150.559 | 41.152.191 | 41.143.384 |
29 | 536.870.912 | 330.745.726 | 165.561.718 | 165.184.008 | 82.673.998 | 82.690.090 | 82.698.413 | 82.683.225 |
30 | 1.073.741.824 | 664.406.235 | 332.578.460 | 331.827.775 | 166.091.529 | 166.102.409 | 166.103.922 | 166.108.375 |
31 | 2.147.483.648 | 1.334.258.049 | 667.836.835 | 666.421.214 | 333.542.211 | 333.574.121 | 333.570.352 | 333.571.365 |
32 | 4.294.967.296 | 2.678.631.309 | 1.340.642.601 | 1.337.988.708 | 669.628.962 | 669.667.591 | 669.661.405 | 669.673.351 |
33 | 8.589.934.592 | 5.376.263.814 | 2.690.692.762 | 2.685.571.052 | 1.344.027.103 | 1.344.061.897 | 1.344.066.452 | 1.344.108.362 |
34 | 17.179.869.184 | 10.788.129.456 | 5.398.934.533 | 5.389.194.923 | 2.696.990.456 | 2.697.022.776 | 2.697.039.240 | 2.697.076.984 |