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+33x-101
f(0)=101
f(1)=67
f(2)=31
f(3)=7
f(4)=47
f(5)=89
f(6)=19
f(7)=179
f(8)=227
f(9)=277
f(10)=1
f(11)=383
f(12)=439
f(13)=71
f(14)=557
f(15)=619
f(16)=683
f(17)=107
f(18)=43
f(19)=887
f(20)=137
f(21)=1033
f(22)=1109
f(23)=1187
f(24)=181
f(25)=1
f(26)=1433
f(27)=1
f(28)=1607
f(29)=1697
f(30)=1789
f(31)=269
f(32)=1979
f(33)=1
f(34)=311
f(35)=53
f(36)=2383
f(37)=131
f(38)=1
f(39)=2707
f(40)=2819
f(41)=419
f(42)=3049
f(43)=3167
f(44)=173
f(45)=487
f(46)=3533
f(47)=3659
f(48)=541
f(49)=3917
f(50)=4049
f(51)=1
f(52)=617
f(53)=4457
f(54)=4597
f(55)=677
f(56)=257
f(57)=1
f(58)=167
f(59)=761
f(60)=5479
f(61)=1
f(62)=827
f(63)=313
f(64)=197
f(65)=6269
f(66)=919
f(67)=6599
f(68)=1
f(69)=991
f(70)=7109
f(71)=7283
f(72)=7459
f(73)=1091
f(74)=7817
f(75)=421
f(76)=1
f(77)=8369
f(78)=199
f(79)=8747
f(80)=1277
f(81)=9133
f(82)=491
f(83)=1361
f(84)=1
f(85)=9929
f(86)=10133
f(87)=211
f(88)=1
f(89)=347
f(90)=1567
f(91)=1
f(92)=11399
f(93)=11617
f(94)=1
f(95)=389
f(96)=1
f(97)=1787
f(98)=271
f(99)=12967
b) Substitution of the polynom
The polynom f(x)=x^2+33x-101 could be written as f(y)= y^2-373.25 with x=y-16.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+16.5
f'(x)>2x+32
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 | 9 | 1 | 1.000000 | 0.900000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 84 | 49 | 35 | 0.840000 | 0.490000 | 0.350000 | 8.400000 | 5.444445 | 35.000000 |
3 | 1.000 | 785 | 324 | 461 | 0.785000 | 0.324000 | 0.461000 | 9.345238 | 6.612245 | 13.171429 |
4 | 10.000 | 7.524 | 2.393 | 5.131 | 0.752400 | 0.239300 | 0.513100 | 9.584713 | 7.385802 | 11.130152 |
5 | 100.000 | 73.886 | 18.657 | 55.229 | 0.738860 | 0.186570 | 0.552290 | 9.820043 | 7.796490 | 10.763789 |
6 | 1.000.000 | 731.427 | 150.993 | 580.434 | 0.731427 | 0.150993 | 0.580434 | 9.899399 | 8.093102 | 10.509587 |
7 | 10.000.000 | 7.259.259 | 1.279.047 | 5.980.212 | 0.725926 | 0.127905 | 0.598021 | 9.924789 | 8.470902 | 10.303000 |
8 | 100.000.000 | 72.165.310 | 11.077.134 | 61.088.176 | 0.721653 | 0.110771 | 0.610882 | 9.941140 | 8.660459 | 10.215052 |
9 | 1.000.000.000 | 718.321.535 | 97.731.929 | 620.589.606 | 0.718322 | 0.097732 | 0.620590 | 9.953834 | 8.822853 | 10.158916 |
10 | 10.000.000.000 | 7.156.956.352 | 874.621.186 | 6.282.335.166 | 0.715696 | 0.087462 | 0.628234 | 9.963444 | 8.949185 | 10.123172 |
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 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 16 | 14 | 2 | 1.000000 | 0.875000 | 0.125000 | 1.777778 | 1.750000 | 2.000000 |
5 | 32 | 30 | 23 | 7 | 0.937500 | 0.718750 | 0.218750 | 1.875000 | 1.642857 | 3.500000 |
6 | 64 | 56 | 35 | 21 | 0.875000 | 0.546875 | 0.328125 | 1.866667 | 1.521739 | 3.000000 |
7 | 128 | 108 | 64 | 44 | 0.843750 | 0.500000 | 0.343750 | 1.928571 | 1.828571 | 2.095238 |
8 | 256 | 210 | 110 | 100 | 0.820312 | 0.429688 | 0.390625 | 1.944444 | 1.718750 | 2.272727 |
9 | 512 | 405 | 189 | 216 | 0.791016 | 0.369141 | 0.421875 | 1.928571 | 1.718182 | 2.160000 |
10 | 1.024 | 804 | 332 | 472 | 0.785156 | 0.324219 | 0.460938 | 1.985185 | 1.756614 | 2.185185 |
11 | 2.048 | 1.577 | 610 | 967 | 0.770020 | 0.297852 | 0.472168 | 1.961443 | 1.837349 | 2.048729 |
12 | 4.096 | 3.102 | 1.106 | 1.996 | 0.757324 | 0.270020 | 0.487305 | 1.967026 | 1.813115 | 2.064116 |
13 | 8.192 | 6.169 | 2.017 | 4.152 | 0.753052 | 0.246216 | 0.506836 | 1.988717 | 1.823689 | 2.080160 |
14 | 16.384 | 12.254 | 3.683 | 8.571 | 0.747925 | 0.224792 | 0.523132 | 1.986384 | 1.825979 | 2.064306 |
15 | 32.768 | 24.342 | 6.839 | 17.503 | 0.742859 | 0.208710 | 0.534149 | 1.986453 | 1.856910 | 2.042119 |
16 | 65.536 | 48.506 | 12.658 | 35.848 | 0.740143 | 0.193146 | 0.546997 | 1.992688 | 1.850855 | 2.048106 |
17 | 131.072 | 96.667 | 23.747 | 72.920 | 0.737511 | 0.181175 | 0.556335 | 1.992887 | 1.876047 | 2.034144 |
18 | 262.144 | 192.877 | 44.416 | 148.461 | 0.735767 | 0.169434 | 0.566334 | 1.995272 | 1.870384 | 2.035944 |
19 | 524.288 | 384.351 | 83.586 | 300.765 | 0.733091 | 0.159428 | 0.573664 | 1.992726 | 1.881889 | 2.025886 |
20 | 1.048.576 | 766.869 | 157.630 | 609.239 | 0.731343 | 0.150328 | 0.581016 | 1.995231 | 1.885842 | 2.025631 |
21 | 2.097.152 | 1.530.071 | 299.250 | 1.230.821 | 0.729595 | 0.142694 | 0.586901 | 1.995218 | 1.898433 | 2.020260 |
22 | 4.194.304 | 3.052.989 | 569.499 | 2.483.490 | 0.727889 | 0.135779 | 0.592110 | 1.995325 | 1.903088 | 2.017751 |
23 | 8.388.608 | 6.092.720 | 1.085.732 | 5.006.988 | 0.726309 | 0.129429 | 0.596879 | 1.995657 | 1.906469 | 2.016110 |
24 | 16.777.216 | 12.161.675 | 2.073.820 | 10.087.855 | 0.724892 | 0.123609 | 0.601283 | 1.996099 | 1.910066 | 2.014755 |
25 | 33.554.432 | 24.278.027 | 3.968.303 | 20.309.724 | 0.723542 | 0.118265 | 0.605277 | 1.996273 | 1.913523 | 2.013285 |
26 | 67.108.864 | 48.473.220 | 7.609.697 | 40.863.523 | 0.722307 | 0.113393 | 0.608914 | 1.996588 | 1.917620 | 2.012018 |
27 | 134.217.728 | 96.796.851 | 14.617.943 | 82.178.908 | 0.721193 | 0.108912 | 0.612281 | 1.996914 | 1.920963 | 2.011058 |
28 | 268.435.456 | 193.309.377 | 28.118.198 | 165.191.179 | 0.720134 | 0.104748 | 0.615385 | 1.997063 | 1.923540 | 2.010141 |
29 | 536.870.912 | 386.089.003 | 54.187.318 | 331.901.685 | 0.719147 | 0.100932 | 0.618215 | 1.997259 | 1.927126 | 2.009197 |
30 | 1.073.741.824 | 771.198.237 | 104.556.474 | 666.641.763 | 0.718234 | 0.097376 | 0.620859 | 1.997462 | 1.929538 | 2.008552 |
31 | 2.147.483.648 | 1.540.569.418 | 201.999.071 | 1.338.570.347 | 0.717384 | 0.094063 | 0.623320 | 1.997631 | 1.931961 | 2.007931 |
32 | 4.294.967.296 | 3.077.744.690 | 390.711.389 | 2.687.033.301 | 0.716593 | 0.090970 | 0.625624 | 1.997797 | 1.934224 | 2.007390 |
33 | 8.589.934.592 | 6.149.125.860 | 756.540.875 | 5.392.584.985 | 0.715852 | 0.088073 | 0.627780 | 1.997932 | 1.936316 | 2.006892 |
34 | 17.179.869.184 | 12.286.275.809 | 1.466.396.881 | 10.819.878.928 | 0.715155 | 0.085356 | 0.629800 | 1.998052 | 1.938292 | 2.006436 |
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 | 0 | 1 | 1 | 1 |
2 | 4 | 5 | 3 | 2 | 0 | 1 | 1 | 3 |
3 | 8 | 8 | 3 | 5 | 1 | 3 | 1 | 3 |
4 | 16 | 14 | 6 | 8 | 1 | 5 | 3 | 5 |
5 | 32 | 23 | 8 | 15 | 4 | 7 | 5 | 7 |
6 | 64 | 35 | 13 | 22 | 7 | 10 | 8 | 10 |
7 | 128 | 64 | 22 | 42 | 15 | 18 | 15 | 16 |
8 | 256 | 110 | 36 | 74 | 26 | 29 | 25 | 30 |
9 | 512 | 189 | 66 | 123 | 45 | 52 | 44 | 48 |
10 | 1.024 | 332 | 118 | 214 | 81 | 86 | 85 | 80 |
11 | 2.048 | 610 | 210 | 400 | 153 | 153 | 143 | 161 |
12 | 4.096 | 1.106 | 378 | 728 | 272 | 262 | 275 | 297 |
13 | 8.192 | 2.017 | 678 | 1.339 | 502 | 497 | 503 | 515 |
14 | 16.384 | 3.683 | 1.235 | 2.448 | 897 | 916 | 934 | 936 |
15 | 32.768 | 6.839 | 2.276 | 4.563 | 1.688 | 1.710 | 1.732 | 1.709 |
16 | 65.536 | 12.658 | 4.207 | 8.451 | 3.157 | 3.175 | 3.155 | 3.171 |
17 | 131.072 | 23.747 | 7.907 | 15.840 | 5.873 | 5.940 | 5.931 | 6.003 |
18 | 262.144 | 44.416 | 14.747 | 29.669 | 11.066 | 11.063 | 11.100 | 11.187 |
19 | 524.288 | 83.586 | 27.910 | 55.676 | 20.949 | 20.843 | 20.813 | 20.981 |
20 | 1.048.576 | 157.630 | 52.517 | 105.113 | 39.474 | 39.398 | 39.136 | 39.622 |
21 | 2.097.152 | 299.250 | 99.797 | 199.453 | 74.926 | 74.764 | 74.421 | 75.139 |
22 | 4.194.304 | 569.499 | 189.884 | 379.615 | 142.571 | 142.333 | 142.003 | 142.592 |
23 | 8.388.608 | 1.085.732 | 361.876 | 723.856 | 271.529 | 271.439 | 271.051 | 271.713 |
24 | 16.777.216 | 2.073.820 | 691.266 | 1.382.554 | 519.202 | 518.369 | 517.716 | 518.533 |
25 | 33.554.432 | 3.968.303 | 1.323.052 | 2.645.251 | 993.121 | 991.932 | 991.192 | 992.058 |
26 | 67.108.864 | 7.609.697 | 2.536.830 | 5.072.867 | 1.903.534 | 1.902.366 | 1.901.532 | 1.902.265 |
27 | 134.217.728 | 14.617.943 | 4.874.559 | 9.743.384 | 3.655.711 | 3.654.331 | 3.653.396 | 3.654.505 |
28 | 268.435.456 | 28.118.198 | 9.374.430 | 18.743.768 | 7.031.426 | 7.029.153 | 7.028.084 | 7.029.535 |
29 | 536.870.912 | 54.187.318 | 18.065.477 | 36.121.841 | 13.547.666 | 13.547.693 | 13.545.410 | 13.546.549 |
30 | 1.073.741.824 | 104.556.474 | 34.857.657 | 69.698.817 | 26.141.215 | 26.138.724 | 26.138.248 | 26.138.287 |
31 | 2.147.483.648 | 201.999.071 | 67.334.637 | 134.664.434 | 50.504.098 | 50.501.822 | 50.495.259 | 50.497.892 |
32 | 4.294.967.296 | 390.711.389 | 130.239.168 | 260.472.221 | 97.685.761 | 97.676.326 | 97.676.585 | 97.672.717 |
33 | 8.589.934.592 | 756.540.875 | 252.171.729 | 504.369.146 | 189.147.240 | 189.130.620 | 189.130.206 | 189.132.809 |
34 | 17.179.869.184 | 1.466.396.881 | 488.786.189 | 977.610.692 | 366.609.910 | 366.594.596 | 366.589.112 | 366.603.263 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
5 | 32 | 7 | 3 | 4 | 1 | 3 | 2 | 1 |
6 | 64 | 21 | 6 | 15 | 5 | 6 | 6 | 4 |
7 | 128 | 44 | 16 | 28 | 9 | 13 | 10 | 12 |
8 | 256 | 100 | 42 | 58 | 21 | 30 | 24 | 25 |
9 | 512 | 216 | 90 | 126 | 53 | 53 | 57 | 53 |
10 | 1.024 | 472 | 205 | 267 | 120 | 125 | 119 | 108 |
11 | 2.048 | 967 | 429 | 538 | 239 | 267 | 235 | 226 |
12 | 4.096 | 1.996 | 902 | 1.094 | 503 | 495 | 508 | 490 |
13 | 8.192 | 4.152 | 1.915 | 2.237 | 1.044 | 1.017 | 1.084 | 1.007 |
14 | 16.384 | 8.571 | 3.963 | 4.608 | 2.156 | 2.092 | 2.217 | 2.106 |
15 | 32.768 | 17.503 | 8.120 | 9.383 | 4.402 | 4.266 | 4.387 | 4.448 |
16 | 65.536 | 35.848 | 16.884 | 18.964 | 9.001 | 8.843 | 9.016 | 8.988 |
17 | 131.072 | 72.920 | 34.564 | 38.356 | 18.344 | 18.064 | 18.181 | 18.331 |
18 | 262.144 | 148.461 | 70.748 | 77.713 | 37.221 | 36.896 | 37.092 | 37.252 |
19 | 524.288 | 300.765 | 143.786 | 156.979 | 75.233 | 75.126 | 75.227 | 75.179 |
20 | 1.048.576 | 609.239 | 292.255 | 316.984 | 152.189 | 152.712 | 152.165 | 152.173 |
21 | 2.097.152 | 1.230.821 | 591.976 | 638.845 | 307.090 | 308.278 | 307.757 | 307.696 |
22 | 4.194.304 | 2.483.490 | 1.197.734 | 1.285.756 | 620.009 | 621.912 | 620.960 | 620.609 |
23 | 8.388.608 | 5.006.988 | 2.419.665 | 2.587.323 | 1.251.273 | 1.253.343 | 1.251.644 | 1.250.728 |
24 | 16.777.216 | 10.087.855 | 4.883.722 | 5.204.133 | 2.521.132 | 2.523.782 | 2.521.734 | 2.521.207 |
25 | 33.554.432 | 20.309.724 | 9.850.877 | 10.458.847 | 5.078.598 | 5.077.671 | 5.076.919 | 5.076.536 |
26 | 67.108.864 | 40.863.523 | 19.849.227 | 21.014.296 | 10.214.393 | 10.217.771 | 10.216.730 | 10.214.629 |
27 | 134.217.728 | 82.178.908 | 39.977.607 | 42.201.301 | 20.540.124 | 20.548.242 | 20.548.129 | 20.542.413 |
28 | 268.435.456 | 165.191.179 | 80.462.653 | 84.728.526 | 41.288.825 | 41.306.512 | 41.304.362 | 41.291.480 |
29 | 536.870.912 | 331.901.685 | 161.857.261 | 170.044.424 | 82.962.574 | 82.989.108 | 82.978.207 | 82.971.796 |
30 | 1.073.741.824 | 666.641.763 | 325.436.487 | 341.205.276 | 166.639.667 | 166.685.678 | 166.660.323 | 166.656.095 |
31 | 2.147.483.648 | 1.338.570.347 | 654.069.715 | 684.500.632 | 334.620.857 | 334.669.903 | 334.653.385 | 334.626.202 |
32 | 4.294.967.296 | 2.687.033.301 | 1.314.105.762 | 1.372.927.539 | 671.710.840 | 671.812.128 | 671.767.130 | 671.743.203 |
33 | 8.589.934.592 | 5.392.584.985 | 2.639.450.169 | 2.753.134.816 | 1.348.083.925 | 1.348.196.244 | 1.348.156.556 | 1.348.148.260 |
34 | 17.179.869.184 | 10.819.878.928 | 5.299.875.371 | 5.520.003.557 | 2.704.878.328 | 2.705.052.426 | 2.704.978.010 | 2.704.970.164 |