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+13x+3
f(0)=3
f(1)=17
f(2)=11
f(3)=1
f(4)=71
f(5)=31
f(6)=13
f(7)=1
f(8)=19
f(9)=67
f(10)=233
f(11)=89
f(12)=101
f(13)=1
f(14)=127
f(15)=47
f(16)=467
f(17)=1
f(18)=1
f(19)=1
f(20)=1
f(21)=239
f(22)=773
f(23)=277
f(24)=1
f(25)=953
f(26)=113
f(27)=1
f(28)=1151
f(29)=37
f(30)=431
f(31)=1367
f(32)=1
f(33)=1
f(34)=1601
f(35)=1
f(36)=1
f(37)=109
f(38)=647
f(39)=677
f(40)=193
f(41)=739
f(42)=257
f(43)=2411
f(44)=1
f(45)=1
f(46)=1
f(47)=941
f(48)=977
f(49)=3041
f(50)=1051
f(51)=1
f(52)=199
f(53)=389
f(54)=1
f(55)=197
f(56)=1289
f(57)=1
f(58)=317
f(59)=1
f(60)=487
f(61)=4517
f(62)=1
f(63)=1597
f(64)=4931
f(65)=1
f(66)=1
f(67)=173
f(68)=167
f(69)=1
f(70)=5813
f(71)=1
f(72)=157
f(73)=571
f(74)=1
f(75)=1
f(76)=1
f(77)=2311
f(78)=263
f(79)=661
f(80)=827
f(81)=2539
f(82)=7793
f(83)=2657
f(84)=1
f(85)=641
f(86)=1
f(87)=967
f(88)=523
f(89)=1009
f(90)=281
f(91)=9467
f(92)=3221
f(93)=1
f(94)=10061
f(95)=311
f(96)=1163
f(97)=821
f(98)=1
f(99)=3697
b) Substitution of the polynom
The polynom f(x)=x^2+13x+3 could be written as f(y)= y^2-39.25 with x=y-6.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+6.5
f'(x)>2x+12
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 | 9 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 19 | 48 | 0.670000 | 0.190000 | 0.480000 | 7.444445 | 4.750000 | 9.600000 |
3 | 1.000 | 686 | 105 | 581 | 0.686000 | 0.105000 | 0.581000 | 10.238806 | 5.526316 | 12.104167 |
4 | 10.000 | 6.860 | 749 | 6.111 | 0.686000 | 0.074900 | 0.611100 | 10.000000 | 7.133333 | 10.518072 |
5 | 100.000 | 68.860 | 5.860 | 63.000 | 0.688600 | 0.058600 | 0.630000 | 10.037901 | 7.823765 | 10.309278 |
6 | 1.000.000 | 689.001 | 47.848 | 641.153 | 0.689001 | 0.047848 | 0.641153 | 10.005823 | 8.165188 | 10.177032 |
7 | 10.000.000 | 6.895.051 | 403.807 | 6.491.244 | 0.689505 | 0.040381 | 0.649124 | 10.007317 | 8.439370 | 10.124330 |
8 | 100.000.000 | 68.975.789 | 3.503.980 | 65.471.809 | 0.689758 | 0.035040 | 0.654718 | 10.003667 | 8.677363 | 10.086173 |
9 | 1.000.000.000 | 690.001.849 | 30.927.926 | 659.073.923 | 0.690002 | 0.030928 | 0.659074 | 10.003536 | 8.826513 | 10.066530 |
10 | 10.000.000.000 | 6.902.231.438 | 276.822.269 | 6.625.409.169 | 0.690223 | 0.027682 | 0.662541 | 10.003207 | 8.950561 | 10.052604 |
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 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.000000 | 4.000000 |
4 | 16 | 14 | 5 | 9 | 0.875000 | 0.312500 | 0.562500 | 2.000000 | 1.666667 | 2.250000 |
5 | 32 | 22 | 9 | 13 | 0.687500 | 0.281250 | 0.406250 | 1.571429 | 1.800000 | 1.444444 |
6 | 64 | 43 | 14 | 29 | 0.671875 | 0.218750 | 0.453125 | 1.954545 | 1.555556 | 2.230769 |
7 | 128 | 87 | 23 | 64 | 0.679688 | 0.179688 | 0.500000 | 2.023256 | 1.642857 | 2.206897 |
8 | 256 | 170 | 38 | 132 | 0.664062 | 0.148438 | 0.515625 | 1.954023 | 1.652174 | 2.062500 |
9 | 512 | 349 | 67 | 282 | 0.681641 | 0.130859 | 0.550781 | 2.052941 | 1.763158 | 2.136364 |
10 | 1.024 | 705 | 106 | 599 | 0.688477 | 0.103516 | 0.584961 | 2.020057 | 1.582090 | 2.124114 |
11 | 2.048 | 1.404 | 184 | 1.220 | 0.685547 | 0.089844 | 0.595703 | 1.991489 | 1.735849 | 2.036728 |
12 | 4.096 | 2.821 | 355 | 2.466 | 0.688721 | 0.086670 | 0.602051 | 2.009259 | 1.929348 | 2.021312 |
13 | 8.192 | 5.620 | 639 | 4.981 | 0.686035 | 0.078003 | 0.608032 | 1.992201 | 1.800000 | 2.019870 |
14 | 16.384 | 11.256 | 1.151 | 10.105 | 0.687012 | 0.070251 | 0.616760 | 2.002847 | 1.801252 | 2.028709 |
15 | 32.768 | 22.580 | 2.125 | 20.455 | 0.689087 | 0.064850 | 0.624237 | 2.006041 | 1.846221 | 2.024246 |
16 | 65.536 | 45.163 | 3.961 | 41.202 | 0.689133 | 0.060440 | 0.628693 | 2.000133 | 1.864000 | 2.014275 |
17 | 131.072 | 90.268 | 7.473 | 82.795 | 0.688690 | 0.057014 | 0.631676 | 1.998716 | 1.886645 | 2.009490 |
18 | 262.144 | 180.588 | 13.993 | 166.595 | 0.688889 | 0.053379 | 0.635509 | 2.000576 | 1.872474 | 2.012138 |
19 | 524.288 | 361.396 | 26.311 | 335.085 | 0.689308 | 0.050184 | 0.639124 | 2.001218 | 1.880297 | 2.011375 |
20 | 1.048.576 | 722.509 | 49.999 | 672.510 | 0.689038 | 0.047683 | 0.641356 | 1.999217 | 1.900308 | 2.006983 |
21 | 2.097.152 | 1.445.554 | 94.642 | 1.350.912 | 0.689294 | 0.045129 | 0.644165 | 2.000742 | 1.892878 | 2.008761 |
22 | 4.194.304 | 2.891.622 | 179.879 | 2.711.743 | 0.689416 | 0.042886 | 0.646530 | 2.000355 | 1.900625 | 2.007342 |
23 | 8.388.608 | 5.783.796 | 342.744 | 5.441.052 | 0.689482 | 0.040858 | 0.648624 | 2.000191 | 1.905414 | 2.006478 |
24 | 16.777.216 | 11.569.476 | 655.739 | 10.913.737 | 0.689595 | 0.039085 | 0.650509 | 2.000326 | 1.913203 | 2.005814 |
25 | 33.554.432 | 23.141.693 | 1.254.460 | 21.887.233 | 0.689676 | 0.037386 | 0.652290 | 2.000237 | 1.913048 | 2.005476 |
26 | 67.108.864 | 46.286.361 | 2.406.819 | 43.879.542 | 0.689721 | 0.035864 | 0.653856 | 2.000129 | 1.918610 | 2.004801 |
27 | 134.217.728 | 92.581.198 | 4.624.943 | 87.956.255 | 0.689784 | 0.034459 | 0.655325 | 2.000183 | 1.921600 | 2.004493 |
28 | 268.435.456 | 185.182.187 | 8.898.568 | 176.283.619 | 0.689857 | 0.033150 | 0.656708 | 2.000214 | 1.924038 | 2.004219 |
29 | 536.870.912 | 370.406.273 | 17.145.274 | 353.260.999 | 0.689935 | 0.031936 | 0.658000 | 2.000226 | 1.926745 | 2.003936 |
30 | 1.073.741.824 | 740.894.299 | 33.088.244 | 707.806.055 | 0.690012 | 0.030816 | 0.659196 | 2.000221 | 1.929875 | 2.003635 |
31 | 2.147.483.648 | 1.481.931.338 | 63.935.173 | 1.417.996.165 | 0.690078 | 0.029772 | 0.660306 | 2.000193 | 1.932262 | 2.003368 |
32 | 4.294.967.296 | 2.964.149.085 | 123.666.553 | 2.840.482.532 | 0.690145 | 0.028793 | 0.661351 | 2.000193 | 1.934249 | 2.003167 |
33 | 8.589.934.592 | 5.928.852.526 | 239.451.199 | 5.689.401.327 | 0.690209 | 0.027876 | 0.662333 | 2.000187 | 1.936265 | 2.002970 |
34 | 17.179.869.184 | 11.858.775.224 | 464.117.589 | 11.394.657.635 | 0.690272 | 0.027015 | 0.663256 | 2.000180 | 1.938255 | 2.002787 |
35 | 34.359.738.368 | 23.719.599.620 | 900.473.019 | 22.819.126.601 | 0.690331 | 0.026207 | 0.664124 | 2.000173 | 1.940183 | 2.002616 |
36 | 68.719.476.736 | 47.443.193.002 | 1.748.632.118 | 45.694.560.884 | 0.690389 | 0.025446 | 0.664943 | 2.000168 | 1.941904 | 2.002468 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
3 | 8 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
4 | 16 | 5 | 0 | 4 | 2 | 2 | 0 | 1 |
5 | 32 | 9 | 0 | 8 | 3 | 2 | 1 | 3 |
6 | 64 | 14 | 0 | 13 | 5 | 4 | 2 | 3 |
7 | 128 | 23 | 0 | 21 | 7 | 7 | 5 | 4 |
8 | 256 | 38 | 0 | 36 | 9 | 10 | 10 | 9 |
9 | 512 | 67 | 0 | 65 | 18 | 18 | 16 | 15 |
10 | 1.024 | 106 | 0 | 104 | 26 | 29 | 27 | 24 |
11 | 2.048 | 184 | 0 | 182 | 44 | 50 | 47 | 43 |
12 | 4.096 | 355 | 0 | 353 | 92 | 94 | 82 | 87 |
13 | 8.192 | 639 | 0 | 637 | 156 | 170 | 155 | 158 |
14 | 16.384 | 1.151 | 0 | 1.149 | 285 | 295 | 275 | 296 |
15 | 32.768 | 2.125 | 0 | 2.123 | 532 | 538 | 523 | 532 |
16 | 65.536 | 3.961 | 0 | 3.959 | 966 | 1.018 | 993 | 984 |
17 | 131.072 | 7.473 | 0 | 7.471 | 1.848 | 1.879 | 1.885 | 1.861 |
18 | 262.144 | 13.993 | 0 | 13.991 | 3.446 | 3.512 | 3.535 | 3.500 |
19 | 524.288 | 26.311 | 0 | 26.309 | 6.583 | 6.606 | 6.565 | 6.557 |
20 | 1.048.576 | 49.999 | 0 | 49.997 | 12.488 | 12.513 | 12.563 | 12.435 |
21 | 2.097.152 | 94.642 | 0 | 94.640 | 23.711 | 23.772 | 23.674 | 23.485 |
22 | 4.194.304 | 179.879 | 0 | 179.877 | 44.941 | 45.181 | 44.993 | 44.764 |
23 | 8.388.608 | 342.744 | 0 | 342.742 | 85.815 | 86.014 | 85.527 | 85.388 |
24 | 16.777.216 | 655.739 | 0 | 655.737 | 163.940 | 164.236 | 163.816 | 163.747 |
25 | 33.554.432 | 1.254.460 | 0 | 1.254.458 | 313.498 | 314.039 | 313.414 | 313.509 |
26 | 67.108.864 | 2.406.819 | 0 | 2.406.817 | 601.015 | 601.967 | 601.755 | 602.082 |
27 | 134.217.728 | 4.624.943 | 0 | 4.624.941 | 1.155.254 | 1.156.636 | 1.156.671 | 1.156.382 |
28 | 268.435.456 | 8.898.568 | 0 | 8.898.566 | 2.223.497 | 2.225.587 | 2.224.336 | 2.225.148 |
29 | 536.870.912 | 17.145.274 | 0 | 17.145.272 | 4.283.493 | 4.287.820 | 4.285.955 | 4.288.006 |
30 | 1.073.741.824 | 33.088.244 | 0 | 33.088.242 | 8.269.103 | 8.274.546 | 8.269.468 | 8.275.127 |
31 | 2.147.483.648 | 63.935.173 | 0 | 63.935.171 | 15.980.917 | 15.986.274 | 15.981.197 | 15.986.785 |
32 | 4.294.967.296 | 123.666.553 | 0 | 123.666.551 | 30.916.737 | 30.918.727 | 30.914.177 | 30.916.912 |
33 | 8.589.934.592 | 239.451.199 | 0 | 239.451.197 | 59.859.159 | 59.863.111 | 59.863.982 | 59.864.947 |
34 | 17.179.869.184 | 464.117.589 | 0 | 464.117.587 | 116.036.562 | 116.030.007 | 116.028.721 | 116.022.299 |
35 | 34.359.738.368 | 900.473.019 | 0 | 900.473.017 | 225.122.202 | 225.126.789 | 225.105.241 | 225.118.787 |
36 | 68.719.476.736 | 1.748.632.118 | 0 | 1.748.632.116 | 437.156.749 | 437.165.149 | 437.154.076 | 437.156.144 |
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 | 4 | 3 | 1 | 0 | 2 | 1 | 1 |
4 | 16 | 9 | 5 | 4 | 1 | 3 | 2 | 3 |
5 | 32 | 13 | 6 | 7 | 2 | 3 | 3 | 5 |
6 | 64 | 29 | 13 | 16 | 6 | 5 | 10 | 8 |
7 | 128 | 64 | 30 | 34 | 15 | 15 | 18 | 16 |
8 | 256 | 132 | 63 | 69 | 32 | 34 | 31 | 35 |
9 | 512 | 282 | 146 | 136 | 69 | 69 | 72 | 72 |
10 | 1.024 | 599 | 306 | 293 | 146 | 147 | 154 | 152 |
11 | 2.048 | 1.220 | 632 | 588 | 298 | 306 | 310 | 306 |
12 | 4.096 | 2.466 | 1.244 | 1.222 | 606 | 613 | 627 | 620 |
13 | 8.192 | 4.981 | 2.531 | 2.450 | 1.263 | 1.247 | 1.220 | 1.251 |
14 | 16.384 | 10.105 | 5.146 | 4.959 | 2.537 | 2.531 | 2.506 | 2.531 |
15 | 32.768 | 20.455 | 10.342 | 10.113 | 5.059 | 5.076 | 5.131 | 5.189 |
16 | 65.536 | 41.202 | 20.721 | 20.481 | 10.248 | 10.261 | 10.316 | 10.377 |
17 | 131.072 | 82.795 | 41.606 | 41.189 | 20.646 | 20.605 | 20.785 | 20.759 |
18 | 262.144 | 166.595 | 83.613 | 82.982 | 41.496 | 41.789 | 41.553 | 41.757 |
19 | 524.288 | 335.085 | 168.373 | 166.712 | 83.401 | 84.018 | 83.784 | 83.882 |
20 | 1.048.576 | 672.510 | 337.754 | 334.756 | 167.679 | 168.142 | 168.469 | 168.220 |
21 | 2.097.152 | 1.350.912 | 678.685 | 672.227 | 337.138 | 338.236 | 337.979 | 337.559 |
22 | 4.194.304 | 2.711.743 | 1.361.949 | 1.349.794 | 677.863 | 678.393 | 677.779 | 677.708 |
23 | 8.388.608 | 5.441.052 | 2.731.900 | 2.709.152 | 1.359.770 | 1.360.481 | 1.359.719 | 1.361.082 |
24 | 16.777.216 | 10.913.737 | 5.475.491 | 5.438.246 | 2.727.689 | 2.728.062 | 2.727.796 | 2.730.190 |
25 | 33.554.432 | 21.887.233 | 10.981.348 | 10.905.885 | 5.470.980 | 5.470.300 | 5.471.415 | 5.474.538 |
26 | 67.108.864 | 43.879.542 | 22.016.914 | 21.862.628 | 10.971.018 | 10.967.312 | 10.970.671 | 10.970.541 |
27 | 134.217.728 | 87.956.255 | 44.118.467 | 43.837.788 | 21.989.050 | 21.988.817 | 21.987.240 | 21.991.148 |
28 | 268.435.456 | 176.283.619 | 88.411.062 | 87.872.557 | 44.064.997 | 44.076.846 | 44.068.705 | 44.073.071 |
29 | 536.870.912 | 353.260.999 | 177.143.751 | 176.117.248 | 88.311.884 | 88.327.617 | 88.312.216 | 88.309.282 |
30 | 1.073.741.824 | 707.806.055 | 354.875.794 | 352.930.261 | 176.958.797 | 176.965.605 | 176.944.969 | 176.936.684 |
31 | 2.147.483.648 | 1.417.996.165 | 710.880.526 | 707.115.639 | 354.495.564 | 354.517.308 | 354.496.953 | 354.486.340 |
32 | 4.294.967.296 | 2.840.482.532 | 1.423.895.997 | 1.416.586.535 | 710.105.539 | 710.119.763 | 710.122.922 | 710.134.308 |
33 | 8.589.934.592 | 5.689.401.327 | 2.851.732.390 | 2.837.668.937 | 1.422.310.970 | 1.422.346.688 | 1.422.346.987 | 1.422.396.682 |
34 | 17.179.869.184 | 11.394.657.635 | 5.710.906.704 | 5.683.750.931 | 2.848.652.333 | 2.848.655.443 | 2.848.620.739 | 2.848.729.120 |
35 | 34.359.738.368 | 22.819.126.601 | 11.435.769.605 | 11.383.356.996 | 5.704.756.866 | 5.704.798.879 | 5.704.738.955 | 5.704.831.901 |
36 | 68.719.476.736 | 45.694.560.884 | 22.897.950.519 | 22.796.610.365 | 11.423.585.800 | 11.423.702.963 | 11.423.598.529 | 11.423.673.592 |