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-167
f(0)=167
f(1)=83
f(2)=163
f(3)=79
f(4)=151
f(5)=71
f(6)=131
f(7)=59
f(8)=103
f(9)=43
f(10)=67
f(11)=23
f(12)=1
f(13)=1
f(14)=29
f(15)=1
f(16)=89
f(17)=61
f(18)=157
f(19)=97
f(20)=233
f(21)=137
f(22)=317
f(23)=181
f(24)=409
f(25)=229
f(26)=509
f(27)=281
f(28)=617
f(29)=337
f(30)=733
f(31)=397
f(32)=857
f(33)=461
f(34)=1
f(35)=1
f(36)=1129
f(37)=601
f(38)=1277
f(39)=677
f(40)=1433
f(41)=757
f(42)=1597
f(43)=1
f(44)=1
f(45)=929
f(46)=1949
f(47)=1021
f(48)=2137
f(49)=1117
f(50)=2333
f(51)=1217
f(52)=1
f(53)=1321
f(54)=2749
f(55)=1429
f(56)=2969
f(57)=1
f(58)=139
f(59)=1657
f(60)=3433
f(61)=1777
f(62)=3677
f(63)=1901
f(64)=3929
f(65)=2029
f(66)=1
f(67)=2161
f(68)=4457
f(69)=2297
f(70)=4733
f(71)=2437
f(72)=173
f(73)=1
f(74)=5309
f(75)=2729
f(76)=1
f(77)=1
f(78)=1
f(79)=3037
f(80)=271
f(81)=1
f(82)=1
f(83)=3361
f(84)=1
f(85)=3529
f(86)=7229
f(87)=3701
f(88)=7577
f(89)=3877
f(90)=7933
f(91)=4057
f(92)=8297
f(93)=4241
f(94)=8669
f(95)=1
f(96)=9049
f(97)=4621
f(98)=9437
f(99)=4817
b) Substitution of the polynom
The polynom f(x)=x^2-167 could be written as f(y)= y^2-167 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 > 13
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 | 11 | 0 | 1.100000 | 1.100000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 83 | 80 | 3 | 0.830000 | 0.800000 | 0.830000 | 7.545455 | 7.272727 | inf |
3 | 1.000 | 803 | 484 | 319 | 0.803000 | 0.484000 | 0.803000 | 9.674699 | 6.050000 | 106.333336 |
4 | 10.000 | 7.714 | 3.416 | 4.298 | 0.771400 | 0.341600 | 0.771400 | 9.606476 | 7.057851 | 13.473354 |
5 | 100.000 | 75.249 | 26.525 | 48.724 | 0.752490 | 0.265250 | 0.752490 | 9.754861 | 7.764930 | 11.336435 |
6 | 1.000.000 | 742.386 | 215.990 | 526.396 | 0.742386 | 0.215990 | 0.742386 | 9.865726 | 8.142884 | 10.803629 |
7 | 10.000.000 | 7.352.110 | 1.821.457 | 5.530.653 | 0.735211 | 0.182146 | 0.735211 | 9.903352 | 8.433062 | 10.506639 |
8 | 100.000.000 | 72.978.475 | 15.756.572 | 57.221.903 | 0.729785 | 0.157566 | 0.729785 | 9.926194 | 8.650532 | 10.346320 |
9 | 1.000.000.000 | 725.520.447 | 138.901.139 | 586.619.308 | 0.725520 | 0.138901 | 0.725520 | 9.941568 | 8.815441 | 10.251657 |
10 | 10.000.000.000 | 7.221.557.011 | 1.241.842.313 | 5.979.714.698 | 0.722156 | 0.124184 | 0.722156 | 9.953624 | 8.940476 | 10.193518 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 14 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.555556 | 1.555556 | -nan |
5 | 32 | 30 | 30 | 0 | 0.937500 | 0.937500 | 0.000000 | 2.142857 | 2.142857 | -nan |
6 | 64 | 56 | 55 | 1 | 0.875000 | 0.859375 | 0.015625 | 1.866667 | 1.833333 | inf |
7 | 128 | 105 | 96 | 9 | 0.820312 | 0.750000 | 0.070312 | 1.875000 | 1.745455 | 9.000000 |
8 | 256 | 207 | 162 | 45 | 0.808594 | 0.632812 | 0.175781 | 1.971429 | 1.687500 | 5.000000 |
9 | 512 | 412 | 283 | 129 | 0.804688 | 0.552734 | 0.251953 | 1.990338 | 1.746914 | 2.866667 |
10 | 1.024 | 821 | 495 | 326 | 0.801758 | 0.483398 | 0.318359 | 1.992718 | 1.749117 | 2.527132 |
11 | 2.048 | 1.617 | 880 | 737 | 0.789551 | 0.429688 | 0.359863 | 1.969549 | 1.777778 | 2.260736 |
12 | 4.096 | 3.202 | 1.584 | 1.618 | 0.781738 | 0.386719 | 0.395020 | 1.980210 | 1.800000 | 2.195387 |
13 | 8.192 | 6.342 | 2.859 | 3.483 | 0.774170 | 0.348999 | 0.425171 | 1.980637 | 1.804924 | 2.152658 |
14 | 16.384 | 12.532 | 5.292 | 7.240 | 0.764893 | 0.322998 | 0.441895 | 1.976033 | 1.850997 | 2.078668 |
15 | 32.768 | 24.914 | 9.724 | 15.190 | 0.760315 | 0.296753 | 0.463562 | 1.988031 | 1.837491 | 2.098066 |
16 | 65.536 | 49.504 | 18.153 | 31.351 | 0.755371 | 0.276993 | 0.478378 | 1.986995 | 1.866824 | 2.063924 |
17 | 131.072 | 98.386 | 33.796 | 64.590 | 0.750626 | 0.257843 | 0.492783 | 1.987435 | 1.861731 | 2.060221 |
18 | 262.144 | 196.000 | 63.427 | 132.573 | 0.747681 | 0.241955 | 0.505726 | 1.992153 | 1.876761 | 2.052531 |
19 | 524.288 | 390.428 | 119.505 | 270.923 | 0.744682 | 0.227938 | 0.516745 | 1.991980 | 1.884135 | 2.043576 |
20 | 1.048.576 | 778.286 | 225.565 | 552.721 | 0.742231 | 0.215116 | 0.527116 | 1.993418 | 1.887494 | 2.040141 |
21 | 2.097.152 | 1.551.630 | 427.285 | 1.124.345 | 0.739875 | 0.203745 | 0.536129 | 1.993650 | 1.894288 | 2.034200 |
22 | 4.194.304 | 3.094.104 | 811.179 | 2.282.925 | 0.737692 | 0.193400 | 0.544292 | 1.994099 | 1.898450 | 2.030449 |
23 | 8.388.608 | 6.171.895 | 1.545.959 | 4.625.936 | 0.735747 | 0.184293 | 0.551455 | 1.994728 | 1.905817 | 2.026320 |
24 | 16.777.216 | 12.312.322 | 2.951.722 | 9.360.600 | 0.733872 | 0.175936 | 0.557935 | 1.994901 | 1.909315 | 2.023504 |
25 | 33.554.432 | 24.568.220 | 5.647.951 | 18.920.269 | 0.732190 | 0.168322 | 0.563868 | 1.995417 | 1.913443 | 2.021267 |
26 | 67.108.864 | 49.032.269 | 10.824.615 | 38.207.654 | 0.730638 | 0.161299 | 0.569338 | 1.995760 | 1.916556 | 2.019403 |
27 | 134.217.728 | 97.869.563 | 20.791.361 | 77.078.202 | 0.729185 | 0.154908 | 0.574277 | 1.996024 | 1.920748 | 2.017350 |
28 | 268.435.456 | 195.374.535 | 39.987.525 | 155.387.010 | 0.727827 | 0.148965 | 0.578862 | 1.996275 | 1.923276 | 2.015966 |
29 | 536.870.912 | 390.074.593 | 77.039.185 | 313.035.408 | 0.726571 | 0.143497 | 0.583074 | 1.996548 | 1.926581 | 2.014553 |
30 | 1.073.741.824 | 778.897.442 | 148.599.807 | 630.297.635 | 0.725405 | 0.138394 | 0.587010 | 1.996791 | 1.928886 | 2.013503 |
31 | 2.147.483.648 | 1.555.469.819 | 286.996.950 | 1.268.472.869 | 0.724322 | 0.133643 | 0.590679 | 1.997015 | 1.931341 | 2.012498 |
32 | 4.294.967.296 | 3.106.581.099 | 554.937.875 | 2.551.643.224 | 0.723307 | 0.129207 | 0.594101 | 1.997198 | 1.933602 | 2.011587 |
33 | 8.589.934.592 | 6.204.997.559 | 1.074.244.338 | 5.130.753.221 | 0.722357 | 0.125059 | 0.597298 | 1.997372 | 1.935792 | 2.010764 |
34 | 17.179.869.184 | 12.394.656.203 | 2.081.651.212 | 10.313.004.991 | 0.721464 | 0.121168 | 0.600296 | 1.997528 | 1.937782 | 2.010037 |
35 | 34.359.738.368 | 24.760.432.605 | 4.037.766.917 | 20.722.665.688 | 0.720623 | 0.117514 | 0.603109 | 1.997670 | 1.939694 | 2.009372 |
36 | 68.719.476.736 | 49.466.476.651 | 7.839.124.674 | 41.627.351.977 | 0.719832 | 0.114074 | 0.605758 | 1.997803 | 1.941450 | 2.008784 |
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 | 1 | 2 | 0 | 2 | 0 | 1 |
2 | 4 | 5 | 3 | 2 | 0 | 2 | 0 | 3 |
3 | 8 | 9 | 4 | 5 | 0 | 4 | 0 | 5 |
4 | 16 | 14 | 6 | 8 | 1 | 6 | 1 | 6 |
5 | 32 | 30 | 15 | 15 | 9 | 6 | 9 | 6 |
6 | 64 | 55 | 28 | 27 | 21 | 6 | 22 | 6 |
7 | 128 | 96 | 47 | 49 | 42 | 6 | 42 | 6 |
8 | 256 | 162 | 79 | 83 | 71 | 6 | 79 | 6 |
9 | 512 | 283 | 138 | 145 | 135 | 6 | 136 | 6 |
10 | 1.024 | 495 | 249 | 246 | 242 | 6 | 241 | 6 |
11 | 2.048 | 880 | 441 | 439 | 429 | 6 | 439 | 6 |
12 | 4.096 | 1.584 | 789 | 795 | 790 | 6 | 782 | 6 |
13 | 8.192 | 2.859 | 1.435 | 1.424 | 1.422 | 6 | 1.425 | 6 |
14 | 16.384 | 5.292 | 2.644 | 2.648 | 2.627 | 6 | 2.653 | 6 |
15 | 32.768 | 9.724 | 4.828 | 4.896 | 4.858 | 6 | 4.854 | 6 |
16 | 65.536 | 18.153 | 9.084 | 9.069 | 9.085 | 6 | 9.056 | 6 |
17 | 131.072 | 33.796 | 16.966 | 16.830 | 16.883 | 6 | 16.901 | 6 |
18 | 262.144 | 63.427 | 31.899 | 31.528 | 31.724 | 6 | 31.691 | 6 |
19 | 524.288 | 119.505 | 60.099 | 59.406 | 59.737 | 6 | 59.756 | 6 |
20 | 1.048.576 | 225.565 | 113.341 | 112.224 | 112.751 | 6 | 112.802 | 6 |
21 | 2.097.152 | 427.285 | 214.701 | 212.584 | 213.500 | 6 | 213.773 | 6 |
22 | 4.194.304 | 811.179 | 407.029 | 404.150 | 405.444 | 6 | 405.723 | 6 |
23 | 8.388.608 | 1.545.959 | 775.185 | 770.774 | 772.946 | 6 | 773.001 | 6 |
24 | 16.777.216 | 2.951.722 | 1.480.743 | 1.470.979 | 1.475.010 | 6 | 1.476.700 | 6 |
25 | 33.554.432 | 5.647.951 | 2.833.270 | 2.814.681 | 2.823.806 | 6 | 2.824.133 | 6 |
26 | 67.108.864 | 10.824.615 | 5.431.021 | 5.393.594 | 5.411.029 | 6 | 5.413.574 | 6 |
27 | 134.217.728 | 20.791.361 | 10.429.396 | 10.361.965 | 10.392.132 | 6 | 10.399.217 | 6 |
28 | 268.435.456 | 39.987.525 | 20.056.256 | 19.931.269 | 19.991.652 | 6 | 19.995.861 | 6 |
29 | 536.870.912 | 77.039.185 | 38.637.272 | 38.401.913 | 38.517.421 | 6 | 38.521.752 | 6 |
30 | 1.073.741.824 | 148.599.807 | 74.520.535 | 74.079.272 | 74.301.244 | 6 | 74.298.551 | 6 |
31 | 2.147.483.648 | 286.996.950 | 143.913.057 | 143.083.893 | 143.490.394 | 6 | 143.506.544 | 6 |
32 | 4.294.967.296 | 554.937.875 | 278.246.544 | 276.691.331 | 277.467.840 | 6 | 277.470.023 | 6 |
33 | 8.589.934.592 | 1.074.244.338 | 538.569.353 | 535.674.985 | 537.110.927 | 6 | 537.133.399 | 6 |
34 | 17.179.869.184 | 2.081.651.212 | 1.043.523.585 | 1.038.127.627 | 1.040.818.777 | 6 | 1.040.832.423 | 6 |
35 | 34.359.738.368 | 4.037.766.917 | 2.023.969.235 | 2.013.797.682 | 2.018.877.371 | 6 | 2.018.889.534 | 6 |
36 | 68.719.476.736 | 7.839.124.674 | 3.929.141.999 | 3.909.982.675 | 3.919.570.804 | 6 | 3.919.553.858 | 6 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 64 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
7 | 128 | 9 | 4 | 5 | 1 | 5 | 1 | 2 |
8 | 256 | 45 | 26 | 19 | 7 | 16 | 7 | 15 |
9 | 512 | 129 | 64 | 65 | 24 | 43 | 20 | 42 |
10 | 1.024 | 326 | 153 | 173 | 54 | 109 | 62 | 101 |
11 | 2.048 | 737 | 364 | 373 | 141 | 232 | 138 | 226 |
12 | 4.096 | 1.618 | 807 | 811 | 318 | 492 | 324 | 484 |
13 | 8.192 | 3.483 | 1.715 | 1.768 | 702 | 1.037 | 744 | 1.000 |
14 | 16.384 | 7.240 | 3.558 | 3.682 | 1.504 | 2.093 | 1.590 | 2.053 |
15 | 32.768 | 15.190 | 7.535 | 7.655 | 3.296 | 4.272 | 3.324 | 4.298 |
16 | 65.536 | 31.351 | 15.561 | 15.790 | 6.939 | 8.736 | 6.980 | 8.696 |
17 | 131.072 | 64.590 | 32.335 | 32.255 | 14.504 | 17.732 | 14.609 | 17.745 |
18 | 262.144 | 132.573 | 66.279 | 66.294 | 30.178 | 36.160 | 30.264 | 35.971 |
19 | 524.288 | 270.923 | 135.306 | 135.617 | 62.226 | 73.141 | 62.418 | 73.138 |
20 | 1.048.576 | 552.721 | 276.044 | 276.677 | 128.006 | 148.104 | 128.233 | 148.378 |
21 | 2.097.152 | 1.124.345 | 561.985 | 562.360 | 261.705 | 300.254 | 262.553 | 299.833 |
22 | 4.194.304 | 2.282.925 | 1.141.734 | 1.141.191 | 534.716 | 606.472 | 535.232 | 606.505 |
23 | 8.388.608 | 4.625.936 | 2.313.723 | 2.312.213 | 1.088.286 | 1.224.354 | 1.089.259 | 1.224.037 |
24 | 16.777.216 | 9.360.600 | 4.681.190 | 4.679.410 | 2.211.130 | 2.468.309 | 2.213.141 | 2.468.020 |
25 | 33.554.432 | 18.920.269 | 9.460.734 | 9.459.535 | 4.485.237 | 4.974.422 | 4.488.606 | 4.972.004 |
26 | 67.108.864 | 38.207.654 | 19.101.899 | 19.105.755 | 9.086.101 | 10.017.513 | 9.088.623 | 10.015.417 |
27 | 134.217.728 | 77.078.202 | 38.532.426 | 38.545.776 | 18.376.305 | 20.162.814 | 18.382.186 | 20.156.897 |
28 | 268.435.456 | 155.387.010 | 77.680.090 | 77.706.920 | 37.139.379 | 40.549.875 | 37.145.555 | 40.552.201 |
29 | 536.870.912 | 313.035.408 | 156.502.239 | 156.533.169 | 74.984.068 | 81.525.276 | 74.993.704 | 81.532.360 |
30 | 1.073.741.824 | 630.297.635 | 315.118.734 | 315.178.901 | 151.287.856 | 163.846.248 | 151.306.917 | 163.856.614 |
31 | 2.147.483.648 | 1.268.472.869 | 634.201.919 | 634.270.950 | 305.028.430 | 329.204.807 | 305.055.385 | 329.184.247 |
32 | 4.294.967.296 | 2.551.643.224 | 1.275.757.299 | 1.275.885.925 | 614.627.836 | 661.196.678 | 614.662.138 | 661.156.572 |
33 | 8.589.934.592 | 5.130.753.221 | 2.565.276.375 | 2.565.476.846 | 1.237.767.207 | 1.327.601.713 | 1.237.810.509 | 1.327.573.792 |
34 | 17.179.869.184 | 10.313.004.991 | 5.156.231.525 | 5.156.773.466 | 2.491.462.084 | 2.664.985.468 | 2.491.537.897 | 2.665.019.542 |
35 | 34.359.738.368 | 20.722.665.688 | 10.360.815.339 | 10.361.850.349 | 5.012.804.722 | 5.348.414.249 | 5.012.937.309 | 5.348.509.408 |
36 | 68.719.476.736 | 41.627.351.977 | 20.812.726.004 | 20.814.625.973 | 10.081.913.900 | 10.731.706.656 | 10.081.943.729 | 10.731.787.692 |