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-40x-7
f(0)=7
f(1)=23
f(2)=83
f(3)=59
f(4)=151
f(5)=13
f(6)=211
f(7)=17
f(8)=263
f(9)=11
f(10)=307
f(11)=163
f(12)=1
f(13)=179
f(14)=53
f(15)=191
f(16)=1
f(17)=199
f(18)=31
f(19)=29
f(20)=37
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=61
f(44)=1
f(45)=109
f(46)=269
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=277
f(52)=617
f(53)=1
f(54)=107
f(55)=409
f(56)=127
f(57)=1
f(58)=1
f(59)=557
f(60)=1193
f(61)=1
f(62)=1
f(63)=103
f(64)=139
f(65)=809
f(66)=1709
f(67)=1
f(68)=271
f(69)=997
f(70)=1
f(71)=1097
f(72)=2297
f(73)=1201
f(74)=193
f(75)=1
f(76)=2729
f(77)=1
f(78)=2957
f(79)=1
f(80)=1
f(81)=1657
f(82)=491
f(83)=137
f(84)=1
f(85)=1
f(86)=359
f(87)=157
f(88)=4217
f(89)=311
f(90)=4493
f(91)=331
f(92)=281
f(93)=1
f(94)=1
f(95)=2609
f(96)=1
f(97)=251
f(98)=811
f(99)=2917
b) Substitution of the polynom
The polynom f(x)=x^2-40x-7 could be written as f(y)= y^2-407 with x=y+20
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-20
f'(x)>2x-41 with x > 20
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 | 11 | 6 | 5 | 1.100000 | 0.600000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 49 | 15 | 34 | 0.490000 | 0.150000 | 0.490000 | 4.454545 | 2.500000 | 6.800000 |
3 | 1.000 | 641 | 119 | 522 | 0.641000 | 0.119000 | 0.641000 | 13.081633 | 7.933333 | 15.352942 |
4 | 10.000 | 6.830 | 788 | 6.042 | 0.683000 | 0.078800 | 0.683000 | 10.655226 | 6.621849 | 11.574713 |
5 | 100.000 | 68.609 | 6.394 | 62.215 | 0.686090 | 0.063940 | 0.686090 | 10.045241 | 8.114213 | 10.297087 |
6 | 1.000.000 | 687.341 | 52.168 | 635.173 | 0.687341 | 0.052168 | 0.687341 | 10.018233 | 8.158899 | 10.209323 |
7 | 10.000.000 | 6.881.393 | 440.117 | 6.441.276 | 0.688139 | 0.044012 | 0.688139 | 10.011614 | 8.436532 | 10.140979 |
8 | 100.000.000 | 68.869.887 | 3.816.324 | 65.053.563 | 0.688699 | 0.038163 | 0.688699 | 10.008132 | 8.671158 | 10.099484 |
9 | 1.000.000.000 | 689.110.065 | 33.673.552 | 655.436.513 | 0.689110 | 0.033674 | 0.689110 | 10.005971 | 8.823557 | 10.075336 |
10 | 10.000.000.000 | 6.894.545.428 | 301.306.498 | 6.593.238.930 | 0.689455 | 0.030131 | 0.689455 | 10.004998 | 8.947868 | 10.059309 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 1.666667 | 1.200000 | 2.250000 |
5 | 32 | 17 | 6 | 11 | 0.531250 | 0.187500 | 0.343750 | 1.133333 | 1.000000 | 1.222222 |
6 | 64 | 26 | 9 | 17 | 0.406250 | 0.140625 | 0.265625 | 1.529412 | 1.500000 | 1.545455 |
7 | 128 | 66 | 18 | 48 | 0.515625 | 0.140625 | 0.375000 | 2.538461 | 2.000000 | 2.823529 |
8 | 256 | 149 | 36 | 113 | 0.582031 | 0.140625 | 0.441406 | 2.257576 | 2.000000 | 2.354167 |
9 | 512 | 314 | 67 | 247 | 0.613281 | 0.130859 | 0.482422 | 2.107383 | 1.861111 | 2.185841 |
10 | 1.024 | 655 | 120 | 535 | 0.639648 | 0.117188 | 0.522461 | 2.085987 | 1.791045 | 2.165992 |
11 | 2.048 | 1.362 | 212 | 1.150 | 0.665039 | 0.103516 | 0.561523 | 2.079389 | 1.766667 | 2.149533 |
12 | 4.096 | 2.759 | 367 | 2.392 | 0.673584 | 0.089600 | 0.583984 | 2.025697 | 1.731132 | 2.080000 |
13 | 8.192 | 5.582 | 663 | 4.919 | 0.681396 | 0.080933 | 0.600464 | 2.023197 | 1.806540 | 2.056438 |
14 | 16.384 | 11.191 | 1.233 | 9.958 | 0.683044 | 0.075256 | 0.607788 | 2.004837 | 1.859728 | 2.024395 |
15 | 32.768 | 22.472 | 2.329 | 20.143 | 0.685791 | 0.071075 | 0.614716 | 2.008042 | 1.888889 | 2.022796 |
16 | 65.536 | 44.953 | 4.366 | 40.587 | 0.685928 | 0.066620 | 0.619308 | 2.000401 | 1.874624 | 2.014943 |
17 | 131.072 | 90.001 | 8.193 | 81.808 | 0.686653 | 0.062508 | 0.624146 | 2.002113 | 1.876546 | 2.015621 |
18 | 262.144 | 180.026 | 15.296 | 164.730 | 0.686745 | 0.058350 | 0.628395 | 2.000267 | 1.866960 | 2.013617 |
19 | 524.288 | 360.234 | 28.878 | 331.356 | 0.687092 | 0.055080 | 0.632011 | 2.001011 | 1.887945 | 2.011510 |
20 | 1.048.576 | 720.748 | 54.509 | 666.239 | 0.687359 | 0.051984 | 0.635375 | 2.000777 | 1.887561 | 2.010644 |
21 | 2.097.152 | 1.442.082 | 103.036 | 1.339.046 | 0.687638 | 0.049131 | 0.638507 | 2.000813 | 1.890257 | 2.009858 |
22 | 4.194.304 | 2.884.765 | 196.238 | 2.688.527 | 0.687782 | 0.046787 | 0.640995 | 2.000417 | 1.904558 | 2.007793 |
23 | 8.388.608 | 5.772.054 | 373.802 | 5.398.252 | 0.688082 | 0.044561 | 0.643522 | 2.000875 | 1.904840 | 2.007885 |
24 | 16.777.216 | 11.547.965 | 714.148 | 10.833.817 | 0.688312 | 0.042567 | 0.645746 | 2.000668 | 1.910498 | 2.006912 |
25 | 33.554.432 | 23.100.894 | 1.367.458 | 21.733.436 | 0.688460 | 0.040753 | 0.647707 | 2.000430 | 1.914810 | 2.006074 |
26 | 67.108.864 | 46.212.514 | 2.622.017 | 43.590.497 | 0.688620 | 0.039071 | 0.649549 | 2.000464 | 1.917439 | 2.005688 |
27 | 134.217.728 | 92.442.952 | 5.036.633 | 87.406.319 | 0.688754 | 0.037526 | 0.651228 | 2.000388 | 1.920900 | 2.005169 |
28 | 268.435.456 | 184.921.740 | 9.689.245 | 175.232.495 | 0.688887 | 0.036095 | 0.652792 | 2.000388 | 1.923754 | 2.004803 |
29 | 536.870.912 | 369.906.338 | 18.672.012 | 351.234.326 | 0.689004 | 0.034779 | 0.654225 | 2.000340 | 1.927086 | 2.004390 |
30 | 1.073.741.824 | 739.939.152 | 36.023.903 | 703.915.249 | 0.689122 | 0.033550 | 0.655572 | 2.000342 | 1.929299 | 2.004119 |
31 | 2.147.483.648 | 1.480.108.777 | 69.594.153 | 1.410.514.624 | 0.689229 | 0.032407 | 0.656822 | 2.000312 | 1.931888 | 2.003813 |
32 | 4.294.967.296 | 2.960.685.019 | 134.597.925 | 2.826.087.094 | 0.689338 | 0.031339 | 0.658000 | 2.000316 | 1.934041 | 2.003586 |
33 | 8.589.934.592 | 5.922.191.886 | 260.623.149 | 5.661.568.737 | 0.689434 | 0.030341 | 0.659093 | 2.000278 | 1.936309 | 2.003324 |
34 | 17.179.869.184 | 11.846.012.031 | 505.154.661 | 11.340.857.370 | 0.689529 | 0.029404 | 0.660125 | 2.000275 | 1.938257 | 2.003130 |
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 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 0 | 2 |
3 | 8 | 5 | 3 | 2 | 0 | 2 | 0 | 3 |
4 | 16 | 6 | 4 | 2 | 0 | 3 | 0 | 3 |
5 | 32 | 6 | 4 | 2 | 0 | 3 | 0 | 3 |
6 | 64 | 9 | 4 | 5 | 2 | 3 | 1 | 3 |
7 | 128 | 18 | 5 | 13 | 6 | 3 | 6 | 3 |
8 | 256 | 36 | 12 | 24 | 16 | 3 | 14 | 3 |
9 | 512 | 67 | 22 | 45 | 31 | 3 | 30 | 3 |
10 | 1.024 | 120 | 39 | 81 | 57 | 3 | 57 | 3 |
11 | 2.048 | 212 | 68 | 144 | 103 | 3 | 103 | 3 |
12 | 4.096 | 367 | 118 | 249 | 177 | 3 | 184 | 3 |
13 | 8.192 | 663 | 214 | 449 | 320 | 3 | 337 | 3 |
14 | 16.384 | 1.233 | 417 | 816 | 601 | 3 | 626 | 3 |
15 | 32.768 | 2.329 | 788 | 1.541 | 1.141 | 3 | 1.182 | 3 |
16 | 65.536 | 4.366 | 1.448 | 2.918 | 2.176 | 3 | 2.184 | 3 |
17 | 131.072 | 8.193 | 2.781 | 5.412 | 4.097 | 3 | 4.090 | 3 |
18 | 262.144 | 15.296 | 5.098 | 10.198 | 7.654 | 3 | 7.636 | 3 |
19 | 524.288 | 28.878 | 9.670 | 19.208 | 14.447 | 3 | 14.425 | 3 |
20 | 1.048.576 | 54.509 | 18.144 | 36.365 | 27.228 | 3 | 27.275 | 3 |
21 | 2.097.152 | 103.036 | 34.265 | 68.771 | 51.402 | 3 | 51.628 | 3 |
22 | 4.194.304 | 196.238 | 65.360 | 130.878 | 98.043 | 3 | 98.189 | 3 |
23 | 8.388.608 | 373.802 | 124.767 | 249.035 | 186.862 | 3 | 186.934 | 3 |
24 | 16.777.216 | 714.148 | 238.454 | 475.694 | 357.031 | 3 | 357.111 | 3 |
25 | 33.554.432 | 1.367.458 | 456.606 | 910.852 | 683.350 | 3 | 684.102 | 3 |
26 | 67.108.864 | 2.622.017 | 875.032 | 1.746.985 | 1.311.256 | 3 | 1.310.755 | 3 |
27 | 134.217.728 | 5.036.633 | 1.679.851 | 3.356.782 | 2.518.893 | 3 | 2.517.734 | 3 |
28 | 268.435.456 | 9.689.245 | 3.230.803 | 6.458.442 | 4.844.991 | 3 | 4.844.248 | 3 |
29 | 536.870.912 | 18.672.012 | 6.225.519 | 12.446.493 | 9.337.252 | 3 | 9.334.754 | 3 |
30 | 1.073.741.824 | 36.023.903 | 12.008.049 | 24.015.854 | 18.012.996 | 3 | 18.010.901 | 3 |
31 | 2.147.483.648 | 69.594.153 | 23.196.345 | 46.397.808 | 34.796.766 | 3 | 34.797.381 | 3 |
32 | 4.294.967.296 | 134.597.925 | 44.862.504 | 89.735.421 | 67.303.702 | 3 | 67.294.217 | 3 |
33 | 8.589.934.592 | 260.623.149 | 86.876.324 | 173.746.825 | 130.307.926 | 3 | 130.315.217 | 3 |
34 | 17.179.869.184 | 505.154.661 | 168.402.451 | 336.752.210 | 252.575.029 | 3 | 252.579.626 | 3 |
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 | 0 | 0 | 1 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 1 | 3 | 1 | 1 | 1 | 1 |
4 | 16 | 9 | 2 | 7 | 1 | 3 | 2 | 3 |
5 | 32 | 11 | 4 | 7 | 1 | 3 | 3 | 4 |
6 | 64 | 17 | 9 | 8 | 2 | 4 | 6 | 5 |
7 | 128 | 48 | 25 | 23 | 12 | 9 | 14 | 13 |
8 | 256 | 113 | 60 | 53 | 33 | 24 | 32 | 24 |
9 | 512 | 247 | 131 | 116 | 66 | 53 | 73 | 55 |
10 | 1.024 | 535 | 279 | 256 | 138 | 119 | 160 | 118 |
11 | 2.048 | 1.150 | 580 | 570 | 288 | 261 | 326 | 275 |
12 | 4.096 | 2.392 | 1.257 | 1.135 | 637 | 550 | 642 | 563 |
13 | 8.192 | 4.919 | 2.535 | 2.384 | 1.285 | 1.162 | 1.321 | 1.151 |
14 | 16.384 | 9.958 | 5.143 | 4.815 | 2.616 | 2.365 | 2.643 | 2.334 |
15 | 32.768 | 20.143 | 10.416 | 9.727 | 5.232 | 4.843 | 5.282 | 4.786 |
16 | 65.536 | 40.587 | 20.921 | 19.666 | 10.631 | 9.664 | 10.700 | 9.592 |
17 | 131.072 | 81.808 | 42.162 | 39.646 | 21.310 | 19.599 | 21.481 | 19.418 |
18 | 262.144 | 164.730 | 84.806 | 79.924 | 42.870 | 39.517 | 42.993 | 39.350 |
19 | 524.288 | 331.356 | 170.468 | 160.888 | 86.166 | 79.404 | 86.156 | 79.630 |
20 | 1.048.576 | 666.239 | 342.749 | 323.490 | 172.556 | 160.270 | 172.912 | 160.501 |
21 | 2.097.152 | 1.339.046 | 687.969 | 651.077 | 346.079 | 323.375 | 346.761 | 322.831 |
22 | 4.194.304 | 2.688.527 | 1.378.730 | 1.309.797 | 694.303 | 649.926 | 694.653 | 649.645 |
23 | 8.388.608 | 5.398.252 | 2.763.300 | 2.634.952 | 1.392.982 | 1.307.083 | 1.392.126 | 1.306.061 |
24 | 16.777.216 | 10.833.817 | 5.540.850 | 5.292.967 | 2.791.416 | 2.627.883 | 2.789.762 | 2.624.756 |
25 | 33.554.432 | 21.733.436 | 11.101.439 | 10.631.997 | 5.593.791 | 5.276.374 | 5.588.158 | 5.275.113 |
26 | 67.108.864 | 43.590.497 | 22.243.667 | 21.346.830 | 11.205.292 | 10.592.856 | 11.201.090 | 10.591.259 |
27 | 134.217.728 | 87.406.319 | 44.562.003 | 42.844.316 | 22.441.190 | 21.265.357 | 22.439.585 | 21.260.187 |
28 | 268.435.456 | 175.232.495 | 89.263.431 | 85.969.064 | 44.941.671 | 42.672.493 | 44.949.072 | 42.669.259 |
29 | 536.870.912 | 351.234.326 | 178.798.433 | 172.435.893 | 90.004.791 | 85.611.816 | 90.008.689 | 85.609.030 |
30 | 1.073.741.824 | 703.915.249 | 358.095.409 | 345.819.840 | 180.221.302 | 171.739.224 | 180.237.736 | 171.716.987 |
31 | 2.147.483.648 | 1.410.514.624 | 717.092.401 | 693.422.223 | 360.843.416 | 344.409.739 | 360.846.523 | 344.414.946 |
32 | 4.294.967.296 | 2.826.087.094 | 1.435.938.574 | 1.390.148.520 | 722.437.893 | 690.613.516 | 722.438.513 | 690.597.172 |
33 | 8.589.934.592 | 5.661.568.737 | 2.875.095.119 | 2.786.473.618 | 1.446.255.851 | 1.384.551.990 | 1.446.250.680 | 1.384.510.216 |
34 | 17.179.869.184 | 11.340.857.370 | 5.756.274.227 | 5.584.583.143 | 2.895.096.240 | 2.775.353.210 | 2.895.081.925 | 2.775.325.995 |