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+29
f(0)=29
f(1)=5
f(2)=47
f(3)=41
f(4)=23
f(5)=73
f(6)=7
f(7)=101
f(8)=227
f(9)=1
f(10)=271
f(11)=1
f(12)=307
f(13)=1
f(14)=67
f(15)=173
f(16)=71
f(17)=181
f(18)=367
f(19)=37
f(20)=53
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)=113
f(43)=79
f(44)=1
f(45)=127
f(46)=61
f(47)=179
f(48)=59
f(49)=1
f(50)=1
f(51)=1
f(52)=653
f(53)=359
f(54)=157
f(55)=1
f(56)=1
f(57)=499
f(58)=1
f(59)=1
f(60)=1229
f(61)=131
f(62)=199
f(63)=739
f(64)=313
f(65)=827
f(66)=349
f(67)=919
f(68)=1933
f(69)=1
f(70)=2129
f(71)=223
f(72)=2333
f(73)=1
f(74)=509
f(75)=1327
f(76)=1
f(77)=1439
f(78)=1
f(79)=311
f(80)=3229
f(81)=1
f(82)=151
f(83)=257
f(84)=149
f(85)=1
f(86)=797
f(87)=1
f(88)=4253
f(89)=439
f(90)=647
f(91)=467
f(92)=4813
f(93)=1
f(94)=1021
f(95)=1
f(96)=1
f(97)=397
f(98)=197
f(99)=587
b) Substitution of the polynom
The polynom f(x)=x^2-40x+29 could be written as f(y)= y^2-371 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 > 19
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 | 5 | 5 | 1.000000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 53 | 17 | 36 | 0.530000 | 0.170000 | 0.530000 | 5.300000 | 3.400000 | 7.200000 |
3 | 1.000 | 655 | 112 | 543 | 0.655000 | 0.112000 | 0.655000 | 12.358491 | 6.588235 | 15.083333 |
4 | 10.000 | 6.868 | 817 | 6.051 | 0.686800 | 0.081700 | 0.686800 | 10.485497 | 7.294643 | 11.143646 |
5 | 100.000 | 69.276 | 6.123 | 63.153 | 0.692760 | 0.061230 | 0.692760 | 10.086780 | 7.494492 | 10.436788 |
6 | 1.000.000 | 692.923 | 49.919 | 643.004 | 0.692923 | 0.049919 | 0.692923 | 10.002353 | 8.152703 | 10.181685 |
7 | 10.000.000 | 6.928.737 | 421.270 | 6.507.467 | 0.692874 | 0.042127 | 0.692874 | 9.999289 | 8.439072 | 10.120415 |
8 | 100.000.000 | 69.276.898 | 3.656.211 | 65.620.687 | 0.692769 | 0.036562 | 0.692769 | 9.998488 | 8.679021 | 10.083906 |
9 | 1.000.000.000 | 692.716.054 | 32.272.314 | 660.443.740 | 0.692716 | 0.032272 | 0.692716 | 9.999236 | 8.826710 | 10.064566 |
10 | 10.000.000.000 | 6.926.875.811 | 288.810.112 | 6.638.065.699 | 0.692688 | 0.028881 | 0.692688 | 9.999589 | 8.949161 | 10.050919 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 9 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 2.000000 | 1.666667 |
4 | 16 | 14 | 6 | 8 | 0.875000 | 0.375000 | 0.500000 | 1.555556 | 1.500000 | 1.600000 |
5 | 32 | 17 | 7 | 10 | 0.531250 | 0.218750 | 0.312500 | 1.214286 | 1.166667 | 1.250000 |
6 | 64 | 29 | 10 | 19 | 0.453125 | 0.156250 | 0.296875 | 1.705882 | 1.428571 | 1.900000 |
7 | 128 | 69 | 20 | 49 | 0.539062 | 0.156250 | 0.382812 | 2.379310 | 2.000000 | 2.578947 |
8 | 256 | 153 | 38 | 115 | 0.597656 | 0.148438 | 0.449219 | 2.217391 | 1.900000 | 2.346939 |
9 | 512 | 330 | 62 | 268 | 0.644531 | 0.121094 | 0.523438 | 2.156863 | 1.631579 | 2.330435 |
10 | 1.024 | 672 | 112 | 560 | 0.656250 | 0.109375 | 0.546875 | 2.036364 | 1.806452 | 2.089552 |
11 | 2.048 | 1.385 | 207 | 1.178 | 0.676270 | 0.101074 | 0.575195 | 2.061012 | 1.848214 | 2.103571 |
12 | 4.096 | 2.788 | 379 | 2.409 | 0.680664 | 0.092529 | 0.588135 | 2.012996 | 1.830918 | 2.044991 |
13 | 8.192 | 5.611 | 691 | 4.920 | 0.684937 | 0.084351 | 0.600586 | 2.012554 | 1.823219 | 2.042341 |
14 | 16.384 | 11.292 | 1.231 | 10.061 | 0.689209 | 0.075134 | 0.614075 | 2.012475 | 1.781476 | 2.044919 |
15 | 32.768 | 22.664 | 2.242 | 20.422 | 0.691650 | 0.068420 | 0.623230 | 2.007085 | 1.821283 | 2.029818 |
16 | 65.536 | 45.405 | 4.170 | 41.235 | 0.692825 | 0.063629 | 0.629196 | 2.003397 | 1.859946 | 2.019146 |
17 | 131.072 | 90.850 | 7.828 | 83.022 | 0.693130 | 0.059723 | 0.633408 | 2.000881 | 1.877218 | 2.013387 |
18 | 262.144 | 181.668 | 14.755 | 166.913 | 0.693008 | 0.056286 | 0.636723 | 1.999648 | 1.884900 | 2.010467 |
19 | 524.288 | 363.438 | 27.685 | 335.753 | 0.693203 | 0.052805 | 0.640398 | 2.000561 | 1.876313 | 2.011545 |
20 | 1.048.576 | 726.661 | 52.147 | 674.514 | 0.692998 | 0.049731 | 0.643267 | 1.999408 | 1.883583 | 2.008959 |
21 | 2.097.152 | 1.452.961 | 98.894 | 1.354.067 | 0.692826 | 0.047156 | 0.645669 | 1.999503 | 1.896447 | 2.007471 |
22 | 4.194.304 | 2.905.924 | 188.140 | 2.717.784 | 0.692826 | 0.044856 | 0.647970 | 2.000001 | 1.902441 | 2.007127 |
23 | 8.388.608 | 5.812.475 | 357.537 | 5.454.938 | 0.692901 | 0.042622 | 0.650279 | 2.000216 | 1.900377 | 2.007127 |
24 | 16.777.216 | 11.623.884 | 683.502 | 10.940.382 | 0.692837 | 0.040740 | 0.652098 | 1.999817 | 1.911696 | 2.005592 |
25 | 33.554.432 | 23.247.519 | 1.309.003 | 21.938.516 | 0.692830 | 0.039011 | 0.653819 | 1.999979 | 1.915141 | 2.005279 |
26 | 67.108.864 | 46.492.958 | 2.511.000 | 43.981.958 | 0.692799 | 0.037417 | 0.655382 | 1.999910 | 1.918254 | 2.004783 |
27 | 134.217.728 | 92.981.709 | 4.825.424 | 88.156.285 | 0.692768 | 0.035952 | 0.656816 | 1.999910 | 1.921714 | 2.004374 |
28 | 268.435.456 | 185.961.445 | 9.283.447 | 176.677.998 | 0.692760 | 0.034584 | 0.658177 | 1.999979 | 1.923861 | 2.004145 |
29 | 536.870.912 | 371.908.848 | 17.894.234 | 354.014.614 | 0.692734 | 0.033331 | 0.659404 | 1.999925 | 1.927542 | 2.003728 |
30 | 1.073.741.824 | 743.801.413 | 34.527.221 | 709.274.192 | 0.692719 | 0.032156 | 0.660563 | 1.999956 | 1.929517 | 2.003517 |
31 | 2.147.483.648 | 1.487.571.314 | 66.701.815 | 1.420.869.499 | 0.692704 | 0.031060 | 0.661644 | 1.999958 | 1.931862 | 2.003273 |
32 | 4.294.967.296 | 2.975.109.716 | 129.023.849 | 2.846.085.867 | 0.692697 | 0.030041 | 0.662656 | 1.999978 | 1.934338 | 2.003059 |
33 | 8.589.934.592 | 5.950.161.747 | 249.819.206 | 5.700.342.541 | 0.692690 | 0.029083 | 0.663607 | 1.999981 | 1.936225 | 2.002871 |
34 | 17.179.869.184 | 11.900.206.982 | 484.229.250 | 11.415.977.732 | 0.692683 | 0.028186 | 0.664497 | 1.999980 | 1.938319 | 2.002683 |
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 | 2 | 0 | 0 | 1 | 1 |
2 | 4 | 2 | 0 | 2 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 1 | 3 | 0 | 1 | 1 | 2 |
4 | 16 | 6 | 3 | 3 | 0 | 2 | 1 | 3 |
5 | 32 | 7 | 4 | 3 | 0 | 2 | 1 | 4 |
6 | 64 | 10 | 4 | 6 | 1 | 2 | 3 | 4 |
7 | 128 | 20 | 7 | 13 | 3 | 2 | 11 | 4 |
8 | 256 | 38 | 15 | 23 | 13 | 2 | 19 | 4 |
9 | 512 | 62 | 25 | 37 | 28 | 2 | 28 | 4 |
10 | 1.024 | 112 | 42 | 70 | 54 | 2 | 52 | 4 |
11 | 2.048 | 207 | 74 | 133 | 99 | 2 | 102 | 4 |
12 | 4.096 | 379 | 130 | 249 | 188 | 2 | 185 | 4 |
13 | 8.192 | 691 | 228 | 463 | 340 | 2 | 345 | 4 |
14 | 16.384 | 1.231 | 406 | 825 | 601 | 2 | 624 | 4 |
15 | 32.768 | 2.242 | 735 | 1.507 | 1.113 | 2 | 1.123 | 4 |
16 | 65.536 | 4.170 | 1.384 | 2.786 | 2.073 | 2 | 2.091 | 4 |
17 | 131.072 | 7.828 | 2.564 | 5.264 | 3.876 | 2 | 3.946 | 4 |
18 | 262.144 | 14.755 | 4.840 | 9.915 | 7.322 | 2 | 7.427 | 4 |
19 | 524.288 | 27.685 | 9.139 | 18.546 | 13.811 | 2 | 13.868 | 4 |
20 | 1.048.576 | 52.147 | 17.292 | 34.855 | 26.006 | 2 | 26.135 | 4 |
21 | 2.097.152 | 98.894 | 32.793 | 66.101 | 49.463 | 2 | 49.425 | 4 |
22 | 4.194.304 | 188.140 | 62.592 | 125.548 | 93.980 | 2 | 94.154 | 4 |
23 | 8.388.608 | 357.537 | 119.216 | 238.321 | 178.568 | 2 | 178.963 | 4 |
24 | 16.777.216 | 683.502 | 227.736 | 455.766 | 341.758 | 2 | 341.738 | 4 |
25 | 33.554.432 | 1.309.003 | 436.304 | 872.699 | 655.156 | 2 | 653.841 | 4 |
26 | 67.108.864 | 2.511.000 | 836.964 | 1.674.036 | 1.256.673 | 2 | 1.254.321 | 4 |
27 | 134.217.728 | 4.825.424 | 1.608.869 | 3.216.555 | 2.413.769 | 2 | 2.411.649 | 4 |
28 | 268.435.456 | 9.283.447 | 3.094.224 | 6.189.223 | 4.642.103 | 2 | 4.641.338 | 4 |
29 | 536.870.912 | 17.894.234 | 5.964.817 | 11.929.417 | 8.946.801 | 2 | 8.947.427 | 4 |
30 | 1.073.741.824 | 34.527.221 | 11.509.101 | 23.018.120 | 17.264.400 | 2 | 17.262.815 | 4 |
31 | 2.147.483.648 | 66.701.815 | 22.228.121 | 44.473.694 | 33.352.698 | 2 | 33.349.111 | 4 |
32 | 4.294.967.296 | 129.023.849 | 43.003.603 | 86.020.246 | 64.510.625 | 2 | 64.513.218 | 4 |
33 | 8.589.934.592 | 249.819.206 | 83.279.629 | 166.539.577 | 124.903.802 | 2 | 124.915.398 | 4 |
34 | 17.179.869.184 | 484.229.250 | 161.416.398 | 322.812.852 | 242.107.485 | 2 | 242.121.759 | 4 |
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 | 1 | 0 |
2 | 4 | 3 | 0 | 3 | 1 | 0 | 1 | 1 |
3 | 8 | 5 | 1 | 4 | 2 | 0 | 2 | 1 |
4 | 16 | 8 | 2 | 6 | 2 | 1 | 3 | 2 |
5 | 32 | 10 | 3 | 7 | 2 | 1 | 5 | 2 |
6 | 64 | 19 | 9 | 10 | 3 | 5 | 6 | 5 |
7 | 128 | 49 | 23 | 26 | 7 | 12 | 13 | 17 |
8 | 256 | 115 | 67 | 48 | 18 | 32 | 25 | 40 |
9 | 512 | 268 | 153 | 115 | 53 | 76 | 54 | 85 |
10 | 1.024 | 560 | 292 | 268 | 115 | 161 | 120 | 164 |
11 | 2.048 | 1.178 | 602 | 576 | 247 | 342 | 253 | 336 |
12 | 4.096 | 2.409 | 1.297 | 1.112 | 488 | 687 | 526 | 708 |
13 | 8.192 | 4.920 | 2.628 | 2.292 | 1.029 | 1.375 | 1.080 | 1.436 |
14 | 16.384 | 10.061 | 5.309 | 4.752 | 2.146 | 2.818 | 2.228 | 2.869 |
15 | 32.768 | 20.422 | 10.678 | 9.744 | 4.448 | 5.734 | 4.562 | 5.678 |
16 | 65.536 | 41.235 | 21.349 | 19.886 | 9.191 | 11.387 | 9.234 | 11.423 |
17 | 131.072 | 83.022 | 42.810 | 40.212 | 18.620 | 22.789 | 18.854 | 22.759 |
18 | 262.144 | 166.913 | 85.916 | 80.997 | 37.695 | 45.443 | 38.064 | 45.711 |
19 | 524.288 | 335.753 | 172.711 | 163.042 | 76.564 | 91.232 | 76.782 | 91.175 |
20 | 1.048.576 | 674.514 | 346.217 | 328.297 | 155.004 | 182.436 | 155.117 | 181.957 |
21 | 2.097.152 | 1.354.067 | 693.790 | 660.277 | 312.834 | 364.518 | 313.332 | 363.383 |
22 | 4.194.304 | 2.717.784 | 1.391.516 | 1.326.268 | 631.065 | 729.280 | 631.228 | 726.211 |
23 | 8.388.608 | 5.454.938 | 2.786.194 | 2.668.744 | 1.272.055 | 1.456.865 | 1.271.537 | 1.454.481 |
24 | 16.777.216 | 10.940.382 | 5.584.755 | 5.355.627 | 2.557.278 | 2.913.429 | 2.559.925 | 2.909.750 |
25 | 33.554.432 | 21.938.516 | 11.188.657 | 10.749.859 | 5.146.384 | 5.824.139 | 5.148.316 | 5.819.677 |
26 | 67.108.864 | 43.981.958 | 22.412.523 | 21.569.435 | 10.349.061 | 11.643.309 | 10.349.892 | 11.639.696 |
27 | 134.217.728 | 88.156.285 | 44.887.402 | 43.268.883 | 20.797.270 | 23.278.488 | 20.801.781 | 23.278.746 |
28 | 268.435.456 | 176.677.998 | 89.899.393 | 86.778.605 | 41.781.710 | 46.548.065 | 41.795.184 | 46.553.039 |
29 | 536.870.912 | 354.014.614 | 180.019.993 | 173.994.621 | 83.910.738 | 93.097.461 | 83.917.376 | 93.089.039 |
30 | 1.073.741.824 | 709.274.192 | 360.437.151 | 348.837.041 | 168.471.782 | 186.164.744 | 168.480.382 | 186.157.284 |
31 | 2.147.483.648 | 1.420.869.499 | 721.626.013 | 699.243.486 | 338.146.766 | 372.307.873 | 338.140.281 | 372.274.579 |
32 | 4.294.967.296 | 2.846.085.867 | 1.444.697.311 | 1.401.388.556 | 678.531.772 | 744.500.843 | 678.540.743 | 744.512.509 |
33 | 8.589.934.592 | 5.700.342.541 | 2.892.121.852 | 2.808.220.689 | 1.361.300.556 | 1.488.882.509 | 1.361.253.410 | 1.488.906.066 |
34 | 17.179.869.184 | 11.415.977.732 | 5.789.284.146 | 5.626.693.586 | 2.730.427.112 | 2.977.557.549 | 2.730.392.386 | 2.977.600.685 |