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-53x+13
f(0)=13
f(1)=3
f(2)=89
f(3)=137
f(4)=61
f(5)=227
f(6)=269
f(7)=103
f(8)=347
f(9)=383
f(10)=139
f(11)=449
f(12)=479
f(13)=1
f(14)=41
f(15)=557
f(16)=193
f(17)=599
f(18)=617
f(19)=211
f(20)=647
f(21)=659
f(22)=223
f(23)=677
f(24)=683
f(25)=229
f(26)=53
f(27)=1
f(28)=1
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)=67
f(55)=1
f(56)=181
f(57)=241
f(58)=101
f(59)=367
f(60)=433
f(61)=167
f(62)=571
f(63)=643
f(64)=239
f(65)=1
f(66)=1
f(67)=317
f(68)=1033
f(69)=1117
f(70)=401
f(71)=1291
f(72)=1381
f(73)=491
f(74)=1567
f(75)=1663
f(76)=587
f(77)=1861
f(78)=151
f(79)=1
f(80)=1
f(81)=2281
f(82)=797
f(83)=2503
f(84)=2617
f(85)=911
f(86)=2851
f(87)=2971
f(88)=1031
f(89)=3217
f(90)=3343
f(91)=1
f(92)=277
f(93)=3733
f(94)=1289
f(95)=4003
f(96)=1
f(97)=1427
f(98)=4423
f(99)=4567
b) Substitution of the polynom
The polynom f(x)=x^2-53x+13 could be written as f(y)= y^2-689.25 with x=y+26.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-26.5
f'(x)>2x-54 with x > 26
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 | 8 | 3 | 1.100000 | 0.800000 | 1.100000 | |||
2 | 100 | 63 | 41 | 22 | 0.630000 | 0.410000 | 0.630000 | 5.727273 | 5.125000 | 7.333333 |
3 | 1.000 | 789 | 339 | 450 | 0.789000 | 0.339000 | 0.789000 | 12.523809 | 8.268292 | 20.454546 |
4 | 10.000 | 7.931 | 2.477 | 5.454 | 0.793100 | 0.247700 | 0.793100 | 10.051965 | 7.306785 | 12.120000 |
5 | 100.000 | 77.673 | 18.868 | 58.805 | 0.776730 | 0.188680 | 0.776730 | 9.793594 | 7.617279 | 10.781995 |
6 | 1.000.000 | 761.492 | 154.921 | 606.571 | 0.761492 | 0.154921 | 0.761492 | 9.803819 | 8.210780 | 10.314957 |
7 | 10.000.000 | 7.512.792 | 1.306.569 | 6.206.223 | 0.751279 | 0.130657 | 0.751279 | 9.865885 | 8.433776 | 10.231651 |
8 | 100.000.000 | 74.366.921 | 11.319.977 | 63.046.944 | 0.743669 | 0.113200 | 0.743669 | 9.898706 | 8.663896 | 10.158666 |
9 | 1.000.000.000 | 737.807.725 | 99.917.556 | 637.890.169 | 0.737808 | 0.099918 | 0.737808 | 9.921182 | 8.826656 | 10.117702 |
10 | 10.000.000.000 | 7.331.893.725 | 894.098.169 | 6.437.795.556 | 0.733189 | 0.089410 | 0.733189 | 9.937405 | 8.948359 | 10.092325 |
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 | |||
2 | 4 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 9 | 7 | 2 | 1.125000 | 0.875000 | 0.250000 | 1.800000 | 1.750000 | 2.000000 |
4 | 16 | 16 | 11 | 5 | 1.000000 | 0.687500 | 0.312500 | 1.777778 | 1.571429 | 2.500000 |
5 | 32 | 26 | 17 | 9 | 0.812500 | 0.531250 | 0.281250 | 1.625000 | 1.545455 | 1.800000 |
6 | 64 | 34 | 23 | 11 | 0.531250 | 0.359375 | 0.171875 | 1.307692 | 1.352941 | 1.222222 |
7 | 128 | 87 | 55 | 32 | 0.679688 | 0.429688 | 0.250000 | 2.558824 | 2.391304 | 2.909091 |
8 | 256 | 190 | 103 | 87 | 0.742188 | 0.402344 | 0.339844 | 2.183908 | 1.872727 | 2.718750 |
9 | 512 | 398 | 185 | 213 | 0.777344 | 0.361328 | 0.416016 | 2.094737 | 1.796116 | 2.448276 |
10 | 1.024 | 808 | 346 | 462 | 0.789062 | 0.337891 | 0.451172 | 2.030151 | 1.870270 | 2.169014 |
11 | 2.048 | 1.638 | 619 | 1.019 | 0.799805 | 0.302246 | 0.497559 | 2.027228 | 1.789017 | 2.205628 |
12 | 4.096 | 3.269 | 1.137 | 2.132 | 0.798096 | 0.277588 | 0.520508 | 1.995726 | 1.836834 | 2.092247 |
13 | 8.192 | 6.525 | 2.076 | 4.449 | 0.796509 | 0.253418 | 0.543091 | 1.996023 | 1.825858 | 2.086773 |
14 | 16.384 | 12.968 | 3.814 | 9.154 | 0.791504 | 0.232788 | 0.558716 | 1.987433 | 1.837187 | 2.057541 |
15 | 32.768 | 25.713 | 7.003 | 18.710 | 0.784698 | 0.213715 | 0.570984 | 1.982804 | 1.836130 | 2.043915 |
16 | 65.536 | 51.127 | 12.876 | 38.251 | 0.780136 | 0.196472 | 0.583664 | 1.988372 | 1.838641 | 2.044415 |
17 | 131.072 | 101.551 | 24.088 | 77.463 | 0.774773 | 0.183777 | 0.590996 | 1.986250 | 1.870767 | 2.025124 |
18 | 262.144 | 201.692 | 45.336 | 156.356 | 0.769394 | 0.172943 | 0.596451 | 1.986115 | 1.882099 | 2.018461 |
19 | 524.288 | 401.147 | 85.624 | 315.523 | 0.765127 | 0.163315 | 0.601812 | 1.988909 | 1.888654 | 2.017978 |
20 | 1.048.576 | 798.111 | 161.752 | 636.359 | 0.761138 | 0.154259 | 0.606879 | 1.989572 | 1.889096 | 2.016839 |
21 | 2.097.152 | 1.589.443 | 306.207 | 1.283.236 | 0.757905 | 0.146011 | 0.611895 | 1.991506 | 1.893065 | 2.016528 |
22 | 4.194.304 | 3.165.999 | 581.696 | 2.584.303 | 0.754833 | 0.138687 | 0.616146 | 1.991892 | 1.899682 | 2.013895 |
23 | 8.388.608 | 6.307.961 | 1.108.528 | 5.199.433 | 0.751968 | 0.132147 | 0.619821 | 1.992408 | 1.905683 | 2.011929 |
24 | 16.777.216 | 12.572.794 | 2.118.447 | 10.454.347 | 0.749397 | 0.126269 | 0.623128 | 1.993163 | 1.911045 | 2.010671 |
25 | 33.554.432 | 25.064.911 | 4.055.129 | 21.009.782 | 0.746993 | 0.120852 | 0.626140 | 1.993583 | 1.914199 | 2.009670 |
26 | 67.108.864 | 49.984.637 | 7.777.799 | 42.206.838 | 0.744829 | 0.115898 | 0.628931 | 1.994208 | 1.918015 | 2.008914 |
27 | 134.217.728 | 99.702.228 | 14.940.774 | 84.761.454 | 0.742839 | 0.111317 | 0.631522 | 1.994657 | 1.920951 | 2.008240 |
28 | 268.435.456 | 198.906.498 | 28.749.943 | 170.156.555 | 0.740984 | 0.107102 | 0.633883 | 1.995006 | 1.924261 | 2.007476 |
29 | 536.870.912 | 396.883.726 | 55.399.312 | 341.484.414 | 0.739254 | 0.103189 | 0.636064 | 1.995328 | 1.926936 | 2.006884 |
30 | 1.073.741.824 | 792.046.238 | 106.895.424 | 685.150.814 | 0.737651 | 0.099554 | 0.638096 | 1.995663 | 1.929544 | 2.006390 |
31 | 2.147.483.648 | 1.580.899.330 | 206.507.016 | 1.374.392.314 | 0.736164 | 0.096162 | 0.640001 | 1.995969 | 1.931860 | 2.005970 |
32 | 4.294.967.296 | 3.155.807.825 | 399.414.092 | 2.756.393.733 | 0.734769 | 0.092996 | 0.641773 | 1.996210 | 1.934143 | 2.005536 |
33 | 8.589.934.592 | 6.300.407.409 | 773.375.712 | 5.527.031.697 | 0.733464 | 0.090033 | 0.643431 | 1.996448 | 1.936276 | 2.005168 |
34 | 17.179.869.184 | 12.579.737.723 | 1.499.069.603 | 11.080.668.120 | 0.732237 | 0.087257 | 0.644980 | 1.996655 | 1.938346 | 2.004813 |
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 | 1 | 1 | 1 | 0 | 1 | 1 |
2 | 4 | 4 | 1 | 2 | 2 | 0 | 1 | 1 |
3 | 8 | 7 | 1 | 5 | 2 | 2 | 2 | 1 |
4 | 16 | 11 | 1 | 9 | 3 | 2 | 3 | 3 |
5 | 32 | 17 | 1 | 15 | 4 | 4 | 4 | 5 |
6 | 64 | 23 | 7 | 15 | 6 | 6 | 5 | 6 |
7 | 128 | 55 | 39 | 15 | 13 | 13 | 13 | 16 |
8 | 256 | 103 | 87 | 15 | 25 | 26 | 24 | 28 |
9 | 512 | 185 | 169 | 15 | 45 | 46 | 47 | 47 |
10 | 1.024 | 346 | 330 | 15 | 87 | 83 | 89 | 87 |
11 | 2.048 | 619 | 603 | 15 | 163 | 147 | 150 | 159 |
12 | 4.096 | 1.137 | 1.121 | 15 | 292 | 277 | 278 | 290 |
13 | 8.192 | 2.076 | 2.060 | 15 | 542 | 499 | 523 | 512 |
14 | 16.384 | 3.814 | 3.798 | 15 | 981 | 951 | 958 | 924 |
15 | 32.768 | 7.003 | 6.987 | 15 | 1.787 | 1.750 | 1.742 | 1.724 |
16 | 65.536 | 12.876 | 12.860 | 15 | 3.270 | 3.205 | 3.177 | 3.224 |
17 | 131.072 | 24.088 | 24.072 | 15 | 6.057 | 6.022 | 5.989 | 6.020 |
18 | 262.144 | 45.336 | 45.320 | 15 | 11.415 | 11.242 | 11.333 | 11.346 |
19 | 524.288 | 85.624 | 85.608 | 15 | 21.486 | 21.281 | 21.415 | 21.442 |
20 | 1.048.576 | 161.752 | 161.736 | 15 | 40.557 | 40.363 | 40.542 | 40.290 |
21 | 2.097.152 | 306.207 | 306.191 | 15 | 76.919 | 76.307 | 76.525 | 76.456 |
22 | 4.194.304 | 581.696 | 581.680 | 15 | 145.916 | 145.224 | 145.467 | 145.089 |
23 | 8.388.608 | 1.108.528 | 1.108.512 | 15 | 277.659 | 277.115 | 277.119 | 276.635 |
24 | 16.777.216 | 2.118.447 | 2.118.431 | 15 | 529.690 | 530.276 | 529.807 | 528.674 |
25 | 33.554.432 | 4.055.129 | 4.055.113 | 15 | 1.014.172 | 1.014.710 | 1.013.607 | 1.012.640 |
26 | 67.108.864 | 7.777.799 | 7.777.783 | 15 | 1.944.691 | 1.944.757 | 1.944.787 | 1.943.564 |
27 | 134.217.728 | 14.940.774 | 14.940.758 | 15 | 3.735.424 | 3.734.259 | 3.735.048 | 3.736.043 |
28 | 268.435.456 | 28.749.943 | 28.749.927 | 15 | 7.186.805 | 7.185.842 | 7.189.945 | 7.187.351 |
29 | 536.870.912 | 55.399.312 | 55.399.296 | 15 | 13.848.632 | 13.847.271 | 13.849.458 | 13.853.951 |
30 | 1.073.741.824 | 106.895.424 | 106.895.408 | 15 | 26.719.139 | 26.722.504 | 26.724.321 | 26.729.460 |
31 | 2.147.483.648 | 206.507.016 | 206.507.000 | 15 | 51.624.681 | 51.624.942 | 51.624.912 | 51.632.481 |
32 | 4.294.967.296 | 399.414.092 | 399.414.076 | 15 | 99.853.368 | 99.845.021 | 99.855.275 | 99.860.428 |
33 | 8.589.934.592 | 773.375.712 | 773.375.696 | 15 | 193.342.909 | 193.331.133 | 193.356.070 | 193.345.600 |
34 | 17.179.869.184 | 1.499.069.603 | 1.499.069.587 | 15 | 374.763.759 | 374.756.234 | 374.779.734 | 374.769.876 |
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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 2 | 0 | 0 | 0 | 1 | 1 |
4 | 16 | 5 | 4 | 1 | 2 | 1 | 1 | 1 |
5 | 32 | 9 | 7 | 2 | 2 | 2 | 3 | 2 |
6 | 64 | 11 | 7 | 4 | 2 | 2 | 3 | 4 |
7 | 128 | 32 | 11 | 21 | 8 | 7 | 9 | 8 |
8 | 256 | 87 | 24 | 63 | 21 | 22 | 19 | 25 |
9 | 512 | 213 | 64 | 149 | 54 | 56 | 47 | 56 |
10 | 1.024 | 462 | 153 | 309 | 127 | 120 | 97 | 118 |
11 | 2.048 | 1.019 | 373 | 646 | 253 | 267 | 250 | 249 |
12 | 4.096 | 2.132 | 815 | 1.317 | 520 | 540 | 537 | 535 |
13 | 8.192 | 4.449 | 1.731 | 2.718 | 1.093 | 1.097 | 1.120 | 1.139 |
14 | 16.384 | 9.154 | 3.651 | 5.503 | 2.256 | 2.288 | 2.298 | 2.312 |
15 | 32.768 | 18.710 | 7.646 | 11.064 | 4.602 | 4.646 | 4.745 | 4.717 |
16 | 65.536 | 38.251 | 15.989 | 22.262 | 9.437 | 9.566 | 9.631 | 9.617 |
17 | 131.072 | 77.463 | 32.905 | 44.558 | 19.228 | 19.374 | 19.427 | 19.434 |
18 | 262.144 | 156.356 | 67.153 | 89.203 | 38.856 | 39.223 | 39.095 | 39.182 |
19 | 524.288 | 315.523 | 137.387 | 178.136 | 78.802 | 78.683 | 79.098 | 78.940 |
20 | 1.048.576 | 636.359 | 279.927 | 356.432 | 159.011 | 159.143 | 159.149 | 159.056 |
21 | 2.097.152 | 1.283.236 | 569.299 | 713.937 | 320.582 | 320.866 | 320.868 | 320.920 |
22 | 4.194.304 | 2.584.303 | 1.155.081 | 1.429.222 | 645.563 | 646.199 | 645.782 | 646.759 |
23 | 8.388.608 | 5.199.433 | 2.337.892 | 2.861.541 | 1.299.440 | 1.299.153 | 1.299.887 | 1.300.953 |
24 | 16.777.216 | 10.454.347 | 4.729.987 | 5.724.360 | 2.614.344 | 2.611.577 | 2.613.835 | 2.614.591 |
25 | 33.554.432 | 21.009.782 | 9.555.937 | 11.453.845 | 5.251.451 | 5.250.449 | 5.254.855 | 5.253.027 |
26 | 67.108.864 | 42.206.838 | 19.281.703 | 22.925.135 | 10.551.156 | 10.550.816 | 10.553.207 | 10.551.659 |
27 | 134.217.728 | 84.761.454 | 38.887.240 | 45.874.214 | 21.187.806 | 21.187.738 | 21.194.754 | 21.191.156 |
28 | 268.435.456 | 170.156.555 | 78.358.298 | 91.798.257 | 42.533.793 | 42.536.858 | 42.543.720 | 42.542.184 |
29 | 536.870.912 | 341.484.414 | 157.811.958 | 183.672.456 | 85.357.196 | 85.375.187 | 85.378.043 | 85.373.988 |
30 | 1.073.741.824 | 685.150.814 | 317.658.542 | 367.492.272 | 171.279.223 | 171.286.621 | 171.291.705 | 171.293.265 |
31 | 2.147.483.648 | 1.374.392.314 | 639.103.272 | 735.289.042 | 343.589.382 | 343.587.472 | 343.613.484 | 343.601.976 |
32 | 4.294.967.296 | 2.756.393.733 | 1.285.277.036 | 1.471.116.697 | 689.104.724 | 689.084.999 | 689.108.204 | 689.095.806 |
33 | 8.589.934.592 | 5.527.031.697 | 2.583.813.100 | 2.943.218.597 | 1.381.753.946 | 1.381.754.682 | 1.381.777.893 | 1.381.745.176 |
34 | 17.179.869.184 | 11.080.668.120 | 5.192.342.711 | 5.888.325.409 | 2.770.174.748 | 2.770.157.132 | 2.770.213.590 | 2.770.122.650 |