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+1x-5
f(0)=5
f(1)=3
f(2)=1
f(3)=7
f(4)=1
f(5)=1
f(6)=37
f(7)=17
f(8)=67
f(9)=1
f(10)=1
f(11)=127
f(12)=151
f(13)=59
f(14)=41
f(15)=47
f(16)=89
f(17)=43
f(18)=337
f(19)=1
f(20)=83
f(21)=457
f(22)=167
f(23)=547
f(24)=1
f(25)=1
f(26)=1
f(27)=751
f(28)=269
f(29)=173
f(30)=1
f(31)=1
f(32)=1051
f(33)=1117
f(34)=79
f(35)=251
f(36)=1327
f(37)=467
f(38)=211
f(39)=311
f(40)=109
f(41)=101
f(42)=1801
f(43)=1
f(44)=1
f(45)=1
f(46)=719
f(47)=2251
f(48)=2347
f(49)=163
f(50)=509
f(51)=2647
f(52)=131
f(53)=2857
f(54)=593
f(55)=1
f(56)=3187
f(57)=3301
f(58)=1
f(59)=1
f(60)=1
f(61)=1259
f(62)=1
f(63)=4027
f(64)=277
f(65)=857
f(66)=631
f(67)=1
f(68)=1
f(69)=193
f(70)=331
f(71)=5107
f(72)=1
f(73)=257
f(74)=1109
f(75)=1
f(76)=1949
f(77)=353
f(78)=1
f(79)=421
f(80)=1
f(81)=6637
f(82)=2267
f(83)=6967
f(84)=1427
f(85)=487
f(86)=7477
f(87)=1093
f(88)=2609
f(89)=1601
f(90)=1637
f(91)=2789
f(92)=503
f(93)=8737
f(94)=1
f(95)=1823
f(96)=227
f(97)=3167
f(98)=9697
f(99)=1979
b) Substitution of the polynom
The polynom f(x)=x^2+1x-5 could be written as f(y)= y^2-5.25 with x=y-0.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+0.5
f'(x)>2x
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 | 6 | 5 | 1 | 0.600000 | 0.500000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 75 | 28 | 47 | 0.750000 | 0.280000 | 0.750000 | 12.500000 | 5.600000 | 47.000000 |
3 | 1.000 | 724 | 160 | 564 | 0.724000 | 0.160000 | 0.724000 | 9.653334 | 5.714286 | 12.000000 |
4 | 10.000 | 7.180 | 1.154 | 6.026 | 0.718000 | 0.115400 | 0.718000 | 9.917127 | 7.212500 | 10.684397 |
5 | 100.000 | 71.333 | 8.913 | 62.420 | 0.713330 | 0.089130 | 0.713330 | 9.934958 | 7.723570 | 10.358447 |
6 | 1.000.000 | 709.047 | 72.774 | 636.273 | 0.709047 | 0.072774 | 0.709047 | 9.939958 | 8.164927 | 10.193416 |
7 | 10.000.000 | 7.064.484 | 616.667 | 6.447.817 | 0.706448 | 0.061667 | 0.706448 | 9.963351 | 8.473727 | 10.133727 |
8 | 100.000.000 | 70.456.302 | 5.343.819 | 65.112.483 | 0.704563 | 0.053438 | 0.704563 | 9.973312 | 8.665648 | 10.098376 |
9 | 1.000.000.000 | 703.097.451 | 47.178.885 | 655.918.566 | 0.703097 | 0.047179 | 0.703097 | 9.979198 | 8.828683 | 10.073623 |
10 | 10.000.000.000 | 7.019.663.877 | 422.252.974 | 6.597.410.903 | 0.701966 | 0.042225 | 0.701966 | 9.983912 | 8.950041 | 10.058277 |
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 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 6 | 5 | 1 | 0.750000 | 0.625000 | 0.125000 | 2.000000 | 1.666667 | inf |
4 | 16 | 12 | 7 | 5 | 0.750000 | 0.437500 | 0.312500 | 2.000000 | 1.400000 | 5.000000 |
5 | 32 | 22 | 12 | 10 | 0.687500 | 0.375000 | 0.312500 | 1.833333 | 1.714286 | 2.000000 |
6 | 64 | 46 | 22 | 24 | 0.718750 | 0.343750 | 0.375000 | 2.090909 | 1.833333 | 2.400000 |
7 | 128 | 93 | 31 | 62 | 0.726562 | 0.242188 | 0.484375 | 2.021739 | 1.409091 | 2.583333 |
8 | 256 | 187 | 53 | 134 | 0.730469 | 0.207031 | 0.523438 | 2.010753 | 1.709677 | 2.161290 |
9 | 512 | 372 | 101 | 271 | 0.726562 | 0.197266 | 0.529297 | 1.989305 | 1.905660 | 2.022388 |
10 | 1.024 | 739 | 162 | 577 | 0.721680 | 0.158203 | 0.563477 | 1.986559 | 1.603960 | 2.129151 |
11 | 2.048 | 1.481 | 298 | 1.183 | 0.723145 | 0.145508 | 0.577637 | 2.004060 | 1.839506 | 2.050260 |
12 | 4.096 | 2.940 | 554 | 2.386 | 0.717773 | 0.135254 | 0.582520 | 1.985145 | 1.859060 | 2.016906 |
13 | 8.192 | 5.891 | 968 | 4.923 | 0.719116 | 0.118164 | 0.600952 | 2.003742 | 1.747292 | 2.063286 |
14 | 16.384 | 11.727 | 1.773 | 9.954 | 0.715759 | 0.108215 | 0.607544 | 1.990664 | 1.831612 | 2.021938 |
15 | 32.768 | 23.418 | 3.271 | 20.147 | 0.714661 | 0.099823 | 0.614838 | 1.996930 | 1.844896 | 2.024010 |
16 | 65.536 | 46.812 | 6.055 | 40.757 | 0.714294 | 0.092392 | 0.621902 | 1.998975 | 1.851116 | 2.022981 |
17 | 131.072 | 93.362 | 11.416 | 81.946 | 0.712296 | 0.087097 | 0.625198 | 1.994403 | 1.885384 | 2.010599 |
18 | 262.144 | 186.436 | 21.352 | 165.084 | 0.711197 | 0.081451 | 0.629745 | 1.996915 | 1.870357 | 2.014546 |
19 | 524.288 | 372.183 | 40.344 | 331.839 | 0.709883 | 0.076950 | 0.632933 | 1.996304 | 1.889472 | 2.010122 |
20 | 1.048.576 | 743.486 | 75.947 | 667.539 | 0.709044 | 0.072429 | 0.636615 | 1.997636 | 1.882486 | 2.011635 |
21 | 2.097.152 | 1.485.176 | 144.008 | 1.341.168 | 0.708187 | 0.068668 | 0.639519 | 1.997584 | 1.896164 | 2.009123 |
22 | 4.194.304 | 2.966.777 | 274.091 | 2.692.686 | 0.707335 | 0.065348 | 0.641986 | 1.997593 | 1.903304 | 2.007717 |
23 | 8.388.608 | 5.927.213 | 523.382 | 5.403.831 | 0.706579 | 0.062392 | 0.644187 | 1.997863 | 1.909519 | 2.006855 |
24 | 16.777.216 | 11.844.478 | 1.000.160 | 10.844.318 | 0.705986 | 0.059614 | 0.646372 | 1.998322 | 1.910956 | 2.006783 |
25 | 33.554.432 | 23.669.475 | 1.913.790 | 21.755.685 | 0.705405 | 0.057035 | 0.648370 | 1.998355 | 1.913484 | 2.006183 |
26 | 67.108.864 | 47.303.205 | 3.670.518 | 43.632.687 | 0.704873 | 0.054695 | 0.650178 | 1.998490 | 1.917931 | 2.005576 |
27 | 134.217.728 | 94.536.466 | 7.053.651 | 87.482.815 | 0.704352 | 0.052554 | 0.651798 | 1.998521 | 1.921705 | 2.004983 |
28 | 268.435.456 | 188.945.066 | 13.575.926 | 175.369.140 | 0.703875 | 0.050574 | 0.653301 | 1.998648 | 1.924667 | 2.004612 |
29 | 536.870.912 | 377.665.380 | 26.157.141 | 351.508.239 | 0.703457 | 0.048721 | 0.654735 | 1.998810 | 1.926730 | 2.004390 |
30 | 1.073.741.824 | 754.901.117 | 50.474.362 | 704.426.755 | 0.703056 | 0.047008 | 0.656049 | 1.998862 | 1.929659 | 2.004012 |
31 | 2.147.483.648 | 1.509.023.316 | 97.526.767 | 1.411.496.549 | 0.702694 | 0.045414 | 0.657279 | 1.998968 | 1.932204 | 2.003752 |
32 | 4.294.967.296 | 3.016.576.011 | 188.620.031 | 2.827.955.980 | 0.702351 | 0.043917 | 0.658435 | 1.999025 | 1.934034 | 2.003516 |
33 | 8.589.934.592 | 6.030.428.350 | 365.239.657 | 5.665.188.693 | 0.702034 | 0.042519 | 0.659515 | 1.999097 | 1.936378 | 2.003280 |
34 | 17.179.869.184 | 12.055.763.917 | 707.940.073 | 11.347.823.844 | 0.701738 | 0.041208 | 0.660530 | 1.999156 | 1.938289 | 2.003079 |
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 | 0 | 1 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 3 | 1 | 0 | 2 | 2 | 1 |
4 | 16 | 7 | 5 | 1 | 0 | 2 | 2 | 3 |
5 | 32 | 12 | 10 | 1 | 2 | 4 | 2 | 4 |
6 | 64 | 22 | 20 | 1 | 4 | 8 | 4 | 6 |
7 | 128 | 31 | 29 | 1 | 6 | 9 | 7 | 9 |
8 | 256 | 53 | 51 | 1 | 10 | 15 | 14 | 14 |
9 | 512 | 101 | 99 | 1 | 20 | 30 | 25 | 26 |
10 | 1.024 | 162 | 160 | 1 | 36 | 45 | 43 | 38 |
11 | 2.048 | 298 | 296 | 1 | 73 | 79 | 74 | 72 |
12 | 4.096 | 554 | 552 | 1 | 145 | 136 | 142 | 131 |
13 | 8.192 | 968 | 966 | 1 | 251 | 238 | 236 | 243 |
14 | 16.384 | 1.773 | 1.771 | 1 | 457 | 434 | 438 | 444 |
15 | 32.768 | 3.271 | 3.269 | 1 | 829 | 807 | 823 | 812 |
16 | 65.536 | 6.055 | 6.053 | 1 | 1.514 | 1.519 | 1.510 | 1.512 |
17 | 131.072 | 11.416 | 11.414 | 1 | 2.832 | 2.844 | 2.859 | 2.881 |
18 | 262.144 | 21.352 | 21.350 | 1 | 5.293 | 5.351 | 5.351 | 5.357 |
19 | 524.288 | 40.344 | 40.342 | 1 | 10.000 | 10.194 | 10.080 | 10.070 |
20 | 1.048.576 | 75.947 | 75.945 | 1 | 18.882 | 19.156 | 18.937 | 18.972 |
21 | 2.097.152 | 144.008 | 144.006 | 1 | 35.907 | 36.013 | 35.962 | 36.126 |
22 | 4.194.304 | 274.091 | 274.089 | 1 | 68.284 | 68.584 | 68.521 | 68.702 |
23 | 8.388.608 | 523.382 | 523.380 | 1 | 130.762 | 130.935 | 130.751 | 130.934 |
24 | 16.777.216 | 1.000.160 | 1.000.158 | 1 | 250.046 | 250.109 | 249.739 | 250.266 |
25 | 33.554.432 | 1.913.790 | 1.913.788 | 1 | 478.585 | 478.960 | 477.614 | 478.631 |
26 | 67.108.864 | 3.670.518 | 3.670.516 | 1 | 916.895 | 918.027 | 916.609 | 918.987 |
27 | 134.217.728 | 7.053.651 | 7.053.649 | 1 | 1.762.997 | 1.764.127 | 1.762.718 | 1.763.809 |
28 | 268.435.456 | 13.575.926 | 13.575.924 | 1 | 3.394.178 | 3.394.853 | 3.392.790 | 3.394.105 |
29 | 536.870.912 | 26.157.141 | 26.157.139 | 1 | 6.542.486 | 6.540.306 | 6.536.882 | 6.537.467 |
30 | 1.073.741.824 | 50.474.362 | 50.474.360 | 1 | 12.622.518 | 12.618.890 | 12.615.332 | 12.617.622 |
31 | 2.147.483.648 | 97.526.767 | 97.526.765 | 1 | 24.386.456 | 24.383.744 | 24.376.407 | 24.380.160 |
32 | 4.294.967.296 | 188.620.031 | 188.620.029 | 1 | 47.161.134 | 47.153.701 | 47.149.726 | 47.155.470 |
33 | 8.589.934.592 | 365.239.657 | 365.239.655 | 1 | 91.322.796 | 91.303.489 | 91.300.523 | 91.312.849 |
34 | 17.179.869.184 | 707.940.073 | 707.940.071 | 1 | 176.998.095 | 176.978.835 | 176.977.631 | 176.985.512 |
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 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 5 | 0 | 5 | 3 | 1 | 0 | 1 |
5 | 32 | 10 | 1 | 9 | 3 | 3 | 2 | 2 |
6 | 64 | 24 | 6 | 18 | 4 | 9 | 6 | 5 |
7 | 128 | 62 | 18 | 44 | 15 | 17 | 15 | 15 |
8 | 256 | 134 | 41 | 93 | 32 | 35 | 32 | 35 |
9 | 512 | 271 | 86 | 185 | 63 | 69 | 68 | 71 |
10 | 1.024 | 577 | 224 | 353 | 139 | 145 | 152 | 141 |
11 | 2.048 | 1.183 | 471 | 712 | 264 | 312 | 302 | 305 |
12 | 4.096 | 2.386 | 979 | 1.407 | 573 | 628 | 588 | 597 |
13 | 8.192 | 4.923 | 2.038 | 2.885 | 1.200 | 1.284 | 1.202 | 1.237 |
14 | 16.384 | 9.954 | 4.254 | 5.700 | 2.438 | 2.536 | 2.484 | 2.496 |
15 | 32.768 | 20.147 | 8.809 | 11.338 | 4.990 | 5.072 | 4.998 | 5.087 |
16 | 65.536 | 40.757 | 18.066 | 22.691 | 10.108 | 10.229 | 10.198 | 10.222 |
17 | 131.072 | 81.946 | 36.717 | 45.229 | 20.220 | 20.562 | 20.553 | 20.611 |
18 | 262.144 | 165.084 | 74.334 | 90.750 | 41.093 | 41.405 | 41.124 | 41.462 |
19 | 524.288 | 331.839 | 150.478 | 181.361 | 82.686 | 82.976 | 83.168 | 83.009 |
20 | 1.048.576 | 667.539 | 304.641 | 362.898 | 166.608 | 167.039 | 166.840 | 167.052 |
21 | 2.097.152 | 1.341.168 | 615.911 | 725.257 | 335.317 | 335.313 | 335.123 | 335.415 |
22 | 4.194.304 | 2.692.686 | 1.243.762 | 1.448.924 | 673.515 | 673.521 | 673.213 | 672.437 |
23 | 8.388.608 | 5.403.831 | 2.505.304 | 2.898.527 | 1.350.899 | 1.351.218 | 1.350.812 | 1.350.902 |
24 | 16.777.216 | 10.844.318 | 5.046.637 | 5.797.681 | 2.710.505 | 2.711.584 | 2.711.037 | 2.711.192 |
25 | 33.554.432 | 21.755.685 | 10.165.444 | 11.590.241 | 5.438.667 | 5.439.122 | 5.438.965 | 5.438.931 |
26 | 67.108.864 | 43.632.687 | 20.447.410 | 23.185.277 | 10.908.635 | 10.907.160 | 10.909.115 | 10.907.777 |
27 | 134.217.728 | 87.482.815 | 41.116.329 | 46.366.486 | 21.875.449 | 21.866.875 | 21.870.088 | 21.870.403 |
28 | 268.435.456 | 175.369.140 | 82.641.400 | 92.727.740 | 43.851.601 | 43.836.941 | 43.840.805 | 43.839.793 |
29 | 536.870.912 | 351.508.239 | 166.053.584 | 185.454.655 | 87.886.339 | 87.872.519 | 87.876.111 | 87.873.270 |
30 | 1.073.741.824 | 704.426.755 | 333.511.277 | 370.915.478 | 176.111.651 | 176.089.255 | 176.109.966 | 176.115.883 |
31 | 2.147.483.648 | 1.411.496.549 | 669.663.721 | 741.832.828 | 352.869.569 | 352.861.668 | 352.885.547 | 352.879.765 |
32 | 4.294.967.296 | 2.827.955.980 | 1.344.200.347 | 1.483.755.633 | 706.985.872 | 706.993.138 | 706.999.116 | 706.977.854 |
33 | 8.589.934.592 | 5.665.188.693 | 2.697.548.942 | 2.967.639.751 | 1.416.264.028 | 1.416.315.304 | 1.416.328.667 | 1.416.280.694 |
34 | 17.179.869.184 | 11.347.823.844 | 5.412.266.497 | 5.935.557.347 | 2.836.964.522 | 2.836.970.531 | 2.836.958.704 | 2.836.930.087 |