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-212x+107
f(0)=107
f(1)=13
f(2)=313
f(3)=5
f(4)=29
f(5)=1
f(6)=1129
f(7)=83
f(8)=61
f(9)=43
f(10)=1913
f(11)=263
f(12)=2293
f(13)=31
f(14)=41
f(15)=89
f(16)=233
f(17)=401
f(18)=677
f(19)=1
f(20)=3733
f(21)=1
f(22)=4073
f(23)=53
f(24)=881
f(25)=571
f(26)=4729
f(27)=47
f(28)=1009
f(29)=1
f(30)=101
f(31)=1
f(32)=5653
f(33)=1
f(34)=1
f(35)=761
f(36)=6229
f(37)=199
f(38)=1301
f(39)=1
f(40)=521
f(41)=863
f(42)=541
f(43)=179
f(44)=1
f(45)=463
f(46)=7529
f(47)=239
f(48)=1553
f(49)=197
f(50)=7993
f(51)=1013
f(52)=191
f(53)=1
f(54)=337
f(55)=1
f(56)=8629
f(57)=1091
f(58)=353
f(59)=223
f(60)=9013
f(61)=569
f(62)=317
f(63)=1
f(64)=1873
f(65)=1181
f(66)=733
f(67)=1201
f(68)=149
f(69)=1
f(70)=9833
f(71)=619
f(72)=9973
f(73)=251
f(74)=1
f(75)=1
f(76)=193
f(77)=643
f(78)=2069
f(79)=1
f(80)=10453
f(81)=1
f(82)=173
f(83)=1
f(84)=2129
f(85)=167
f(86)=10729
f(87)=673
f(88)=2161
f(89)=271
f(90)=131
f(91)=1
f(92)=1
f(93)=137
f(94)=1
f(95)=1
f(96)=269
f(97)=1381
f(98)=2213
f(99)=277
b) Substitution of the polynom
The polynom f(x)=x^2-212x+107 could be written as f(y)= y^2-11129 with x=y+106
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-106
f'(x)>2x-213 with x > 105
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 | 4 | 5 | 0.900000 | 0.400000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 74 | 19 | 55 | 0.740000 | 0.190000 | 0.740000 | 8.222222 | 4.750000 | 11.000000 |
3 | 1.000 | 510 | 118 | 392 | 0.510000 | 0.118000 | 0.510000 | 6.891892 | 6.210526 | 7.127273 |
4 | 10.000 | 6.275 | 868 | 5.407 | 0.627500 | 0.086800 | 0.627500 | 12.303922 | 7.355932 | 13.793367 |
5 | 100.000 | 65.181 | 6.835 | 58.346 | 0.651810 | 0.068350 | 0.651810 | 10.387410 | 7.874424 | 10.790827 |
6 | 1.000.000 | 661.244 | 55.651 | 605.593 | 0.661244 | 0.055651 | 0.661244 | 10.144735 | 8.142063 | 10.379340 |
7 | 10.000.000 | 6.659.697 | 470.562 | 6.189.135 | 0.665970 | 0.047056 | 0.665970 | 10.071466 | 8.455589 | 10.219958 |
8 | 100.000.000 | 66.949.442 | 4.075.062 | 62.874.380 | 0.669494 | 0.040751 | 0.669494 | 10.052926 | 8.659989 | 10.158832 |
9 | 1.000.000.000 | 672.174.325 | 35.965.596 | 636.208.729 | 0.672174 | 0.035966 | 0.672174 | 10.040030 | 8.825779 | 10.118728 |
10 | 10.000.000.000 | 6.743.126.566 | 321.825.525 | 6.421.301.041 | 0.674313 | 0.032183 | 0.674313 | 10.031812 | 8.948150 | 10.093074 |
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 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
4 | 16 | 15 | 5 | 10 | 0.937500 | 0.312500 | 0.625000 | 2.142857 | 1.666667 | 2.500000 |
5 | 32 | 26 | 9 | 17 | 0.812500 | 0.281250 | 0.531250 | 1.733333 | 1.800000 | 1.700000 |
6 | 64 | 51 | 14 | 37 | 0.796875 | 0.218750 | 0.578125 | 1.961538 | 1.555556 | 2.176471 |
7 | 128 | 77 | 20 | 57 | 0.601562 | 0.156250 | 0.445312 | 1.509804 | 1.428571 | 1.540541 |
8 | 256 | 89 | 24 | 65 | 0.347656 | 0.093750 | 0.253906 | 1.155844 | 1.200000 | 1.140351 |
9 | 512 | 223 | 56 | 167 | 0.435547 | 0.109375 | 0.326172 | 2.505618 | 2.333333 | 2.569231 |
10 | 1.024 | 528 | 123 | 405 | 0.515625 | 0.120117 | 0.395508 | 2.367713 | 2.196429 | 2.425150 |
11 | 2.048 | 1.161 | 217 | 944 | 0.566895 | 0.105957 | 0.460938 | 2.198864 | 1.764228 | 2.330864 |
12 | 4.096 | 2.467 | 389 | 2.078 | 0.602295 | 0.094971 | 0.507324 | 2.124892 | 1.792627 | 2.201271 |
13 | 8.192 | 5.105 | 732 | 4.373 | 0.623169 | 0.089355 | 0.533813 | 2.069315 | 1.881748 | 2.104427 |
14 | 16.384 | 10.380 | 1.343 | 9.037 | 0.633545 | 0.081970 | 0.551575 | 2.033301 | 1.834700 | 2.066545 |
15 | 32.768 | 21.049 | 2.492 | 18.557 | 0.642365 | 0.076050 | 0.566315 | 2.027842 | 1.855547 | 2.053447 |
16 | 65.536 | 42.593 | 4.689 | 37.904 | 0.649918 | 0.071548 | 0.578369 | 2.023517 | 1.881621 | 2.042572 |
17 | 131.072 | 85.680 | 8.719 | 76.961 | 0.653687 | 0.066521 | 0.587166 | 2.011598 | 1.859458 | 2.030419 |
18 | 262.144 | 172.209 | 16.291 | 155.918 | 0.656925 | 0.062145 | 0.594780 | 2.009909 | 1.868448 | 2.025935 |
19 | 524.288 | 345.681 | 30.674 | 315.007 | 0.659334 | 0.058506 | 0.600828 | 2.007334 | 1.882880 | 2.020338 |
20 | 1.048.576 | 693.395 | 58.142 | 635.253 | 0.661273 | 0.055449 | 0.605824 | 2.005881 | 1.895481 | 2.016631 |
21 | 2.097.152 | 1.390.350 | 110.422 | 1.279.928 | 0.662971 | 0.052653 | 0.610317 | 2.005134 | 1.899178 | 2.014832 |
22 | 4.194.304 | 2.786.759 | 209.671 | 2.577.088 | 0.664415 | 0.049989 | 0.614426 | 2.004358 | 1.898816 | 2.013463 |
23 | 8.388.608 | 5.584.213 | 399.575 | 5.184.638 | 0.665690 | 0.047633 | 0.618057 | 2.003838 | 1.905724 | 2.011820 |
24 | 16.777.216 | 11.188.278 | 762.619 | 10.425.659 | 0.666873 | 0.045456 | 0.621418 | 2.003555 | 1.908575 | 2.010875 |
25 | 33.554.432 | 22.412.622 | 1.459.741 | 20.952.881 | 0.667948 | 0.043504 | 0.624444 | 2.003224 | 1.914116 | 2.009742 |
26 | 67.108.864 | 44.893.209 | 2.799.415 | 42.093.794 | 0.668961 | 0.041715 | 0.627246 | 2.003032 | 1.917748 | 2.008974 |
27 | 134.217.728 | 89.909.529 | 5.377.315 | 84.532.214 | 0.669878 | 0.040064 | 0.629814 | 2.002742 | 1.920871 | 2.008187 |
28 | 268.435.456 | 180.045.638 | 10.352.208 | 169.693.430 | 0.670722 | 0.038565 | 0.632157 | 2.002520 | 1.925163 | 2.007441 |
29 | 536.870.912 | 360.515.433 | 19.946.333 | 340.569.100 | 0.671512 | 0.037153 | 0.634359 | 2.002356 | 1.926771 | 2.006967 |
30 | 1.073.741.824 | 721.822.569 | 38.478.576 | 683.343.993 | 0.672250 | 0.035836 | 0.636414 | 2.002196 | 1.929105 | 2.006477 |
31 | 2.147.483.648 | 1.445.122.905 | 74.334.358 | 1.370.788.547 | 0.672938 | 0.034615 | 0.638323 | 2.002047 | 1.931838 | 2.006001 |
32 | 4.294.967.296 | 2.893.022.455 | 143.779.303 | 2.749.243.152 | 0.673584 | 0.033476 | 0.640108 | 2.001921 | 1.934224 | 2.005592 |
33 | 8.589.934.592 | 5.791.212.165 | 278.379.917 | 5.512.832.248 | 0.674186 | 0.032408 | 0.641778 | 2.001786 | 1.936161 | 2.005218 |
34 | 17.179.869.184 | 11.592.162.701 | 539.549.921 | 11.052.612.780 | 0.674753 | 0.031406 | 0.643347 | 2.001682 | 1.938179 | 2.004888 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 3 | 2 | 1 | 2 | 1 | 0 | 0 |
4 | 16 | 5 | 3 | 2 | 3 | 1 | 1 | 0 |
5 | 32 | 9 | 6 | 3 | 5 | 1 | 3 | 0 |
6 | 64 | 14 | 10 | 4 | 7 | 1 | 6 | 0 |
7 | 128 | 20 | 14 | 6 | 10 | 1 | 9 | 0 |
8 | 256 | 24 | 16 | 8 | 10 | 4 | 9 | 1 |
9 | 512 | 56 | 28 | 28 | 10 | 20 | 9 | 17 |
10 | 1.024 | 123 | 51 | 72 | 10 | 53 | 9 | 51 |
11 | 2.048 | 217 | 79 | 138 | 10 | 99 | 9 | 99 |
12 | 4.096 | 389 | 136 | 253 | 10 | 184 | 9 | 186 |
13 | 8.192 | 732 | 250 | 482 | 10 | 361 | 9 | 352 |
14 | 16.384 | 1.343 | 448 | 895 | 10 | 666 | 9 | 658 |
15 | 32.768 | 2.492 | 809 | 1.683 | 10 | 1.233 | 9 | 1.240 |
16 | 65.536 | 4.689 | 1.552 | 3.137 | 10 | 2.294 | 9 | 2.376 |
17 | 131.072 | 8.719 | 2.920 | 5.799 | 10 | 4.319 | 9 | 4.381 |
18 | 262.144 | 16.291 | 5.414 | 10.877 | 10 | 8.111 | 9 | 8.161 |
19 | 524.288 | 30.674 | 10.149 | 20.525 | 10 | 15.273 | 9 | 15.382 |
20 | 1.048.576 | 58.142 | 19.294 | 38.848 | 10 | 28.998 | 9 | 29.125 |
21 | 2.097.152 | 110.422 | 36.807 | 73.615 | 10 | 55.104 | 9 | 55.299 |
22 | 4.194.304 | 209.671 | 70.059 | 139.612 | 10 | 104.494 | 9 | 105.158 |
23 | 8.388.608 | 399.575 | 133.405 | 266.170 | 10 | 199.396 | 9 | 200.160 |
24 | 16.777.216 | 762.619 | 254.237 | 508.382 | 10 | 380.724 | 9 | 381.876 |
25 | 33.554.432 | 1.459.741 | 486.784 | 972.957 | 10 | 729.128 | 9 | 730.594 |
26 | 67.108.864 | 2.799.415 | 932.573 | 1.866.842 | 10 | 1.398.392 | 9 | 1.401.004 |
27 | 134.217.728 | 5.377.315 | 1.791.272 | 3.586.043 | 10 | 2.687.294 | 9 | 2.690.002 |
28 | 268.435.456 | 10.352.208 | 3.448.615 | 6.903.593 | 10 | 5.174.995 | 9 | 5.177.194 |
29 | 536.870.912 | 19.946.333 | 6.646.376 | 13.299.957 | 10 | 9.971.816 | 9 | 9.974.498 |
30 | 1.073.741.824 | 38.478.576 | 12.824.850 | 25.653.726 | 10 | 19.237.377 | 9 | 19.241.180 |
31 | 2.147.483.648 | 74.334.358 | 24.775.161 | 49.559.197 | 10 | 37.163.594 | 9 | 37.170.745 |
32 | 4.294.967.296 | 143.779.303 | 47.925.512 | 95.853.791 | 10 | 71.882.350 | 9 | 71.896.934 |
33 | 8.589.934.592 | 278.379.917 | 92.798.082 | 185.581.835 | 10 | 139.180.736 | 9 | 139.199.162 |
34 | 17.179.869.184 | 539.549.921 | 179.847.427 | 359.702.494 | 10 | 269.777.127 | 9 | 269.772.775 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 3 | 0 |
4 | 16 | 10 | 3 | 7 | 3 | 3 | 3 | 1 |
5 | 32 | 17 | 5 | 12 | 6 | 4 | 6 | 1 |
6 | 64 | 37 | 11 | 26 | 13 | 6 | 11 | 7 |
7 | 128 | 57 | 21 | 36 | 18 | 10 | 20 | 9 |
8 | 256 | 65 | 26 | 39 | 18 | 14 | 21 | 12 |
9 | 512 | 167 | 82 | 85 | 34 | 45 | 45 | 43 |
10 | 1.024 | 405 | 204 | 201 | 79 | 117 | 80 | 129 |
11 | 2.048 | 944 | 478 | 466 | 201 | 274 | 187 | 282 |
12 | 4.096 | 2.078 | 1.066 | 1.012 | 428 | 618 | 403 | 629 |
13 | 8.192 | 4.373 | 2.251 | 2.122 | 924 | 1.285 | 893 | 1.271 |
14 | 16.384 | 9.037 | 4.667 | 4.370 | 1.908 | 2.605 | 1.892 | 2.632 |
15 | 32.768 | 18.557 | 9.510 | 9.047 | 3.944 | 5.337 | 3.955 | 5.321 |
16 | 65.536 | 37.904 | 19.370 | 18.534 | 8.163 | 10.726 | 8.237 | 10.778 |
17 | 131.072 | 76.961 | 39.466 | 37.495 | 16.769 | 21.588 | 16.941 | 21.663 |
18 | 262.144 | 155.918 | 79.785 | 76.133 | 34.502 | 43.380 | 34.541 | 43.495 |
19 | 524.288 | 315.007 | 161.131 | 153.876 | 70.451 | 87.009 | 70.622 | 86.925 |
20 | 1.048.576 | 635.253 | 324.932 | 310.321 | 143.074 | 174.568 | 143.495 | 174.116 |
21 | 2.097.152 | 1.279.928 | 652.958 | 626.970 | 290.811 | 349.467 | 290.984 | 348.666 |
22 | 4.194.304 | 2.577.088 | 1.313.848 | 1.263.240 | 589.445 | 700.087 | 589.447 | 698.109 |
23 | 8.388.608 | 5.184.638 | 2.639.149 | 2.545.489 | 1.191.934 | 1.401.204 | 1.192.652 | 1.398.848 |
24 | 16.777.216 | 10.425.659 | 5.300.744 | 5.124.915 | 2.408.079 | 2.805.754 | 2.408.537 | 2.803.289 |
25 | 33.554.432 | 20.952.881 | 10.645.435 | 10.307.446 | 4.856.994 | 5.616.817 | 4.862.454 | 5.616.616 |
26 | 67.108.864 | 42.093.794 | 21.369.353 | 20.724.441 | 9.797.106 | 11.245.709 | 9.806.244 | 11.244.735 |
27 | 134.217.728 | 84.532.214 | 42.885.392 | 41.646.822 | 19.750.965 | 22.515.263 | 19.753.529 | 22.512.457 |
28 | 268.435.456 | 169.693.430 | 86.032.374 | 83.661.056 | 39.771.498 | 45.078.277 | 39.771.876 | 45.071.779 |
29 | 536.870.912 | 340.569.100 | 172.575.975 | 167.993.125 | 80.035.362 | 90.247.089 | 80.046.691 | 90.239.958 |
30 | 1.073.741.824 | 683.343.993 | 346.093.630 | 337.250.363 | 161.008.723 | 180.654.683 | 161.018.399 | 180.662.188 |
31 | 2.147.483.648 | 1.370.788.547 | 693.952.230 | 676.836.317 | 323.758.984 | 361.654.300 | 323.751.221 | 361.624.042 |
32 | 4.294.967.296 | 2.749.243.152 | 1.391.134.194 | 1.358.108.958 | 650.725.062 | 723.904.156 | 650.724.469 | 723.889.465 |
33 | 8.589.934.592 | 5.512.832.248 | 2.788.273.823 | 2.724.558.425 | 1.307.495.153 | 1.448.912.706 | 1.307.535.901 | 1.448.888.488 |
34 | 17.179.869.184 | 11.052.612.780 | 5.587.986.965 | 5.464.625.815 | 2.626.283.429 | 2.900.001.381 | 2.626.354.960 | 2.899.973.010 |