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-180x-53
f(0)=53
f(1)=29
f(2)=409
f(3)=73
f(4)=757
f(5)=1
f(6)=1097
f(7)=79
f(8)=1429
f(9)=199
f(10)=1753
f(11)=239
f(12)=2069
f(13)=139
f(14)=2377
f(15)=1
f(16)=2677
f(17)=353
f(18)=2969
f(19)=389
f(20)=3253
f(21)=1
f(22)=3529
f(23)=229
f(24)=3797
f(25)=491
f(26)=4057
f(27)=523
f(28)=31
f(29)=277
f(30)=157
f(31)=1
f(32)=4789
f(33)=613
f(34)=173
f(35)=641
f(36)=5237
f(37)=167
f(38)=5449
f(39)=347
f(40)=5653
f(41)=719
f(42)=5849
f(43)=743
f(44)=6037
f(45)=383
f(46)=6217
f(47)=197
f(48)=6389
f(49)=809
f(50)=6553
f(51)=829
f(52)=6709
f(53)=1
f(54)=6857
f(55)=433
f(56)=6997
f(57)=883
f(58)=7129
f(59)=1
f(60)=7253
f(61)=457
f(62)=7369
f(63)=1
f(64)=7477
f(65)=941
f(66)=7577
f(67)=953
f(68)=7669
f(69)=241
f(70)=7753
f(71)=487
f(72)=7829
f(73)=983
f(74)=149
f(75)=991
f(76)=109
f(77)=499
f(78)=8009
f(79)=251
f(80)=8053
f(81)=1009
f(82)=8089
f(83)=1013
f(84)=8117
f(85)=127
f(86)=103
f(87)=509
f(88)=281
f(89)=1019
f(90)=263
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-180x-53 could be written as f(y)= y^2-8153 with x=y+90
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-90
f'(x)>2x-181 with x > 90
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 | 6 | 4 | 1.000000 | 0.600000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 39 | 42 | 0.810000 | 0.390000 | 0.810000 | 8.100000 | 6.500000 | 10.500000 |
3 | 1.000 | 705 | 271 | 434 | 0.705000 | 0.271000 | 0.705000 | 8.703704 | 6.948718 | 10.333333 |
4 | 10.000 | 7.571 | 2.132 | 5.439 | 0.757100 | 0.213200 | 0.757100 | 10.739007 | 7.867159 | 12.532258 |
5 | 100.000 | 75.106 | 16.678 | 58.428 | 0.751060 | 0.166780 | 0.751060 | 9.920222 | 7.822701 | 10.742415 |
6 | 1.000.000 | 741.761 | 135.490 | 606.271 | 0.741761 | 0.135490 | 0.741761 | 9.876188 | 8.123876 | 10.376378 |
7 | 10.000.000 | 7.342.025 | 1.144.241 | 6.197.784 | 0.734203 | 0.114424 | 0.734203 | 9.898101 | 8.445207 | 10.222795 |
8 | 100.000.000 | 72.864.853 | 9.910.665 | 62.954.188 | 0.728649 | 0.099107 | 0.728649 | 9.924355 | 8.661345 | 10.157532 |
9 | 1.000.000.000 | 724.450.913 | 87.436.311 | 637.014.602 | 0.724451 | 0.087436 | 0.724451 | 9.942391 | 8.822447 | 10.118701 |
10 | 10.000.000.000 | 7.211.324.810 | 782.498.961 | 6.428.825.849 | 0.721133 | 0.078250 | 0.721133 | 9.954193 | 8.949359 | 10.092116 |
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 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 1.600000 | 1.666667 | 1.500000 |
4 | 16 | 15 | 9 | 6 | 0.937500 | 0.562500 | 0.375000 | 1.875000 | 1.800000 | 2.000000 |
5 | 32 | 29 | 16 | 13 | 0.906250 | 0.500000 | 0.406250 | 1.933333 | 1.777778 | 2.166667 |
6 | 64 | 58 | 31 | 27 | 0.906250 | 0.484375 | 0.421875 | 2.000000 | 1.937500 | 2.076923 |
7 | 128 | 81 | 39 | 42 | 0.632812 | 0.304688 | 0.328125 | 1.396552 | 1.258065 | 1.555556 |
8 | 256 | 128 | 68 | 60 | 0.500000 | 0.265625 | 0.234375 | 1.580247 | 1.743590 | 1.428571 |
9 | 512 | 328 | 148 | 180 | 0.640625 | 0.289062 | 0.351562 | 2.562500 | 2.176471 | 3.000000 |
10 | 1.024 | 721 | 278 | 443 | 0.704102 | 0.271484 | 0.432617 | 2.198171 | 1.878378 | 2.461111 |
11 | 2.048 | 1.513 | 527 | 986 | 0.738770 | 0.257324 | 0.481445 | 2.098474 | 1.895683 | 2.225734 |
12 | 4.096 | 3.076 | 972 | 2.104 | 0.750977 | 0.237305 | 0.513672 | 2.033047 | 1.844402 | 2.133874 |
13 | 8.192 | 6.181 | 1.784 | 4.397 | 0.754517 | 0.217773 | 0.536743 | 2.009428 | 1.835391 | 2.089829 |
14 | 16.384 | 12.366 | 3.250 | 9.116 | 0.754761 | 0.198364 | 0.556396 | 2.000647 | 1.821749 | 2.073232 |
15 | 32.768 | 24.771 | 6.044 | 18.727 | 0.755951 | 0.184448 | 0.571503 | 2.003154 | 1.859692 | 2.054300 |
16 | 65.536 | 49.389 | 11.329 | 38.060 | 0.753616 | 0.172867 | 0.580750 | 1.993823 | 1.874421 | 2.032360 |
17 | 131.072 | 98.294 | 21.261 | 77.033 | 0.749924 | 0.162209 | 0.587715 | 1.990200 | 1.876688 | 2.023988 |
18 | 262.144 | 195.869 | 39.927 | 155.942 | 0.747181 | 0.152309 | 0.594872 | 1.992685 | 1.877946 | 2.024353 |
19 | 524.288 | 390.168 | 75.216 | 314.952 | 0.744186 | 0.143463 | 0.600723 | 1.991984 | 1.883838 | 2.019674 |
20 | 1.048.576 | 777.636 | 141.524 | 636.112 | 0.741611 | 0.134968 | 0.606644 | 1.993080 | 1.881568 | 2.019711 |
21 | 2.097.152 | 1.549.583 | 268.248 | 1.281.335 | 0.738899 | 0.127911 | 0.610988 | 1.992684 | 1.895424 | 2.014323 |
22 | 4.194.304 | 3.089.768 | 509.987 | 2.579.781 | 0.736658 | 0.121590 | 0.615068 | 1.993935 | 1.901177 | 2.013354 |
23 | 8.388.608 | 6.162.996 | 971.252 | 5.191.744 | 0.734686 | 0.115782 | 0.618904 | 1.994647 | 1.904464 | 2.012475 |
24 | 16.777.216 | 12.294.670 | 1.854.825 | 10.439.845 | 0.732819 | 0.110556 | 0.622263 | 1.994918 | 1.909726 | 2.010855 |
25 | 33.554.432 | 24.531.186 | 3.551.062 | 20.980.124 | 0.731086 | 0.105830 | 0.625256 | 1.995270 | 1.914500 | 2.009620 |
26 | 67.108.864 | 48.957.106 | 6.809.753 | 42.147.353 | 0.729518 | 0.101473 | 0.628044 | 1.995709 | 1.917667 | 2.008918 |
27 | 134.217.728 | 97.717.162 | 13.077.962 | 84.639.200 | 0.728050 | 0.097438 | 0.630611 | 1.995975 | 1.920475 | 2.008174 |
28 | 268.435.456 | 195.080.624 | 25.158.187 | 169.922.437 | 0.726732 | 0.093722 | 0.633010 | 1.996380 | 1.923709 | 2.007609 |
29 | 536.870.912 | 389.491.767 | 48.479.218 | 341.012.549 | 0.725485 | 0.090300 | 0.635185 | 1.996568 | 1.926976 | 2.006872 |
30 | 1.073.741.824 | 777.747.453 | 93.546.113 | 684.201.340 | 0.724334 | 0.087122 | 0.637212 | 1.996826 | 1.929613 | 2.006382 |
31 | 2.147.483.648 | 1.553.198.483 | 180.722.411 | 1.372.476.072 | 0.723264 | 0.084155 | 0.639109 | 1.997047 | 1.931907 | 2.005953 |
32 | 4.294.967.296 | 3.102.105.342 | 349.548.846 | 2.752.556.496 | 0.722265 | 0.081386 | 0.640880 | 1.997237 | 1.934175 | 2.005541 |
33 | 8.589.934.592 | 6.196.181.475 | 676.849.733 | 5.519.331.742 | 0.721330 | 0.078796 | 0.642535 | 1.997412 | 1.936352 | 2.005166 |
34 | 17.179.869.184 | 12.377.295.411 | 1.311.956.859 | 11.065.338.552 | 0.720453 | 0.076366 | 0.644087 | 1.997568 | 1.938328 | 2.004833 |
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 | 1 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
3 | 8 | 5 | 3 | 2 | 2 | 0 | 3 | 0 |
4 | 16 | 9 | 6 | 3 | 4 | 0 | 5 | 0 |
5 | 32 | 16 | 11 | 5 | 7 | 0 | 9 | 0 |
6 | 64 | 31 | 21 | 10 | 14 | 0 | 17 | 0 |
7 | 128 | 39 | 25 | 14 | 18 | 0 | 21 | 0 |
8 | 256 | 68 | 34 | 34 | 18 | 14 | 21 | 15 |
9 | 512 | 148 | 61 | 87 | 18 | 52 | 21 | 57 |
10 | 1.024 | 278 | 107 | 171 | 18 | 113 | 21 | 126 |
11 | 2.048 | 527 | 188 | 339 | 18 | 241 | 21 | 247 |
12 | 4.096 | 972 | 335 | 637 | 18 | 473 | 21 | 460 |
13 | 8.192 | 1.784 | 606 | 1.178 | 18 | 876 | 21 | 869 |
14 | 16.384 | 3.250 | 1.090 | 2.160 | 18 | 1.621 | 21 | 1.590 |
15 | 32.768 | 6.044 | 2.037 | 4.007 | 18 | 3.015 | 21 | 2.990 |
16 | 65.536 | 11.329 | 3.785 | 7.544 | 18 | 5.650 | 21 | 5.640 |
17 | 131.072 | 21.261 | 7.101 | 14.160 | 18 | 10.586 | 21 | 10.636 |
18 | 262.144 | 39.927 | 13.288 | 26.639 | 18 | 19.892 | 21 | 19.996 |
19 | 524.288 | 75.216 | 25.075 | 50.141 | 18 | 37.541 | 21 | 37.636 |
20 | 1.048.576 | 141.524 | 47.188 | 94.336 | 18 | 70.784 | 21 | 70.701 |
21 | 2.097.152 | 268.248 | 89.350 | 178.898 | 18 | 134.217 | 21 | 133.992 |
22 | 4.194.304 | 509.987 | 169.795 | 340.192 | 18 | 255.114 | 21 | 254.834 |
23 | 8.388.608 | 971.252 | 323.778 | 647.474 | 18 | 485.509 | 21 | 485.704 |
24 | 16.777.216 | 1.854.825 | 618.397 | 1.236.428 | 18 | 928.152 | 21 | 926.634 |
25 | 33.554.432 | 3.551.062 | 1.184.371 | 2.366.691 | 18 | 1.776.032 | 21 | 1.774.991 |
26 | 67.108.864 | 6.809.753 | 2.270.626 | 4.539.127 | 18 | 3.404.779 | 21 | 3.404.935 |
27 | 134.217.728 | 13.077.962 | 4.359.426 | 8.718.536 | 18 | 6.538.266 | 21 | 6.539.657 |
28 | 268.435.456 | 25.158.187 | 8.387.321 | 16.770.866 | 18 | 12.579.270 | 21 | 12.578.878 |
29 | 536.870.912 | 48.479.218 | 16.159.578 | 32.319.640 | 18 | 24.238.947 | 21 | 24.240.232 |
30 | 1.073.741.824 | 93.546.113 | 31.178.151 | 62.367.962 | 18 | 46.774.417 | 21 | 46.771.657 |
31 | 2.147.483.648 | 180.722.411 | 60.236.882 | 120.485.529 | 18 | 90.360.682 | 21 | 90.361.690 |
32 | 4.294.967.296 | 349.548.846 | 116.505.818 | 233.043.028 | 18 | 174.773.571 | 21 | 174.775.236 |
33 | 8.589.934.592 | 676.849.733 | 225.610.328 | 451.239.405 | 18 | 338.424.620 | 21 | 338.425.074 |
34 | 17.179.869.184 | 1.311.956.859 | 437.305.433 | 874.651.426 | 18 | 655.975.095 | 21 | 655.981.725 |
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 | 1 | 0 | 1 | 0 |
3 | 8 | 3 | 2 | 1 | 1 | 0 | 1 | 1 |
4 | 16 | 6 | 4 | 2 | 1 | 1 | 1 | 3 |
5 | 32 | 13 | 8 | 5 | 2 | 3 | 5 | 3 |
6 | 64 | 27 | 13 | 14 | 6 | 5 | 9 | 7 |
7 | 128 | 42 | 18 | 24 | 10 | 8 | 13 | 11 |
8 | 256 | 60 | 27 | 33 | 13 | 13 | 18 | 16 |
9 | 512 | 180 | 96 | 84 | 45 | 40 | 48 | 47 |
10 | 1.024 | 443 | 239 | 204 | 102 | 112 | 111 | 118 |
11 | 2.048 | 986 | 529 | 457 | 233 | 255 | 244 | 254 |
12 | 4.096 | 2.104 | 1.117 | 987 | 486 | 559 | 513 | 546 |
13 | 8.192 | 4.397 | 2.298 | 2.099 | 1.043 | 1.149 | 1.082 | 1.123 |
14 | 16.384 | 9.116 | 4.770 | 4.346 | 2.199 | 2.314 | 2.230 | 2.373 |
15 | 32.768 | 18.727 | 9.729 | 8.998 | 4.531 | 4.777 | 4.539 | 4.880 |
16 | 65.536 | 38.060 | 19.759 | 18.301 | 9.314 | 9.764 | 9.245 | 9.737 |
17 | 131.072 | 77.033 | 39.725 | 37.308 | 18.756 | 19.719 | 18.785 | 19.773 |
18 | 262.144 | 155.942 | 80.197 | 75.745 | 38.182 | 39.835 | 38.155 | 39.770 |
19 | 524.288 | 314.952 | 161.472 | 153.480 | 77.338 | 80.185 | 77.210 | 80.219 |
20 | 1.048.576 | 636.112 | 326.090 | 310.022 | 156.390 | 161.714 | 156.318 | 161.690 |
21 | 2.097.152 | 1.281.335 | 656.382 | 624.953 | 315.356 | 325.368 | 315.614 | 324.997 |
22 | 4.194.304 | 2.579.781 | 1.319.603 | 1.260.178 | 635.667 | 654.287 | 636.220 | 653.607 |
23 | 8.388.608 | 5.191.744 | 2.652.684 | 2.539.060 | 1.280.492 | 1.315.179 | 1.280.372 | 1.315.701 |
24 | 16.777.216 | 10.439.845 | 5.330.692 | 5.109.153 | 2.576.862 | 2.642.375 | 2.576.992 | 2.643.616 |
25 | 33.554.432 | 20.980.124 | 10.702.655 | 10.277.469 | 5.181.926 | 5.307.437 | 5.181.998 | 5.308.763 |
26 | 67.108.864 | 42.147.353 | 21.479.700 | 20.667.653 | 10.415.055 | 10.656.511 | 10.416.665 | 10.659.122 |
27 | 134.217.728 | 84.639.200 | 43.091.477 | 41.547.723 | 20.927.489 | 21.389.440 | 20.930.757 | 21.391.514 |
28 | 268.435.456 | 169.922.437 | 86.442.517 | 83.479.920 | 42.038.755 | 42.923.696 | 42.038.805 | 42.921.181 |
29 | 536.870.912 | 341.012.549 | 173.347.787 | 167.664.762 | 84.391.859 | 86.104.865 | 84.406.742 | 86.109.083 |
30 | 1.073.741.824 | 684.201.340 | 347.580.660 | 336.620.680 | 169.402.983 | 172.698.233 | 169.413.387 | 172.686.737 |
31 | 2.147.483.648 | 1.372.476.072 | 696.829.598 | 675.646.474 | 339.947.935 | 346.297.128 | 339.970.632 | 346.260.377 |
32 | 4.294.967.296 | 2.752.556.496 | 1.396.765.142 | 1.355.791.354 | 682.019.670 | 694.257.898 | 682.055.911 | 694.223.017 |
33 | 8.589.934.592 | 5.519.331.742 | 2.799.268.015 | 2.720.063.727 | 1.368.022.091 | 1.391.626.688 | 1.368.103.043 | 1.391.579.920 |
34 | 17.179.869.184 | 11.065.338.552 | 5.609.288.295 | 5.456.050.257 | 2.743.504.577 | 2.789.154.091 | 2.743.598.323 | 2.789.081.561 |