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+17x-127
f(0)=127
f(1)=109
f(2)=89
f(3)=67
f(4)=43
f(5)=17
f(6)=11
f(7)=41
f(8)=73
f(9)=107
f(10)=13
f(11)=181
f(12)=1
f(13)=263
f(14)=307
f(15)=353
f(16)=401
f(17)=1
f(18)=503
f(19)=557
f(20)=613
f(21)=61
f(22)=1
f(23)=1
f(24)=857
f(25)=71
f(26)=991
f(27)=1061
f(28)=103
f(29)=1
f(30)=1283
f(31)=1361
f(32)=131
f(33)=1523
f(34)=1607
f(35)=1693
f(36)=137
f(37)=1871
f(38)=151
f(39)=1
f(40)=2153
f(41)=2251
f(42)=2351
f(43)=223
f(44)=2557
f(45)=2663
f(46)=163
f(47)=1
f(48)=1
f(49)=239
f(50)=293
f(51)=257
f(52)=3461
f(53)=3583
f(54)=337
f(55)=3833
f(56)=233
f(57)=4091
f(58)=1
f(59)=4357
f(60)=4493
f(61)=421
f(62)=367
f(63)=1
f(64)=389
f(65)=1
f(66)=5351
f(67)=5501
f(68)=5653
f(69)=5807
f(70)=1
f(71)=6121
f(72)=571
f(73)=379
f(74)=6607
f(75)=521
f(76)=631
f(77)=547
f(78)=7283
f(79)=7457
f(80)=449
f(81)=1
f(82)=1
f(83)=743
f(84)=1
f(85)=8543
f(86)=8731
f(87)=811
f(88)=701
f(89)=227
f(90)=1
f(91)=1
f(92)=9901
f(93)=10103
f(94)=937
f(95)=10513
f(96)=1
f(97)=643
f(98)=1013
f(99)=277
b) Substitution of the polynom
The polynom f(x)=x^2+17x-127 could be written as f(y)= y^2-199.25 with x=y-8.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+8.5
f'(x)>2x+16
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 | 9 | 0 | 0.900000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 80 | 50 | 30 | 0.800000 | 0.500000 | 0.300000 | 8.888889 | 5.555555 | inf |
3 | 1.000 | 751 | 328 | 423 | 0.751000 | 0.328000 | 0.423000 | 9.387500 | 6.560000 | 14.100000 |
4 | 10.000 | 7.361 | 2.363 | 4.998 | 0.736100 | 0.236300 | 0.499800 | 9.801598 | 7.204268 | 11.815603 |
5 | 100.000 | 72.991 | 18.149 | 54.842 | 0.729910 | 0.181490 | 0.548420 | 9.915908 | 7.680491 | 10.972789 |
6 | 1.000.000 | 724.093 | 147.500 | 576.593 | 0.724093 | 0.147500 | 0.576593 | 9.920305 | 8.127170 | 10.513712 |
7 | 10.000.000 | 7.194.132 | 1.249.820 | 5.944.312 | 0.719413 | 0.124982 | 0.594431 | 9.935370 | 8.473356 | 10.309373 |
8 | 100.000.000 | 71.584.590 | 10.829.037 | 60.755.553 | 0.715846 | 0.108290 | 0.607556 | 9.950414 | 8.664477 | 10.220788 |
9 | 1.000.000.000 | 713.206.575 | 95.546.552 | 617.660.023 | 0.713207 | 0.095547 | 0.617660 | 9.963130 | 8.823181 | 10.166314 |
10 | 10.000.000.000 | 7.111.030.067 | 855.053.941 | 6.255.976.126 | 0.711103 | 0.085505 | 0.625598 | 9.970506 | 8.949082 | 10.128510 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 8 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.600000 | 1.600000 | -nan |
4 | 16 | 14 | 14 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.750000 | 1.750000 | -nan |
5 | 32 | 26 | 22 | 4 | 0.812500 | 0.687500 | 0.125000 | 1.857143 | 1.571429 | inf |
6 | 64 | 53 | 37 | 16 | 0.828125 | 0.578125 | 0.250000 | 2.038461 | 1.681818 | 4.000000 |
7 | 128 | 103 | 65 | 38 | 0.804688 | 0.507812 | 0.296875 | 1.943396 | 1.756757 | 2.375000 |
8 | 256 | 197 | 111 | 86 | 0.769531 | 0.433594 | 0.335938 | 1.912621 | 1.707692 | 2.263158 |
9 | 512 | 390 | 194 | 196 | 0.761719 | 0.378906 | 0.382812 | 1.979695 | 1.747748 | 2.279070 |
10 | 1.024 | 769 | 336 | 433 | 0.750977 | 0.328125 | 0.422852 | 1.971795 | 1.731959 | 2.209184 |
11 | 2.048 | 1.530 | 597 | 933 | 0.747070 | 0.291504 | 0.455566 | 1.989597 | 1.776786 | 2.154734 |
12 | 4.096 | 3.035 | 1.084 | 1.951 | 0.740967 | 0.264648 | 0.476318 | 1.983660 | 1.815745 | 2.091104 |
13 | 8.192 | 6.027 | 1.984 | 4.043 | 0.735718 | 0.242188 | 0.493530 | 1.985832 | 1.830258 | 2.072271 |
14 | 16.384 | 12.041 | 3.635 | 8.406 | 0.734924 | 0.221863 | 0.513062 | 1.997843 | 1.832157 | 2.079149 |
15 | 32.768 | 23.988 | 6.674 | 17.314 | 0.732056 | 0.203674 | 0.528381 | 1.992193 | 1.836038 | 2.059719 |
16 | 65.536 | 47.929 | 12.403 | 35.526 | 0.731339 | 0.189255 | 0.542084 | 1.998041 | 1.858406 | 2.051866 |
17 | 131.072 | 95.569 | 23.194 | 72.375 | 0.729134 | 0.176956 | 0.552177 | 1.993970 | 1.870031 | 2.037240 |
18 | 262.144 | 190.690 | 43.296 | 147.394 | 0.727425 | 0.165161 | 0.562263 | 1.995312 | 1.866690 | 2.036532 |
19 | 524.288 | 380.437 | 81.534 | 298.903 | 0.725626 | 0.155514 | 0.570112 | 1.995055 | 1.883176 | 2.027918 |
20 | 1.048.576 | 759.053 | 154.116 | 604.937 | 0.723889 | 0.146976 | 0.576913 | 1.995213 | 1.890205 | 2.023857 |
21 | 2.097.152 | 1.514.782 | 292.948 | 1.221.834 | 0.722304 | 0.139688 | 0.582616 | 1.995621 | 1.900828 | 2.019771 |
22 | 4.194.304 | 3.024.095 | 556.698 | 2.467.397 | 0.721000 | 0.132727 | 0.588273 | 1.996390 | 1.900330 | 2.019421 |
23 | 8.388.608 | 6.037.298 | 1.060.750 | 4.976.548 | 0.719702 | 0.126451 | 0.593251 | 1.996398 | 1.905432 | 2.016922 |
24 | 16.777.216 | 12.054.010 | 2.025.883 | 10.028.127 | 0.718475 | 0.120752 | 0.597723 | 1.996590 | 1.909859 | 2.015077 |
25 | 33.554.432 | 24.072.030 | 3.878.705 | 20.193.325 | 0.717402 | 0.115594 | 0.601808 | 1.997014 | 1.914575 | 2.013669 |
26 | 67.108.864 | 48.075.531 | 7.437.680 | 40.637.851 | 0.716381 | 0.110830 | 0.605551 | 1.997153 | 1.917568 | 2.012440 |
27 | 134.217.728 | 96.032.178 | 14.291.130 | 81.741.048 | 0.715495 | 0.106477 | 0.609018 | 1.997527 | 1.921450 | 2.011451 |
28 | 268.435.456 | 191.835.681 | 27.495.171 | 164.340.510 | 0.714644 | 0.102427 | 0.612216 | 1.997619 | 1.923933 | 2.010502 |
29 | 536.870.912 | 383.252.627 | 52.981.383 | 330.271.244 | 0.713864 | 0.098686 | 0.615178 | 1.997817 | 1.926934 | 2.009676 |
30 | 1.073.741.824 | 765.722.737 | 102.221.257 | 663.501.480 | 0.713135 | 0.095201 | 0.617934 | 1.997958 | 1.929381 | 2.008960 |
31 | 2.147.483.648 | 1.529.986.353 | 197.487.341 | 1.332.499.012 | 0.712455 | 0.091962 | 0.620493 | 1.998094 | 1.931960 | 2.008283 |
32 | 4.294.967.296 | 3.057.258.241 | 381.976.709 | 2.675.281.532 | 0.711823 | 0.088936 | 0.622887 | 1.998226 | 1.934183 | 2.007717 |
33 | 8.589.934.592 | 6.109.406.893 | 739.610.641 | 5.369.796.252 | 0.711229 | 0.086102 | 0.625127 | 1.998329 | 1.936272 | 2.007189 |
34 | 17.179.869.184 | 12.209.236.148 | 1.433.572.472 | 10.775.663.676 | 0.710671 | 0.083445 | 0.627226 | 1.998432 | 1.938280 | 2.006717 |
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 | 2 | 1 | 1 | 0 | 1 | 1 |
2 | 4 | 5 | 4 | 1 | 1 | 2 | 1 | 1 |
3 | 8 | 8 | 5 | 3 | 4 | 2 | 1 | 1 |
4 | 16 | 14 | 7 | 7 | 6 | 4 | 2 | 2 |
5 | 32 | 22 | 9 | 13 | 8 | 5 | 5 | 4 |
6 | 64 | 37 | 14 | 23 | 10 | 8 | 10 | 9 |
7 | 128 | 65 | 26 | 39 | 18 | 14 | 15 | 18 |
8 | 256 | 111 | 37 | 74 | 30 | 26 | 28 | 27 |
9 | 512 | 194 | 68 | 126 | 49 | 44 | 50 | 51 |
10 | 1.024 | 336 | 117 | 219 | 81 | 83 | 88 | 84 |
11 | 2.048 | 597 | 203 | 394 | 145 | 147 | 155 | 150 |
12 | 4.096 | 1.084 | 372 | 712 | 258 | 280 | 279 | 267 |
13 | 8.192 | 1.984 | 677 | 1.307 | 504 | 501 | 497 | 482 |
14 | 16.384 | 3.635 | 1.208 | 2.427 | 916 | 913 | 915 | 891 |
15 | 32.768 | 6.674 | 2.239 | 4.435 | 1.673 | 1.657 | 1.684 | 1.660 |
16 | 65.536 | 12.403 | 4.133 | 8.270 | 3.105 | 3.089 | 3.106 | 3.103 |
17 | 131.072 | 23.194 | 7.731 | 15.463 | 5.801 | 5.786 | 5.787 | 5.820 |
18 | 262.144 | 43.296 | 14.422 | 28.874 | 10.763 | 10.857 | 10.829 | 10.847 |
19 | 524.288 | 81.534 | 27.172 | 54.362 | 20.279 | 20.462 | 20.405 | 20.388 |
20 | 1.048.576 | 154.116 | 51.268 | 102.848 | 38.434 | 38.528 | 38.621 | 38.533 |
21 | 2.097.152 | 292.948 | 97.477 | 195.471 | 73.013 | 73.352 | 73.303 | 73.280 |
22 | 4.194.304 | 556.698 | 185.390 | 371.308 | 138.853 | 139.286 | 139.364 | 139.195 |
23 | 8.388.608 | 1.060.750 | 353.291 | 707.459 | 264.839 | 265.383 | 265.303 | 265.225 |
24 | 16.777.216 | 2.025.883 | 674.455 | 1.351.428 | 506.080 | 506.647 | 506.561 | 506.595 |
25 | 33.554.432 | 3.878.705 | 1.292.535 | 2.586.170 | 969.216 | 969.826 | 969.323 | 970.340 |
26 | 67.108.864 | 7.437.680 | 2.478.705 | 4.958.975 | 1.858.874 | 1.859.195 | 1.859.168 | 1.860.443 |
27 | 134.217.728 | 14.291.130 | 4.762.624 | 9.528.506 | 3.571.719 | 3.573.335 | 3.572.233 | 3.573.843 |
28 | 268.435.456 | 27.495.171 | 9.164.863 | 18.330.308 | 6.871.772 | 6.875.195 | 6.873.177 | 6.875.027 |
29 | 536.870.912 | 52.981.383 | 17.660.266 | 35.321.117 | 13.242.708 | 13.246.553 | 13.244.458 | 13.247.664 |
30 | 1.073.741.824 | 102.221.257 | 34.074.736 | 68.146.521 | 25.555.485 | 25.558.075 | 25.549.533 | 25.558.164 |
31 | 2.147.483.648 | 197.487.341 | 65.822.630 | 131.664.711 | 49.376.118 | 49.368.230 | 49.368.893 | 49.374.100 |
32 | 4.294.967.296 | 381.976.709 | 127.320.385 | 254.656.324 | 95.492.930 | 95.487.675 | 95.501.452 | 95.494.652 |
33 | 8.589.934.592 | 739.610.641 | 246.535.091 | 493.075.550 | 184.889.961 | 184.896.672 | 184.910.213 | 184.913.795 |
34 | 17.179.869.184 | 1.433.572.472 | 477.860.384 | 955.712.088 | 358.379.567 | 358.386.732 | 358.402.772 | 358.403.401 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
6 | 64 | 16 | 8 | 8 | 4 | 2 | 4 | 6 |
7 | 128 | 38 | 21 | 17 | 8 | 10 | 11 | 9 |
8 | 256 | 86 | 47 | 39 | 19 | 19 | 26 | 22 |
9 | 512 | 196 | 98 | 98 | 42 | 42 | 60 | 52 |
10 | 1.024 | 433 | 218 | 215 | 92 | 117 | 118 | 106 |
11 | 2.048 | 933 | 466 | 467 | 215 | 235 | 238 | 245 |
12 | 4.096 | 1.951 | 964 | 987 | 468 | 489 | 487 | 507 |
13 | 8.192 | 4.043 | 2.029 | 2.014 | 1.017 | 1.009 | 1.020 | 997 |
14 | 16.384 | 8.406 | 4.259 | 4.147 | 2.120 | 2.118 | 2.086 | 2.082 |
15 | 32.768 | 17.314 | 8.804 | 8.510 | 4.370 | 4.391 | 4.263 | 4.290 |
16 | 65.536 | 35.526 | 18.078 | 17.448 | 8.880 | 8.925 | 8.834 | 8.887 |
17 | 131.072 | 72.375 | 36.721 | 35.654 | 18.061 | 18.080 | 18.065 | 18.169 |
18 | 262.144 | 147.394 | 74.761 | 72.633 | 36.883 | 36.781 | 36.838 | 36.892 |
19 | 524.288 | 298.903 | 150.895 | 148.008 | 74.471 | 74.560 | 74.879 | 74.993 |
20 | 1.048.576 | 604.937 | 305.409 | 299.528 | 150.683 | 151.343 | 151.506 | 151.405 |
21 | 2.097.152 | 1.221.834 | 616.577 | 605.257 | 304.378 | 305.588 | 305.777 | 306.091 |
22 | 4.194.304 | 2.467.397 | 1.244.527 | 1.222.870 | 615.405 | 616.892 | 616.909 | 618.191 |
23 | 8.388.608 | 4.976.548 | 2.509.101 | 2.467.447 | 1.242.805 | 1.243.749 | 1.244.436 | 1.245.558 |
24 | 16.777.216 | 10.028.127 | 5.054.709 | 4.973.418 | 2.504.288 | 2.507.842 | 2.508.048 | 2.507.949 |
25 | 33.554.432 | 20.193.325 | 10.175.582 | 10.017.743 | 5.046.396 | 5.049.731 | 5.047.873 | 5.049.325 |
26 | 67.108.864 | 40.637.851 | 20.470.952 | 20.166.899 | 10.155.882 | 10.161.140 | 10.157.449 | 10.163.380 |
27 | 134.217.728 | 81.741.048 | 41.159.443 | 40.581.605 | 20.432.773 | 20.435.255 | 20.430.736 | 20.442.284 |
28 | 268.435.456 | 164.340.510 | 82.722.710 | 81.617.800 | 41.080.115 | 41.088.237 | 41.079.163 | 41.092.995 |
29 | 536.870.912 | 330.271.244 | 166.200.969 | 164.070.275 | 82.565.693 | 82.570.249 | 82.559.656 | 82.575.646 |
30 | 1.073.741.824 | 663.501.480 | 333.800.845 | 329.700.635 | 165.870.360 | 165.875.060 | 165.858.550 | 165.897.510 |
31 | 2.147.483.648 | 1.332.499.012 | 670.213.129 | 662.285.883 | 333.121.667 | 333.113.060 | 333.101.018 | 333.163.267 |
32 | 4.294.967.296 | 2.675.281.532 | 1.345.251.927 | 1.330.029.605 | 668.813.904 | 668.814.817 | 668.793.369 | 668.859.442 |
33 | 8.589.934.592 | 5.369.796.252 | 2.699.574.286 | 2.670.221.966 | 1.342.445.103 | 1.342.446.519 | 1.342.432.155 | 1.342.472.475 |
34 | 17.179.869.184 | 10.775.663.676 | 5.416.255.581 | 5.359.408.095 | 2.693.952.298 | 2.693.925.227 | 2.693.881.897 | 2.693.904.254 |