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-109
f(0)=109
f(1)=107
f(2)=103
f(3)=97
f(4)=89
f(5)=79
f(6)=67
f(7)=53
f(8)=37
f(9)=19
f(10)=1
f(11)=23
f(12)=47
f(13)=73
f(14)=101
f(15)=131
f(16)=163
f(17)=197
f(18)=233
f(19)=271
f(20)=311
f(21)=353
f(22)=397
f(23)=443
f(24)=491
f(25)=541
f(26)=593
f(27)=647
f(28)=1
f(29)=761
f(30)=821
f(31)=883
f(32)=947
f(33)=1013
f(34)=1
f(35)=1151
f(36)=1223
f(37)=1297
f(38)=1373
f(39)=1451
f(40)=1531
f(41)=1613
f(42)=1697
f(43)=1783
f(44)=1871
f(45)=1
f(46)=2053
f(47)=113
f(48)=2243
f(49)=2341
f(50)=2441
f(51)=2543
f(52)=2647
f(53)=2753
f(54)=2861
f(55)=2971
f(56)=3083
f(57)=139
f(58)=3313
f(59)=1
f(60)=1
f(61)=3673
f(62)=3797
f(63)=3923
f(64)=4051
f(65)=1
f(66)=227
f(67)=4447
f(68)=4583
f(69)=4721
f(70)=4861
f(71)=5003
f(72)=5147
f(73)=1
f(74)=5441
f(75)=5591
f(76)=5743
f(77)=5897
f(78)=6053
f(79)=6211
f(80)=277
f(81)=1
f(82)=181
f(83)=6863
f(84)=1
f(85)=379
f(86)=1
f(87)=7547
f(88)=7723
f(89)=7901
f(90)=8081
f(91)=8263
f(92)=8447
f(93)=1
f(94)=8821
f(95)=9011
f(96)=9203
f(97)=9397
f(98)=1
f(99)=9791
b) Substitution of the polynom
The polynom f(x)=x^2+1x-109 could be written as f(y)= y^2-109.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 | 10 | 10 | 0 | 1.000000 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 87 | 81 | 6 | 0.870000 | 0.810000 | 0.870000 | 8.700000 | 8.100000 | inf |
3 | 1.000 | 842 | 486 | 356 | 0.842000 | 0.486000 | 0.842000 | 9.678161 | 6.000000 | 59.333332 |
4 | 10.000 | 7.973 | 3.450 | 4.523 | 0.797300 | 0.345000 | 0.797300 | 9.469121 | 7.098765 | 12.705056 |
5 | 100.000 | 77.286 | 26.836 | 50.450 | 0.772860 | 0.268360 | 0.772860 | 9.693465 | 7.778551 | 11.154101 |
6 | 1.000.000 | 758.916 | 219.562 | 539.354 | 0.758916 | 0.219562 | 0.758916 | 9.819579 | 8.181622 | 10.690863 |
7 | 10.000.000 | 7.493.788 | 1.858.110 | 5.635.678 | 0.749379 | 0.185811 | 0.749379 | 9.874331 | 8.462803 | 10.448941 |
8 | 100.000.000 | 74.220.439 | 16.096.930 | 58.123.509 | 0.742204 | 0.160969 | 0.742204 | 9.904262 | 8.663066 | 10.313490 |
9 | 1.000.000.000 | 736.606.622 | 142.047.448 | 594.559.174 | 0.736607 | 0.142047 | 0.736607 | 9.924579 | 8.824506 | 10.229238 |
10 | 10.000.000.000 | 7.321.394.092 | 1.271.143.765 | 6.050.250.327 | 0.732139 | 0.127114 | 0.732139 | 9.939355 | 8.948727 | 10.176027 |
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 | 16 | 16 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.777778 | 1.777778 | -nan |
5 | 32 | 31 | 31 | 0 | 0.968750 | 0.968750 | 0.000000 | 1.937500 | 1.937500 | -nan |
6 | 64 | 59 | 57 | 2 | 0.921875 | 0.890625 | 0.031250 | 1.903226 | 1.838710 | inf |
7 | 128 | 110 | 95 | 15 | 0.859375 | 0.742188 | 0.117188 | 1.864407 | 1.666667 | 7.500000 |
8 | 256 | 220 | 165 | 55 | 0.859375 | 0.644531 | 0.214844 | 2.000000 | 1.736842 | 3.666667 |
9 | 512 | 436 | 285 | 151 | 0.851562 | 0.556641 | 0.294922 | 1.981818 | 1.727273 | 2.745455 |
10 | 1.024 | 864 | 495 | 369 | 0.843750 | 0.483398 | 0.360352 | 1.981651 | 1.736842 | 2.443709 |
11 | 2.048 | 1.686 | 877 | 809 | 0.823242 | 0.428223 | 0.395020 | 1.951389 | 1.771717 | 2.192412 |
12 | 4.096 | 3.310 | 1.589 | 1.721 | 0.808105 | 0.387939 | 0.420166 | 1.963227 | 1.811859 | 2.127318 |
13 | 8.192 | 6.556 | 2.892 | 3.664 | 0.800293 | 0.353027 | 0.447266 | 1.980665 | 1.820013 | 2.128995 |
14 | 16.384 | 12.944 | 5.343 | 7.601 | 0.790039 | 0.326111 | 0.463928 | 1.974375 | 1.847510 | 2.074509 |
15 | 32.768 | 25.639 | 9.885 | 15.754 | 0.782440 | 0.301666 | 0.480774 | 1.980763 | 1.850084 | 2.072622 |
16 | 65.536 | 50.899 | 18.288 | 32.611 | 0.776657 | 0.279053 | 0.497604 | 1.985218 | 1.850076 | 2.070014 |
17 | 131.072 | 101.040 | 34.313 | 66.727 | 0.770874 | 0.261787 | 0.509087 | 1.985108 | 1.876258 | 2.046150 |
18 | 262.144 | 200.876 | 64.306 | 136.570 | 0.766281 | 0.245308 | 0.520973 | 1.988084 | 1.874100 | 2.046698 |
19 | 524.288 | 399.790 | 121.102 | 278.688 | 0.762539 | 0.230984 | 0.531555 | 1.990233 | 1.883215 | 2.040624 |
20 | 1.048.576 | 795.633 | 229.417 | 566.216 | 0.758775 | 0.218789 | 0.539986 | 1.990127 | 1.894411 | 2.031720 |
21 | 2.097.152 | 1.584.585 | 435.017 | 1.149.568 | 0.755589 | 0.207432 | 0.548157 | 1.991603 | 1.896185 | 2.030264 |
22 | 4.194.304 | 3.156.946 | 827.517 | 2.329.429 | 0.752675 | 0.197295 | 0.555379 | 1.992286 | 1.902264 | 2.026352 |
23 | 8.388.608 | 6.291.443 | 1.577.329 | 4.714.114 | 0.749998 | 0.188032 | 0.561966 | 1.992889 | 1.906099 | 2.023721 |
24 | 16.777.216 | 12.541.961 | 3.013.504 | 9.528.457 | 0.747559 | 0.179619 | 0.567940 | 1.993495 | 1.910511 | 2.021261 |
25 | 33.554.432 | 25.011.476 | 5.766.946 | 19.244.530 | 0.745400 | 0.171868 | 0.573532 | 1.994224 | 1.913701 | 2.019690 |
26 | 67.108.864 | 49.883.922 | 11.058.633 | 38.825.289 | 0.743328 | 0.164786 | 0.578542 | 1.994441 | 1.917589 | 2.017471 |
27 | 134.217.728 | 99.509.162 | 21.242.317 | 78.266.845 | 0.741401 | 0.158268 | 0.583133 | 1.994814 | 1.920881 | 2.015873 |
28 | 268.435.456 | 198.548.527 | 40.869.458 | 157.679.069 | 0.739651 | 0.152251 | 0.587400 | 1.995279 | 1.923964 | 2.014634 |
29 | 536.870.912 | 396.206.597 | 78.755.204 | 317.451.393 | 0.737992 | 0.146693 | 0.591299 | 1.995515 | 1.926994 | 2.013275 |
30 | 1.073.741.824 | 790.760.760 | 151.972.857 | 638.787.903 | 0.736453 | 0.141536 | 0.594918 | 1.995829 | 1.929687 | 2.012239 |
31 | 2.147.483.648 | 1.578.431.562 | 293.595.393 | 1.284.836.169 | 0.735014 | 0.136716 | 0.598298 | 1.996092 | 1.931893 | 2.011366 |
32 | 4.294.967.296 | 3.151.060.425 | 567.872.710 | 2.583.187.715 | 0.733663 | 0.132218 | 0.601445 | 1.996324 | 1.934202 | 2.010519 |
33 | 8.589.934.592 | 6.291.315.825 | 1.099.534.547 | 5.191.781.278 | 0.732406 | 0.128003 | 0.604403 | 1.996571 | 1.936234 | 2.009835 |
34 | 17.179.869.184 | 12.562.242.292 | 2.131.209.659 | 10.431.032.633 | 0.731219 | 0.124053 | 0.607166 | 1.996759 | 1.938283 | 2.009143 |
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 | 5 | 3 | 2 | 2 | 1 | 1 | 1 |
3 | 8 | 9 | 6 | 3 | 2 | 2 | 3 | 2 |
4 | 16 | 16 | 9 | 7 | 3 | 5 | 4 | 4 |
5 | 32 | 31 | 13 | 18 | 7 | 9 | 8 | 7 |
6 | 64 | 57 | 23 | 34 | 13 | 16 | 15 | 13 |
7 | 128 | 95 | 35 | 60 | 22 | 26 | 23 | 24 |
8 | 256 | 165 | 54 | 111 | 42 | 42 | 42 | 39 |
9 | 512 | 285 | 96 | 189 | 72 | 68 | 73 | 72 |
10 | 1.024 | 495 | 169 | 326 | 126 | 120 | 122 | 127 |
11 | 2.048 | 877 | 300 | 577 | 215 | 214 | 221 | 227 |
12 | 4.096 | 1.589 | 535 | 1.054 | 395 | 391 | 396 | 407 |
13 | 8.192 | 2.892 | 967 | 1.925 | 720 | 714 | 720 | 738 |
14 | 16.384 | 5.343 | 1.771 | 3.572 | 1.325 | 1.327 | 1.351 | 1.340 |
15 | 32.768 | 9.885 | 3.267 | 6.618 | 2.480 | 2.471 | 2.475 | 2.459 |
16 | 65.536 | 18.288 | 6.095 | 12.193 | 4.555 | 4.572 | 4.564 | 4.597 |
17 | 131.072 | 34.313 | 11.487 | 22.826 | 8.580 | 8.567 | 8.561 | 8.605 |
18 | 262.144 | 64.306 | 21.507 | 42.799 | 16.127 | 16.008 | 16.010 | 16.161 |
19 | 524.288 | 121.102 | 40.326 | 80.776 | 30.300 | 30.174 | 30.217 | 30.411 |
20 | 1.048.576 | 229.417 | 76.518 | 152.899 | 57.562 | 57.248 | 57.287 | 57.320 |
21 | 2.097.152 | 435.017 | 145.111 | 289.906 | 109.016 | 108.766 | 108.605 | 108.630 |
22 | 4.194.304 | 827.517 | 276.132 | 551.385 | 207.082 | 207.001 | 206.594 | 206.840 |
23 | 8.388.608 | 1.577.329 | 526.089 | 1.051.240 | 394.610 | 394.325 | 394.270 | 394.124 |
24 | 16.777.216 | 3.013.504 | 1.004.991 | 2.008.513 | 753.246 | 753.812 | 752.724 | 753.722 |
25 | 33.554.432 | 5.766.946 | 1.922.492 | 3.844.454 | 1.441.139 | 1.441.822 | 1.441.861 | 1.442.124 |
26 | 67.108.864 | 11.058.633 | 3.686.320 | 7.372.313 | 2.764.809 | 2.764.864 | 2.764.862 | 2.764.098 |
27 | 134.217.728 | 21.242.317 | 7.079.602 | 14.162.715 | 5.312.090 | 5.308.156 | 5.312.236 | 5.309.835 |
28 | 268.435.456 | 40.869.458 | 13.623.504 | 27.245.954 | 10.218.064 | 10.215.028 | 10.220.363 | 10.216.003 |
29 | 536.870.912 | 78.755.204 | 26.250.509 | 52.504.695 | 19.693.338 | 19.684.772 | 19.688.172 | 19.688.922 |
30 | 1.073.741.824 | 151.972.857 | 50.660.580 | 101.312.277 | 38.000.041 | 37.987.656 | 37.991.393 | 37.993.767 |
31 | 2.147.483.648 | 293.595.393 | 97.862.167 | 195.733.226 | 73.402.915 | 73.395.489 | 73.399.554 | 73.397.435 |
32 | 4.294.967.296 | 567.872.710 | 189.282.232 | 378.590.478 | 141.965.989 | 141.968.788 | 141.976.536 | 141.961.397 |
33 | 8.589.934.592 | 1.099.534.547 | 366.500.069 | 733.034.478 | 274.888.922 | 274.878.100 | 274.894.363 | 274.873.162 |
34 | 17.179.869.184 | 2.131.209.659 | 710.390.576 | 1.420.819.083 | 532.786.911 | 532.799.009 | 532.835.407 | 532.788.332 |
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 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
7 | 128 | 15 | 7 | 8 | 4 | 4 | 5 | 2 |
8 | 256 | 55 | 27 | 28 | 16 | 15 | 15 | 9 |
9 | 512 | 151 | 73 | 78 | 32 | 44 | 42 | 33 |
10 | 1.024 | 369 | 179 | 190 | 87 | 91 | 99 | 92 |
11 | 2.048 | 809 | 389 | 420 | 195 | 209 | 208 | 197 |
12 | 4.096 | 1.721 | 848 | 873 | 415 | 438 | 436 | 432 |
13 | 8.192 | 3.664 | 1.824 | 1.840 | 899 | 916 | 917 | 932 |
14 | 16.384 | 7.601 | 3.771 | 3.830 | 1.877 | 1.904 | 1.908 | 1.912 |
15 | 32.768 | 15.754 | 7.873 | 7.881 | 3.896 | 3.913 | 3.975 | 3.970 |
16 | 65.536 | 32.611 | 16.290 | 16.321 | 8.157 | 8.141 | 8.172 | 8.141 |
17 | 131.072 | 66.727 | 33.233 | 33.494 | 16.642 | 16.671 | 16.684 | 16.730 |
18 | 262.144 | 136.570 | 68.096 | 68.474 | 34.165 | 34.086 | 34.219 | 34.100 |
19 | 524.288 | 278.688 | 138.940 | 139.748 | 69.466 | 69.630 | 69.832 | 69.760 |
20 | 1.048.576 | 566.216 | 282.395 | 283.821 | 141.105 | 141.465 | 141.635 | 142.011 |
21 | 2.097.152 | 1.149.568 | 574.338 | 575.230 | 287.266 | 286.934 | 287.577 | 287.791 |
22 | 4.194.304 | 2.329.429 | 1.163.443 | 1.165.986 | 581.903 | 582.234 | 582.920 | 582.372 |
23 | 8.388.608 | 4.714.114 | 2.355.501 | 2.358.613 | 1.177.718 | 1.179.077 | 1.178.957 | 1.178.362 |
24 | 16.777.216 | 9.528.457 | 4.762.404 | 4.766.053 | 2.379.907 | 2.382.743 | 2.383.911 | 2.381.896 |
25 | 33.554.432 | 19.244.530 | 9.620.636 | 9.623.894 | 4.808.385 | 4.813.267 | 4.813.040 | 4.809.838 |
26 | 67.108.864 | 38.825.289 | 19.409.642 | 19.415.647 | 9.706.323 | 9.707.722 | 9.708.372 | 9.702.872 |
27 | 134.217.728 | 78.266.845 | 39.126.750 | 39.140.095 | 19.566.641 | 19.571.437 | 19.563.056 | 19.565.711 |
28 | 268.435.456 | 157.679.069 | 78.827.462 | 78.851.607 | 39.418.977 | 39.427.900 | 39.413.652 | 39.418.540 |
29 | 536.870.912 | 317.451.393 | 158.693.151 | 158.758.242 | 79.363.986 | 79.374.947 | 79.357.994 | 79.354.466 |
30 | 1.073.741.824 | 638.787.903 | 319.329.077 | 319.458.826 | 159.697.210 | 159.710.847 | 159.692.197 | 159.687.649 |
31 | 2.147.483.648 | 1.284.836.169 | 642.289.607 | 642.546.562 | 321.214.060 | 321.221.433 | 321.199.927 | 321.200.749 |
32 | 4.294.967.296 | 2.583.187.715 | 1.291.341.668 | 1.291.846.047 | 645.791.632 | 645.809.482 | 645.801.528 | 645.785.073 |
33 | 8.589.934.592 | 5.191.781.278 | 2.595.398.401 | 2.596.382.877 | 1.297.967.528 | 1.297.955.978 | 1.297.941.383 | 1.297.916.389 |
34 | 17.179.869.184 | 10.431.032.633 | 5.214.472.028 | 5.216.560.605 | 2.607.773.915 | 2.607.779.759 | 2.607.753.264 | 2.607.725.695 |