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+96x-17
f(0)=17
f(1)=5
f(2)=179
f(3)=7
f(4)=383
f(5)=61
f(6)=1
f(7)=11
f(8)=163
f(9)=29
f(10)=149
f(11)=1
f(12)=1279
f(13)=1
f(14)=1523
f(15)=103
f(16)=71
f(17)=1
f(18)=37
f(19)=271
f(20)=47
f(21)=1
f(22)=2579
f(23)=1
f(24)=409
f(25)=1
f(26)=631
f(27)=59
f(28)=691
f(29)=41
f(30)=53
f(31)=1
f(32)=4079
f(33)=1
f(34)=1
f(35)=571
f(36)=947
f(37)=613
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=5779
f(43)=1
f(44)=6143
f(45)=113
f(46)=1303
f(47)=419
f(48)=197
f(49)=443
f(50)=7283
f(51)=1
f(52)=1097
f(53)=1
f(54)=137
f(55)=1
f(56)=1699
f(57)=1
f(58)=1783
f(59)=1
f(60)=9343
f(61)=239
f(62)=127
f(63)=1
f(64)=10223
f(65)=653
f(66)=1
f(67)=1
f(68)=131
f(69)=1
f(70)=283
f(71)=1
f(72)=257
f(73)=1
f(74)=739
f(75)=1601
f(76)=373
f(77)=1663
f(78)=2711
f(79)=863
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1373
f(85)=1
f(86)=1
f(87)=1
f(88)=647
f(89)=1
f(90)=2389
f(91)=1
f(92)=467
f(93)=439
f(94)=2549
f(95)=1
f(96)=1
f(97)=167
f(98)=1
f(99)=2411
b) Substitution of the polynom
The polynom f(x)=x^2+96x-17 could be written as f(y)= y^2-2321 with x=y-48
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+48
f'(x)>2x+95
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 59 | 13 | 46 | 0.590000 | 0.130000 | 0.590000 | 5.900000 | 4.333333 | 6.571429 |
3 | 1.000 | 595 | 90 | 505 | 0.595000 | 0.090000 | 0.595000 | 10.084745 | 6.923077 | 10.978261 |
4 | 10.000 | 6.180 | 644 | 5.536 | 0.618000 | 0.064400 | 0.618000 | 10.386555 | 7.155556 | 10.962377 |
5 | 100.000 | 63.441 | 4.979 | 58.462 | 0.634410 | 0.049790 | 0.634410 | 10.265534 | 7.731367 | 10.560332 |
6 | 1.000.000 | 645.558 | 40.490 | 605.068 | 0.645558 | 0.040490 | 0.645558 | 10.175722 | 8.132155 | 10.349766 |
7 | 10.000.000 | 6.524.204 | 341.839 | 6.182.365 | 0.652420 | 0.034184 | 0.652420 | 10.106302 | 8.442554 | 10.217637 |
8 | 100.000.000 | 65.770.040 | 2.968.524 | 62.801.516 | 0.657700 | 0.029685 | 0.657700 | 10.080930 | 8.683983 | 10.158170 |
9 | 1.000.000.000 | 661.723.196 | 26.205.502 | 635.517.694 | 0.661723 | 0.026206 | 0.661723 | 10.061165 | 8.827788 | 10.119464 |
10 | 10.000.000.000 | 6.649.356.721 | 234.471.170 | 6.414.885.551 | 0.664936 | 0.023447 | 0.664936 | 10.048547 | 8.947402 | 10.093952 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.000000 | 2.500000 |
4 | 16 | 14 | 5 | 9 | 0.875000 | 0.312500 | 0.562500 | 1.750000 | 1.666667 | 1.800000 |
5 | 32 | 23 | 7 | 16 | 0.718750 | 0.218750 | 0.500000 | 1.642857 | 1.400000 | 1.777778 |
6 | 64 | 42 | 12 | 30 | 0.656250 | 0.187500 | 0.468750 | 1.826087 | 1.714286 | 1.875000 |
7 | 128 | 75 | 16 | 59 | 0.585938 | 0.125000 | 0.460938 | 1.785714 | 1.333333 | 1.966667 |
8 | 256 | 150 | 28 | 122 | 0.585938 | 0.109375 | 0.476562 | 2.000000 | 1.750000 | 2.067797 |
9 | 512 | 300 | 54 | 246 | 0.585938 | 0.105469 | 0.480469 | 2.000000 | 1.928571 | 2.016393 |
10 | 1.024 | 611 | 91 | 520 | 0.596680 | 0.088867 | 0.507812 | 2.036667 | 1.685185 | 2.113821 |
11 | 2.048 | 1.239 | 167 | 1.072 | 0.604980 | 0.081543 | 0.523438 | 2.027823 | 1.835165 | 2.061538 |
12 | 4.096 | 2.504 | 304 | 2.200 | 0.611328 | 0.074219 | 0.537109 | 2.020985 | 1.820359 | 2.052239 |
13 | 8.192 | 5.052 | 547 | 4.505 | 0.616699 | 0.066772 | 0.549927 | 2.017572 | 1.799342 | 2.047727 |
14 | 16.384 | 10.197 | 1.007 | 9.190 | 0.622375 | 0.061462 | 0.560913 | 2.018409 | 1.840951 | 2.039956 |
15 | 32.768 | 20.564 | 1.820 | 18.744 | 0.627563 | 0.055542 | 0.572021 | 2.016672 | 1.807349 | 2.039608 |
16 | 65.536 | 41.459 | 3.379 | 38.080 | 0.632614 | 0.051559 | 0.581055 | 2.016096 | 1.856593 | 2.031584 |
17 | 131.072 | 83.338 | 6.365 | 76.973 | 0.635818 | 0.048561 | 0.587257 | 2.010130 | 1.883693 | 2.021350 |
18 | 262.144 | 167.791 | 11.872 | 155.919 | 0.640072 | 0.045288 | 0.594784 | 2.013379 | 1.865200 | 2.025632 |
19 | 524.288 | 337.175 | 22.389 | 314.786 | 0.643110 | 0.042704 | 0.600407 | 2.009494 | 1.885866 | 2.018907 |
20 | 1.048.576 | 677.155 | 42.329 | 634.826 | 0.645785 | 0.040368 | 0.605417 | 2.008319 | 1.890616 | 2.016691 |
21 | 2.097.152 | 1.358.708 | 80.210 | 1.278.498 | 0.647882 | 0.038247 | 0.609635 | 2.006495 | 1.894918 | 2.013935 |
22 | 4.194.304 | 2.726.079 | 152.225 | 2.573.854 | 0.649948 | 0.036293 | 0.613655 | 2.006376 | 1.897831 | 2.013186 |
23 | 8.388.608 | 5.468.944 | 290.401 | 5.178.543 | 0.651949 | 0.034618 | 0.617330 | 2.006158 | 1.907709 | 2.011980 |
24 | 16.777.216 | 10.968.635 | 555.081 | 10.413.554 | 0.653782 | 0.033085 | 0.620696 | 2.005622 | 1.911429 | 2.010904 |
25 | 33.554.432 | 21.991.716 | 1.062.913 | 20.928.803 | 0.655404 | 0.031677 | 0.623727 | 2.004964 | 1.914879 | 2.009766 |
26 | 67.108.864 | 44.083.635 | 2.038.325 | 42.045.310 | 0.656897 | 0.030373 | 0.626524 | 2.004556 | 1.917678 | 2.008969 |
27 | 134.217.728 | 88.349.874 | 3.918.979 | 84.430.895 | 0.658258 | 0.029199 | 0.629059 | 2.004142 | 1.922647 | 2.008093 |
28 | 268.435.456 | 177.044.007 | 7.539.658 | 169.504.349 | 0.659540 | 0.028087 | 0.631453 | 2.003896 | 1.923883 | 2.007611 |
29 | 536.870.912 | 354.729.632 | 14.528.251 | 340.201.381 | 0.660735 | 0.027061 | 0.633674 | 2.003624 | 1.926911 | 2.007036 |
30 | 1.073.741.824 | 710.636.432 | 28.036.292 | 682.600.140 | 0.661832 | 0.026111 | 0.635721 | 2.003319 | 1.929778 | 2.006459 |
31 | 2.147.483.648 | 1.423.504.109 | 54.165.909 | 1.369.338.200 | 0.662871 | 0.025223 | 0.637648 | 2.003140 | 1.931993 | 2.006062 |
32 | 4.294.967.296 | 2.851.151.404 | 104.746.634 | 2.746.404.770 | 0.663835 | 0.024388 | 0.639447 | 2.002911 | 1.933811 | 2.005644 |
33 | 8.589.934.592 | 5.710.105.104 | 202.822.445 | 5.507.282.659 | 0.664744 | 0.023612 | 0.641132 | 2.002737 | 1.936315 | 2.005270 |
34 | 17.179.869.184 | 11.434.905.941 | 393.125.021 | 11.041.780.920 | 0.665599 | 0.022883 | 0.642716 | 2.002573 | 1.938272 | 2.004942 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 3 | 1 | 1 | 0 | 1 |
3 | 8 | 3 | 0 | 3 | 1 | 1 | 0 | 1 |
4 | 16 | 5 | 1 | 4 | 1 | 2 | 0 | 2 |
5 | 32 | 7 | 1 | 6 | 1 | 3 | 0 | 3 |
6 | 64 | 12 | 3 | 9 | 1 | 5 | 0 | 6 |
7 | 128 | 16 | 4 | 12 | 1 | 6 | 0 | 9 |
8 | 256 | 28 | 7 | 21 | 1 | 10 | 0 | 17 |
9 | 512 | 54 | 13 | 41 | 1 | 23 | 0 | 30 |
10 | 1.024 | 91 | 28 | 63 | 1 | 44 | 0 | 46 |
11 | 2.048 | 167 | 53 | 114 | 1 | 82 | 0 | 84 |
12 | 4.096 | 304 | 96 | 208 | 1 | 160 | 0 | 143 |
13 | 8.192 | 547 | 186 | 361 | 1 | 288 | 0 | 258 |
14 | 16.384 | 1.007 | 322 | 685 | 1 | 511 | 0 | 495 |
15 | 32.768 | 1.820 | 591 | 1.229 | 1 | 907 | 0 | 912 |
16 | 65.536 | 3.379 | 1.130 | 2.249 | 1 | 1.688 | 0 | 1.690 |
17 | 131.072 | 6.365 | 2.138 | 4.227 | 1 | 3.195 | 0 | 3.169 |
18 | 262.144 | 11.872 | 3.936 | 7.936 | 1 | 5.966 | 0 | 5.905 |
19 | 524.288 | 22.389 | 7.458 | 14.931 | 1 | 11.220 | 0 | 11.168 |
20 | 1.048.576 | 42.329 | 14.092 | 28.237 | 1 | 21.147 | 0 | 21.181 |
21 | 2.097.152 | 80.210 | 26.706 | 53.504 | 1 | 40.122 | 0 | 40.087 |
22 | 4.194.304 | 152.225 | 50.751 | 101.474 | 1 | 76.220 | 0 | 76.004 |
23 | 8.388.608 | 290.401 | 96.666 | 193.735 | 1 | 145.481 | 0 | 144.919 |
24 | 16.777.216 | 555.081 | 184.778 | 370.303 | 1 | 277.839 | 0 | 277.241 |
25 | 33.554.432 | 1.062.913 | 354.048 | 708.865 | 1 | 531.645 | 0 | 531.267 |
26 | 67.108.864 | 2.038.325 | 679.773 | 1.358.552 | 1 | 1.019.760 | 0 | 1.018.564 |
27 | 134.217.728 | 3.918.979 | 1.306.426 | 2.612.553 | 1 | 1.959.958 | 0 | 1.959.020 |
28 | 268.435.456 | 7.539.658 | 2.513.880 | 5.025.778 | 1 | 3.771.038 | 0 | 3.768.619 |
29 | 536.870.912 | 14.528.251 | 4.843.214 | 9.685.037 | 1 | 7.266.366 | 0 | 7.261.884 |
30 | 1.073.741.824 | 28.036.292 | 9.345.584 | 18.690.708 | 1 | 14.018.678 | 0 | 14.017.613 |
31 | 2.147.483.648 | 54.165.909 | 18.055.119 | 36.110.790 | 1 | 27.087.121 | 0 | 27.078.787 |
32 | 4.294.967.296 | 104.746.634 | 34.914.631 | 69.832.003 | 1 | 52.381.473 | 0 | 52.365.160 |
33 | 8.589.934.592 | 202.822.445 | 67.599.641 | 135.222.804 | 1 | 101.410.919 | 0 | 101.411.525 |
34 | 17.179.869.184 | 393.125.021 | 131.033.020 | 262.092.001 | 1 | 196.559.084 | 0 | 196.565.936 |
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 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 5 | 3 | 2 | 0 | 2 | 2 | 1 |
4 | 16 | 9 | 4 | 5 | 0 | 2 | 4 | 3 |
5 | 32 | 16 | 9 | 7 | 1 | 4 | 5 | 6 |
6 | 64 | 30 | 15 | 15 | 4 | 9 | 7 | 10 |
7 | 128 | 59 | 25 | 34 | 11 | 15 | 15 | 18 |
8 | 256 | 122 | 60 | 62 | 25 | 34 | 27 | 36 |
9 | 512 | 246 | 126 | 120 | 52 | 63 | 60 | 71 |
10 | 1.024 | 520 | 255 | 265 | 112 | 133 | 124 | 151 |
11 | 2.048 | 1.072 | 520 | 552 | 243 | 292 | 257 | 280 |
12 | 4.096 | 2.200 | 1.106 | 1.094 | 510 | 582 | 546 | 562 |
13 | 8.192 | 4.505 | 2.284 | 2.221 | 1.069 | 1.179 | 1.079 | 1.178 |
14 | 16.384 | 9.190 | 4.702 | 4.488 | 2.214 | 2.439 | 2.201 | 2.336 |
15 | 32.768 | 18.744 | 9.559 | 9.185 | 4.514 | 4.876 | 4.513 | 4.841 |
16 | 65.536 | 38.080 | 19.451 | 18.629 | 9.157 | 9.889 | 9.238 | 9.796 |
17 | 131.072 | 76.973 | 39.212 | 37.761 | 18.730 | 19.789 | 18.610 | 19.844 |
18 | 262.144 | 155.919 | 79.391 | 76.528 | 37.988 | 40.134 | 37.868 | 39.929 |
19 | 524.288 | 314.786 | 160.126 | 154.660 | 76.877 | 80.481 | 77.036 | 80.392 |
20 | 1.048.576 | 634.826 | 322.656 | 312.170 | 155.038 | 162.213 | 155.365 | 162.210 |
21 | 2.097.152 | 1.278.498 | 648.686 | 629.812 | 312.550 | 326.015 | 313.827 | 326.106 |
22 | 4.194.304 | 2.573.854 | 1.305.106 | 1.268.748 | 631.452 | 654.991 | 632.252 | 655.159 |
23 | 8.388.608 | 5.178.543 | 2.622.735 | 2.555.808 | 1.271.800 | 1.316.633 | 1.273.714 | 1.316.396 |
24 | 16.777.216 | 10.413.554 | 5.271.249 | 5.142.305 | 2.560.266 | 2.645.513 | 2.562.238 | 2.645.537 |
25 | 33.554.432 | 20.928.803 | 10.588.368 | 10.340.435 | 5.150.794 | 5.314.816 | 5.151.113 | 5.312.080 |
26 | 67.108.864 | 42.045.310 | 21.264.001 | 20.781.309 | 10.355.896 | 10.669.445 | 10.353.850 | 10.666.119 |
27 | 134.217.728 | 84.430.895 | 42.680.681 | 41.750.214 | 20.811.568 | 21.409.498 | 20.806.528 | 21.403.301 |
28 | 268.435.456 | 169.504.349 | 85.650.966 | 83.853.383 | 41.810.743 | 42.952.171 | 41.799.255 | 42.942.180 |
29 | 536.870.912 | 340.201.381 | 171.827.669 | 168.373.712 | 83.954.092 | 86.154.761 | 83.944.635 | 86.147.893 |
30 | 1.073.741.824 | 682.600.140 | 344.611.178 | 337.988.962 | 168.520.389 | 172.770.917 | 168.534.032 | 172.774.802 |
31 | 2.147.483.648 | 1.369.338.200 | 691.058.597 | 678.279.603 | 338.225.477 | 346.447.115 | 338.231.959 | 346.433.649 |
32 | 4.294.967.296 | 2.746.404.770 | 1.385.520.458 | 1.360.884.312 | 678.662.613 | 694.540.173 | 678.669.024 | 694.532.960 |
33 | 8.589.934.592 | 5.507.282.659 | 2.777.434.139 | 2.729.848.520 | 1.361.484.278 | 1.392.147.520 | 1.361.498.439 | 1.392.152.422 |
34 | 17.179.869.184 | 11.041.780.920 | 5.566.958.597 | 5.474.822.323 | 2.730.795.872 | 2.790.114.352 | 2.730.761.415 | 2.790.109.281 |