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-57x-17
f(0)=17
f(1)=73
f(2)=127
f(3)=179
f(4)=229
f(5)=277
f(6)=19
f(7)=367
f(8)=409
f(9)=449
f(10)=487
f(11)=523
f(12)=557
f(13)=31
f(14)=619
f(15)=647
f(16)=673
f(17)=41
f(18)=719
f(19)=739
f(20)=757
f(21)=773
f(22)=787
f(23)=47
f(24)=809
f(25)=43
f(26)=823
f(27)=827
f(28)=829
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
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)=101
f(60)=163
f(61)=227
f(62)=293
f(63)=1
f(64)=431
f(65)=503
f(66)=577
f(67)=653
f(68)=1
f(69)=811
f(70)=1
f(71)=977
f(72)=1063
f(73)=1151
f(74)=1
f(75)=1
f(76)=1427
f(77)=1523
f(78)=1621
f(79)=1721
f(80)=1823
f(81)=1
f(82)=107
f(83)=2141
f(84)=2251
f(85)=139
f(86)=2477
f(87)=2593
f(88)=2711
f(89)=149
f(90)=2953
f(91)=181
f(92)=3203
f(93)=3331
f(94)=3461
f(95)=3593
f(96)=3727
f(97)=3863
f(98)=4001
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-57x-17 could be written as f(y)= y^2-829.25 with x=y+28.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-28.5
f'(x)>2x-58 with x > 29
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 | 11 | 10 | 1 | 1.100000 | 1.000000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 59 | 56 | 3 | 0.590000 | 0.560000 | 0.590000 | 5.363636 | 5.600000 | 3.000000 |
3 | 1.000 | 796 | 469 | 327 | 0.796000 | 0.469000 | 0.796000 | 13.491526 | 8.375000 | 109.000000 |
4 | 10.000 | 7.978 | 3.358 | 4.620 | 0.797800 | 0.335800 | 0.797800 | 10.022614 | 7.159914 | 14.128440 |
5 | 100.000 | 78.093 | 26.013 | 52.080 | 0.780930 | 0.260130 | 0.780930 | 9.788544 | 7.746575 | 11.272727 |
6 | 1.000.000 | 764.764 | 213.307 | 551.457 | 0.764764 | 0.213307 | 0.764764 | 9.792991 | 8.200015 | 10.588652 |
7 | 10.000.000 | 7.540.605 | 1.803.813 | 5.736.792 | 0.754061 | 0.180381 | 0.754061 | 9.860042 | 8.456417 | 10.402972 |
8 | 100.000.000 | 74.620.526 | 15.626.741 | 58.993.785 | 0.746205 | 0.156267 | 0.746205 | 9.895827 | 8.663172 | 10.283410 |
9 | 1.000.000.000 | 740.111.217 | 137.891.063 | 602.220.154 | 0.740111 | 0.137891 | 0.740111 | 9.918333 | 8.824044 | 10.208197 |
10 | 10.000.000.000 | 7.352.683.390 | 1.234.096.866 | 6.118.586.524 | 0.735268 | 0.123410 | 0.735268 | 9.934566 | 8.949797 | 10.160049 |
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 | 17 | 16 | 1 | 1.062500 | 1.000000 | 0.062500 | 1.888889 | 2.000000 | 1.000000 |
5 | 32 | 28 | 25 | 3 | 0.875000 | 0.781250 | 0.093750 | 1.647059 | 1.562500 | 3.000000 |
6 | 64 | 32 | 29 | 3 | 0.500000 | 0.453125 | 0.046875 | 1.142857 | 1.160000 | 1.000000 |
7 | 128 | 80 | 71 | 9 | 0.625000 | 0.554688 | 0.070312 | 2.500000 | 2.448276 | 3.000000 |
8 | 256 | 193 | 142 | 51 | 0.753906 | 0.554688 | 0.199219 | 2.412500 | 2.000000 | 5.666667 |
9 | 512 | 408 | 261 | 147 | 0.796875 | 0.509766 | 0.287109 | 2.113990 | 1.838028 | 2.882353 |
10 | 1.024 | 816 | 476 | 340 | 0.796875 | 0.464844 | 0.332031 | 2.000000 | 1.823755 | 2.312925 |
11 | 2.048 | 1.635 | 863 | 772 | 0.798340 | 0.421387 | 0.376953 | 2.003676 | 1.813025 | 2.270588 |
12 | 4.096 | 3.296 | 1.547 | 1.749 | 0.804688 | 0.377686 | 0.427002 | 2.015902 | 1.792584 | 2.265544 |
13 | 8.192 | 6.547 | 2.851 | 3.696 | 0.799194 | 0.348022 | 0.451172 | 1.986347 | 1.842922 | 2.113208 |
14 | 16.384 | 13.024 | 5.182 | 7.842 | 0.794922 | 0.316284 | 0.478638 | 1.989308 | 1.817608 | 2.121753 |
15 | 32.768 | 25.884 | 9.606 | 16.278 | 0.789917 | 0.293152 | 0.496765 | 1.987408 | 1.853724 | 2.075746 |
16 | 65.536 | 51.371 | 17.836 | 33.535 | 0.783859 | 0.272156 | 0.511703 | 1.984662 | 1.856756 | 2.060143 |
17 | 131.072 | 102.035 | 33.270 | 68.765 | 0.778465 | 0.253830 | 0.524635 | 1.986237 | 1.865329 | 2.050544 |
18 | 262.144 | 202.686 | 62.521 | 140.165 | 0.773186 | 0.238499 | 0.534687 | 1.986436 | 1.879200 | 2.038319 |
19 | 524.288 | 402.918 | 117.934 | 284.984 | 0.768505 | 0.224941 | 0.543564 | 1.987893 | 1.886310 | 2.033204 |
20 | 1.048.576 | 801.697 | 222.871 | 578.826 | 0.764558 | 0.212546 | 0.552011 | 1.989727 | 1.889794 | 2.031082 |
21 | 2.097.152 | 1.596.024 | 422.413 | 1.173.611 | 0.761044 | 0.201422 | 0.559621 | 1.990807 | 1.895325 | 2.027571 |
22 | 4.194.304 | 3.178.504 | 803.103 | 2.375.401 | 0.757814 | 0.191475 | 0.566340 | 1.991514 | 1.901227 | 2.024010 |
23 | 8.388.608 | 6.331.739 | 1.530.292 | 4.801.447 | 0.754802 | 0.182425 | 0.572377 | 1.992050 | 1.905474 | 2.021321 |
24 | 16.777.216 | 12.619.492 | 2.924.046 | 9.695.446 | 0.752180 | 0.174287 | 0.577894 | 1.993053 | 1.910776 | 2.019276 |
25 | 33.554.432 | 25.155.004 | 5.597.275 | 19.557.729 | 0.749678 | 0.166812 | 0.582866 | 1.993345 | 1.914223 | 2.017208 |
26 | 67.108.864 | 50.159.340 | 10.733.823 | 39.425.517 | 0.747432 | 0.159946 | 0.587486 | 1.994010 | 1.917687 | 2.015854 |
27 | 134.217.728 | 100.036.203 | 20.623.980 | 79.412.223 | 0.745328 | 0.153661 | 0.591667 | 1.994368 | 1.921401 | 2.014234 |
28 | 268.435.456 | 199.557.781 | 39.681.465 | 159.876.316 | 0.743411 | 0.147825 | 0.595586 | 1.994856 | 1.924045 | 2.013246 |
29 | 536.870.912 | 398.152.973 | 76.458.863 | 321.694.110 | 0.741618 | 0.142416 | 0.599202 | 1.995176 | 1.926816 | 2.012144 |
30 | 1.073.741.824 | 794.507.440 | 147.527.383 | 646.980.057 | 0.739943 | 0.137396 | 0.602547 | 1.995483 | 1.929500 | 2.011165 |
31 | 2.147.483.648 | 1.585.663.623 | 285.030.668 | 1.300.632.955 | 0.738382 | 0.132728 | 0.605654 | 1.995782 | 1.932053 | 2.010314 |
32 | 4.294.967.296 | 3.165.066.462 | 551.298.740 | 2.613.767.722 | 0.736924 | 0.128359 | 0.608565 | 1.996052 | 1.934174 | 2.009612 |
33 | 8.589.934.592 | 6.318.373.919 | 1.067.480.131 | 5.250.893.788 | 0.735556 | 0.124271 | 0.611284 | 1.996285 | 1.936301 | 2.008937 |
34 | 17.179.869.184 | 12.614.701.680 | 2.069.086.141 | 10.545.615.539 | 0.734272 | 0.120437 | 0.613836 | 1.996511 | 1.938290 | 2.008347 |
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 | 2 | 0 | 0 | 1 |
2 | 4 | 5 | 3 | 2 | 2 | 1 | 1 | 1 |
3 | 8 | 8 | 6 | 2 | 3 | 1 | 2 | 2 |
4 | 16 | 16 | 11 | 5 | 5 | 3 | 4 | 4 |
5 | 32 | 25 | 16 | 9 | 6 | 6 | 7 | 6 |
6 | 64 | 29 | 17 | 12 | 6 | 8 | 8 | 7 |
7 | 128 | 71 | 30 | 41 | 16 | 18 | 18 | 19 |
8 | 256 | 142 | 59 | 83 | 34 | 37 | 37 | 34 |
9 | 512 | 261 | 97 | 164 | 62 | 70 | 67 | 62 |
10 | 1.024 | 476 | 171 | 305 | 116 | 125 | 122 | 113 |
11 | 2.048 | 863 | 295 | 568 | 215 | 214 | 213 | 221 |
12 | 4.096 | 1.547 | 517 | 1.030 | 386 | 380 | 384 | 397 |
13 | 8.192 | 2.851 | 960 | 1.891 | 728 | 715 | 693 | 715 |
14 | 16.384 | 5.182 | 1.735 | 3.447 | 1.317 | 1.310 | 1.273 | 1.282 |
15 | 32.768 | 9.606 | 3.191 | 6.415 | 2.450 | 2.394 | 2.368 | 2.394 |
16 | 65.536 | 17.836 | 5.944 | 11.892 | 4.506 | 4.435 | 4.447 | 4.448 |
17 | 131.072 | 33.270 | 11.048 | 22.222 | 8.360 | 8.311 | 8.285 | 8.314 |
18 | 262.144 | 62.521 | 20.842 | 41.679 | 15.736 | 15.617 | 15.591 | 15.577 |
19 | 524.288 | 117.934 | 39.424 | 78.510 | 29.412 | 29.590 | 29.523 | 29.409 |
20 | 1.048.576 | 222.871 | 74.592 | 148.279 | 55.588 | 55.949 | 55.742 | 55.592 |
21 | 2.097.152 | 422.413 | 141.055 | 281.358 | 105.405 | 105.813 | 105.796 | 105.399 |
22 | 4.194.304 | 803.103 | 268.077 | 535.026 | 200.378 | 201.011 | 201.055 | 200.659 |
23 | 8.388.608 | 1.530.292 | 510.523 | 1.019.769 | 382.092 | 382.699 | 382.578 | 382.923 |
24 | 16.777.216 | 2.924.046 | 975.315 | 1.948.731 | 730.649 | 731.178 | 730.535 | 731.684 |
25 | 33.554.432 | 5.597.275 | 1.866.471 | 3.730.804 | 1.399.253 | 1.398.694 | 1.399.815 | 1.399.513 |
26 | 67.108.864 | 10.733.823 | 3.577.682 | 7.156.141 | 2.682.277 | 2.684.019 | 2.684.114 | 2.683.413 |
27 | 134.217.728 | 20.623.980 | 6.873.342 | 13.750.638 | 5.155.222 | 5.155.506 | 5.157.644 | 5.155.608 |
28 | 268.435.456 | 39.681.465 | 13.225.114 | 26.456.351 | 9.920.781 | 9.919.334 | 9.921.662 | 9.919.688 |
29 | 536.870.912 | 76.458.863 | 25.482.825 | 50.976.038 | 19.115.519 | 19.115.988 | 19.116.078 | 19.111.278 |
30 | 1.073.741.824 | 147.527.383 | 49.174.490 | 98.352.893 | 36.886.294 | 36.880.022 | 36.883.862 | 36.877.205 |
31 | 2.147.483.648 | 285.030.668 | 95.009.577 | 190.021.091 | 71.265.578 | 71.256.579 | 71.261.212 | 71.247.299 |
32 | 4.294.967.296 | 551.298.740 | 183.767.534 | 367.531.206 | 137.838.195 | 137.825.776 | 137.825.528 | 137.809.241 |
33 | 8.589.934.592 | 1.067.480.131 | 355.834.101 | 711.646.030 | 266.871.410 | 266.882.407 | 266.863.819 | 266.862.495 |
34 | 17.179.869.184 | 2.069.086.141 | 689.691.080 | 1.379.395.061 | 517.285.486 | 517.274.300 | 517.270.126 | 517.256.229 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 32 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
6 | 64 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
7 | 128 | 9 | 4 | 5 | 3 | 3 | 2 | 1 |
8 | 256 | 51 | 25 | 26 | 13 | 16 | 12 | 10 |
9 | 512 | 147 | 74 | 73 | 36 | 32 | 40 | 39 |
10 | 1.024 | 340 | 167 | 173 | 80 | 86 | 82 | 92 |
11 | 2.048 | 772 | 375 | 397 | 171 | 198 | 204 | 199 |
12 | 4.096 | 1.749 | 850 | 899 | 424 | 449 | 434 | 442 |
13 | 8.192 | 3.696 | 1.807 | 1.889 | 914 | 933 | 907 | 942 |
14 | 16.384 | 7.842 | 3.936 | 3.906 | 1.932 | 1.968 | 1.968 | 1.974 |
15 | 32.768 | 16.278 | 8.153 | 8.125 | 4.043 | 4.038 | 4.092 | 4.105 |
16 | 65.536 | 33.535 | 16.774 | 16.761 | 8.405 | 8.312 | 8.371 | 8.447 |
17 | 131.072 | 68.765 | 34.418 | 34.347 | 17.183 | 17.214 | 17.084 | 17.284 |
18 | 262.144 | 140.165 | 70.124 | 70.041 | 35.007 | 35.113 | 35.015 | 35.030 |
19 | 524.288 | 284.984 | 142.668 | 142.316 | 71.200 | 71.406 | 71.269 | 71.109 |
20 | 1.048.576 | 578.826 | 289.989 | 288.837 | 144.655 | 144.951 | 144.581 | 144.639 |
21 | 2.097.152 | 1.173.611 | 588.218 | 585.393 | 293.533 | 293.518 | 293.246 | 293.314 |
22 | 4.194.304 | 2.375.401 | 1.190.246 | 1.185.155 | 594.250 | 594.435 | 593.443 | 593.273 |
23 | 8.388.608 | 4.801.447 | 2.405.421 | 2.396.026 | 1.200.287 | 1.201.098 | 1.200.271 | 1.199.791 |
24 | 16.777.216 | 9.695.446 | 4.854.490 | 4.840.956 | 2.424.687 | 2.423.576 | 2.423.319 | 2.423.864 |
25 | 33.554.432 | 19.557.729 | 9.792.902 | 9.764.827 | 4.890.022 | 4.888.995 | 4.886.939 | 4.891.773 |
26 | 67.108.864 | 39.425.517 | 19.739.420 | 19.686.097 | 9.855.552 | 9.857.968 | 9.854.526 | 9.857.471 |
27 | 134.217.728 | 79.412.223 | 39.761.431 | 39.650.792 | 19.852.809 | 19.854.428 | 19.850.867 | 19.854.119 |
28 | 268.435.456 | 159.876.316 | 80.041.359 | 79.834.957 | 39.969.714 | 39.969.501 | 39.967.461 | 39.969.640 |
29 | 536.870.912 | 321.694.110 | 161.043.557 | 160.650.553 | 80.421.389 | 80.416.489 | 80.420.266 | 80.435.966 |
30 | 1.073.741.824 | 646.980.057 | 323.869.038 | 323.111.019 | 161.744.155 | 161.737.845 | 161.743.831 | 161.754.226 |
31 | 2.147.483.648 | 1.300.632.955 | 651.025.850 | 649.607.105 | 325.153.601 | 325.153.619 | 325.159.859 | 325.165.876 |
32 | 4.294.967.296 | 2.613.767.722 | 1.308.261.613 | 1.305.506.109 | 653.444.336 | 653.437.132 | 653.432.780 | 653.453.474 |
33 | 8.589.934.592 | 5.250.893.788 | 2.628.054.013 | 2.622.839.775 | 1.312.689.036 | 1.312.743.872 | 1.312.718.513 | 1.312.742.367 |
34 | 17.179.869.184 | 10.545.615.539 | 5.277.806.400 | 5.267.809.139 | 2.636.340.099 | 2.636.458.889 | 2.636.423.059 | 2.636.393.492 |