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+84x-109
f(0)=109
f(1)=3
f(2)=7
f(3)=19
f(4)=1
f(5)=1
f(6)=431
f(7)=11
f(8)=1
f(9)=13
f(10)=277
f(11)=1
f(12)=149
f(13)=1
f(14)=421
f(15)=43
f(16)=71
f(17)=67
f(18)=157
f(19)=1
f(20)=73
f(21)=131
f(22)=1
f(23)=1
f(24)=191
f(25)=1
f(26)=1
f(27)=1
f(28)=1009
f(29)=1
f(30)=1
f(31)=1
f(32)=1201
f(33)=1
f(34)=1301
f(35)=1
f(36)=4211
f(37)=1
f(38)=503
f(39)=293
f(40)=1
f(41)=1
f(42)=1
f(43)=223
f(44)=263
f(45)=89
f(46)=103
f(47)=1
f(48)=479
f(49)=1
f(50)=1
f(51)=1
f(52)=211
f(53)=1
f(54)=1049
f(55)=1
f(56)=859
f(57)=991
f(58)=1
f(59)=347
f(60)=449
f(61)=1
f(62)=271
f(63)=1
f(64)=3121
f(65)=1
f(66)=9791
f(67)=139
f(68)=487
f(69)=653
f(70)=3557
f(71)=227
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=12527
f(79)=1
f(80)=4337
f(81)=1657
f(82)=643
f(83)=1
f(84)=1
f(85)=1
f(86)=691
f(87)=1
f(88)=5009
f(89)=1
f(90)=15551
f(91)=659
f(92)=1787
f(93)=1
f(94)=1847
f(95)=1
f(96)=1
f(97)=727
f(98)=311
f(99)=2251
b) Substitution of the polynom
The polynom f(x)=x^2+84x-109 could be written as f(y)= y^2-1873 with x=y-42
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+42
f'(x)>2x+83
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 | 6 | 4 | 2 | 0.600000 | 0.400000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 52 | 15 | 37 | 0.520000 | 0.150000 | 0.370000 | 8.666667 | 3.750000 | 18.500000 |
3 | 1.000 | 560 | 106 | 454 | 0.560000 | 0.106000 | 0.454000 | 10.769231 | 7.066667 | 12.270270 |
4 | 10.000 | 5.959 | 737 | 5.222 | 0.595900 | 0.073700 | 0.522200 | 10.641071 | 6.952830 | 11.502203 |
5 | 100.000 | 61.846 | 5.544 | 56.302 | 0.618460 | 0.055440 | 0.563020 | 10.378587 | 7.522388 | 10.781693 |
6 | 1.000.000 | 632.013 | 44.509 | 587.504 | 0.632013 | 0.044509 | 0.587504 | 10.219141 | 8.028319 | 10.434869 |
7 | 10.000.000 | 6.411.502 | 371.732 | 6.039.770 | 0.641150 | 0.037173 | 0.603977 | 10.144573 | 8.351839 | 10.280390 |
8 | 100.000.000 | 64.789.233 | 3.200.967 | 61.588.266 | 0.647892 | 0.032010 | 0.615883 | 10.105157 | 8.610953 | 10.197121 |
9 | 1.000.000.000 | 653.077.553 | 28.074.601 | 625.002.952 | 0.653078 | 0.028075 | 0.625003 | 10.080032 | 8.770662 | 10.148085 |
10 | 10.000.000.000 | 6.571.867.165 | 250.209.181 | 6.321.657.984 | 0.657187 | 0.025021 | 0.632166 | 10.062920 | 8.912297 | 10.114605 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 5 | 4 | 1 | 0.625000 | 0.500000 | 0.125000 | 1.250000 | 1.333333 | 1.000000 |
4 | 16 | 10 | 5 | 5 | 0.625000 | 0.312500 | 0.312500 | 2.000000 | 1.250000 | 5.000000 |
5 | 32 | 17 | 6 | 11 | 0.531250 | 0.187500 | 0.343750 | 1.700000 | 1.200000 | 2.200000 |
6 | 64 | 33 | 9 | 24 | 0.515625 | 0.140625 | 0.375000 | 1.941176 | 1.500000 | 2.181818 |
7 | 128 | 67 | 20 | 47 | 0.523438 | 0.156250 | 0.367188 | 2.030303 | 2.222222 | 1.958333 |
8 | 256 | 138 | 34 | 104 | 0.539062 | 0.132812 | 0.406250 | 2.059701 | 1.700000 | 2.212766 |
9 | 512 | 277 | 60 | 217 | 0.541016 | 0.117188 | 0.423828 | 2.007246 | 1.764706 | 2.086539 |
10 | 1.024 | 575 | 108 | 467 | 0.561523 | 0.105469 | 0.456055 | 2.075812 | 1.800000 | 2.152074 |
11 | 2.048 | 1.180 | 192 | 988 | 0.576172 | 0.093750 | 0.482422 | 2.052174 | 1.777778 | 2.115632 |
12 | 4.096 | 2.388 | 340 | 2.048 | 0.583008 | 0.083008 | 0.500000 | 2.023729 | 1.770833 | 2.072875 |
13 | 8.192 | 4.861 | 631 | 4.230 | 0.593384 | 0.077026 | 0.516357 | 2.035595 | 1.855882 | 2.065430 |
14 | 16.384 | 9.902 | 1.113 | 8.789 | 0.604370 | 0.067932 | 0.536438 | 2.037030 | 1.763867 | 2.077778 |
15 | 32.768 | 20.009 | 2.054 | 17.955 | 0.610626 | 0.062683 | 0.547943 | 2.020703 | 1.845463 | 2.042895 |
16 | 65.536 | 40.349 | 3.820 | 36.529 | 0.615677 | 0.058289 | 0.557388 | 2.016543 | 1.859786 | 2.034475 |
17 | 131.072 | 81.332 | 7.061 | 74.271 | 0.620514 | 0.053871 | 0.566643 | 2.015713 | 1.848429 | 2.033206 |
18 | 262.144 | 163.743 | 13.249 | 150.494 | 0.624630 | 0.050541 | 0.574089 | 2.013267 | 1.876363 | 2.026282 |
19 | 524.288 | 329.620 | 24.867 | 304.753 | 0.628700 | 0.047430 | 0.581270 | 2.013033 | 1.876896 | 2.025017 |
20 | 1.048.576 | 663.082 | 46.414 | 616.668 | 0.632364 | 0.044264 | 0.588100 | 2.011656 | 1.866490 | 2.023501 |
21 | 2.097.152 | 1.332.380 | 87.895 | 1.244.485 | 0.635328 | 0.041912 | 0.593417 | 2.009374 | 1.893717 | 2.018080 |
22 | 4.194.304 | 2.676.377 | 166.613 | 2.509.764 | 0.638098 | 0.039724 | 0.598374 | 2.008719 | 1.895591 | 2.016709 |
23 | 8.388.608 | 5.373.517 | 315.851 | 5.057.666 | 0.640573 | 0.037652 | 0.602921 | 2.007758 | 1.895716 | 2.015196 |
24 | 16.777.216 | 10.785.181 | 602.125 | 10.183.056 | 0.642847 | 0.035889 | 0.606957 | 2.007099 | 1.906358 | 2.013390 |
25 | 33.554.432 | 21.641.328 | 1.150.362 | 20.490.966 | 0.644962 | 0.034283 | 0.610678 | 2.006580 | 1.910504 | 2.012261 |
26 | 67.108.864 | 43.410.462 | 2.201.363 | 41.209.099 | 0.646866 | 0.032803 | 0.614063 | 2.005906 | 1.913626 | 2.011086 |
27 | 134.217.728 | 87.057.885 | 4.220.433 | 82.837.452 | 0.648632 | 0.031445 | 0.617187 | 2.005459 | 1.917191 | 2.010174 |
28 | 268.435.456 | 174.556.192 | 8.103.364 | 166.452.828 | 0.650272 | 0.030187 | 0.620085 | 2.005059 | 1.920031 | 2.009391 |
29 | 536.870.912 | 349.936.602 | 15.587.587 | 334.349.015 | 0.651808 | 0.029034 | 0.622774 | 2.004722 | 1.923595 | 2.008671 |
30 | 1.073.741.824 | 701.388.686 | 30.032.365 | 671.356.321 | 0.653219 | 0.027970 | 0.625249 | 2.004331 | 1.926685 | 2.007951 |
31 | 2.147.483.648 | 1.405.617.949 | 57.941.975 | 1.347.675.974 | 0.654542 | 0.026981 | 0.627561 | 2.004050 | 1.929318 | 2.007393 |
32 | 4.294.967.296 | 2.816.554.310 | 111.929.146 | 2.704.625.164 | 0.655780 | 0.026061 | 0.629720 | 2.003784 | 1.931745 | 2.006881 |
33 | 8.589.934.592 | 5.643.080.635 | 216.478.560 | 5.426.602.075 | 0.656941 | 0.025201 | 0.631740 | 2.003541 | 1.934068 | 2.006416 |
34 | 17.179.869.184 | 11.304.886.475 | 419.146.814 | 10.885.739.661 | 0.658031 | 0.024398 | 0.633633 | 2.003318 | 1.936205 | 2.005996 |
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 | 0 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 2 | 0 | 0 | 2 | 1 | 0 |
3 | 8 | 4 | 2 | 1 | 0 | 2 | 1 | 1 |
4 | 16 | 5 | 3 | 1 | 0 | 3 | 1 | 1 |
5 | 32 | 6 | 3 | 2 | 0 | 4 | 1 | 1 |
6 | 64 | 9 | 4 | 4 | 0 | 5 | 2 | 2 |
7 | 128 | 20 | 9 | 10 | 3 | 9 | 3 | 5 |
8 | 256 | 34 | 15 | 18 | 4 | 14 | 5 | 11 |
9 | 512 | 60 | 21 | 38 | 6 | 23 | 8 | 23 |
10 | 1.024 | 108 | 37 | 70 | 15 | 39 | 11 | 43 |
11 | 2.048 | 192 | 69 | 122 | 29 | 68 | 22 | 73 |
12 | 4.096 | 340 | 122 | 217 | 48 | 123 | 41 | 128 |
13 | 8.192 | 631 | 215 | 415 | 82 | 227 | 85 | 237 |
14 | 16.384 | 1.113 | 386 | 726 | 148 | 409 | 151 | 405 |
15 | 32.768 | 2.054 | 715 | 1.338 | 283 | 754 | 274 | 743 |
16 | 65.536 | 3.820 | 1.340 | 2.479 | 533 | 1.403 | 500 | 1.384 |
17 | 131.072 | 7.061 | 2.493 | 4.567 | 982 | 2.604 | 922 | 2.553 |
18 | 262.144 | 13.249 | 4.625 | 8.623 | 1.785 | 4.898 | 1.747 | 4.819 |
19 | 524.288 | 24.867 | 8.647 | 16.219 | 3.320 | 9.280 | 3.270 | 8.997 |
20 | 1.048.576 | 46.414 | 16.069 | 30.344 | 6.146 | 17.196 | 6.094 | 16.978 |
21 | 2.097.152 | 87.895 | 30.426 | 57.468 | 11.483 | 32.434 | 11.553 | 32.425 |
22 | 4.194.304 | 166.613 | 57.818 | 108.794 | 21.760 | 61.509 | 21.957 | 61.387 |
23 | 8.388.608 | 315.851 | 109.353 | 206.497 | 41.340 | 116.854 | 41.397 | 116.260 |
24 | 16.777.216 | 602.125 | 208.297 | 393.827 | 78.597 | 222.794 | 78.940 | 221.794 |
25 | 33.554.432 | 1.150.362 | 397.276 | 753.085 | 150.086 | 425.428 | 150.339 | 424.509 |
26 | 67.108.864 | 2.201.363 | 759.314 | 1.442.048 | 286.652 | 814.488 | 287.047 | 813.176 |
27 | 134.217.728 | 4.220.433 | 1.453.751 | 2.766.681 | 548.920 | 1.562.069 | 549.391 | 1.560.053 |
28 | 268.435.456 | 8.103.364 | 2.788.640 | 5.314.723 | 1.053.349 | 2.999.506 | 1.053.048 | 2.997.461 |
29 | 536.870.912 | 15.587.587 | 5.358.766 | 10.228.820 | 2.023.416 | 5.771.271 | 2.022.285 | 5.770.615 |
30 | 1.073.741.824 | 30.032.365 | 10.315.595 | 19.716.769 | 3.894.178 | 11.124.770 | 3.890.535 | 11.122.882 |
31 | 2.147.483.648 | 57.941.975 | 19.877.398 | 38.064.576 | 7.501.127 | 21.473.904 | 7.496.246 | 21.470.698 |
32 | 4.294.967.296 | 111.929.146 | 38.358.641 | 73.570.504 | 14.471.872 | 41.496.896 | 14.468.027 | 41.492.351 |
33 | 8.589.934.592 | 216.478.560 | 74.119.349 | 142.359.210 | 27.958.609 | 80.283.375 | 27.951.944 | 80.284.632 |
34 | 17.179.869.184 | 419.146.814 | 143.400.222 | 275.746.591 | 54.079.133 | 155.503.249 | 54.065.938 | 155.498.494 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
4 | 16 | 5 | 3 | 2 | 0 | 0 | 3 | 2 |
5 | 32 | 11 | 8 | 3 | 3 | 1 | 4 | 3 |
6 | 64 | 24 | 14 | 10 | 6 | 4 | 5 | 9 |
7 | 128 | 47 | 23 | 24 | 12 | 12 | 6 | 17 |
8 | 256 | 104 | 45 | 59 | 27 | 25 | 24 | 28 |
9 | 512 | 217 | 101 | 116 | 57 | 53 | 54 | 53 |
10 | 1.024 | 467 | 221 | 246 | 127 | 104 | 119 | 117 |
11 | 2.048 | 988 | 474 | 514 | 267 | 227 | 256 | 238 |
12 | 4.096 | 2.048 | 982 | 1.066 | 529 | 480 | 545 | 494 |
13 | 8.192 | 4.230 | 2.075 | 2.155 | 1.097 | 998 | 1.130 | 1.005 |
14 | 16.384 | 8.789 | 4.276 | 4.513 | 2.296 | 2.083 | 2.315 | 2.095 |
15 | 32.768 | 17.955 | 8.787 | 9.168 | 4.688 | 4.283 | 4.678 | 4.306 |
16 | 65.536 | 36.529 | 17.839 | 18.690 | 9.478 | 8.714 | 9.670 | 8.667 |
17 | 131.072 | 74.271 | 36.368 | 37.903 | 19.293 | 17.840 | 19.407 | 17.731 |
18 | 262.144 | 150.494 | 73.826 | 76.668 | 39.241 | 35.945 | 39.150 | 36.158 |
19 | 524.288 | 304.753 | 149.797 | 154.956 | 79.119 | 73.226 | 79.064 | 73.344 |
20 | 1.048.576 | 616.668 | 303.987 | 312.681 | 159.740 | 148.749 | 159.385 | 148.794 |
21 | 2.097.152 | 1.244.485 | 614.679 | 629.806 | 321.832 | 300.798 | 321.445 | 300.410 |
22 | 4.194.304 | 2.509.764 | 1.240.581 | 1.269.183 | 647.360 | 607.919 | 647.312 | 607.173 |
23 | 8.388.608 | 5.057.666 | 2.500.709 | 2.556.957 | 1.302.458 | 1.227.412 | 1.302.136 | 1.225.660 |
24 | 16.777.216 | 10.183.056 | 5.039.349 | 5.143.707 | 2.616.782 | 2.473.153 | 2.619.244 | 2.473.877 |
25 | 33.554.432 | 20.490.966 | 10.145.582 | 10.345.384 | 5.261.486 | 4.982.487 | 5.263.140 | 4.983.853 |
26 | 67.108.864 | 41.209.099 | 20.412.214 | 20.796.885 | 10.566.561 | 10.031.134 | 10.575.311 | 10.036.093 |
27 | 134.217.728 | 82.837.452 | 41.051.074 | 41.786.378 | 21.216.673 | 20.194.370 | 21.228.636 | 20.197.773 |
28 | 268.435.456 | 166.452.828 | 82.517.718 | 83.935.110 | 42.595.745 | 40.627.290 | 42.606.985 | 40.622.808 |
29 | 536.870.912 | 334.349.015 | 165.798.927 | 168.550.088 | 85.477.115 | 81.688.346 | 85.487.794 | 81.695.760 |
30 | 1.073.741.824 | 671.356.321 | 333.044.382 | 338.311.939 | 171.480.287 | 164.190.300 | 171.498.941 | 164.186.793 |
31 | 2.147.483.648 | 1.347.675.974 | 668.769.898 | 678.906.076 | 343.974.071 | 329.857.953 | 343.972.563 | 329.871.387 |
32 | 4.294.967.296 | 2.704.625.164 | 1.342.537.714 | 1.362.087.450 | 689.788.527 | 662.521.137 | 689.796.020 | 662.519.480 |
33 | 8.589.934.592 | 5.426.602.075 | 2.694.388.194 | 2.732.213.881 | 1.383.018.511 | 1.330.288.480 | 1.383.051.940 | 1.330.243.144 |
34 | 17.179.869.184 | 10.885.739.661 | 5.406.287.112 | 5.479.452.549 | 2.772.553.584 | 2.670.323.956 | 2.772.630.449 | 2.670.231.672 |