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-72x-23
f(0)=23
f(1)=47
f(2)=163
f(3)=5
f(4)=59
f(5)=179
f(6)=419
f(7)=239
f(8)=107
f(9)=1
f(10)=643
f(11)=347
f(12)=743
f(13)=79
f(14)=167
f(15)=439
f(16)=919
f(17)=479
f(18)=199
f(19)=103
f(20)=1063
f(21)=547
f(22)=1123
f(23)=1
f(24)=1
f(25)=599
f(26)=53
f(27)=619
f(28)=251
f(29)=127
f(30)=1283
f(31)=647
f(32)=1303
f(33)=131
f(34)=263
f(35)=659
f(36)=1319
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=101
f(76)=281
f(77)=181
f(78)=89
f(79)=1
f(80)=617
f(81)=353
f(82)=797
f(83)=1
f(84)=197
f(85)=541
f(86)=1181
f(87)=641
f(88)=277
f(89)=149
f(90)=1597
f(91)=853
f(92)=1
f(93)=193
f(94)=409
f(95)=1
f(96)=2281
f(97)=1201
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-72x-23 could be written as f(y)= y^2-1319 with x=y+36
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-36
f'(x)>2x-73 with x > 36
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 | 7 | 2 | 0.900000 | 0.700000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 50 | 35 | 15 | 0.500000 | 0.350000 | 0.150000 | 5.555555 | 5.000000 | 7.500000 |
3 | 1.000 | 725 | 328 | 397 | 0.725000 | 0.328000 | 0.397000 | 14.500000 | 9.371428 | 26.466667 |
4 | 10.000 | 7.483 | 2.344 | 5.139 | 0.748300 | 0.234400 | 0.513900 | 10.321380 | 7.146341 | 12.944585 |
5 | 100.000 | 74.007 | 18.034 | 55.973 | 0.740070 | 0.180340 | 0.559730 | 9.890018 | 7.693686 | 10.891808 |
6 | 1.000.000 | 730.794 | 147.652 | 583.142 | 0.730794 | 0.147652 | 0.583142 | 9.874660 | 8.187424 | 10.418273 |
7 | 10.000.000 | 7.253.098 | 1.245.366 | 6.007.732 | 0.725310 | 0.124537 | 0.600773 | 9.924955 | 8.434467 | 10.302348 |
8 | 100.000.000 | 72.103.756 | 10.770.139 | 61.333.617 | 0.721038 | 0.107701 | 0.613336 | 9.941098 | 8.648171 | 10.209113 |
9 | 1.000.000.000 | 717.763.227 | 94.898.127 | 622.865.100 | 0.717763 | 0.094898 | 0.622865 | 9.954588 | 8.811226 | 10.155362 |
10 | 10.000.000.000 | 7.151.575.047 | 848.413.819 | 6.303.161.228 | 0.715158 | 0.084841 | 0.630316 | 9.963697 | 8.940259 | 10.119625 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.000000 | inf |
3 | 8 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 2.000000 | 2.000000 | 2.000000 |
4 | 16 | 15 | 11 | 4 | 0.937500 | 0.687500 | 0.250000 | 1.875000 | 1.833333 | 2.000000 |
5 | 32 | 29 | 20 | 9 | 0.906250 | 0.625000 | 0.281250 | 1.933333 | 1.818182 | 2.250000 |
6 | 64 | 33 | 22 | 11 | 0.515625 | 0.343750 | 0.171875 | 1.137931 | 1.100000 | 1.222222 |
7 | 128 | 73 | 49 | 24 | 0.570312 | 0.382812 | 0.187500 | 2.212121 | 2.227273 | 2.181818 |
8 | 256 | 169 | 96 | 73 | 0.660156 | 0.375000 | 0.285156 | 2.315068 | 1.959184 | 3.041667 |
9 | 512 | 363 | 181 | 182 | 0.708984 | 0.353516 | 0.355469 | 2.147929 | 1.885417 | 2.493151 |
10 | 1.024 | 745 | 336 | 409 | 0.727539 | 0.328125 | 0.399414 | 2.052342 | 1.856354 | 2.247253 |
11 | 2.048 | 1.520 | 597 | 923 | 0.742188 | 0.291504 | 0.450684 | 2.040268 | 1.776786 | 2.256724 |
12 | 4.096 | 3.057 | 1.091 | 1.966 | 0.746338 | 0.266357 | 0.479980 | 2.011184 | 1.827471 | 2.130011 |
13 | 8.192 | 6.131 | 1.959 | 4.172 | 0.748413 | 0.239136 | 0.509277 | 2.005561 | 1.795600 | 2.122075 |
14 | 16.384 | 12.228 | 3.617 | 8.611 | 0.746338 | 0.220764 | 0.525574 | 1.994454 | 1.846350 | 2.063998 |
15 | 32.768 | 24.369 | 6.672 | 17.697 | 0.743683 | 0.203613 | 0.540070 | 1.992885 | 1.844623 | 2.055162 |
16 | 65.536 | 48.587 | 12.363 | 36.224 | 0.741379 | 0.188644 | 0.552734 | 1.993804 | 1.852968 | 2.046901 |
17 | 131.072 | 96.751 | 23.035 | 73.716 | 0.738152 | 0.175743 | 0.562408 | 1.991294 | 1.863221 | 2.035004 |
18 | 262.144 | 192.875 | 43.309 | 149.566 | 0.735760 | 0.165211 | 0.570549 | 1.993519 | 1.880139 | 2.028949 |
19 | 524.288 | 384.250 | 81.587 | 302.663 | 0.732899 | 0.155615 | 0.577284 | 1.992223 | 1.883835 | 2.023608 |
20 | 1.048.576 | 766.211 | 154.208 | 612.003 | 0.730716 | 0.147064 | 0.583652 | 1.994043 | 1.890105 | 2.022061 |
21 | 2.097.152 | 1.528.279 | 292.541 | 1.235.738 | 0.728740 | 0.139494 | 0.589246 | 1.994593 | 1.897055 | 2.019170 |
22 | 4.194.304 | 3.049.536 | 555.689 | 2.493.847 | 0.727066 | 0.132487 | 0.594579 | 1.995405 | 1.899525 | 2.018103 |
23 | 8.388.608 | 6.086.590 | 1.057.588 | 5.029.002 | 0.725578 | 0.126074 | 0.599504 | 1.995907 | 1.903201 | 2.016564 |
24 | 16.777.216 | 12.151.219 | 2.017.954 | 10.133.265 | 0.724269 | 0.120279 | 0.603990 | 1.996392 | 1.908072 | 2.014965 |
25 | 33.554.432 | 24.257.214 | 3.860.778 | 20.396.436 | 0.722921 | 0.115060 | 0.607861 | 1.996278 | 1.913214 | 2.012820 |
26 | 67.108.864 | 48.431.889 | 7.401.373 | 41.030.516 | 0.721691 | 0.110289 | 0.611402 | 1.996597 | 1.917068 | 2.011651 |
27 | 134.217.728 | 96.713.953 | 14.208.985 | 82.504.968 | 0.720575 | 0.105865 | 0.614710 | 1.996907 | 1.919777 | 2.010820 |
28 | 268.435.456 | 193.150.473 | 27.327.777 | 165.822.696 | 0.719542 | 0.101804 | 0.617738 | 1.997131 | 1.923274 | 2.009851 |
29 | 536.870.912 | 385.782.399 | 52.634.527 | 333.147.872 | 0.718576 | 0.098039 | 0.620536 | 1.997315 | 1.926045 | 2.009061 |
30 | 1.073.741.824 | 770.599.735 | 101.521.121 | 669.078.614 | 0.717677 | 0.094549 | 0.623128 | 1.997498 | 1.928793 | 2.008353 |
31 | 2.147.483.648 | 1.539.389.658 | 196.077.526 | 1.343.312.132 | 0.716834 | 0.091306 | 0.625528 | 1.997651 | 1.931396 | 2.007704 |
32 | 4.294.967.296 | 3.075.413.295 | 379.121.284 | 2.696.292.011 | 0.716050 | 0.088271 | 0.627779 | 1.997813 | 1.933527 | 2.007197 |
33 | 8.589.934.592 | 6.144.503.384 | 733.901.927 | 5.410.601.457 | 0.715314 | 0.085437 | 0.629877 | 1.997944 | 1.935797 | 2.006682 |
34 | 17.179.869.184 | 12.277.110.833 | 1.422.197.791 | 10.854.913.042 | 0.714622 | 0.082783 | 0.631839 | 1.998064 | 1.937858 | 2.006230 |
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 | 3 | 1 | 2 | 0 | 1 | 0 | 2 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 0 | 2 |
3 | 8 | 6 | 1 | 5 | 0 | 3 | 0 | 3 |
4 | 16 | 11 | 4 | 7 | 0 | 5 | 0 | 6 |
5 | 32 | 20 | 9 | 11 | 0 | 9 | 0 | 11 |
6 | 64 | 22 | 9 | 13 | 0 | 10 | 0 | 12 |
7 | 128 | 49 | 22 | 27 | 13 | 10 | 14 | 12 |
8 | 256 | 96 | 45 | 51 | 37 | 10 | 37 | 12 |
9 | 512 | 181 | 88 | 93 | 78 | 10 | 81 | 12 |
10 | 1.024 | 336 | 163 | 173 | 154 | 10 | 160 | 12 |
11 | 2.048 | 597 | 295 | 302 | 294 | 10 | 281 | 12 |
12 | 4.096 | 1.091 | 552 | 539 | 535 | 10 | 534 | 12 |
13 | 8.192 | 1.959 | 999 | 960 | 950 | 10 | 987 | 12 |
14 | 16.384 | 3.617 | 1.829 | 1.788 | 1.808 | 10 | 1.787 | 12 |
15 | 32.768 | 6.672 | 3.400 | 3.272 | 3.323 | 10 | 3.327 | 12 |
16 | 65.536 | 12.363 | 6.300 | 6.063 | 6.127 | 10 | 6.214 | 12 |
17 | 131.072 | 23.035 | 11.682 | 11.353 | 11.477 | 10 | 11.536 | 12 |
18 | 262.144 | 43.309 | 21.834 | 21.475 | 21.664 | 10 | 21.623 | 12 |
19 | 524.288 | 81.587 | 41.029 | 40.558 | 40.787 | 10 | 40.778 | 12 |
20 | 1.048.576 | 154.208 | 77.350 | 76.858 | 77.122 | 10 | 77.064 | 12 |
21 | 2.097.152 | 292.541 | 146.893 | 145.648 | 146.198 | 10 | 146.321 | 12 |
22 | 4.194.304 | 555.689 | 279.115 | 276.574 | 277.707 | 10 | 277.960 | 12 |
23 | 8.388.608 | 1.057.588 | 531.408 | 526.180 | 528.517 | 10 | 529.049 | 12 |
24 | 16.777.216 | 2.017.954 | 1.013.784 | 1.004.170 | 1.009.231 | 10 | 1.008.701 | 12 |
25 | 33.554.432 | 3.860.778 | 1.938.461 | 1.922.317 | 1.930.454 | 10 | 1.930.302 | 12 |
26 | 67.108.864 | 7.401.373 | 3.713.919 | 3.687.454 | 3.700.555 | 10 | 3.700.796 | 12 |
27 | 134.217.728 | 14.208.985 | 7.128.848 | 7.080.137 | 7.103.852 | 10 | 7.105.111 | 12 |
28 | 268.435.456 | 27.327.777 | 13.707.448 | 13.620.329 | 13.664.165 | 10 | 13.663.590 | 12 |
29 | 536.870.912 | 52.634.527 | 26.400.196 | 26.234.331 | 26.318.182 | 10 | 26.316.323 | 12 |
30 | 1.073.741.824 | 101.521.121 | 50.909.275 | 50.611.846 | 50.759.630 | 10 | 50.761.469 | 12 |
31 | 2.147.483.648 | 196.077.526 | 98.317.591 | 97.759.935 | 98.039.886 | 10 | 98.037.618 | 12 |
32 | 4.294.967.296 | 379.121.284 | 190.082.662 | 189.038.622 | 189.554.948 | 10 | 189.566.314 | 12 |
33 | 8.589.934.592 | 733.901.927 | 367.928.863 | 365.973.064 | 366.961.454 | 10 | 366.940.451 | 12 |
34 | 17.179.869.184 | 1.422.197.791 | 712.942.540 | 709.255.251 | 711.118.144 | 10 | 711.079.625 | 12 |
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 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 2 | 0 | 2 | 0 | 0 |
4 | 16 | 4 | 1 | 3 | 0 | 2 | 0 | 2 |
5 | 32 | 9 | 4 | 5 | 0 | 3 | 1 | 5 |
6 | 64 | 11 | 4 | 7 | 0 | 4 | 1 | 6 |
7 | 128 | 24 | 9 | 15 | 5 | 4 | 9 | 6 |
8 | 256 | 73 | 35 | 38 | 27 | 9 | 28 | 9 |
9 | 512 | 182 | 83 | 99 | 64 | 26 | 69 | 23 |
10 | 1.024 | 409 | 191 | 218 | 142 | 67 | 140 | 60 |
11 | 2.048 | 923 | 448 | 475 | 300 | 167 | 293 | 163 |
12 | 4.096 | 1.966 | 951 | 1.015 | 601 | 385 | 603 | 377 |
13 | 8.192 | 4.172 | 2.025 | 2.147 | 1.220 | 862 | 1.238 | 852 |
14 | 16.384 | 8.611 | 4.236 | 4.375 | 2.489 | 1.839 | 2.467 | 1.816 |
15 | 32.768 | 17.697 | 8.741 | 8.956 | 5.007 | 3.871 | 5.038 | 3.781 |
16 | 65.536 | 36.224 | 18.004 | 18.220 | 10.157 | 7.992 | 10.183 | 7.892 |
17 | 131.072 | 73.716 | 36.779 | 36.937 | 20.572 | 16.412 | 20.473 | 16.259 |
18 | 262.144 | 149.566 | 74.685 | 74.881 | 41.182 | 33.469 | 41.206 | 33.709 |
19 | 524.288 | 302.663 | 150.939 | 151.724 | 82.940 | 68.317 | 82.969 | 68.437 |
20 | 1.048.576 | 612.003 | 305.471 | 306.532 | 166.949 | 139.132 | 166.936 | 138.986 |
21 | 2.097.152 | 1.235.738 | 616.537 | 619.201 | 335.780 | 282.479 | 335.563 | 281.916 |
22 | 4.194.304 | 2.493.847 | 1.245.669 | 1.248.178 | 674.024 | 573.018 | 673.663 | 573.142 |
23 | 8.388.608 | 5.029.002 | 2.513.016 | 2.515.986 | 1.352.999 | 1.160.755 | 1.354.136 | 1.161.112 |
24 | 16.777.216 | 10.133.265 | 5.064.687 | 5.068.578 | 2.716.459 | 2.348.550 | 2.718.277 | 2.349.979 |
25 | 33.554.432 | 20.396.436 | 10.193.006 | 10.203.430 | 5.450.536 | 4.746.891 | 5.452.252 | 4.746.757 |
26 | 67.108.864 | 41.030.516 | 20.505.996 | 20.524.520 | 10.933.369 | 9.580.307 | 10.934.715 | 9.582.125 |
27 | 134.217.728 | 82.504.968 | 41.240.494 | 41.264.474 | 21.922.675 | 19.327.921 | 21.929.011 | 19.325.361 |
28 | 268.435.456 | 165.822.696 | 82.886.804 | 82.935.892 | 43.954.783 | 38.952.440 | 43.962.938 | 38.952.535 |
29 | 536.870.912 | 333.147.872 | 166.527.377 | 166.620.495 | 88.106.797 | 78.455.015 | 88.124.241 | 78.461.819 |
30 | 1.073.741.824 | 669.078.614 | 334.450.608 | 334.628.006 | 176.590.245 | 157.936.188 | 176.589.857 | 157.962.324 |
31 | 2.147.483.648 | 1.343.312.132 | 671.479.751 | 671.832.381 | 353.836.328 | 317.803.238 | 353.836.713 | 317.835.853 |
32 | 4.294.967.296 | 2.696.292.011 | 1.347.807.575 | 1.348.484.436 | 708.901.490 | 639.212.283 | 708.919.300 | 639.258.938 |
33 | 8.589.934.592 | 5.410.601.457 | 2.704.655.555 | 2.705.945.902 | 1.420.081.653 | 1.285.162.903 | 1.420.122.437 | 1.285.234.464 |
34 | 17.179.869.184 | 10.854.913.042 | 5.426.234.250 | 5.428.678.792 | 2.844.466.487 | 2.582.942.879 | 2.844.457.432 | 2.583.046.244 |