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+1x-13
f(0)=13
f(1)=11
f(2)=7
f(3)=1
f(4)=1
f(5)=17
f(6)=29
f(7)=43
f(8)=59
f(9)=1
f(10)=97
f(11)=1
f(12)=1
f(13)=1
f(14)=197
f(15)=227
f(16)=37
f(17)=293
f(18)=47
f(19)=367
f(20)=1
f(21)=449
f(22)=1
f(23)=1
f(24)=587
f(25)=1
f(26)=53
f(27)=743
f(28)=1
f(29)=857
f(30)=131
f(31)=89
f(32)=149
f(33)=1109
f(34)=107
f(35)=1
f(36)=1319
f(37)=199
f(38)=113
f(39)=1
f(40)=1627
f(41)=1709
f(42)=163
f(43)=1879
f(44)=281
f(45)=1
f(46)=307
f(47)=2243
f(48)=2339
f(49)=2437
f(50)=1
f(51)=1
f(52)=211
f(53)=1
f(54)=2957
f(55)=3067
f(56)=1
f(57)=1
f(58)=487
f(59)=3527
f(60)=521
f(61)=3769
f(62)=229
f(63)=4019
f(64)=1
f(65)=1
f(66)=4409
f(67)=1
f(68)=4679
f(69)=4817
f(70)=4957
f(71)=5099
f(72)=1
f(73)=317
f(74)=1
f(75)=1
f(76)=5839
f(77)=461
f(78)=1
f(79)=1
f(80)=223
f(81)=947
f(82)=6793
f(83)=6959
f(84)=7127
f(85)=7297
f(86)=1
f(87)=7643
f(88)=1117
f(89)=727
f(90)=1
f(91)=643
f(92)=8543
f(93)=1
f(94)=241
f(95)=1301
f(96)=547
f(97)=863
f(98)=9689
f(99)=9887
b) Substitution of the polynom
The polynom f(x)=x^2+1x-13 could be written as f(y)= y^2-13.25 with x=y-0.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+0.5
f'(x)>2x
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 | 8 | 8 | 0 | 0.800000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 70 | 44 | 26 | 0.700000 | 0.440000 | 0.260000 | 8.750000 | 5.500000 | inf |
3 | 1.000 | 728 | 242 | 486 | 0.728000 | 0.242000 | 0.486000 | 10.400000 | 5.500000 | 18.692308 |
4 | 10.000 | 7.216 | 1.707 | 5.509 | 0.721600 | 0.170700 | 0.550900 | 9.912087 | 7.053719 | 11.335391 |
5 | 100.000 | 71.515 | 13.277 | 58.238 | 0.715150 | 0.132770 | 0.582380 | 9.910615 | 7.777973 | 10.571428 |
6 | 1.000.000 | 711.376 | 108.783 | 602.593 | 0.711376 | 0.108783 | 0.602593 | 9.947227 | 8.193342 | 10.347075 |
7 | 10.000.000 | 7.084.291 | 919.114 | 6.165.177 | 0.708429 | 0.091911 | 0.616518 | 9.958574 | 8.449059 | 10.231080 |
8 | 100.000.000 | 70.621.475 | 7.970.135 | 62.651.340 | 0.706215 | 0.079701 | 0.626513 | 9.968742 | 8.671541 | 10.162131 |
9 | 1.000.000.000 | 704.598.498 | 70.335.984 | 634.262.514 | 0.704599 | 0.070336 | 0.634263 | 9.977115 | 8.824943 | 10.123687 |
10 | 10.000.000.000 | 7.033.411.961 | 629.416.842 | 6.403.995.119 | 0.703341 | 0.062942 | 0.640400 | 9.982156 | 8.948717 | 10.096758 |
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 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 2.333333 | 2.333333 | -nan |
4 | 16 | 11 | 10 | 1 | 0.687500 | 0.625000 | 0.062500 | 1.571429 | 1.428571 | inf |
5 | 32 | 22 | 17 | 5 | 0.687500 | 0.531250 | 0.156250 | 2.000000 | 1.700000 | 5.000000 |
6 | 64 | 45 | 30 | 15 | 0.703125 | 0.468750 | 0.234375 | 2.045455 | 1.764706 | 3.000000 |
7 | 128 | 92 | 51 | 41 | 0.718750 | 0.398438 | 0.320312 | 2.044445 | 1.700000 | 2.733333 |
8 | 256 | 184 | 82 | 102 | 0.718750 | 0.320312 | 0.398438 | 2.000000 | 1.607843 | 2.487805 |
9 | 512 | 375 | 146 | 229 | 0.732422 | 0.285156 | 0.447266 | 2.038043 | 1.780488 | 2.245098 |
10 | 1.024 | 744 | 249 | 495 | 0.726562 | 0.243164 | 0.483398 | 1.984000 | 1.705480 | 2.161572 |
11 | 2.048 | 1.485 | 449 | 1.036 | 0.725098 | 0.219238 | 0.505859 | 1.995968 | 1.803213 | 2.092929 |
12 | 4.096 | 2.975 | 799 | 2.176 | 0.726318 | 0.195068 | 0.531250 | 2.003367 | 1.779510 | 2.100386 |
13 | 8.192 | 5.914 | 1.431 | 4.483 | 0.721924 | 0.174683 | 0.547241 | 1.987899 | 1.790989 | 2.060202 |
14 | 16.384 | 11.779 | 2.667 | 9.112 | 0.718933 | 0.162781 | 0.556152 | 1.991715 | 1.863732 | 2.032568 |
15 | 32.768 | 23.501 | 4.957 | 18.544 | 0.717194 | 0.151276 | 0.565918 | 1.995161 | 1.858643 | 2.035119 |
16 | 65.536 | 46.914 | 9.147 | 37.767 | 0.715851 | 0.139572 | 0.576279 | 1.996256 | 1.845269 | 2.036616 |
17 | 131.072 | 93.729 | 16.969 | 76.760 | 0.715096 | 0.129463 | 0.585632 | 1.997890 | 1.855144 | 2.032462 |
18 | 262.144 | 187.138 | 31.750 | 155.388 | 0.713875 | 0.121117 | 0.592758 | 1.996586 | 1.871059 | 2.024336 |
19 | 524.288 | 373.509 | 59.967 | 313.542 | 0.712412 | 0.114378 | 0.598034 | 1.995901 | 1.888724 | 2.017801 |
20 | 1.048.576 | 745.802 | 113.603 | 632.199 | 0.711252 | 0.108340 | 0.602912 | 1.996744 | 1.894425 | 2.016314 |
21 | 2.097.152 | 1.490.157 | 214.973 | 1.275.184 | 0.710562 | 0.102507 | 0.608055 | 1.998060 | 1.892318 | 2.017061 |
22 | 4.194.304 | 2.975.364 | 409.227 | 2.566.137 | 0.709382 | 0.097567 | 0.611815 | 1.996678 | 1.903620 | 2.012366 |
23 | 8.388.608 | 5.944.225 | 780.190 | 5.164.035 | 0.708607 | 0.093006 | 0.615601 | 1.997814 | 1.906497 | 2.012377 |
24 | 16.777.216 | 11.875.693 | 1.490.689 | 10.385.004 | 0.707846 | 0.088852 | 0.618994 | 1.997854 | 1.910674 | 2.011025 |
25 | 33.554.432 | 23.727.938 | 2.855.285 | 20.872.653 | 0.707148 | 0.085094 | 0.622054 | 1.998026 | 1.915413 | 2.009884 |
26 | 67.108.864 | 47.415.137 | 5.476.477 | 41.938.660 | 0.706541 | 0.081606 | 0.624935 | 1.998283 | 1.918014 | 2.009264 |
27 | 134.217.728 | 94.755.440 | 10.518.384 | 84.237.056 | 0.705983 | 0.078368 | 0.627615 | 1.998422 | 1.920648 | 2.008578 |
28 | 268.435.456 | 189.375.326 | 20.236.922 | 169.138.404 | 0.705478 | 0.075388 | 0.630090 | 1.998569 | 1.923957 | 2.007886 |
29 | 536.870.912 | 378.492.989 | 38.997.885 | 339.495.104 | 0.704998 | 0.072639 | 0.632359 | 1.998639 | 1.927066 | 2.007203 |
30 | 1.073.741.824 | 756.508.980 | 75.248.031 | 681.260.949 | 0.704554 | 0.070080 | 0.634474 | 1.998740 | 1.929541 | 2.006689 |
31 | 2.147.483.648 | 1.512.153.837 | 145.367.265 | 1.366.786.572 | 0.704152 | 0.067692 | 0.636460 | 1.998858 | 1.931841 | 2.006260 |
32 | 4.294.967.296 | 3.022.672.526 | 281.175.332 | 2.741.497.194 | 0.703771 | 0.065466 | 0.638305 | 1.998919 | 1.934241 | 2.005798 |
33 | 8.589.934.592 | 6.042.299.640 | 544.431.703 | 5.497.867.937 | 0.703416 | 0.063380 | 0.640036 | 1.998992 | 1.936271 | 2.005425 |
34 | 17.179.869.184 | 12.078.876.605 | 1.055.266.492 | 11.023.610.113 | 0.703083 | 0.061425 | 0.641659 | 1.999053 | 1.938290 | 2.005070 |
35 | 34.359.738.368 | 24.147.071.248 | 2.047.338.807 | 22.099.732.441 | 0.702772 | 0.059585 | 0.643187 | 1.999116 | 1.940115 | 2.004764 |
36 | 68.719.476.736 | 48.274.055.509 | 3.975.721.296 | 44.298.334.213 | 0.702480 | 0.057854 | 0.644626 | 1.999168 | 1.941897 | 2.004474 |
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 | 0 | 1 | 1 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 7 | 3 | 4 | 1 | 3 | 2 | 1 |
4 | 16 | 10 | 4 | 6 | 2 | 4 | 3 | 1 |
5 | 32 | 17 | 5 | 12 | 5 | 5 | 4 | 3 |
6 | 64 | 30 | 10 | 20 | 6 | 10 | 8 | 6 |
7 | 128 | 51 | 17 | 34 | 14 | 12 | 12 | 13 |
8 | 256 | 82 | 29 | 53 | 25 | 18 | 20 | 19 |
9 | 512 | 146 | 53 | 93 | 39 | 37 | 36 | 34 |
10 | 1.024 | 249 | 87 | 162 | 64 | 57 | 70 | 58 |
11 | 2.048 | 449 | 153 | 296 | 121 | 103 | 108 | 117 |
12 | 4.096 | 799 | 277 | 522 | 216 | 198 | 184 | 201 |
13 | 8.192 | 1.431 | 480 | 951 | 375 | 363 | 335 | 358 |
14 | 16.384 | 2.667 | 912 | 1.755 | 694 | 670 | 621 | 682 |
15 | 32.768 | 4.957 | 1.674 | 3.283 | 1.275 | 1.238 | 1.198 | 1.246 |
16 | 65.536 | 9.147 | 3.107 | 6.040 | 2.307 | 2.283 | 2.256 | 2.301 |
17 | 131.072 | 16.969 | 5.709 | 11.260 | 4.229 | 4.222 | 4.220 | 4.298 |
18 | 262.144 | 31.750 | 10.613 | 21.137 | 7.921 | 7.960 | 7.856 | 8.013 |
19 | 524.288 | 59.967 | 19.998 | 39.969 | 15.029 | 15.027 | 14.864 | 15.047 |
20 | 1.048.576 | 113.603 | 37.898 | 75.705 | 28.423 | 28.397 | 28.218 | 28.565 |
21 | 2.097.152 | 214.973 | 71.671 | 143.302 | 53.708 | 53.697 | 53.594 | 53.974 |
22 | 4.194.304 | 409.227 | 136.594 | 272.633 | 102.363 | 102.230 | 101.963 | 102.671 |
23 | 8.388.608 | 780.190 | 260.481 | 519.709 | 194.900 | 194.915 | 195.366 | 195.009 |
24 | 16.777.216 | 1.490.689 | 497.553 | 993.136 | 373.082 | 372.437 | 372.753 | 372.417 |
25 | 33.554.432 | 2.855.285 | 952.180 | 1.903.105 | 714.726 | 713.439 | 713.768 | 713.352 |
26 | 67.108.864 | 5.476.477 | 1.825.549 | 3.650.928 | 1.369.723 | 1.368.732 | 1.369.810 | 1.368.212 |
27 | 134.217.728 | 10.518.384 | 3.506.371 | 7.012.013 | 2.630.672 | 2.628.819 | 2.629.773 | 2.629.120 |
28 | 268.435.456 | 20.236.922 | 6.746.350 | 13.490.572 | 5.062.014 | 5.058.333 | 5.058.031 | 5.058.544 |
29 | 536.870.912 | 38.997.885 | 13.000.136 | 25.997.749 | 9.753.886 | 9.746.306 | 9.746.941 | 9.750.752 |
30 | 1.073.741.824 | 75.248.031 | 25.084.102 | 50.163.929 | 18.816.745 | 18.810.787 | 18.810.888 | 18.809.611 |
31 | 2.147.483.648 | 145.367.265 | 48.457.373 | 96.909.892 | 36.345.302 | 36.343.307 | 36.341.895 | 36.336.761 |
32 | 4.294.967.296 | 281.175.332 | 93.730.835 | 187.444.497 | 70.301.216 | 70.292.047 | 70.297.071 | 70.284.998 |
33 | 8.589.934.592 | 544.431.703 | 181.487.158 | 362.944.545 | 136.123.368 | 136.100.437 | 136.109.193 | 136.098.705 |
34 | 17.179.869.184 | 1.055.266.492 | 351.755.413 | 703.511.079 | 263.833.063 | 263.801.800 | 263.822.221 | 263.809.408 |
35 | 34.359.738.368 | 2.047.338.807 | 682.451.908 | 1.364.886.899 | 511.855.883 | 511.808.383 | 511.838.209 | 511.836.332 |
36 | 68.719.476.736 | 3.975.721.296 | 1.325.244.275 | 2.650.477.021 | 993.956.936 | 993.908.368 | 993.934.461 | 993.921.531 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
5 | 32 | 5 | 1 | 4 | 1 | 1 | 2 | 1 |
6 | 64 | 15 | 7 | 8 | 4 | 5 | 3 | 3 |
7 | 128 | 41 | 20 | 21 | 7 | 9 | 12 | 13 |
8 | 256 | 102 | 52 | 50 | 20 | 28 | 26 | 28 |
9 | 512 | 229 | 113 | 116 | 48 | 65 | 58 | 58 |
10 | 1.024 | 495 | 237 | 258 | 113 | 128 | 134 | 120 |
11 | 2.048 | 1.036 | 510 | 526 | 265 | 270 | 258 | 243 |
12 | 4.096 | 2.176 | 1.067 | 1.109 | 536 | 562 | 533 | 545 |
13 | 8.192 | 4.483 | 2.186 | 2.297 | 1.120 | 1.094 | 1.130 | 1.139 |
14 | 16.384 | 9.112 | 4.468 | 4.644 | 2.282 | 2.233 | 2.302 | 2.295 |
15 | 32.768 | 18.544 | 9.191 | 9.353 | 4.627 | 4.610 | 4.664 | 4.643 |
16 | 65.536 | 37.767 | 18.710 | 19.057 | 9.399 | 9.431 | 9.497 | 9.440 |
17 | 131.072 | 76.760 | 38.281 | 38.479 | 19.121 | 19.264 | 19.218 | 19.157 |
18 | 262.144 | 155.388 | 77.623 | 77.765 | 38.822 | 38.832 | 38.760 | 38.974 |
19 | 524.288 | 313.542 | 156.260 | 157.282 | 78.565 | 78.392 | 78.226 | 78.359 |
20 | 1.048.576 | 632.199 | 315.327 | 316.872 | 158.518 | 157.651 | 157.774 | 158.256 |
21 | 2.097.152 | 1.275.184 | 635.908 | 639.276 | 318.742 | 318.274 | 318.908 | 319.260 |
22 | 4.194.304 | 2.566.137 | 1.279.750 | 1.286.387 | 641.293 | 641.708 | 641.545 | 641.591 |
23 | 8.388.608 | 5.164.035 | 2.574.971 | 2.589.064 | 1.290.347 | 1.291.767 | 1.291.772 | 1.290.149 |
24 | 16.777.216 | 10.385.004 | 5.179.391 | 5.205.613 | 2.596.200 | 2.596.721 | 2.596.048 | 2.596.035 |
25 | 33.554.432 | 20.872.653 | 10.412.361 | 10.460.292 | 5.217.512 | 5.219.552 | 5.219.170 | 5.216.419 |
26 | 67.108.864 | 41.938.660 | 20.927.777 | 21.010.883 | 10.485.294 | 10.485.214 | 10.486.254 | 10.481.898 |
27 | 134.217.728 | 84.237.056 | 42.031.346 | 42.205.710 | 21.060.042 | 21.057.597 | 21.063.409 | 21.056.008 |
28 | 268.435.456 | 169.138.404 | 84.396.519 | 84.741.885 | 42.281.075 | 42.283.536 | 42.289.967 | 42.283.826 |
29 | 536.870.912 | 339.495.104 | 169.422.759 | 170.072.345 | 84.880.243 | 84.865.188 | 84.881.236 | 84.868.437 |
30 | 1.073.741.824 | 681.260.949 | 339.998.240 | 341.262.709 | 170.331.457 | 170.298.098 | 170.319.777 | 170.311.617 |
31 | 2.147.483.648 | 1.366.786.572 | 682.162.528 | 684.624.044 | 341.700.518 | 341.695.808 | 341.702.299 | 341.687.947 |
32 | 4.294.967.296 | 2.741.497.194 | 1.368.351.968 | 1.373.145.226 | 685.379.279 | 685.356.860 | 685.386.141 | 685.374.914 |
33 | 8.589.934.592 | 5.497.867.937 | 2.744.255.942 | 2.753.611.995 | 1.374.441.892 | 1.374.440.877 | 1.374.494.292 | 1.374.490.876 |
34 | 17.179.869.184 | 11.023.610.113 | 5.502.698.983 | 5.520.911.130 | 2.755.888.909 | 2.755.919.105 | 2.755.870.192 | 2.755.931.907 |
35 | 34.359.738.368 | 22.099.732.441 | 11.032.101.722 | 11.067.630.719 | 5.524.936.463 | 5.524.944.050 | 5.524.837.792 | 5.525.014.136 |
36 | 68.719.476.736 | 44.298.334.213 | 22.114.466.030 | 22.183.868.183 | 11.074.560.698 | 11.074.679.731 | 11.074.450.233 | 11.074.643.551 |