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+32x-79
f(0)=79
f(1)=23
f(2)=11
f(3)=13
f(4)=5
f(5)=53
f(6)=149
f(7)=97
f(8)=241
f(9)=29
f(10)=31
f(11)=197
f(12)=449
f(13)=1
f(14)=113
f(15)=313
f(16)=1
f(17)=1
f(18)=821
f(19)=89
f(20)=1
f(21)=47
f(22)=1109
f(23)=593
f(24)=1
f(25)=673
f(26)=1429
f(27)=757
f(28)=1601
f(29)=1
f(30)=137
f(31)=937
f(32)=179
f(33)=1033
f(34)=433
f(35)=103
f(36)=1
f(37)=1237
f(38)=1
f(39)=269
f(40)=2801
f(41)=1
f(42)=233
f(43)=1
f(44)=653
f(45)=1693
f(46)=1
f(47)=1
f(48)=3761
f(49)=389
f(50)=4021
f(51)=67
f(52)=4289
f(53)=2213
f(54)=83
f(55)=181
f(56)=373
f(57)=227
f(58)=1
f(59)=1
f(60)=5441
f(61)=2797
f(62)=5749
f(63)=2953
f(64)=1213
f(65)=283
f(66)=6389
f(67)=1
f(68)=1
f(69)=1
f(70)=307
f(71)=3617
f(72)=239
f(73)=3793
f(74)=1553
f(75)=1
f(76)=739
f(77)=4157
f(78)=8501
f(79)=1
f(80)=107
f(81)=349
f(82)=1
f(83)=4733
f(84)=1933
f(85)=4933
f(86)=10069
f(87)=467
f(88)=223
f(89)=1069
f(90)=991
f(91)=5557
f(92)=11329
f(93)=251
f(94)=1
f(95)=461
f(96)=421
f(97)=6217
f(98)=1151
f(99)=1289
b) Substitution of the polynom
The polynom f(x)=x^2+32x-79 could be written as f(y)= y^2-335 with x=y-16
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+16
f'(x)>2x+31
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 | 5 | 6 | 1.100000 | 0.500000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 78 | 21 | 57 | 0.780000 | 0.210000 | 0.780000 | 7.090909 | 4.200000 | 9.500000 |
3 | 1.000 | 695 | 122 | 573 | 0.695000 | 0.122000 | 0.695000 | 8.910256 | 5.809524 | 10.052631 |
4 | 10.000 | 6.947 | 938 | 6.009 | 0.694700 | 0.093800 | 0.694700 | 9.995684 | 7.688525 | 10.486911 |
5 | 100.000 | 69.797 | 7.064 | 62.733 | 0.697970 | 0.070640 | 0.697970 | 10.047071 | 7.530917 | 10.439840 |
6 | 1.000.000 | 696.497 | 57.577 | 638.920 | 0.696497 | 0.057577 | 0.696497 | 9.978896 | 8.150764 | 10.184752 |
7 | 10.000.000 | 6.958.922 | 485.734 | 6.473.188 | 0.695892 | 0.048573 | 0.695892 | 9.991317 | 8.436251 | 10.131454 |
8 | 100.000.000 | 69.540.495 | 4.206.977 | 65.333.518 | 0.695405 | 0.042070 | 0.695405 | 9.992998 | 8.661072 | 10.092943 |
9 | 1.000.000.000 | 695.042.953 | 37.118.496 | 657.924.457 | 0.695043 | 0.037118 | 0.695043 | 9.994794 | 8.823080 | 10.070244 |
10 | 10.000.000.000 | 6.947.768.436 | 332.208.460 | 6.615.559.976 | 0.694777 | 0.033221 | 0.694777 | 9.996171 | 8.949944 | 10.055197 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 1.666667 | 1.200000 | 2.250000 |
5 | 32 | 27 | 10 | 17 | 0.843750 | 0.312500 | 0.531250 | 1.800000 | 1.666667 | 1.888889 |
6 | 64 | 50 | 16 | 34 | 0.781250 | 0.250000 | 0.531250 | 1.851852 | 1.600000 | 2.000000 |
7 | 128 | 95 | 23 | 72 | 0.742188 | 0.179688 | 0.562500 | 1.900000 | 1.437500 | 2.117647 |
8 | 256 | 182 | 40 | 142 | 0.710938 | 0.156250 | 0.554688 | 1.915789 | 1.739130 | 1.972222 |
9 | 512 | 357 | 68 | 289 | 0.697266 | 0.132812 | 0.564453 | 1.961538 | 1.700000 | 2.035211 |
10 | 1.024 | 710 | 125 | 585 | 0.693359 | 0.122070 | 0.571289 | 1.988796 | 1.838235 | 2.024221 |
11 | 2.048 | 1.428 | 227 | 1.201 | 0.697266 | 0.110840 | 0.586426 | 2.011268 | 1.816000 | 2.052991 |
12 | 4.096 | 2.847 | 425 | 2.422 | 0.695068 | 0.103760 | 0.591309 | 1.993698 | 1.872247 | 2.016653 |
13 | 8.192 | 5.696 | 795 | 4.901 | 0.695312 | 0.097046 | 0.598267 | 2.000702 | 1.870588 | 2.023534 |
14 | 16.384 | 11.392 | 1.424 | 9.968 | 0.695312 | 0.086914 | 0.608398 | 2.000000 | 1.791195 | 2.033871 |
15 | 32.768 | 22.864 | 2.590 | 20.274 | 0.697754 | 0.079041 | 0.618713 | 2.007022 | 1.818820 | 2.033909 |
16 | 65.536 | 45.691 | 4.838 | 40.853 | 0.697189 | 0.073822 | 0.623367 | 1.998382 | 1.867954 | 2.015044 |
17 | 131.072 | 91.387 | 9.042 | 82.345 | 0.697227 | 0.068985 | 0.628242 | 2.000109 | 1.868954 | 2.015641 |
18 | 262.144 | 182.790 | 16.998 | 165.792 | 0.697289 | 0.064842 | 0.632446 | 2.000175 | 1.879894 | 2.013383 |
19 | 524.288 | 365.214 | 31.833 | 333.381 | 0.696590 | 0.060717 | 0.635874 | 1.997998 | 1.872750 | 2.010839 |
20 | 1.048.576 | 730.386 | 60.125 | 670.261 | 0.696550 | 0.057340 | 0.639211 | 1.999885 | 1.888763 | 2.010495 |
21 | 2.097.152 | 1.460.316 | 113.957 | 1.346.359 | 0.696333 | 0.054339 | 0.641994 | 1.999376 | 1.895335 | 2.008708 |
22 | 4.194.304 | 2.919.783 | 216.398 | 2.703.385 | 0.696131 | 0.051593 | 0.644537 | 1.999419 | 1.898944 | 2.007923 |
23 | 8.388.608 | 5.837.446 | 412.552 | 5.424.894 | 0.695878 | 0.049180 | 0.646698 | 1.999274 | 1.906450 | 2.006704 |
24 | 16.777.216 | 11.672.291 | 787.685 | 10.884.606 | 0.695723 | 0.046950 | 0.648773 | 1.999554 | 1.909299 | 2.006418 |
25 | 33.554.432 | 23.339.931 | 1.507.331 | 21.832.600 | 0.695584 | 0.044922 | 0.650662 | 1.999602 | 1.913622 | 2.005824 |
26 | 67.108.864 | 46.672.823 | 2.890.443 | 43.782.380 | 0.695479 | 0.043071 | 0.652408 | 1.999698 | 1.917590 | 2.005367 |
27 | 134.217.728 | 93.325.117 | 5.552.053 | 87.773.064 | 0.695326 | 0.041366 | 0.653960 | 1.999560 | 1.920831 | 2.004758 |
28 | 268.435.456 | 186.625.731 | 10.680.814 | 175.944.917 | 0.695235 | 0.039789 | 0.655446 | 1.999737 | 1.923759 | 2.004543 |
29 | 536.870.912 | 373.188.961 | 20.581.031 | 352.607.930 | 0.695119 | 0.038335 | 0.656783 | 1.999665 | 1.926916 | 2.004081 |
30 | 1.073.741.824 | 746.286.675 | 39.712.401 | 706.574.274 | 0.695034 | 0.036985 | 0.658049 | 1.999756 | 1.929563 | 2.003852 |
31 | 2.147.483.648 | 1.492.384.947 | 76.729.180 | 1.415.655.767 | 0.694946 | 0.035730 | 0.659216 | 1.999748 | 1.932122 | 2.003548 |
32 | 4.294.967.296 | 2.984.431.252 | 148.411.956 | 2.836.019.296 | 0.694867 | 0.034555 | 0.660312 | 1.999773 | 1.934231 | 2.003325 |
33 | 8.589.934.592 | 5.968.223.680 | 287.356.362 | 5.680.867.318 | 0.694793 | 0.033453 | 0.661340 | 1.999786 | 1.936208 | 2.003113 |
34 | 17.179.869.184 | 11.935.255.537 | 557.002.534 | 11.378.253.003 | 0.694723 | 0.032422 | 0.662301 | 1.999800 | 1.938369 | 2.002908 |
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 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
3 | 8 | 5 | 2 | 3 | 2 | 1 | 1 | 1 |
4 | 16 | 6 | 2 | 4 | 3 | 1 | 1 | 1 |
5 | 32 | 10 | 3 | 7 | 4 | 1 | 4 | 1 |
6 | 64 | 16 | 5 | 11 | 8 | 1 | 6 | 1 |
7 | 128 | 23 | 8 | 15 | 10 | 1 | 11 | 1 |
8 | 256 | 40 | 13 | 27 | 19 | 1 | 19 | 1 |
9 | 512 | 68 | 19 | 49 | 35 | 1 | 31 | 1 |
10 | 1.024 | 125 | 39 | 86 | 64 | 1 | 59 | 1 |
11 | 2.048 | 227 | 71 | 156 | 114 | 1 | 111 | 1 |
12 | 4.096 | 425 | 144 | 281 | 214 | 1 | 209 | 1 |
13 | 8.192 | 795 | 279 | 516 | 395 | 1 | 398 | 1 |
14 | 16.384 | 1.424 | 485 | 939 | 724 | 1 | 698 | 1 |
15 | 32.768 | 2.590 | 863 | 1.727 | 1.304 | 1 | 1.284 | 1 |
16 | 65.536 | 4.838 | 1.626 | 3.212 | 2.415 | 1 | 2.421 | 1 |
17 | 131.072 | 9.042 | 3.007 | 6.035 | 4.534 | 1 | 4.506 | 1 |
18 | 262.144 | 16.998 | 5.692 | 11.306 | 8.481 | 1 | 8.515 | 1 |
19 | 524.288 | 31.833 | 10.601 | 21.232 | 15.898 | 1 | 15.933 | 1 |
20 | 1.048.576 | 60.125 | 20.004 | 40.121 | 30.061 | 1 | 30.062 | 1 |
21 | 2.097.152 | 113.957 | 37.739 | 76.218 | 56.892 | 1 | 57.063 | 1 |
22 | 4.194.304 | 216.398 | 71.904 | 144.494 | 108.114 | 1 | 108.282 | 1 |
23 | 8.388.608 | 412.552 | 137.060 | 275.492 | 206.494 | 1 | 206.056 | 1 |
24 | 16.777.216 | 787.685 | 262.255 | 525.430 | 394.144 | 1 | 393.539 | 1 |
25 | 33.554.432 | 1.507.331 | 502.143 | 1.005.188 | 754.139 | 1 | 753.190 | 1 |
26 | 67.108.864 | 2.890.443 | 963.281 | 1.927.162 | 1.445.765 | 1 | 1.444.676 | 1 |
27 | 134.217.728 | 5.552.053 | 1.850.064 | 3.701.989 | 2.777.742 | 1 | 2.774.309 | 1 |
28 | 268.435.456 | 10.680.814 | 3.558.486 | 7.122.328 | 5.341.550 | 1 | 5.339.262 | 1 |
29 | 536.870.912 | 20.581.031 | 6.858.781 | 13.722.250 | 10.292.895 | 1 | 10.288.134 | 1 |
30 | 1.073.741.824 | 39.712.401 | 13.236.301 | 26.476.100 | 19.861.215 | 1 | 19.851.184 | 1 |
31 | 2.147.483.648 | 76.729.180 | 25.574.709 | 51.154.471 | 38.366.551 | 1 | 38.362.627 | 1 |
32 | 4.294.967.296 | 148.411.956 | 49.469.229 | 98.942.727 | 74.206.277 | 1 | 74.205.677 | 1 |
33 | 8.589.934.592 | 287.356.362 | 95.785.718 | 191.570.644 | 143.671.791 | 1 | 143.684.569 | 1 |
34 | 17.179.869.184 | 557.002.534 | 185.676.895 | 371.325.639 | 278.497.327 | 1 | 278.505.205 | 1 |
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 | 0 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 0 | 2 | 1 |
4 | 16 | 9 | 4 | 5 | 3 | 0 | 4 | 2 |
5 | 32 | 17 | 7 | 10 | 8 | 1 | 5 | 3 |
6 | 64 | 34 | 18 | 16 | 12 | 2 | 16 | 4 |
7 | 128 | 72 | 39 | 33 | 21 | 8 | 29 | 14 |
8 | 256 | 142 | 79 | 63 | 42 | 22 | 52 | 26 |
9 | 512 | 289 | 165 | 124 | 90 | 52 | 99 | 48 |
10 | 1.024 | 585 | 316 | 269 | 176 | 130 | 183 | 96 |
11 | 2.048 | 1.201 | 658 | 543 | 365 | 251 | 363 | 222 |
12 | 4.096 | 2.422 | 1.280 | 1.142 | 687 | 499 | 719 | 517 |
13 | 8.192 | 4.901 | 2.562 | 2.339 | 1.384 | 1.038 | 1.436 | 1.043 |
14 | 16.384 | 9.968 | 5.247 | 4.721 | 2.838 | 2.174 | 2.831 | 2.125 |
15 | 32.768 | 20.274 | 10.577 | 9.697 | 5.723 | 4.398 | 5.716 | 4.437 |
16 | 65.536 | 40.853 | 21.313 | 19.540 | 11.347 | 8.985 | 11.380 | 9.141 |
17 | 131.072 | 82.345 | 42.767 | 39.578 | 22.655 | 18.278 | 22.933 | 18.479 |
18 | 262.144 | 165.792 | 85.646 | 80.146 | 45.467 | 37.229 | 45.706 | 37.390 |
19 | 524.288 | 333.381 | 171.721 | 161.660 | 91.267 | 75.386 | 91.190 | 75.538 |
20 | 1.048.576 | 670.261 | 345.139 | 325.122 | 182.493 | 152.186 | 182.792 | 152.790 |
21 | 2.097.152 | 1.346.359 | 692.356 | 654.003 | 364.856 | 307.664 | 365.299 | 308.540 |
22 | 4.194.304 | 2.703.385 | 1.388.821 | 1.314.564 | 730.083 | 621.699 | 730.329 | 621.274 |
23 | 8.388.608 | 5.424.894 | 2.781.726 | 2.643.168 | 1.458.948 | 1.252.473 | 1.460.935 | 1.252.538 |
24 | 16.777.216 | 10.884.606 | 5.573.253 | 5.311.353 | 2.917.131 | 2.521.742 | 2.922.041 | 2.523.692 |
25 | 33.554.432 | 21.832.600 | 11.170.859 | 10.661.741 | 5.835.580 | 5.077.959 | 5.840.026 | 5.079.035 |
26 | 67.108.864 | 43.782.380 | 22.378.132 | 21.404.248 | 11.669.972 | 10.219.255 | 11.677.213 | 10.215.940 |
27 | 134.217.728 | 87.773.064 | 44.819.672 | 42.953.392 | 23.339.839 | 20.548.182 | 23.340.145 | 20.544.898 |
28 | 268.435.456 | 175.944.917 | 89.772.380 | 86.172.537 | 46.674.939 | 41.293.857 | 46.675.799 | 41.300.322 |
29 | 536.870.912 | 352.607.930 | 179.773.501 | 172.834.429 | 93.330.082 | 82.959.217 | 93.342.247 | 82.976.384 |
30 | 1.073.741.824 | 706.574.274 | 359.979.780 | 346.594.494 | 186.657.616 | 166.614.093 | 186.664.256 | 166.638.309 |
31 | 2.147.483.648 | 1.415.655.767 | 720.740.246 | 694.915.521 | 373.266.258 | 334.548.234 | 373.278.813 | 334.562.462 |
32 | 4.294.967.296 | 2.836.019.296 | 1.442.983.198 | 1.393.036.098 | 746.450.291 | 671.550.011 | 746.467.274 | 671.551.720 |
33 | 8.589.934.592 | 5.680.867.318 | 2.888.757.330 | 2.792.109.988 | 1.492.779.837 | 1.347.639.309 | 1.492.805.807 | 1.347.642.365 |
34 | 17.179.869.184 | 11.378.253.003 | 5.782.823.972 | 5.595.429.031 | 2.985.301.746 | 2.703.840.625 | 2.985.284.574 | 2.703.826.058 |