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+24x-19
f(0)=19
f(1)=3
f(2)=11
f(3)=31
f(4)=1
f(5)=7
f(6)=23
f(7)=1
f(8)=79
f(9)=139
f(10)=107
f(11)=61
f(12)=59
f(13)=1
f(14)=1
f(15)=283
f(16)=1
f(17)=113
f(18)=67
f(19)=1
f(20)=41
f(21)=463
f(22)=331
f(23)=1
f(24)=103
f(25)=1
f(26)=1
f(27)=97
f(28)=479
f(29)=1
f(30)=1601
f(31)=281
f(32)=197
f(33)=1
f(34)=1
f(35)=1
f(36)=2141
f(37)=373
f(38)=1
f(39)=53
f(40)=1
f(41)=1
f(42)=2753
f(43)=1
f(44)=991
f(45)=1543
f(46)=1
f(47)=1
f(48)=491
f(49)=593
f(50)=409
f(51)=173
f(52)=1
f(53)=677
f(54)=599
f(55)=1
f(56)=1487
f(57)=1
f(58)=1579
f(59)=271
f(60)=5021
f(61)=1
f(62)=1
f(63)=2731
f(64)=1871
f(65)=1
f(66)=191
f(67)=1013
f(68)=1
f(69)=457
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=2411
f(75)=1
f(76)=1
f(77)=431
f(78)=7937
f(79)=1
f(80)=2767
f(81)=4243
f(82)=1
f(83)=211
f(84)=823
f(85)=1
f(86)=1049
f(87)=1
f(88)=1093
f(89)=239
f(90)=1
f(91)=1741
f(92)=1
f(93)=5431
f(94)=3691
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=6079
b) Substitution of the polynom
The polynom f(x)=x^2+24x-19 could be written as f(y)= y^2-163 with x=y-12
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
f'(x)>2x+23
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 | 16 | 41 | 0.570000 | 0.160000 | 0.410000 | 7.125000 | 4.000000 | 10.250000 |
3 | 1.000 | 629 | 93 | 536 | 0.629000 | 0.093000 | 0.536000 | 11.035088 | 5.812500 | 13.073171 |
4 | 10.000 | 6.491 | 682 | 5.809 | 0.649100 | 0.068200 | 0.580900 | 10.319555 | 7.333333 | 10.837687 |
5 | 100.000 | 66.032 | 5.095 | 60.937 | 0.660320 | 0.050950 | 0.609370 | 10.172854 | 7.470675 | 10.490102 |
6 | 1.000.000 | 666.168 | 41.260 | 624.908 | 0.666168 | 0.041260 | 0.624908 | 10.088563 | 8.098135 | 10.254985 |
7 | 10.000.000 | 6.699.712 | 347.624 | 6.352.088 | 0.669971 | 0.034762 | 0.635209 | 10.057091 | 8.425206 | 10.164837 |
8 | 100.000.000 | 67.281.971 | 3.007.839 | 64.274.132 | 0.672820 | 0.030078 | 0.642741 | 10.042517 | 8.652564 | 10.118584 |
9 | 1.000.000.000 | 675.019.044 | 26.509.831 | 648.509.213 | 0.675019 | 0.026510 | 0.648509 | 10.032689 | 8.813581 | 10.089739 |
10 | 10.000.000.000 | 6.767.911.493 | 237.031.493 | 6.530.880.000 | 0.676791 | 0.023703 | 0.653088 | 10.026252 | 8.941267 | 10.070605 |
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 | 6 | 3 | 3 | 0.750000 | 0.375000 | 0.375000 | 1.500000 | 1.000000 | 3.000000 |
4 | 16 | 11 | 5 | 6 | 0.687500 | 0.312500 | 0.375000 | 1.833333 | 1.666667 | 2.000000 |
5 | 32 | 22 | 7 | 15 | 0.687500 | 0.218750 | 0.468750 | 2.000000 | 1.400000 | 2.500000 |
6 | 64 | 39 | 12 | 27 | 0.609375 | 0.187500 | 0.421875 | 1.772727 | 1.714286 | 1.800000 |
7 | 128 | 75 | 17 | 58 | 0.585938 | 0.132812 | 0.453125 | 1.923077 | 1.416667 | 2.148148 |
8 | 256 | 160 | 28 | 132 | 0.625000 | 0.109375 | 0.515625 | 2.133333 | 1.647059 | 2.275862 |
9 | 512 | 320 | 54 | 266 | 0.625000 | 0.105469 | 0.519531 | 2.000000 | 1.928571 | 2.015152 |
10 | 1.024 | 646 | 93 | 553 | 0.630859 | 0.090820 | 0.540039 | 2.018750 | 1.722222 | 2.078947 |
11 | 2.048 | 1.307 | 179 | 1.128 | 0.638184 | 0.087402 | 0.550781 | 2.023220 | 1.924731 | 2.039783 |
12 | 4.096 | 2.649 | 320 | 2.329 | 0.646729 | 0.078125 | 0.568604 | 2.026779 | 1.787709 | 2.064716 |
13 | 8.192 | 5.307 | 577 | 4.730 | 0.647827 | 0.070435 | 0.577393 | 2.003397 | 1.803125 | 2.030915 |
14 | 16.384 | 10.676 | 1.022 | 9.654 | 0.651611 | 0.062378 | 0.589233 | 2.011683 | 1.771230 | 2.041015 |
15 | 32.768 | 21.479 | 1.867 | 19.612 | 0.655487 | 0.056976 | 0.598511 | 2.011896 | 1.826810 | 2.031490 |
16 | 65.536 | 43.225 | 3.486 | 39.739 | 0.659561 | 0.053192 | 0.606369 | 2.012431 | 1.867167 | 2.026259 |
17 | 131.072 | 86.670 | 6.450 | 80.220 | 0.661240 | 0.049210 | 0.612030 | 2.005090 | 1.850258 | 2.018672 |
18 | 262.144 | 173.825 | 12.203 | 161.622 | 0.663090 | 0.046551 | 0.616539 | 2.005596 | 1.891938 | 2.014735 |
19 | 524.288 | 348.600 | 22.864 | 325.736 | 0.664902 | 0.043610 | 0.621292 | 2.005465 | 1.873638 | 2.015419 |
20 | 1.048.576 | 698.522 | 43.154 | 655.368 | 0.666162 | 0.041155 | 0.625008 | 2.003792 | 1.887421 | 2.011961 |
21 | 2.097.152 | 1.400.109 | 81.531 | 1.318.578 | 0.667624 | 0.038877 | 0.628747 | 2.004388 | 1.889303 | 2.011966 |
22 | 4.194.304 | 2.804.726 | 154.861 | 2.649.865 | 0.668699 | 0.036922 | 0.631777 | 2.003220 | 1.899413 | 2.009638 |
23 | 8.388.608 | 5.618.107 | 295.208 | 5.322.899 | 0.669731 | 0.035192 | 0.634539 | 2.003086 | 1.906277 | 2.008744 |
24 | 16.777.216 | 11.252.797 | 562.998 | 10.689.799 | 0.670719 | 0.033557 | 0.637162 | 2.002952 | 1.907123 | 2.008266 |
25 | 33.554.432 | 22.534.179 | 1.077.625 | 21.456.554 | 0.671571 | 0.032116 | 0.639455 | 2.002540 | 1.914083 | 2.007199 |
26 | 67.108.864 | 45.121.991 | 2.066.612 | 43.055.379 | 0.672370 | 0.030795 | 0.641575 | 2.002380 | 1.917747 | 2.006631 |
27 | 134.217.728 | 90.345.737 | 3.968.922 | 86.376.815 | 0.673128 | 0.029571 | 0.643557 | 2.002255 | 1.920497 | 2.006179 |
28 | 268.435.456 | 180.877.303 | 7.633.466 | 173.243.837 | 0.673820 | 0.028437 | 0.645384 | 2.002057 | 1.923310 | 2.005675 |
29 | 536.870.912 | 362.103.185 | 14.703.419 | 347.399.766 | 0.674470 | 0.027387 | 0.647083 | 2.001927 | 1.926179 | 2.005265 |
30 | 1.073.741.824 | 724.859.205 | 28.361.236 | 696.497.969 | 0.675078 | 0.026413 | 0.648664 | 2.001803 | 1.928887 | 2.004889 |
31 | 2.147.483.648 | 1.450.939.653 | 54.772.122 | 1.396.167.531 | 0.675646 | 0.025505 | 0.650141 | 2.001685 | 1.931232 | 2.004554 |
32 | 4.294.967.296 | 2.904.161.904 | 105.918.794 | 2.798.243.110 | 0.676178 | 0.024661 | 0.651517 | 2.001573 | 1.933809 | 2.004231 |
33 | 8.589.934.592 | 5.812.669.917 | 205.042.824 | 5.607.627.093 | 0.676684 | 0.023870 | 0.652814 | 2.001497 | 1.935849 | 2.003981 |
34 | 17.179.869.184 | 11.633.502.821 | 397.332.779 | 11.236.170.042 | 0.677159 | 0.023128 | 0.654031 | 2.001404 | 1.937804 | 2.003730 |
35 | 34.359.738.368 | 23.282.389.770 | 770.716.644 | 22.511.673.126 | 0.677607 | 0.022431 | 0.655176 | 2.001322 | 1.939726 | 2.003501 |
36 | 68.719.476.736 | 46.593.769.416 | 1.496.331.947 | 45.097.437.469 | 0.678029 | 0.021774 | 0.656254 | 2.001245 | 1.941481 | 2.003291 |
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 | 0 | 0 | 2 | 0 | 0 |
2 | 4 | 3 | 2 | 0 | 0 | 2 | 0 | 1 |
3 | 8 | 3 | 2 | 0 | 0 | 2 | 0 | 1 |
4 | 16 | 5 | 4 | 0 | 0 | 4 | 0 | 1 |
5 | 32 | 7 | 5 | 1 | 1 | 4 | 0 | 2 |
6 | 64 | 12 | 7 | 4 | 2 | 5 | 2 | 3 |
7 | 128 | 17 | 11 | 5 | 3 | 7 | 2 | 5 |
8 | 256 | 28 | 16 | 11 | 7 | 11 | 4 | 6 |
9 | 512 | 54 | 30 | 23 | 12 | 19 | 11 | 12 |
10 | 1.024 | 93 | 46 | 46 | 23 | 24 | 23 | 23 |
11 | 2.048 | 179 | 86 | 92 | 50 | 41 | 42 | 46 |
12 | 4.096 | 320 | 159 | 160 | 84 | 77 | 76 | 83 |
13 | 8.192 | 577 | 289 | 287 | 147 | 140 | 140 | 150 |
14 | 16.384 | 1.022 | 520 | 501 | 261 | 261 | 240 | 260 |
15 | 32.768 | 1.867 | 966 | 900 | 474 | 482 | 426 | 485 |
16 | 65.536 | 3.486 | 1.791 | 1.694 | 857 | 892 | 837 | 900 |
17 | 131.072 | 6.450 | 3.293 | 3.156 | 1.606 | 1.632 | 1.550 | 1.662 |
18 | 262.144 | 12.203 | 6.198 | 6.004 | 3.013 | 3.094 | 2.991 | 3.105 |
19 | 524.288 | 22.864 | 11.561 | 11.302 | 5.628 | 5.763 | 5.674 | 5.799 |
20 | 1.048.576 | 43.154 | 21.812 | 21.341 | 10.623 | 10.879 | 10.718 | 10.934 |
21 | 2.097.152 | 81.531 | 41.200 | 40.330 | 20.112 | 20.612 | 20.218 | 20.589 |
22 | 4.194.304 | 154.861 | 78.473 | 76.387 | 38.159 | 39.254 | 38.228 | 39.220 |
23 | 8.388.608 | 295.208 | 149.367 | 145.840 | 72.919 | 74.649 | 72.921 | 74.719 |
24 | 16.777.216 | 562.998 | 284.744 | 278.253 | 138.963 | 142.463 | 139.290 | 142.282 |
25 | 33.554.432 | 1.077.625 | 544.861 | 532.763 | 266.399 | 272.261 | 266.364 | 272.601 |
26 | 67.108.864 | 2.066.612 | 1.043.878 | 1.022.733 | 511.573 | 521.328 | 511.160 | 522.551 |
27 | 134.217.728 | 3.968.922 | 2.003.644 | 1.965.277 | 983.006 | 1.001.277 | 982.271 | 1.002.368 |
28 | 268.435.456 | 7.633.466 | 3.852.145 | 3.781.320 | 1.891.198 | 1.925.443 | 1.890.122 | 1.926.703 |
29 | 536.870.912 | 14.703.419 | 7.419.094 | 7.284.324 | 3.642.027 | 3.708.846 | 3.642.297 | 3.710.249 |
30 | 1.073.741.824 | 28.361.236 | 14.303.701 | 14.057.534 | 7.029.174 | 7.150.780 | 7.028.360 | 7.152.922 |
31 | 2.147.483.648 | 54.772.122 | 27.615.978 | 27.156.143 | 13.577.028 | 13.805.708 | 13.579.115 | 13.810.271 |
32 | 4.294.967.296 | 105.918.794 | 53.394.202 | 52.524.591 | 26.265.780 | 26.693.958 | 26.258.811 | 26.700.245 |
33 | 8.589.934.592 | 205.042.824 | 103.337.308 | 101.705.515 | 50.856.444 | 51.665.333 | 50.849.071 | 51.671.976 |
34 | 17.179.869.184 | 397.332.779 | 200.207.451 | 197.125.327 | 98.565.884 | 100.097.789 | 98.559.443 | 100.109.663 |
35 | 34.359.738.368 | 770.716.644 | 388.257.603 | 382.459.040 | 191.223.747 | 194.124.169 | 191.235.293 | 194.133.435 |
36 | 68.719.476.736 | 1.496.331.947 | 753.649.590 | 742.682.356 | 371.335.386 | 376.819.443 | 371.346.970 | 376.830.148 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 3 | 1 | 2 | 0 | 1 | 0 | 2 |
4 | 16 | 6 | 2 | 4 | 0 | 3 | 1 | 2 |
5 | 32 | 15 | 6 | 9 | 4 | 5 | 2 | 4 |
6 | 64 | 27 | 11 | 16 | 6 | 7 | 5 | 9 |
7 | 128 | 58 | 25 | 33 | 10 | 15 | 15 | 18 |
8 | 256 | 132 | 65 | 67 | 28 | 33 | 38 | 33 |
9 | 512 | 266 | 118 | 148 | 57 | 72 | 71 | 66 |
10 | 1.024 | 553 | 266 | 287 | 123 | 149 | 142 | 139 |
11 | 2.048 | 1.128 | 539 | 589 | 274 | 277 | 298 | 279 |
12 | 4.096 | 2.329 | 1.135 | 1.194 | 559 | 554 | 621 | 595 |
13 | 8.192 | 4.730 | 2.361 | 2.369 | 1.178 | 1.136 | 1.227 | 1.189 |
14 | 16.384 | 9.654 | 4.799 | 4.855 | 2.390 | 2.386 | 2.483 | 2.395 |
15 | 32.768 | 19.612 | 9.813 | 9.799 | 4.869 | 4.919 | 5.024 | 4.800 |
16 | 65.536 | 39.739 | 19.928 | 19.811 | 9.845 | 9.966 | 10.102 | 9.826 |
17 | 131.072 | 80.220 | 40.147 | 40.073 | 19.935 | 20.110 | 20.216 | 19.959 |
18 | 262.144 | 161.622 | 80.796 | 80.826 | 40.330 | 40.440 | 40.568 | 40.284 |
19 | 524.288 | 325.736 | 162.529 | 163.207 | 81.301 | 81.407 | 81.554 | 81.474 |
20 | 1.048.576 | 655.368 | 327.230 | 328.138 | 164.155 | 163.710 | 164.240 | 163.263 |
21 | 2.097.152 | 1.318.578 | 659.088 | 659.490 | 329.937 | 329.566 | 329.879 | 329.196 |
22 | 4.194.304 | 2.649.865 | 1.325.355 | 1.324.510 | 662.583 | 661.973 | 662.751 | 662.558 |
23 | 8.388.608 | 5.322.899 | 2.661.552 | 2.661.347 | 1.330.730 | 1.330.877 | 1.330.617 | 1.330.675 |
24 | 16.777.216 | 10.689.799 | 5.347.568 | 5.342.231 | 2.672.328 | 2.672.241 | 2.673.529 | 2.671.701 |
25 | 33.554.432 | 21.456.554 | 10.730.039 | 10.726.515 | 5.365.902 | 5.361.290 | 5.369.854 | 5.359.508 |
26 | 67.108.864 | 43.055.379 | 21.531.697 | 21.523.682 | 10.767.204 | 10.759.201 | 10.772.223 | 10.756.751 |
27 | 134.217.728 | 86.376.815 | 43.194.675 | 43.182.140 | 21.602.998 | 21.587.348 | 21.606.618 | 21.579.851 |
28 | 268.435.456 | 173.243.837 | 86.632.271 | 86.611.566 | 43.327.674 | 43.296.017 | 43.329.759 | 43.290.387 |
29 | 536.870.912 | 347.399.766 | 173.726.496 | 173.673.270 | 86.884.157 | 86.802.558 | 86.893.330 | 86.819.721 |
30 | 1.073.741.824 | 696.497.969 | 348.294.334 | 348.203.635 | 174.191.297 | 174.046.902 | 174.198.958 | 174.060.812 |
31 | 2.147.483.648 | 1.396.167.531 | 698.166.301 | 698.001.230 | 349.163.042 | 348.918.190 | 349.169.860 | 348.916.439 |
32 | 4.294.967.296 | 2.798.243.110 | 1.399.240.159 | 1.399.002.951 | 699.773.069 | 699.338.205 | 699.792.153 | 699.339.683 |
33 | 8.589.934.592 | 5.607.627.093 | 2.803.980.530 | 2.803.646.563 | 1.402.332.954 | 1.401.518.180 | 1.402.319.547 | 1.401.456.412 |
34 | 17.179.869.184 | 11.236.170.042 | 5.618.445.608 | 5.617.724.434 | 2.809.841.596 | 2.808.284.748 | 2.809.832.940 | 2.808.210.758 |
35 | 34.359.738.368 | 22.511.673.126 | 11.256.468.467 | 11.255.204.659 | 5.629.390.487 | 5.626.546.531 | 5.629.363.649 | 5.626.372.459 |
36 | 68.719.476.736 | 45.097.437.469 | 22.549.970.744 | 22.547.466.725 | 11.277.105.800 | 11.271.711.337 | 11.277.133.506 | 11.271.486.826 |