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+47
f(0)=47
f(1)=3
f(2)=17
f(3)=7
f(4)=1
f(5)=1
f(6)=83
f(7)=1
f(8)=37
f(9)=1
f(10)=1
f(11)=1
f(12)=191
f(13)=1
f(14)=1
f(15)=1
f(16)=101
f(17)=1
f(18)=53
f(19)=1
f(20)=149
f(21)=61
f(22)=59
f(23)=1
f(24)=89
f(25)=1
f(26)=241
f(27)=97
f(28)=277
f(29)=1
f(30)=947
f(31)=1
f(32)=1
f(33)=71
f(34)=401
f(35)=1
f(36)=79
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1811
f(43)=1
f(44)=661
f(45)=1
f(46)=103
f(47)=1
f(48)=2351
f(49)=1
f(50)=283
f(51)=331
f(52)=131
f(53)=1
f(54)=2963
f(55)=1
f(56)=1061
f(57)=1
f(58)=379
f(59)=1
f(60)=521
f(61)=157
f(62)=1297
f(63)=251
f(64)=1381
f(65)=1
f(66)=1
f(67)=1
f(68)=173
f(69)=601
f(70)=1
f(71)=1
f(72)=5231
f(73)=1
f(74)=263
f(75)=709
f(76)=647
f(77)=1
f(78)=6131
f(79)=1
f(80)=307
f(81)=1
f(82)=1
f(83)=1
f(84)=7103
f(85)=1
f(86)=827
f(87)=1
f(88)=1
f(89)=1
f(90)=8147
f(91)=347
f(92)=2837
f(93)=1087
f(94)=1
f(95)=1
f(96)=1
f(97)=197
f(98)=3217
f(99)=1231
b) Substitution of the polynom
The polynom f(x)=x^2+47 could be written as f(y)= y^2+47 with x=y+0
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
f'(x)>2x-1 with x > 7
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.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 52 | 22 | 30 | 0.520000 | 0.220000 | 0.520000 | 8.666667 | 5.500000 | 15.000000 |
3 | 1.000 | 593 | 130 | 463 | 0.593000 | 0.130000 | 0.593000 | 11.403846 | 5.909091 | 15.433333 |
4 | 10.000 | 6.227 | 921 | 5.306 | 0.622700 | 0.092100 | 0.622700 | 10.500843 | 7.084615 | 11.460043 |
5 | 100.000 | 64.039 | 7.005 | 57.034 | 0.640390 | 0.070050 | 0.640390 | 10.284085 | 7.605863 | 10.748963 |
6 | 1.000.000 | 649.697 | 56.271 | 593.426 | 0.649697 | 0.056271 | 0.649697 | 10.145333 | 8.032976 | 10.404777 |
7 | 10.000.000 | 6.560.873 | 471.018 | 6.089.855 | 0.656087 | 0.047102 | 0.656087 | 10.098358 | 8.370528 | 10.262197 |
8 | 100.000.000 | 66.076.776 | 4.054.370 | 62.022.406 | 0.660768 | 0.040544 | 0.660768 | 10.071339 | 8.607676 | 10.184546 |
9 | 1.000.000.000 | 664.424.939 | 35.597.184 | 628.827.755 | 0.664425 | 0.035597 | 0.664425 | 10.055347 | 8.779955 | 10.138720 |
10 | 10.000.000.000 | 6.673.231.601 | 317.177.547 | 6.356.054.054 | 0.667323 | 0.031718 | 0.667323 | 10.043619 | 8.910186 | 10.107782 |
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 | 6 | 4 | 2 | 0.750000 | 0.500000 | 0.250000 | 1.500000 | 1.333333 | 2.000000 |
4 | 16 | 8 | 5 | 3 | 0.500000 | 0.312500 | 0.187500 | 1.333333 | 1.250000 | 1.500000 |
5 | 32 | 17 | 8 | 9 | 0.531250 | 0.250000 | 0.281250 | 2.125000 | 1.600000 | 3.000000 |
6 | 64 | 35 | 14 | 21 | 0.546875 | 0.218750 | 0.328125 | 2.058824 | 1.750000 | 2.333333 |
7 | 128 | 68 | 26 | 42 | 0.531250 | 0.203125 | 0.328125 | 1.942857 | 1.857143 | 2.000000 |
8 | 256 | 142 | 39 | 103 | 0.554688 | 0.152344 | 0.402344 | 2.088235 | 1.500000 | 2.452381 |
9 | 512 | 301 | 70 | 231 | 0.587891 | 0.136719 | 0.451172 | 2.119718 | 1.794872 | 2.242718 |
10 | 1.024 | 610 | 134 | 476 | 0.595703 | 0.130859 | 0.464844 | 2.026578 | 1.914286 | 2.060606 |
11 | 2.048 | 1.242 | 238 | 1.004 | 0.606445 | 0.116211 | 0.490234 | 2.036066 | 1.776119 | 2.109244 |
12 | 4.096 | 2.521 | 424 | 2.097 | 0.615479 | 0.103516 | 0.511963 | 2.029791 | 1.781513 | 2.088645 |
13 | 8.192 | 5.107 | 773 | 4.334 | 0.623413 | 0.094360 | 0.529053 | 2.025783 | 1.823113 | 2.066762 |
14 | 16.384 | 10.327 | 1.438 | 8.889 | 0.630310 | 0.087769 | 0.542542 | 2.022126 | 1.860285 | 2.050992 |
15 | 32.768 | 20.784 | 2.588 | 18.196 | 0.634277 | 0.078979 | 0.555298 | 2.012588 | 1.799722 | 2.047024 |
16 | 65.536 | 41.802 | 4.782 | 37.020 | 0.637848 | 0.072968 | 0.564880 | 2.011259 | 1.847759 | 2.034513 |
17 | 131.072 | 84.125 | 8.933 | 75.192 | 0.641823 | 0.068153 | 0.573669 | 2.012464 | 1.868047 | 2.031118 |
18 | 262.144 | 168.991 | 16.643 | 152.348 | 0.644650 | 0.063488 | 0.581161 | 2.008808 | 1.863092 | 2.026120 |
19 | 524.288 | 339.403 | 31.219 | 308.184 | 0.647360 | 0.059546 | 0.587814 | 2.008409 | 1.875804 | 2.022895 |
20 | 1.048.576 | 681.395 | 58.737 | 622.658 | 0.649829 | 0.056016 | 0.593813 | 2.007628 | 1.881450 | 2.020410 |
21 | 2.097.152 | 1.367.116 | 110.972 | 1.256.144 | 0.651892 | 0.052916 | 0.598976 | 2.006349 | 1.889303 | 2.017390 |
22 | 4.194.304 | 2.742.576 | 210.500 | 2.532.076 | 0.653881 | 0.050187 | 0.603694 | 2.006103 | 1.896875 | 2.015753 |
23 | 8.388.608 | 5.499.951 | 400.136 | 5.099.815 | 0.655645 | 0.047700 | 0.607945 | 2.005396 | 1.900884 | 2.014085 |
24 | 16.777.216 | 11.026.967 | 762.376 | 10.264.591 | 0.657258 | 0.045441 | 0.611817 | 2.004921 | 1.905292 | 2.012738 |
25 | 33.554.432 | 22.102.207 | 1.456.640 | 20.645.567 | 0.658697 | 0.043411 | 0.615286 | 2.004378 | 1.910658 | 2.011338 |
26 | 67.108.864 | 44.294.930 | 2.787.765 | 41.507.165 | 0.660046 | 0.041541 | 0.618505 | 2.004095 | 1.913833 | 2.010464 |
27 | 134.217.728 | 88.758.166 | 5.346.343 | 83.411.823 | 0.661300 | 0.039833 | 0.621467 | 2.003800 | 1.917788 | 2.009577 |
28 | 268.435.456 | 177.824.562 | 10.271.634 | 167.552.928 | 0.662448 | 0.038265 | 0.624183 | 2.003473 | 1.921245 | 2.008743 |
29 | 536.870.912 | 356.225.518 | 19.762.292 | 336.463.226 | 0.663522 | 0.036810 | 0.626712 | 2.003241 | 1.923968 | 2.008101 |
30 | 1.073.741.824 | 713.526.999 | 38.078.144 | 675.448.855 | 0.664524 | 0.035463 | 0.629061 | 2.003021 | 1.926808 | 2.007497 |
31 | 2.147.483.648 | 1.429.055.612 | 73.461.221 | 1.355.594.391 | 0.665456 | 0.034208 | 0.631248 | 2.002805 | 1.929223 | 2.006953 |
32 | 4.294.967.296 | 2.861.858.040 | 141.900.159 | 2.719.957.881 | 0.666328 | 0.033039 | 0.633290 | 2.002622 | 1.931633 | 2.006469 |
33 | 8.589.934.592 | 5.730.779.711 | 274.426.725 | 5.456.352.986 | 0.667151 | 0.031947 | 0.635203 | 2.002468 | 1.933942 | 2.006043 |
34 | 17.179.869.184 | 11.474.782.194 | 531.342.618 | 10.943.439.576 | 0.667920 | 0.030928 | 0.636992 | 2.002307 | 1.936191 | 2.005633 |
35 | 34.359.738.368 | 22.974.540.000 | 1.029.811.709 | 21.944.728.291 | 0.668647 | 0.029971 | 0.638676 | 2.002177 | 1.938131 | 2.005286 |
36 | 68.719.476.736 | 45.996.253.544 | 1.997.843.400 | 43.998.410.144 | 0.669334 | 0.029072 | 0.640261 | 2.002053 | 1.940009 | 2.004965 |
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 | 0 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 0 | 2 |
3 | 8 | 4 | 1 | 2 | 0 | 2 | 0 | 2 |
4 | 16 | 5 | 1 | 3 | 0 | 2 | 0 | 3 |
5 | 32 | 8 | 3 | 4 | 1 | 3 | 1 | 3 |
6 | 64 | 14 | 4 | 9 | 1 | 7 | 1 | 5 |
7 | 128 | 26 | 8 | 17 | 2 | 11 | 3 | 10 |
8 | 256 | 39 | 14 | 24 | 2 | 17 | 5 | 15 |
9 | 512 | 70 | 28 | 41 | 9 | 26 | 9 | 26 |
10 | 1.024 | 134 | 48 | 85 | 15 | 48 | 21 | 50 |
11 | 2.048 | 238 | 89 | 148 | 34 | 92 | 33 | 79 |
12 | 4.096 | 424 | 148 | 275 | 58 | 156 | 63 | 147 |
13 | 8.192 | 773 | 268 | 504 | 103 | 284 | 112 | 274 |
14 | 16.384 | 1.438 | 507 | 930 | 205 | 523 | 200 | 510 |
15 | 32.768 | 2.588 | 928 | 1.659 | 367 | 931 | 345 | 945 |
16 | 65.536 | 4.782 | 1.700 | 3.081 | 664 | 1.751 | 638 | 1.729 |
17 | 131.072 | 8.933 | 3.169 | 5.763 | 1.227 | 3.249 | 1.191 | 3.266 |
18 | 262.144 | 16.643 | 5.828 | 10.814 | 2.245 | 6.059 | 2.247 | 6.092 |
19 | 524.288 | 31.219 | 10.915 | 20.303 | 4.180 | 11.462 | 4.199 | 11.378 |
20 | 1.048.576 | 58.737 | 20.484 | 38.252 | 7.834 | 21.679 | 7.799 | 21.425 |
21 | 2.097.152 | 110.972 | 38.571 | 72.400 | 14.711 | 40.951 | 14.625 | 40.685 |
22 | 4.194.304 | 210.500 | 73.222 | 137.277 | 27.892 | 77.629 | 27.609 | 77.370 |
23 | 8.388.608 | 400.136 | 138.843 | 261.292 | 52.652 | 147.761 | 52.572 | 147.151 |
24 | 16.777.216 | 762.376 | 263.628 | 498.747 | 99.902 | 281.346 | 99.650 | 281.478 |
25 | 33.554.432 | 1.456.640 | 503.026 | 953.613 | 190.044 | 538.332 | 190.083 | 538.181 |
26 | 67.108.864 | 2.787.765 | 961.728 | 1.826.036 | 363.084 | 1.030.349 | 363.751 | 1.030.581 |
27 | 134.217.728 | 5.346.343 | 1.842.381 | 3.503.961 | 695.920 | 1.976.807 | 696.214 | 1.977.402 |
28 | 268.435.456 | 10.271.634 | 3.535.175 | 6.736.458 | 1.334.656 | 3.799.306 | 1.336.016 | 3.801.656 |
29 | 536.870.912 | 19.762.292 | 6.793.007 | 12.969.284 | 2.564.165 | 7.315.076 | 2.565.824 | 7.317.227 |
30 | 1.073.741.824 | 38.078.144 | 13.072.650 | 25.005.493 | 4.934.783 | 14.103.360 | 4.935.154 | 14.104.847 |
31 | 2.147.483.648 | 73.461.221 | 25.197.474 | 48.263.746 | 9.512.017 | 27.219.084 | 9.510.448 | 27.219.672 |
32 | 4.294.967.296 | 141.900.159 | 48.631.997 | 93.268.161 | 18.349.687 | 52.600.524 | 18.346.589 | 52.603.359 |
33 | 8.589.934.592 | 274.426.725 | 93.966.853 | 180.459.871 | 35.446.132 | 101.761.427 | 35.438.726 | 101.780.440 |
34 | 17.179.869.184 | 531.342.618 | 181.798.301 | 349.544.316 | 68.559.819 | 197.106.525 | 68.551.641 | 197.124.633 |
35 | 34.359.738.368 | 1.029.811.709 | 352.072.531 | 677.739.177 | 132.747.959 | 382.155.934 | 132.730.431 | 382.177.385 |
36 | 68.719.476.736 | 1.997.843.400 | 682.491.732 | 1.315.351.667 | 257.266.757 | 741.632.888 | 257.278.045 | 741.665.710 |
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 | 1 | 0 | 0 | 0 |
2 | 4 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
3 | 8 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 0 | 2 | 0 |
5 | 32 | 9 | 3 | 6 | 3 | 1 | 5 | 0 |
6 | 64 | 21 | 11 | 10 | 6 | 4 | 9 | 2 |
7 | 128 | 42 | 18 | 24 | 11 | 8 | 15 | 8 |
8 | 256 | 103 | 48 | 55 | 30 | 23 | 29 | 21 |
9 | 512 | 231 | 112 | 119 | 65 | 54 | 67 | 45 |
10 | 1.024 | 476 | 232 | 244 | 134 | 110 | 129 | 103 |
11 | 2.048 | 1.004 | 499 | 505 | 272 | 225 | 281 | 226 |
12 | 4.096 | 2.097 | 1.027 | 1.070 | 574 | 460 | 579 | 484 |
13 | 8.192 | 4.334 | 2.127 | 2.207 | 1.187 | 954 | 1.176 | 1.017 |
14 | 16.384 | 8.889 | 4.399 | 4.490 | 2.388 | 2.030 | 2.413 | 2.058 |
15 | 32.768 | 18.196 | 8.981 | 9.215 | 4.911 | 4.212 | 4.812 | 4.261 |
16 | 65.536 | 37.020 | 18.342 | 18.678 | 9.845 | 8.659 | 9.845 | 8.671 |
17 | 131.072 | 75.192 | 37.306 | 37.886 | 19.728 | 17.823 | 19.890 | 17.751 |
18 | 262.144 | 152.348 | 75.809 | 76.539 | 40.007 | 36.175 | 40.088 | 36.078 |
19 | 524.288 | 308.184 | 153.401 | 154.783 | 80.877 | 73.252 | 80.903 | 73.152 |
20 | 1.048.576 | 622.658 | 310.218 | 312.440 | 162.613 | 148.685 | 162.655 | 148.705 |
21 | 2.097.152 | 1.256.144 | 625.884 | 630.260 | 327.162 | 300.643 | 327.816 | 300.523 |
22 | 4.194.304 | 2.532.076 | 1.262.172 | 1.269.904 | 658.182 | 607.557 | 659.440 | 606.897 |
23 | 8.388.608 | 5.099.815 | 2.541.753 | 2.558.062 | 1.323.694 | 1.225.524 | 1.324.354 | 1.226.243 |
24 | 16.777.216 | 10.264.591 | 5.116.115 | 5.148.476 | 2.659.032 | 2.472.047 | 2.659.958 | 2.473.554 |
25 | 33.554.432 | 20.645.567 | 10.290.702 | 10.354.865 | 5.338.475 | 4.984.186 | 5.340.189 | 4.982.717 |
26 | 67.108.864 | 41.507.165 | 20.692.871 | 20.814.294 | 10.717.952 | 10.036.321 | 10.717.509 | 10.035.383 |
27 | 134.217.728 | 83.411.823 | 41.590.521 | 41.821.302 | 21.508.365 | 20.196.040 | 21.506.075 | 20.201.343 |
28 | 268.435.456 | 167.552.928 | 83.552.381 | 84.000.547 | 43.141.011 | 40.627.547 | 43.146.525 | 40.637.845 |
29 | 536.870.912 | 336.463.226 | 167.796.568 | 168.666.658 | 86.531.825 | 81.693.374 | 86.530.024 | 81.708.003 |
30 | 1.073.741.824 | 675.448.855 | 336.896.587 | 338.552.268 | 173.521.949 | 164.204.068 | 173.516.192 | 164.206.646 |
31 | 2.147.483.648 | 1.355.594.391 | 676.204.665 | 679.389.726 | 347.907.135 | 329.902.553 | 347.873.996 | 329.910.707 |
32 | 4.294.967.296 | 2.719.957.881 | 1.356.922.215 | 1.363.035.666 | 697.413.101 | 662.598.884 | 697.332.191 | 662.613.705 |
33 | 8.589.934.592 | 5.456.352.986 | 2.722.264.105 | 2.734.088.881 | 1.397.772.321 | 1.330.412.332 | 1.397.709.731 | 1.330.458.602 |
34 | 17.179.869.184 | 10.943.439.576 | 5.460.209.030 | 5.483.230.546 | 2.801.090.495 | 2.670.632.678 | 2.801.025.163 | 2.670.691.240 |
35 | 34.359.738.368 | 21.944.728.291 | 10.949.967.884 | 10.994.760.407 | 5.612.655.384 | 5.359.698.647 | 5.612.617.478 | 5.359.756.782 |
36 | 68.719.476.736 | 43.998.410.144 | 21.955.636.282 | 22.042.773.862 | 11.245.151.872 | 10.754.041.641 | 11.245.096.428 | 10.754.120.203 |