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+44x-61
f(0)=61
f(1)=1
f(2)=31
f(3)=5
f(4)=131
f(5)=23
f(6)=239
f(7)=37
f(8)=71
f(9)=13
f(10)=479
f(11)=17
f(12)=47
f(13)=1
f(14)=751
f(15)=103
f(16)=29
f(17)=1
f(18)=211
f(19)=1
f(20)=53
f(21)=163
f(22)=107
f(23)=1
f(24)=1571
f(25)=1
f(26)=1759
f(27)=1
f(28)=1
f(29)=257
f(30)=127
f(31)=283
f(32)=2371
f(33)=1
f(34)=2591
f(35)=1
f(36)=2819
f(37)=367
f(38)=1
f(39)=397
f(40)=3299
f(41)=1
f(42)=67
f(43)=1
f(44)=1
f(45)=1
f(46)=4079
f(47)=1
f(48)=1
f(49)=281
f(50)=4639
f(51)=1
f(52)=4931
f(53)=1
f(54)=5231
f(55)=673
f(56)=191
f(57)=89
f(58)=1171
f(59)=1
f(60)=167
f(61)=1
f(62)=383
f(63)=1
f(64)=1
f(65)=439
f(66)=313
f(67)=461
f(68)=1511
f(69)=967
f(70)=7919
f(71)=1013
f(72)=8291
f(73)=1
f(74)=1
f(75)=277
f(76)=9059
f(77)=1
f(78)=1
f(79)=1
f(80)=9859
f(81)=1
f(82)=10271
f(83)=1
f(84)=10691
f(85)=1
f(86)=11119
f(87)=109
f(88)=2311
f(89)=1
f(90)=1
f(91)=1
f(92)=12451
f(93)=317
f(94)=12911
f(95)=1
f(96)=787
f(97)=1
f(98)=1
f(99)=881
b) Substitution of the polynom
The polynom f(x)=x^2+44x-61 could be written as f(y)= y^2-545 with x=y-22
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+22
f'(x)>2x+43
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 | 5 | 4 | 0.900000 | 0.500000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 59 | 25 | 34 | 0.590000 | 0.250000 | 0.590000 | 6.555555 | 5.000000 | 8.500000 |
3 | 1.000 | 638 | 135 | 503 | 0.638000 | 0.135000 | 0.638000 | 10.813560 | 5.400000 | 14.794118 |
4 | 10.000 | 6.574 | 980 | 5.594 | 0.657400 | 0.098000 | 0.657400 | 10.304075 | 7.259259 | 11.121272 |
5 | 100.000 | 66.413 | 7.677 | 58.736 | 0.664130 | 0.076770 | 0.664130 | 10.102373 | 7.833673 | 10.499822 |
6 | 1.000.000 | 669.370 | 63.393 | 605.977 | 0.669370 | 0.063393 | 0.669370 | 10.078900 | 8.257523 | 10.316960 |
7 | 10.000.000 | 6.727.380 | 536.991 | 6.190.389 | 0.672738 | 0.053699 | 0.672738 | 10.050316 | 8.470825 | 10.215551 |
8 | 100.000.000 | 67.525.075 | 4.648.035 | 62.877.040 | 0.675251 | 0.046480 | 0.675251 | 10.037351 | 8.655704 | 10.157204 |
9 | 1.000.000.000 | 677.238.634 | 41.004.271 | 636.234.363 | 0.677239 | 0.041004 | 0.677239 | 10.029440 | 8.821851 | 10.118708 |
10 | 10.000.000.000 | 6.788.160.156 | 366.945.608 | 6.421.214.548 | 0.678816 | 0.036695 | 0.678816 | 10.023291 | 8.948960 | 10.092530 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 2.000000 | 1.500000 | inf |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 1.333333 | 4.000000 |
4 | 16 | 12 | 6 | 6 | 0.750000 | 0.375000 | 0.375000 | 1.500000 | 1.500000 | 1.500000 |
5 | 32 | 22 | 9 | 13 | 0.687500 | 0.281250 | 0.406250 | 1.833333 | 1.500000 | 2.166667 |
6 | 64 | 37 | 16 | 21 | 0.578125 | 0.250000 | 0.328125 | 1.681818 | 1.777778 | 1.615385 |
7 | 128 | 80 | 29 | 51 | 0.625000 | 0.226562 | 0.398438 | 2.162162 | 1.812500 | 2.428571 |
8 | 256 | 158 | 46 | 112 | 0.617188 | 0.179688 | 0.437500 | 1.975000 | 1.586207 | 2.196079 |
9 | 512 | 323 | 74 | 249 | 0.630859 | 0.144531 | 0.486328 | 2.044304 | 1.608696 | 2.223214 |
10 | 1.024 | 657 | 137 | 520 | 0.641602 | 0.133789 | 0.507812 | 2.034056 | 1.851351 | 2.088353 |
11 | 2.048 | 1.328 | 249 | 1.079 | 0.648438 | 0.121582 | 0.526855 | 2.021309 | 1.817518 | 2.075000 |
12 | 4.096 | 2.668 | 451 | 2.217 | 0.651367 | 0.110107 | 0.541260 | 2.009036 | 1.811245 | 2.054680 |
13 | 8.192 | 5.362 | 833 | 4.529 | 0.654541 | 0.101685 | 0.552856 | 2.009745 | 1.847007 | 2.042851 |
14 | 16.384 | 10.789 | 1.515 | 9.274 | 0.658508 | 0.092468 | 0.566040 | 2.012122 | 1.818727 | 2.047693 |
15 | 32.768 | 21.684 | 2.819 | 18.865 | 0.661743 | 0.086029 | 0.575714 | 2.009825 | 1.860726 | 2.034182 |
16 | 65.536 | 43.462 | 5.229 | 38.233 | 0.663177 | 0.079788 | 0.583389 | 2.004335 | 1.854913 | 2.026663 |
17 | 131.072 | 87.129 | 9.843 | 77.286 | 0.664742 | 0.075096 | 0.589645 | 2.004717 | 1.882387 | 2.021447 |
18 | 262.144 | 174.729 | 18.641 | 156.088 | 0.666538 | 0.071110 | 0.595428 | 2.005406 | 1.893833 | 2.019615 |
19 | 524.288 | 350.290 | 34.977 | 315.313 | 0.668125 | 0.066713 | 0.601412 | 2.004762 | 1.876348 | 2.020098 |
20 | 1.048.576 | 701.910 | 66.177 | 635.733 | 0.669394 | 0.063111 | 0.606282 | 2.003797 | 1.892015 | 2.016196 |
21 | 2.097.152 | 1.406.351 | 125.577 | 1.280.774 | 0.670600 | 0.059880 | 0.610721 | 2.003606 | 1.897593 | 2.014641 |
22 | 4.194.304 | 2.816.651 | 239.226 | 2.577.425 | 0.671542 | 0.057036 | 0.614506 | 2.002808 | 1.905014 | 2.012396 |
23 | 8.388.608 | 5.641.360 | 456.032 | 5.185.328 | 0.672503 | 0.054363 | 0.618139 | 2.002861 | 1.906281 | 2.011825 |
24 | 16.777.216 | 11.296.886 | 869.968 | 10.426.918 | 0.673347 | 0.051854 | 0.621493 | 2.002511 | 1.907691 | 2.010850 |
25 | 33.554.432 | 22.620.878 | 1.665.296 | 20.955.582 | 0.674155 | 0.049630 | 0.624525 | 2.002399 | 1.914204 | 2.009758 |
26 | 67.108.864 | 45.289.363 | 3.193.438 | 42.095.925 | 0.674864 | 0.047586 | 0.627278 | 2.002105 | 1.917640 | 2.008817 |
27 | 134.217.728 | 90.669.999 | 6.134.138 | 84.535.861 | 0.675544 | 0.045703 | 0.629841 | 2.002015 | 1.920857 | 2.008172 |
28 | 268.435.456 | 181.507.499 | 11.798.935 | 169.708.564 | 0.676168 | 0.043954 | 0.632214 | 2.001848 | 1.923487 | 2.007533 |
29 | 536.870.912 | 363.330.820 | 22.734.835 | 340.595.985 | 0.676756 | 0.042347 | 0.634409 | 2.001740 | 1.926855 | 2.006947 |
30 | 1.073.741.824 | 727.238.696 | 43.867.886 | 683.370.810 | 0.677294 | 0.040855 | 0.636439 | 2.001588 | 1.929545 | 2.006397 |
31 | 2.147.483.648 | 1.455.564.268 | 84.749.261 | 1.370.815.007 | 0.677800 | 0.039464 | 0.638335 | 2.001494 | 1.931920 | 2.005961 |
32 | 4.294.967.296 | 2.913.159.124 | 163.925.378 | 2.749.233.746 | 0.678273 | 0.038167 | 0.640106 | 2.001395 | 1.934240 | 2.005547 |
33 | 8.589.934.592 | 5.830.168.234 | 317.407.035 | 5.512.761.199 | 0.678721 | 0.036951 | 0.641770 | 2.001322 | 1.936290 | 2.005199 |
34 | 17.179.869.184 | 11.667.555.435 | 615.248.944 | 11.052.306.491 | 0.679141 | 0.035812 | 0.643329 | 2.001238 | 1.938359 | 2.004858 |
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 | 2 | 0 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
4 | 16 | 6 | 3 | 3 | 0 | 1 | 1 | 4 |
5 | 32 | 9 | 5 | 4 | 0 | 3 | 1 | 5 |
6 | 64 | 16 | 6 | 10 | 0 | 6 | 1 | 9 |
7 | 128 | 29 | 11 | 18 | 0 | 13 | 1 | 15 |
8 | 256 | 46 | 15 | 31 | 0 | 21 | 1 | 24 |
9 | 512 | 74 | 25 | 49 | 0 | 36 | 1 | 37 |
10 | 1.024 | 137 | 46 | 91 | 0 | 68 | 1 | 68 |
11 | 2.048 | 249 | 90 | 159 | 0 | 118 | 1 | 130 |
12 | 4.096 | 451 | 157 | 294 | 0 | 218 | 1 | 232 |
13 | 8.192 | 833 | 295 | 538 | 0 | 409 | 1 | 423 |
14 | 16.384 | 1.515 | 519 | 996 | 0 | 733 | 1 | 781 |
15 | 32.768 | 2.819 | 969 | 1.850 | 0 | 1.398 | 1 | 1.420 |
16 | 65.536 | 5.229 | 1.754 | 3.475 | 0 | 2.598 | 1 | 2.630 |
17 | 131.072 | 9.843 | 3.261 | 6.582 | 0 | 4.946 | 1 | 4.896 |
18 | 262.144 | 18.641 | 6.203 | 12.438 | 0 | 9.293 | 1 | 9.347 |
19 | 524.288 | 34.977 | 11.632 | 23.345 | 0 | 17.423 | 1 | 17.553 |
20 | 1.048.576 | 66.177 | 21.997 | 44.180 | 0 | 33.057 | 1 | 33.119 |
21 | 2.097.152 | 125.577 | 41.916 | 83.661 | 0 | 62.815 | 1 | 62.761 |
22 | 4.194.304 | 239.226 | 79.836 | 159.390 | 0 | 119.587 | 1 | 119.638 |
23 | 8.388.608 | 456.032 | 152.136 | 303.896 | 0 | 227.824 | 1 | 228.207 |
24 | 16.777.216 | 869.968 | 290.029 | 579.939 | 0 | 435.043 | 1 | 434.924 |
25 | 33.554.432 | 1.665.296 | 555.228 | 1.110.068 | 0 | 832.555 | 1 | 832.740 |
26 | 67.108.864 | 3.193.438 | 1.064.946 | 2.128.492 | 0 | 1.596.483 | 1 | 1.596.954 |
27 | 134.217.728 | 6.134.138 | 2.045.923 | 4.088.215 | 0 | 3.066.795 | 1 | 3.067.342 |
28 | 268.435.456 | 11.798.935 | 3.933.459 | 7.865.476 | 0 | 5.898.728 | 1 | 5.900.206 |
29 | 536.870.912 | 22.734.835 | 7.577.901 | 15.156.934 | 0 | 11.367.676 | 1 | 11.367.158 |
30 | 1.073.741.824 | 43.867.886 | 14.622.461 | 29.245.425 | 0 | 21.937.602 | 1 | 21.930.283 |
31 | 2.147.483.648 | 84.749.261 | 28.249.516 | 56.499.745 | 0 | 42.375.856 | 1 | 42.373.404 |
32 | 4.294.967.296 | 163.925.378 | 54.634.197 | 109.291.181 | 0 | 81.960.844 | 1 | 81.964.533 |
33 | 8.589.934.592 | 317.407.035 | 105.796.314 | 211.610.721 | 0 | 158.703.450 | 1 | 158.703.584 |
34 | 17.179.869.184 | 615.248.944 | 205.078.822 | 410.170.122 | 0 | 307.621.338 | 1 | 307.627.605 |
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 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 4 | 1 | 3 | 0 | 0 | 2 | 2 |
4 | 16 | 6 | 2 | 4 | 0 | 0 | 2 | 4 |
5 | 32 | 13 | 6 | 7 | 1 | 4 | 3 | 5 |
6 | 64 | 21 | 10 | 11 | 3 | 5 | 4 | 9 |
7 | 128 | 51 | 28 | 23 | 9 | 10 | 10 | 22 |
8 | 256 | 112 | 61 | 51 | 18 | 28 | 27 | 39 |
9 | 512 | 249 | 136 | 113 | 46 | 76 | 56 | 71 |
10 | 1.024 | 520 | 274 | 246 | 98 | 159 | 112 | 151 |
11 | 2.048 | 1.079 | 566 | 513 | 208 | 322 | 242 | 307 |
12 | 4.096 | 2.217 | 1.147 | 1.070 | 470 | 638 | 499 | 610 |
13 | 8.192 | 4.529 | 2.349 | 2.180 | 1.009 | 1.243 | 1.023 | 1.254 |
14 | 16.384 | 9.274 | 4.778 | 4.496 | 2.151 | 2.523 | 2.118 | 2.482 |
15 | 32.768 | 18.865 | 9.678 | 9.187 | 4.382 | 5.058 | 4.393 | 5.032 |
16 | 65.536 | 38.233 | 19.459 | 18.774 | 8.928 | 10.195 | 8.966 | 10.144 |
17 | 131.072 | 77.286 | 39.571 | 37.715 | 18.138 | 20.429 | 18.192 | 20.527 |
18 | 262.144 | 156.088 | 79.486 | 76.602 | 36.705 | 41.340 | 36.844 | 41.199 |
19 | 524.288 | 315.313 | 160.963 | 154.350 | 74.520 | 83.058 | 74.696 | 83.039 |
20 | 1.048.576 | 635.733 | 324.208 | 311.525 | 150.865 | 167.123 | 151.015 | 166.730 |
21 | 2.097.152 | 1.280.774 | 652.227 | 628.547 | 305.209 | 335.676 | 305.024 | 334.865 |
22 | 4.194.304 | 2.577.425 | 1.310.692 | 1.266.733 | 615.922 | 673.492 | 615.854 | 672.157 |
23 | 8.388.608 | 5.185.328 | 2.633.425 | 2.551.903 | 1.242.612 | 1.351.125 | 1.241.568 | 1.350.023 |
24 | 16.777.216 | 10.426.918 | 5.293.223 | 5.133.695 | 2.504.201 | 2.711.865 | 2.502.524 | 2.708.328 |
25 | 33.554.432 | 20.955.582 | 10.625.123 | 10.330.459 | 5.043.010 | 5.437.065 | 5.040.360 | 5.435.147 |
26 | 67.108.864 | 42.095.925 | 21.332.271 | 20.763.654 | 10.147.426 | 10.903.019 | 10.146.952 | 10.898.528 |
27 | 134.217.728 | 84.535.861 | 42.815.858 | 41.720.003 | 20.412.218 | 21.858.856 | 20.413.372 | 21.851.415 |
28 | 268.435.456 | 169.708.564 | 85.911.971 | 83.796.593 | 41.036.653 | 43.823.327 | 41.041.589 | 43.806.995 |
29 | 536.870.912 | 340.595.985 | 172.345.559 | 168.250.426 | 82.472.920 | 87.830.062 | 82.476.648 | 87.816.355 |
30 | 1.073.741.824 | 683.370.810 | 345.613.351 | 337.757.459 | 165.689.697 | 175.994.596 | 165.700.763 | 175.985.754 |
31 | 2.147.483.648 | 1.370.815.007 | 692.990.753 | 677.824.254 | 332.777.425 | 352.608.216 | 332.808.603 | 352.620.763 |
32 | 4.294.967.296 | 2.749.233.746 | 1.389.269.950 | 1.359.963.796 | 668.153.079 | 706.456.858 | 668.159.156 | 706.464.653 |
33 | 8.589.934.592 | 5.512.761.199 | 2.784.737.619 | 2.728.023.580 | 1.341.133.384 | 1.415.234.413 | 1.341.142.264 | 1.415.251.138 |
34 | 17.179.869.184 | 11.052.306.491 | 5.581.040.017 | 5.471.266.474 | 2.691.386.628 | 2.834.770.917 | 2.691.319.440 | 2.834.829.506 |