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+7
f(0)=7
f(1)=1
f(2)=11
f(3)=1
f(4)=23
f(5)=1
f(6)=43
f(7)=1
f(8)=71
f(9)=1
f(10)=107
f(11)=1
f(12)=151
f(13)=1
f(14)=29
f(15)=1
f(16)=263
f(17)=37
f(18)=331
f(19)=1
f(20)=1
f(21)=1
f(22)=491
f(23)=67
f(24)=53
f(25)=79
f(26)=683
f(27)=1
f(28)=113
f(29)=1
f(30)=907
f(31)=1
f(32)=1031
f(33)=137
f(34)=1163
f(35)=1
f(36)=1303
f(37)=1
f(38)=1451
f(39)=191
f(40)=1607
f(41)=211
f(42)=1
f(43)=1
f(44)=1
f(45)=127
f(46)=193
f(47)=277
f(48)=2311
f(49)=1
f(50)=109
f(51)=163
f(52)=2711
f(53)=1
f(54)=1
f(55)=379
f(56)=449
f(57)=1
f(58)=3371
f(59)=1
f(60)=3607
f(61)=233
f(62)=3851
f(63)=1
f(64)=373
f(65)=1
f(66)=4363
f(67)=281
f(68)=421
f(69)=149
f(70)=701
f(71)=631
f(72)=179
f(73)=1
f(74)=5483
f(75)=1
f(76)=5783
f(77)=1
f(78)=6091
f(79)=1
f(80)=1
f(81)=821
f(82)=1
f(83)=431
f(84)=1009
f(85)=1
f(86)=673
f(87)=947
f(88)=337
f(89)=991
f(90)=1
f(91)=1
f(92)=197
f(93)=541
f(94)=239
f(95)=1129
f(96)=401
f(97)=1
f(98)=1373
f(99)=613
b) Substitution of the polynom
The polynom f(x)=x^2+7 could be written as f(y)= y^2+7 with x=y+0
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
f'(x)>2x-1 with x > 3
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 | 6 | 0 | 0.600000 | 0.600000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 65 | 48 | 17 | 0.650000 | 0.480000 | 0.650000 | 10.833333 | 8.000000 | inf |
3 | 1.000 | 670 | 369 | 301 | 0.670000 | 0.369000 | 0.670000 | 10.307693 | 7.687500 | 17.705883 |
4 | 10.000 | 6.824 | 2.694 | 4.130 | 0.682400 | 0.269400 | 0.682400 | 10.185075 | 7.300813 | 13.720930 |
5 | 100.000 | 68.467 | 20.513 | 47.954 | 0.684670 | 0.205130 | 0.684670 | 10.033265 | 7.614328 | 11.611138 |
6 | 1.000.000 | 685.939 | 164.773 | 521.166 | 0.685939 | 0.164773 | 0.685939 | 10.018535 | 8.032614 | 10.868040 |
7 | 10.000.000 | 6.869.035 | 1.380.107 | 5.488.928 | 0.686903 | 0.138011 | 0.686903 | 10.014061 | 8.375808 | 10.532015 |
8 | 100.000.000 | 68.751.925 | 11.871.076 | 56.880.849 | 0.687519 | 0.118711 | 0.687519 | 10.008965 | 8.601562 | 10.362834 |
9 | 1.000.000.000 | 688.059.671 | 104.180.631 | 583.879.040 | 0.688060 | 0.104181 | 0.688060 | 10.007859 | 8.776006 | 10.264950 |
10 | 10.000.000.000 | 6.885.009.841 | 928.440.430 | 5.956.569.411 | 0.688501 | 0.092844 | 0.688501 | 10.006414 | 8.911834 | 10.201718 |
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 | 5 | 5 | 0 | 0.625000 | 0.625000 | 0.000000 | 1.666667 | 1.666667 | -nan |
4 | 16 | 9 | 8 | 1 | 0.562500 | 0.500000 | 0.062500 | 1.800000 | 1.600000 | inf |
5 | 32 | 19 | 16 | 3 | 0.593750 | 0.500000 | 0.093750 | 2.111111 | 2.000000 | 3.000000 |
6 | 64 | 40 | 33 | 7 | 0.625000 | 0.515625 | 0.109375 | 2.105263 | 2.062500 | 2.333333 |
7 | 128 | 84 | 63 | 21 | 0.656250 | 0.492188 | 0.164062 | 2.100000 | 1.909091 | 3.000000 |
8 | 256 | 169 | 116 | 53 | 0.660156 | 0.453125 | 0.207031 | 2.011905 | 1.841270 | 2.523809 |
9 | 512 | 339 | 208 | 131 | 0.662109 | 0.406250 | 0.255859 | 2.005917 | 1.793103 | 2.471698 |
10 | 1.024 | 687 | 380 | 307 | 0.670898 | 0.371094 | 0.299805 | 2.026549 | 1.826923 | 2.343511 |
11 | 2.048 | 1.386 | 689 | 697 | 0.676758 | 0.336426 | 0.340332 | 2.017467 | 1.813158 | 2.270358 |
12 | 4.096 | 2.789 | 1.244 | 1.545 | 0.680908 | 0.303711 | 0.377197 | 2.012265 | 1.805515 | 2.216643 |
13 | 8.192 | 5.578 | 2.261 | 3.317 | 0.680908 | 0.276001 | 0.404907 | 2.000000 | 1.817524 | 2.146925 |
14 | 16.384 | 11.162 | 4.127 | 7.035 | 0.681274 | 0.251892 | 0.429382 | 2.001076 | 1.825299 | 2.120892 |
15 | 32.768 | 22.381 | 7.637 | 14.744 | 0.683014 | 0.233063 | 0.449951 | 2.005107 | 1.850497 | 2.095807 |
16 | 65.536 | 44.867 | 14.076 | 30.791 | 0.684616 | 0.214783 | 0.469833 | 2.004691 | 1.843132 | 2.088375 |
17 | 131.072 | 89.709 | 26.175 | 63.534 | 0.684425 | 0.199699 | 0.484726 | 1.999443 | 1.859548 | 2.063395 |
18 | 262.144 | 179.628 | 48.757 | 130.871 | 0.685226 | 0.185993 | 0.499233 | 2.002341 | 1.862732 | 2.059858 |
19 | 524.288 | 359.539 | 91.289 | 268.250 | 0.685766 | 0.174120 | 0.511646 | 2.001575 | 1.872326 | 2.049728 |
20 | 1.048.576 | 719.222 | 172.083 | 547.139 | 0.685904 | 0.164111 | 0.521792 | 2.000401 | 1.885035 | 2.039661 |
21 | 2.097.152 | 1.439.181 | 325.364 | 1.113.817 | 0.686255 | 0.155146 | 0.531109 | 2.001025 | 1.890739 | 2.035711 |
22 | 4.194.304 | 2.879.859 | 617.002 | 2.262.857 | 0.686612 | 0.147105 | 0.539507 | 2.001040 | 1.896344 | 2.031624 |
23 | 8.388.608 | 5.761.591 | 1.172.630 | 4.588.961 | 0.686835 | 0.139788 | 0.547047 | 2.000650 | 1.900529 | 2.027950 |
24 | 16.777.216 | 11.527.270 | 2.233.080 | 9.294.190 | 0.687079 | 0.133102 | 0.553977 | 2.000710 | 1.904335 | 2.025337 |
25 | 33.554.432 | 23.060.169 | 4.265.627 | 18.794.542 | 0.687247 | 0.127126 | 0.560121 | 2.000488 | 1.910199 | 2.022182 |
26 | 67.108.864 | 46.132.627 | 8.162.380 | 37.970.247 | 0.687430 | 0.121629 | 0.565801 | 2.000533 | 1.913524 | 2.020281 |
27 | 134.217.728 | 92.287.418 | 15.654.359 | 76.633.059 | 0.687595 | 0.116634 | 0.570961 | 2.000480 | 1.917867 | 2.018239 |
28 | 268.435.456 | 184.620.639 | 30.066.355 | 154.554.284 | 0.687765 | 0.112006 | 0.575760 | 2.000496 | 1.920638 | 2.016810 |
29 | 536.870.912 | 369.324.282 | 57.844.290 | 311.479.992 | 0.687920 | 0.107743 | 0.580177 | 2.000450 | 1.923887 | 2.015344 |
30 | 1.073.741.824 | 738.812.244 | 111.444.489 | 627.367.755 | 0.688073 | 0.103791 | 0.584282 | 2.000443 | 1.926629 | 2.014151 |
31 | 2.147.483.648 | 1.477.930.950 | 215.011.627 | 1.262.919.323 | 0.688215 | 0.100123 | 0.588093 | 2.000415 | 1.929316 | 2.013045 |
32 | 4.294.967.296 | 2.956.435.154 | 415.340.217 | 2.541.094.937 | 0.688349 | 0.096704 | 0.591645 | 2.000388 | 1.931710 | 2.012080 |
33 | 8.589.934.592 | 5.913.966.529 | 803.276.718 | 5.110.689.811 | 0.688476 | 0.093514 | 0.594963 | 2.000371 | 1.934021 | 2.011216 |
34 | 17.179.869.184 | 11.829.978.234 | 1.555.292.322 | 10.274.685.912 | 0.688595 | 0.090530 | 0.598065 | 2.000346 | 1.936185 | 2.010430 |
35 | 34.359.738.368 | 23.663.886.462 | 3.014.365.556 | 20.649.520.906 | 0.688710 | 0.087730 | 0.600980 | 2.000332 | 1.938134 | 2.009747 |
36 | 68.719.476.736 | 47.335.288.405 | 5.847.820.757 | 41.487.467.648 | 0.688819 | 0.085097 | 0.603722 | 2.000318 | 1.939984 | 2.009125 |
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 | 1 | 2 | 0 | 1 | 0 | 2 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 0 | 3 |
4 | 16 | 8 | 3 | 5 | 0 | 3 | 0 | 5 |
5 | 32 | 16 | 8 | 8 | 0 | 8 | 1 | 7 |
6 | 64 | 33 | 16 | 17 | 2 | 15 | 2 | 14 |
7 | 128 | 63 | 29 | 34 | 6 | 25 | 7 | 25 |
8 | 256 | 116 | 54 | 62 | 14 | 43 | 13 | 46 |
9 | 512 | 208 | 94 | 114 | 26 | 74 | 25 | 83 |
10 | 1.024 | 380 | 173 | 207 | 53 | 125 | 50 | 152 |
11 | 2.048 | 689 | 310 | 379 | 103 | 246 | 87 | 253 |
12 | 4.096 | 1.244 | 570 | 674 | 177 | 461 | 162 | 444 |
13 | 8.192 | 2.261 | 1.021 | 1.240 | 317 | 820 | 306 | 818 |
14 | 16.384 | 4.127 | 1.861 | 2.266 | 573 | 1.503 | 556 | 1.495 |
15 | 32.768 | 7.637 | 3.427 | 4.210 | 1.071 | 2.792 | 1.037 | 2.737 |
16 | 65.536 | 14.076 | 6.311 | 7.765 | 1.924 | 5.148 | 1.882 | 5.122 |
17 | 131.072 | 26.175 | 11.835 | 14.340 | 3.540 | 9.536 | 3.495 | 9.604 |
18 | 262.144 | 48.757 | 21.985 | 26.772 | 6.471 | 17.827 | 6.609 | 17.850 |
19 | 524.288 | 91.289 | 40.982 | 50.307 | 12.057 | 33.479 | 12.231 | 33.522 |
20 | 1.048.576 | 172.083 | 77.369 | 94.714 | 22.639 | 63.193 | 22.869 | 63.382 |
21 | 2.097.152 | 325.364 | 146.403 | 178.961 | 42.738 | 119.636 | 43.127 | 119.863 |
22 | 4.194.304 | 617.002 | 277.381 | 339.621 | 81.057 | 227.375 | 81.261 | 227.309 |
23 | 8.388.608 | 1.172.630 | 526.710 | 645.920 | 153.512 | 432.719 | 153.931 | 432.468 |
24 | 16.777.216 | 2.233.080 | 1.002.747 | 1.230.333 | 292.537 | 824.067 | 292.329 | 824.147 |
25 | 33.554.432 | 4.265.627 | 1.914.482 | 2.351.145 | 557.329 | 1.575.148 | 557.956 | 1.575.194 |
26 | 67.108.864 | 8.162.380 | 3.659.575 | 4.502.805 | 1.064.857 | 3.017.033 | 1.064.748 | 3.015.742 |
27 | 134.217.728 | 15.654.359 | 7.016.486 | 8.637.873 | 2.039.093 | 5.788.939 | 2.037.347 | 5.788.980 |
28 | 268.435.456 | 30.066.355 | 13.470.373 | 16.595.982 | 3.908.747 | 11.126.600 | 3.905.843 | 11.125.165 |
29 | 536.870.912 | 57.844.290 | 25.908.476 | 31.935.814 | 7.508.970 | 21.413.219 | 7.505.971 | 21.416.130 |
30 | 1.073.741.824 | 111.444.489 | 49.903.953 | 61.540.536 | 14.442.205 | 41.278.869 | 14.444.643 | 41.278.772 |
31 | 2.147.483.648 | 215.011.627 | 96.256.994 | 118.754.633 | 27.827.564 | 79.671.068 | 27.835.919 | 79.677.076 |
32 | 4.294.967.296 | 415.340.217 | 185.900.172 | 229.440.045 | 53.693.901 | 153.966.462 | 53.705.784 | 153.974.070 |
33 | 8.589.934.592 | 803.276.718 | 359.443.768 | 443.832.950 | 103.738.984 | 297.881.161 | 103.747.621 | 297.908.952 |
34 | 17.179.869.184 | 1.555.292.322 | 695.809.150 | 859.483.172 | 200.649.105 | 576.964.857 | 200.663.432 | 577.014.928 |
35 | 34.359.738.368 | 3.014.365.556 | 1.348.282.434 | 1.666.083.122 | 388.503.100 | 1.118.633.067 | 388.547.006 | 1.118.682.383 |
36 | 68.719.476.736 | 5.847.820.757 | 2.615.173.320 | 3.232.647.437 | 753.020.013 | 2.170.824.114 | 753.055.033 | 2.170.921.597 |
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 | 1 | 0 |
5 | 32 | 3 | 0 | 3 | 1 | 0 | 2 | 0 |
6 | 64 | 7 | 3 | 4 | 3 | 0 | 4 | 0 |
7 | 128 | 21 | 8 | 13 | 7 | 2 | 10 | 2 |
8 | 256 | 53 | 21 | 32 | 15 | 8 | 23 | 7 |
9 | 512 | 131 | 62 | 69 | 35 | 20 | 49 | 27 |
10 | 1.024 | 307 | 153 | 154 | 81 | 54 | 105 | 67 |
11 | 2.048 | 697 | 344 | 353 | 198 | 147 | 211 | 141 |
12 | 4.096 | 1.545 | 754 | 791 | 436 | 333 | 458 | 318 |
13 | 8.192 | 3.317 | 1.669 | 1.648 | 919 | 708 | 966 | 724 |
14 | 16.384 | 7.035 | 3.550 | 3.485 | 1.923 | 1.524 | 2.020 | 1.568 |
15 | 32.768 | 14.744 | 7.484 | 7.260 | 3.958 | 3.352 | 4.096 | 3.338 |
16 | 65.536 | 30.791 | 15.540 | 15.251 | 8.296 | 7.073 | 8.412 | 7.010 |
17 | 131.072 | 63.534 | 32.059 | 31.475 | 17.172 | 14.771 | 17.034 | 14.557 |
18 | 262.144 | 130.871 | 65.982 | 64.889 | 34.877 | 30.556 | 35.016 | 30.422 |
19 | 524.288 | 268.250 | 134.918 | 133.332 | 71.299 | 62.792 | 71.304 | 62.855 |
20 | 1.048.576 | 547.139 | 275.021 | 272.118 | 145.106 | 128.758 | 144.641 | 128.634 |
21 | 2.097.152 | 1.113.817 | 559.402 | 554.415 | 293.605 | 262.976 | 293.626 | 263.610 |
22 | 4.194.304 | 2.262.857 | 1.136.596 | 1.126.261 | 594.236 | 537.238 | 594.051 | 537.332 |
23 | 8.388.608 | 4.588.961 | 2.305.134 | 2.283.827 | 1.201.740 | 1.092.540 | 1.201.966 | 1.092.715 |
24 | 16.777.216 | 9.294.190 | 4.668.744 | 4.625.446 | 2.427.789 | 2.218.388 | 2.428.809 | 2.219.204 |
25 | 33.554.432 | 18.794.542 | 9.438.649 | 9.355.893 | 4.899.604 | 4.498.246 | 4.900.127 | 4.496.565 |
26 | 67.108.864 | 37.970.247 | 19.059.086 | 18.911.161 | 9.874.542 | 9.108.089 | 9.878.449 | 9.109.167 |
27 | 134.217.728 | 76.633.059 | 38.463.835 | 38.169.224 | 19.891.408 | 18.422.130 | 19.895.897 | 18.423.624 |
28 | 268.435.456 | 154.554.284 | 77.549.668 | 77.004.616 | 40.041.794 | 37.229.609 | 40.052.623 | 37.230.258 |
29 | 536.870.912 | 311.479.992 | 156.266.970 | 155.213.022 | 80.573.499 | 75.160.051 | 80.584.396 | 75.162.046 |
30 | 1.073.741.824 | 627.367.755 | 314.686.914 | 312.680.841 | 162.051.943 | 151.621.222 | 162.071.860 | 151.622.730 |
31 | 2.147.483.648 | 1.262.919.323 | 633.397.465 | 629.521.858 | 325.774.867 | 305.665.800 | 325.804.209 | 305.674.447 |
32 | 4.294.967.296 | 2.541.094.937 | 1.274.302.502 | 1.266.792.435 | 654.655.396 | 615.868.134 | 654.716.467 | 615.854.940 |
33 | 8.589.934.592 | 5.110.689.811 | 2.562.606.920 | 2.548.082.891 | 1.315.163.071 | 1.240.161.674 | 1.315.259.885 | 1.240.105.181 |
34 | 17.179.869.184 | 10.274.685.912 | 5.151.407.931 | 5.123.277.981 | 2.641.290.634 | 2.496.046.026 | 2.641.352.499 | 2.495.996.753 |
35 | 34.359.738.368 | 20.649.520.906 | 10.352.007.704 | 10.297.513.202 | 5.303.043.133 | 5.021.664.362 | 5.303.134.687 | 5.021.678.724 |
36 | 68.719.476.736 | 41.487.467.648 | 20.796.531.971 | 20.690.935.677 | 10.644.593.062 | 10.098.939.653 | 10.644.945.040 | 10.098.989.893 |