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-19
f(0)=19
f(1)=17
f(2)=13
f(3)=7
f(4)=1
f(5)=11
f(6)=23
f(7)=37
f(8)=53
f(9)=71
f(10)=1
f(11)=113
f(12)=137
f(13)=163
f(14)=191
f(15)=1
f(16)=1
f(17)=41
f(18)=1
f(19)=1
f(20)=401
f(21)=443
f(22)=487
f(23)=1
f(24)=83
f(25)=631
f(26)=683
f(27)=67
f(28)=61
f(29)=1
f(30)=911
f(31)=139
f(32)=1
f(33)=1103
f(34)=1171
f(35)=73
f(36)=101
f(37)=1
f(38)=1
f(39)=1
f(40)=1621
f(41)=131
f(42)=1787
f(43)=1873
f(44)=1
f(45)=293
f(46)=2143
f(47)=2237
f(48)=2333
f(49)=1
f(50)=2531
f(51)=2633
f(52)=1
f(53)=2843
f(54)=227
f(55)=3061
f(56)=167
f(57)=173
f(58)=1
f(59)=503
f(60)=331
f(61)=1
f(62)=1
f(63)=4013
f(64)=1
f(65)=4271
f(66)=1
f(67)=349
f(68)=4673
f(69)=283
f(70)=4951
f(71)=463
f(72)=5237
f(73)=769
f(74)=5531
f(75)=1
f(76)=307
f(77)=5987
f(78)=6143
f(79)=6301
f(80)=1
f(81)=179
f(82)=617
f(83)=409
f(84)=7121
f(85)=317
f(86)=439
f(87)=1091
f(88)=601
f(89)=1
f(90)=8171
f(91)=8353
f(92)=8537
f(93)=1
f(94)=1
f(95)=479
f(96)=9293
f(97)=1
f(98)=421
f(99)=241
b) Substitution of the polynom
The polynom f(x)=x^2+1x-19 could be written as f(y)= y^2-19.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 | 9 | 9 | 0 | 0.900000 | 0.900000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 75 | 45 | 30 | 0.750000 | 0.450000 | 0.750000 | 8.333333 | 5.000000 | inf |
3 | 1.000 | 734 | 265 | 469 | 0.734000 | 0.265000 | 0.734000 | 9.786667 | 5.888889 | 15.633333 |
4 | 10.000 | 7.238 | 1.938 | 5.300 | 0.723800 | 0.193800 | 0.723800 | 9.861035 | 7.313208 | 11.300640 |
5 | 100.000 | 71.825 | 14.876 | 56.949 | 0.718250 | 0.148760 | 0.718250 | 9.923322 | 7.675955 | 10.745094 |
6 | 1.000.000 | 714.410 | 121.610 | 592.800 | 0.714410 | 0.121610 | 0.714410 | 9.946537 | 8.174912 | 10.409313 |
7 | 10.000.000 | 7.109.983 | 1.026.378 | 6.083.605 | 0.710998 | 0.102638 | 0.710998 | 9.952245 | 8.439915 | 10.262491 |
8 | 100.000.000 | 70.851.668 | 8.908.838 | 61.942.830 | 0.708517 | 0.089088 | 0.708517 | 9.965096 | 8.679880 | 10.181929 |
9 | 1.000.000.000 | 706.661.302 | 78.609.966 | 628.051.336 | 0.706661 | 0.078610 | 0.706661 | 9.973814 | 8.823818 | 10.139209 |
10 | 10.000.000.000 | 7.051.922.917 | 703.536.302 | 6.348.386.615 | 0.705192 | 0.070354 | 0.705192 | 9.979212 | 8.949709 | 10.108070 |
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 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 8 | 8 | 0 | 1.000000 | 1.000000 | 0.000000 | 2.000000 | 2.000000 | -nan |
4 | 16 | 13 | 13 | 0 | 0.812500 | 0.812500 | 0.000000 | 1.625000 | 1.625000 | -nan |
5 | 32 | 24 | 19 | 5 | 0.750000 | 0.593750 | 0.156250 | 1.846154 | 1.461538 | inf |
6 | 64 | 46 | 32 | 14 | 0.718750 | 0.500000 | 0.218750 | 1.916667 | 1.684211 | 2.800000 |
7 | 128 | 94 | 53 | 41 | 0.734375 | 0.414062 | 0.320312 | 2.043478 | 1.656250 | 2.928571 |
8 | 256 | 188 | 91 | 97 | 0.734375 | 0.355469 | 0.378906 | 2.000000 | 1.716981 | 2.365854 |
9 | 512 | 375 | 154 | 221 | 0.732422 | 0.300781 | 0.431641 | 1.994681 | 1.692308 | 2.278351 |
10 | 1.024 | 750 | 273 | 477 | 0.732422 | 0.266602 | 0.465820 | 2.000000 | 1.772727 | 2.158371 |
11 | 2.048 | 1.497 | 500 | 997 | 0.730957 | 0.244141 | 0.486816 | 1.996000 | 1.831502 | 2.090147 |
12 | 4.096 | 2.977 | 895 | 2.082 | 0.726807 | 0.218506 | 0.508301 | 1.988644 | 1.790000 | 2.088265 |
13 | 8.192 | 5.953 | 1.633 | 4.320 | 0.726685 | 0.199341 | 0.527344 | 1.999664 | 1.824581 | 2.074928 |
14 | 16.384 | 11.866 | 2.939 | 8.927 | 0.724243 | 0.179382 | 0.544861 | 1.993281 | 1.799755 | 2.066435 |
15 | 32.768 | 23.661 | 5.464 | 18.197 | 0.722076 | 0.166748 | 0.555328 | 1.994017 | 1.859136 | 2.038423 |
16 | 65.536 | 47.167 | 10.184 | 36.983 | 0.719711 | 0.155396 | 0.564316 | 1.993449 | 1.863836 | 2.032368 |
17 | 131.072 | 94.135 | 18.961 | 75.174 | 0.718193 | 0.144661 | 0.573532 | 1.995781 | 1.861842 | 2.032664 |
18 | 262.144 | 187.907 | 35.691 | 152.216 | 0.716808 | 0.136150 | 0.580658 | 1.996144 | 1.882337 | 2.024849 |
19 | 524.288 | 375.172 | 67.177 | 307.995 | 0.715584 | 0.128130 | 0.587454 | 1.996583 | 1.882183 | 2.023407 |
20 | 1.048.576 | 749.012 | 126.903 | 622.109 | 0.714314 | 0.121024 | 0.593289 | 1.996450 | 1.889084 | 2.019867 |
21 | 2.097.152 | 1.495.799 | 240.337 | 1.255.462 | 0.713253 | 0.114602 | 0.598651 | 1.997029 | 1.893864 | 2.018074 |
22 | 4.194.304 | 2.987.074 | 457.479 | 2.529.595 | 0.712174 | 0.109071 | 0.603102 | 1.996976 | 1.903490 | 2.014872 |
23 | 8.388.608 | 5.965.866 | 871.830 | 5.094.036 | 0.711187 | 0.103930 | 0.607256 | 1.997227 | 1.905727 | 2.013775 |
24 | 16.777.216 | 11.917.873 | 1.665.247 | 10.252.626 | 0.710361 | 0.099256 | 0.611104 | 1.997677 | 1.910059 | 2.012672 |
25 | 33.554.432 | 23.811.126 | 3.188.255 | 20.622.871 | 0.709627 | 0.095017 | 0.614609 | 1.997934 | 1.914584 | 2.011472 |
26 | 67.108.864 | 47.573.226 | 6.118.950 | 41.454.276 | 0.708896 | 0.091179 | 0.617717 | 1.997941 | 1.919216 | 2.010112 |
27 | 134.217.728 | 95.059.383 | 11.755.928 | 83.303.455 | 0.708248 | 0.087588 | 0.620659 | 1.998170 | 1.921233 | 2.009526 |
28 | 268.435.456 | 189.964.974 | 22.616.382 | 167.348.592 | 0.707675 | 0.084253 | 0.623422 | 1.998382 | 1.923828 | 2.008903 |
29 | 536.870.912 | 379.637.393 | 43.580.543 | 336.056.850 | 0.707130 | 0.081175 | 0.625955 | 1.998460 | 1.926946 | 2.008125 |
30 | 1.073.741.824 | 758.716.717 | 84.103.392 | 674.613.325 | 0.706610 | 0.078327 | 0.628283 | 1.998530 | 1.929838 | 2.007438 |
31 | 2.147.483.648 | 1.516.414.553 | 162.493.497 | 1.353.921.056 | 0.706136 | 0.075667 | 0.630469 | 1.998657 | 1.932068 | 2.006959 |
32 | 4.294.967.296 | 3.030.923.392 | 314.285.879 | 2.716.637.513 | 0.705692 | 0.073175 | 0.632516 | 1.998743 | 1.934144 | 2.006496 |
33 | 8.589.934.592 | 6.058.303.114 | 608.553.969 | 5.449.749.145 | 0.705279 | 0.070845 | 0.634434 | 1.998831 | 1.936307 | 2.006064 |
34 | 17.179.869.184 | 12.110.001.087 | 1.179.526.697 | 10.930.474.390 | 0.704895 | 0.068657 | 0.636237 | 1.998910 | 1.938245 | 2.005684 |
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 | 1 | 1 | 1 | 0 |
2 | 4 | 4 | 3 | 1 | 1 | 1 | 1 | 1 |
3 | 8 | 8 | 4 | 4 | 1 | 2 | 3 | 2 |
4 | 16 | 13 | 5 | 8 | 3 | 3 | 3 | 4 |
5 | 32 | 19 | 7 | 12 | 4 | 5 | 3 | 7 |
6 | 64 | 32 | 12 | 20 | 6 | 9 | 8 | 9 |
7 | 128 | 53 | 17 | 36 | 12 | 14 | 14 | 13 |
8 | 256 | 91 | 31 | 60 | 24 | 24 | 21 | 22 |
9 | 512 | 154 | 51 | 103 | 39 | 41 | 37 | 37 |
10 | 1.024 | 273 | 89 | 184 | 68 | 70 | 63 | 72 |
11 | 2.048 | 500 | 163 | 337 | 123 | 130 | 122 | 125 |
12 | 4.096 | 895 | 309 | 586 | 222 | 235 | 218 | 220 |
13 | 8.192 | 1.633 | 562 | 1.071 | 398 | 409 | 413 | 413 |
14 | 16.384 | 2.939 | 983 | 1.956 | 708 | 730 | 778 | 723 |
15 | 32.768 | 5.464 | 1.852 | 3.612 | 1.342 | 1.379 | 1.424 | 1.319 |
16 | 65.536 | 10.184 | 3.419 | 6.765 | 2.491 | 2.587 | 2.621 | 2.485 |
17 | 131.072 | 18.961 | 6.349 | 12.612 | 4.660 | 4.768 | 4.768 | 4.765 |
18 | 262.144 | 35.691 | 11.940 | 23.751 | 8.772 | 8.955 | 9.029 | 8.935 |
19 | 524.288 | 67.177 | 22.450 | 44.727 | 16.684 | 16.842 | 16.852 | 16.799 |
20 | 1.048.576 | 126.903 | 42.375 | 84.528 | 31.616 | 31.695 | 31.771 | 31.821 |
21 | 2.097.152 | 240.337 | 80.216 | 160.121 | 59.983 | 60.134 | 59.998 | 60.222 |
22 | 4.194.304 | 457.479 | 152.645 | 304.834 | 114.420 | 114.440 | 114.158 | 114.461 |
23 | 8.388.608 | 871.830 | 290.545 | 581.285 | 218.176 | 218.007 | 217.584 | 218.063 |
24 | 16.777.216 | 1.665.247 | 554.920 | 1.110.327 | 416.274 | 415.973 | 416.405 | 416.595 |
25 | 33.554.432 | 3.188.255 | 1.062.241 | 2.126.014 | 797.170 | 796.616 | 797.169 | 797.300 |
26 | 67.108.864 | 6.118.950 | 2.038.285 | 4.080.665 | 1.530.529 | 1.529.060 | 1.529.160 | 1.530.201 |
27 | 134.217.728 | 11.755.928 | 3.917.237 | 7.838.691 | 2.939.101 | 2.937.809 | 2.938.760 | 2.940.258 |
28 | 268.435.456 | 22.616.382 | 7.538.155 | 15.078.227 | 5.652.449 | 5.653.495 | 5.654.003 | 5.656.435 |
29 | 536.870.912 | 43.580.543 | 14.523.898 | 29.056.645 | 10.893.543 | 10.892.293 | 10.896.778 | 10.897.929 |
30 | 1.073.741.824 | 84.103.392 | 28.028.833 | 56.074.559 | 21.025.210 | 21.024.089 | 21.026.705 | 21.027.388 |
31 | 2.147.483.648 | 162.493.497 | 54.154.860 | 108.338.637 | 40.621.400 | 40.622.172 | 40.626.379 | 40.623.546 |
32 | 4.294.967.296 | 314.285.879 | 104.750.353 | 209.535.526 | 78.561.710 | 78.575.915 | 78.576.464 | 78.571.790 |
33 | 8.589.934.592 | 608.553.969 | 202.847.653 | 405.706.316 | 152.132.374 | 152.139.811 | 152.148.786 | 152.132.998 |
34 | 17.179.869.184 | 1.179.526.697 | 393.177.331 | 786.349.366 | 294.876.945 | 294.871.407 | 294.889.610 | 294.888.735 |
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 | 5 | 3 | 2 | 1 | 3 | 1 | 0 |
6 | 64 | 14 | 5 | 9 | 2 | 6 | 4 | 2 |
7 | 128 | 41 | 22 | 19 | 11 | 12 | 11 | 7 |
8 | 256 | 97 | 48 | 49 | 22 | 30 | 25 | 20 |
9 | 512 | 221 | 101 | 120 | 46 | 57 | 60 | 58 |
10 | 1.024 | 477 | 229 | 248 | 109 | 121 | 124 | 123 |
11 | 2.048 | 997 | 490 | 507 | 241 | 252 | 255 | 249 |
12 | 4.096 | 2.082 | 1.014 | 1.068 | 500 | 538 | 534 | 510 |
13 | 8.192 | 4.320 | 2.137 | 2.183 | 1.057 | 1.103 | 1.096 | 1.064 |
14 | 16.384 | 8.927 | 4.452 | 4.475 | 2.177 | 2.230 | 2.291 | 2.229 |
15 | 32.768 | 18.197 | 9.081 | 9.116 | 4.479 | 4.551 | 4.599 | 4.568 |
16 | 65.536 | 36.983 | 18.452 | 18.531 | 9.157 | 9.238 | 9.289 | 9.299 |
17 | 131.072 | 75.174 | 37.512 | 37.662 | 18.709 | 18.781 | 18.873 | 18.811 |
18 | 262.144 | 152.216 | 76.091 | 76.125 | 37.982 | 38.194 | 37.960 | 38.080 |
19 | 524.288 | 307.995 | 153.814 | 154.181 | 76.890 | 76.996 | 77.137 | 76.972 |
20 | 1.048.576 | 622.109 | 310.252 | 311.857 | 155.210 | 155.674 | 155.679 | 155.546 |
21 | 2.097.152 | 1.255.462 | 626.835 | 628.627 | 313.250 | 313.740 | 314.164 | 314.308 |
22 | 4.194.304 | 2.529.595 | 1.262.660 | 1.266.935 | 631.932 | 632.321 | 632.342 | 633.000 |
23 | 8.388.608 | 5.094.036 | 2.542.733 | 2.551.303 | 1.272.009 | 1.273.936 | 1.273.800 | 1.274.291 |
24 | 16.777.216 | 10.252.626 | 5.118.836 | 5.133.790 | 2.562.202 | 2.563.655 | 2.562.966 | 2.563.803 |
25 | 33.554.432 | 20.622.871 | 10.294.230 | 10.328.641 | 5.155.546 | 5.156.223 | 5.155.251 | 5.155.851 |
26 | 67.108.864 | 41.454.276 | 20.690.465 | 20.763.811 | 10.364.184 | 10.366.077 | 10.359.549 | 10.364.466 |
27 | 134.217.728 | 83.303.455 | 41.588.839 | 41.714.616 | 20.824.414 | 20.826.639 | 20.827.439 | 20.824.963 |
28 | 268.435.456 | 167.348.592 | 83.557.513 | 83.791.079 | 41.835.305 | 41.838.489 | 41.839.845 | 41.834.953 |
29 | 536.870.912 | 336.056.850 | 167.801.716 | 168.255.134 | 84.006.776 | 84.017.512 | 84.019.830 | 84.012.732 |
30 | 1.073.741.824 | 674.613.325 | 336.852.295 | 337.761.030 | 168.660.082 | 168.652.557 | 168.656.033 | 168.644.653 |
31 | 2.147.483.648 | 1.353.921.056 | 676.027.137 | 677.893.919 | 338.469.920 | 338.480.039 | 338.494.021 | 338.477.076 |
32 | 4.294.967.296 | 2.716.637.513 | 1.356.512.021 | 1.360.125.492 | 679.156.984 | 679.154.667 | 679.178.388 | 679.147.474 |
33 | 8.589.934.592 | 5.449.749.145 | 2.721.331.038 | 2.728.418.107 | 1.362.439.298 | 1.362.456.798 | 1.362.427.511 | 1.362.425.538 |
34 | 17.179.869.184 | 10.930.474.390 | 5.458.285.635 | 5.472.188.755 | 2.732.643.603 | 2.732.650.010 | 2.732.599.349 | 2.732.581.428 |