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-41
f(0)=41
f(1)=5
f(2)=37
f(3)=1
f(4)=1
f(5)=1
f(6)=1
f(7)=1
f(8)=23
f(9)=1
f(10)=59
f(11)=1
f(12)=103
f(13)=1
f(14)=31
f(15)=1
f(16)=43
f(17)=1
f(18)=283
f(19)=1
f(20)=359
f(21)=1
f(22)=443
f(23)=61
f(24)=107
f(25)=73
f(26)=127
f(27)=1
f(28)=743
f(29)=1
f(30)=859
f(31)=1
f(32)=983
f(33)=131
f(34)=223
f(35)=1
f(36)=251
f(37)=83
f(38)=1
f(39)=1
f(40)=1559
f(41)=1
f(42)=1723
f(43)=113
f(44)=379
f(45)=1
f(46)=1
f(47)=271
f(48)=1
f(49)=1
f(50)=2459
f(51)=1
f(52)=2663
f(53)=173
f(54)=1
f(55)=373
f(56)=619
f(57)=401
f(58)=3323
f(59)=1
f(60)=3559
f(61)=1
f(62)=3803
f(63)=491
f(64)=811
f(65)=523
f(66)=863
f(67)=139
f(68)=4583
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=661
f(74)=1087
f(75)=349
f(76)=1
f(77)=1
f(78)=6043
f(79)=1
f(80)=6359
f(81)=163
f(82)=1
f(83)=1
f(84)=1
f(85)=449
f(86)=1471
f(87)=941
f(88)=7703
f(89)=197
f(90)=8059
f(91)=1
f(92)=8423
f(93)=269
f(94)=1759
f(95)=1123
f(96)=367
f(97)=1171
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-41 could be written as f(y)= y^2-41 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 > 6
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 | 5 | 5 | 0 | 0.500000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 61 | 44 | 17 | 0.610000 | 0.440000 | 0.610000 | 12.200000 | 8.800000 | inf |
3 | 1.000 | 674 | 316 | 358 | 0.674000 | 0.316000 | 0.674000 | 11.049180 | 7.181818 | 21.058823 |
4 | 10.000 | 6.774 | 2.320 | 4.454 | 0.677400 | 0.232000 | 0.677400 | 10.050446 | 7.341772 | 12.441340 |
5 | 100.000 | 68.362 | 17.501 | 50.861 | 0.683620 | 0.175010 | 0.683620 | 10.091822 | 7.543534 | 11.419174 |
6 | 1.000.000 | 684.747 | 141.198 | 543.549 | 0.684747 | 0.141198 | 0.684747 | 10.016486 | 8.067996 | 10.686951 |
7 | 10.000.000 | 6.859.692 | 1.180.066 | 5.679.626 | 0.685969 | 0.118007 | 0.685969 | 10.017849 | 8.357527 | 10.449152 |
8 | 100.000.000 | 68.668.176 | 10.153.940 | 58.514.236 | 0.686682 | 0.101539 | 0.686682 | 10.010387 | 8.604552 | 10.302481 |
9 | 1.000.000.000 | 687.290.845 | 89.101.802 | 598.189.043 | 0.687291 | 0.089102 | 0.687291 | 10.008869 | 8.775096 | 10.222966 |
10 | 10.000.000.000 | 6.877.986.088 | 794.057.576 | 6.083.928.512 | 0.687799 | 0.079406 | 0.687799 | 10.007389 | 8.911802 | 10.170578 |
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 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 4 | 4 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.333333 | 1.333333 | -nan |
4 | 16 | 8 | 6 | 2 | 0.500000 | 0.375000 | 0.125000 | 2.000000 | 1.500000 | inf |
5 | 32 | 18 | 14 | 4 | 0.562500 | 0.437500 | 0.125000 | 2.250000 | 2.333333 | 2.000000 |
6 | 64 | 38 | 29 | 9 | 0.593750 | 0.453125 | 0.140625 | 2.111111 | 2.071429 | 2.250000 |
7 | 128 | 80 | 52 | 28 | 0.625000 | 0.406250 | 0.218750 | 2.105263 | 1.793103 | 3.111111 |
8 | 256 | 169 | 102 | 67 | 0.660156 | 0.398438 | 0.261719 | 2.112500 | 1.961538 | 2.392857 |
9 | 512 | 338 | 179 | 159 | 0.660156 | 0.349609 | 0.310547 | 2.000000 | 1.754902 | 2.373134 |
10 | 1.024 | 690 | 325 | 365 | 0.673828 | 0.317383 | 0.356445 | 2.041420 | 1.815642 | 2.295598 |
11 | 2.048 | 1.388 | 596 | 792 | 0.677734 | 0.291016 | 0.386719 | 2.011594 | 1.833846 | 2.169863 |
12 | 4.096 | 2.774 | 1.089 | 1.685 | 0.677246 | 0.265869 | 0.411377 | 1.998559 | 1.827181 | 2.127525 |
13 | 8.192 | 5.554 | 1.947 | 3.607 | 0.677979 | 0.237671 | 0.440308 | 2.002163 | 1.787879 | 2.140653 |
14 | 16.384 | 11.151 | 3.563 | 7.588 | 0.680603 | 0.217468 | 0.463135 | 2.007742 | 1.829995 | 2.103687 |
15 | 32.768 | 22.349 | 6.573 | 15.776 | 0.682037 | 0.200592 | 0.481445 | 2.004215 | 1.844794 | 2.079072 |
16 | 65.536 | 44.777 | 12.029 | 32.748 | 0.683243 | 0.183548 | 0.499695 | 2.003535 | 1.830062 | 2.075811 |
17 | 131.072 | 89.619 | 22.315 | 67.304 | 0.683739 | 0.170250 | 0.513489 | 2.001452 | 1.855100 | 2.055209 |
18 | 262.144 | 179.211 | 41.744 | 137.467 | 0.683636 | 0.159241 | 0.524395 | 1.999699 | 1.870670 | 2.042479 |
19 | 524.288 | 358.835 | 78.308 | 280.527 | 0.684423 | 0.149361 | 0.535063 | 2.002305 | 1.875910 | 2.040686 |
20 | 1.048.576 | 717.999 | 147.483 | 570.516 | 0.684737 | 0.140651 | 0.544086 | 2.000917 | 1.883371 | 2.033729 |
21 | 2.097.152 | 1.437.068 | 278.234 | 1.158.834 | 0.685247 | 0.132672 | 0.552575 | 2.001490 | 1.886550 | 2.031203 |
22 | 4.194.304 | 2.875.324 | 527.334 | 2.347.990 | 0.685531 | 0.125726 | 0.559804 | 2.000827 | 1.895290 | 2.026166 |
23 | 8.388.608 | 5.753.878 | 1.002.063 | 4.751.815 | 0.685916 | 0.119455 | 0.566460 | 2.001123 | 1.900244 | 2.023780 |
24 | 16.777.216 | 11.510.776 | 1.910.485 | 9.600.291 | 0.686096 | 0.113874 | 0.572222 | 2.000525 | 1.906552 | 2.020342 |
25 | 33.554.432 | 23.029.061 | 3.648.322 | 19.380.739 | 0.686319 | 0.108728 | 0.577591 | 2.000652 | 1.909631 | 2.018766 |
26 | 67.108.864 | 46.074.709 | 6.982.392 | 39.092.317 | 0.686567 | 0.104046 | 0.582521 | 2.000720 | 1.913864 | 2.017070 |
27 | 134.217.728 | 92.175.093 | 13.389.068 | 78.786.025 | 0.686758 | 0.099756 | 0.587002 | 2.000557 | 1.917547 | 2.015384 |
28 | 268.435.456 | 184.403.806 | 25.713.394 | 158.690.412 | 0.686958 | 0.095790 | 0.591168 | 2.000582 | 1.920477 | 2.014195 |
29 | 536.870.912 | 368.903.028 | 49.470.656 | 319.432.372 | 0.687135 | 0.092146 | 0.594989 | 2.000517 | 1.923926 | 2.012928 |
30 | 1.073.741.824 | 737.992.132 | 95.314.186 | 642.677.946 | 0.687309 | 0.088768 | 0.598540 | 2.000504 | 1.926681 | 2.011937 |
31 | 2.147.483.648 | 1.476.328.953 | 183.887.930 | 1.292.441.023 | 0.687469 | 0.085629 | 0.601840 | 2.000467 | 1.929282 | 2.011024 |
32 | 4.294.967.296 | 2.953.319.523 | 355.227.153 | 2.598.092.370 | 0.687623 | 0.082708 | 0.604915 | 2.000448 | 1.931759 | 2.010221 |
33 | 8.589.934.592 | 5.907.892.383 | 687.015.227 | 5.220.877.156 | 0.687769 | 0.079979 | 0.607790 | 2.000424 | 1.934017 | 2.009504 |
34 | 17.179.869.184 | 11.818.134.176 | 1.330.179.947 | 10.487.954.229 | 0.687906 | 0.077427 | 0.610479 | 2.000398 | 1.936172 | 2.008849 |
35 | 34.359.738.368 | 23.640.795.225 | 2.578.061.115 | 21.062.734.110 | 0.688038 | 0.075031 | 0.613006 | 2.000383 | 1.938130 | 2.008279 |
36 | 68.719.476.736 | 47.290.207.876 | 5.001.405.060 | 42.288.802.816 | 0.688163 | 0.072780 | 0.615383 | 2.000365 | 1.939987 | 2.007755 |
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 | 1 | 0 | 2 | 0 |
2 | 4 | 3 | 1 | 2 | 1 | 0 | 2 | 0 |
3 | 8 | 4 | 1 | 3 | 1 | 0 | 2 | 1 |
4 | 16 | 6 | 2 | 4 | 1 | 1 | 2 | 2 |
5 | 32 | 14 | 6 | 8 | 2 | 4 | 3 | 5 |
6 | 64 | 29 | 10 | 19 | 4 | 11 | 5 | 9 |
7 | 128 | 52 | 22 | 30 | 6 | 20 | 11 | 15 |
8 | 256 | 102 | 47 | 55 | 14 | 39 | 16 | 33 |
9 | 512 | 179 | 77 | 102 | 25 | 64 | 25 | 65 |
10 | 1.024 | 325 | 142 | 183 | 40 | 121 | 42 | 122 |
11 | 2.048 | 596 | 259 | 337 | 74 | 222 | 81 | 219 |
12 | 4.096 | 1.089 | 473 | 616 | 147 | 404 | 145 | 393 |
13 | 8.192 | 1.947 | 866 | 1.081 | 262 | 709 | 260 | 716 |
14 | 16.384 | 3.563 | 1.610 | 1.953 | 484 | 1.287 | 484 | 1.308 |
15 | 32.768 | 6.573 | 2.976 | 3.597 | 889 | 2.394 | 888 | 2.402 |
16 | 65.536 | 12.029 | 5.433 | 6.596 | 1.630 | 4.375 | 1.618 | 4.406 |
17 | 131.072 | 22.315 | 9.961 | 12.354 | 2.972 | 8.121 | 3.018 | 8.204 |
18 | 262.144 | 41.744 | 18.662 | 23.082 | 5.586 | 15.239 | 5.641 | 15.278 |
19 | 524.288 | 78.308 | 35.077 | 43.231 | 10.442 | 28.588 | 10.524 | 28.754 |
20 | 1.048.576 | 147.483 | 66.073 | 81.410 | 19.527 | 54.080 | 19.622 | 54.254 |
21 | 2.097.152 | 278.234 | 124.656 | 153.578 | 36.764 | 102.074 | 36.793 | 102.603 |
22 | 4.194.304 | 527.334 | 236.523 | 290.811 | 69.478 | 193.776 | 69.542 | 194.538 |
23 | 8.388.608 | 1.002.063 | 449.258 | 552.805 | 131.563 | 368.834 | 131.559 | 370.107 |
24 | 16.777.216 | 1.910.485 | 856.189 | 1.054.296 | 250.169 | 704.246 | 250.458 | 705.612 |
25 | 33.554.432 | 3.648.322 | 1.634.315 | 2.014.007 | 476.920 | 1.346.711 | 477.192 | 1.347.499 |
26 | 67.108.864 | 6.982.392 | 3.128.285 | 3.854.107 | 911.193 | 2.578.970 | 911.460 | 2.580.769 |
27 | 134.217.728 | 13.389.068 | 5.998.756 | 7.390.312 | 1.744.978 | 4.950.203 | 1.743.693 | 4.950.194 |
28 | 268.435.456 | 25.713.394 | 11.520.322 | 14.193.072 | 3.344.628 | 9.512.775 | 3.343.116 | 9.512.875 |
29 | 536.870.912 | 49.470.656 | 22.159.482 | 27.311.174 | 6.422.910 | 18.317.193 | 6.420.407 | 18.310.146 |
30 | 1.073.741.824 | 95.314.186 | 42.679.740 | 52.634.446 | 12.353.760 | 35.305.713 | 12.352.473 | 35.302.240 |
31 | 2.147.483.648 | 183.887.930 | 82.319.841 | 101.568.089 | 23.804.862 | 68.145.741 | 23.803.485 | 68.133.842 |
32 | 4.294.967.296 | 355.227.153 | 158.985.690 | 196.241.463 | 45.931.526 | 131.695.704 | 45.928.809 | 131.671.114 |
33 | 8.589.934.592 | 687.015.227 | 307.421.757 | 379.593.470 | 88.726.277 | 254.787.524 | 88.730.242 | 254.771.184 |
34 | 17.179.869.184 | 1.330.179.947 | 595.103.862 | 735.076.085 | 171.615.805 | 493.494.257 | 171.617.165 | 493.452.720 |
35 | 34.359.738.368 | 2.578.061.115 | 1.153.174.361 | 1.424.886.754 | 332.278.283 | 956.745.316 | 332.304.751 | 956.732.765 |
36 | 68.719.476.736 | 5.001.405.060 | 2.236.691.124 | 2.764.713.936 | 644.054.668 | 1.856.637.245 | 644.050.871 | 1.856.662.276 |
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 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
5 | 32 | 4 | 3 | 1 | 0 | 2 | 0 | 2 |
6 | 64 | 9 | 7 | 2 | 0 | 6 | 0 | 3 |
7 | 128 | 28 | 19 | 9 | 3 | 10 | 3 | 12 |
8 | 256 | 67 | 36 | 31 | 10 | 24 | 10 | 23 |
9 | 512 | 159 | 73 | 86 | 30 | 49 | 30 | 50 |
10 | 1.024 | 365 | 187 | 178 | 78 | 112 | 68 | 107 |
11 | 2.048 | 792 | 406 | 386 | 165 | 228 | 174 | 225 |
12 | 4.096 | 1.685 | 872 | 813 | 354 | 485 | 389 | 457 |
13 | 8.192 | 3.607 | 1.828 | 1.779 | 800 | 997 | 811 | 999 |
14 | 16.384 | 7.588 | 3.885 | 3.703 | 1.715 | 2.038 | 1.749 | 2.086 |
15 | 32.768 | 15.776 | 7.996 | 7.780 | 3.651 | 4.237 | 3.692 | 4.196 |
16 | 65.536 | 32.748 | 16.623 | 16.125 | 7.619 | 8.637 | 7.703 | 8.789 |
17 | 131.072 | 67.304 | 34.200 | 33.104 | 15.724 | 17.801 | 15.903 | 17.876 |
18 | 262.144 | 137.467 | 69.722 | 67.745 | 32.439 | 36.211 | 32.482 | 36.335 |
19 | 524.288 | 280.527 | 142.043 | 138.484 | 66.607 | 73.529 | 66.680 | 73.711 |
20 | 1.048.576 | 570.516 | 288.674 | 281.842 | 135.962 | 149.336 | 136.181 | 149.037 |
21 | 2.097.152 | 1.158.834 | 585.456 | 573.378 | 276.776 | 302.447 | 277.711 | 301.900 |
22 | 4.194.304 | 2.347.990 | 1.184.812 | 1.163.178 | 563.100 | 611.243 | 563.109 | 610.538 |
23 | 8.388.608 | 4.751.815 | 2.396.590 | 2.355.225 | 1.141.757 | 1.234.917 | 1.142.999 | 1.232.142 |
24 | 16.777.216 | 9.600.291 | 4.839.437 | 4.760.854 | 2.312.982 | 2.487.748 | 2.313.918 | 2.485.643 |
25 | 33.554.432 | 19.380.739 | 9.767.219 | 9.613.520 | 4.679.814 | 5.010.827 | 4.681.861 | 5.008.237 |
26 | 67.108.864 | 39.092.317 | 19.695.829 | 19.396.488 | 9.454.378 | 10.091.964 | 9.459.003 | 10.086.972 |
27 | 134.217.728 | 78.786.025 | 39.689.715 | 39.096.310 | 19.082.817 | 20.305.511 | 19.091.516 | 20.306.181 |
28 | 268.435.456 | 158.690.412 | 79.917.992 | 78.772.420 | 38.492.227 | 40.846.447 | 38.506.498 | 40.845.240 |
29 | 536.870.912 | 319.432.372 | 160.826.116 | 158.606.256 | 77.587.282 | 82.108.766 | 77.612.109 | 82.124.215 |
30 | 1.073.741.824 | 642.677.946 | 323.481.195 | 319.196.751 | 156.301.546 | 165.018.035 | 156.320.851 | 165.037.514 |
31 | 2.147.483.648 | 1.292.441.023 | 650.351.176 | 642.089.847 | 314.672.171 | 331.529.258 | 314.695.763 | 331.543.831 |
32 | 4.294.967.296 | 2.598.092.370 | 1.307.043.965 | 1.291.048.405 | 633.230.026 | 665.796.447 | 633.249.712 | 665.816.185 |
33 | 8.589.934.592 | 5.220.877.156 | 2.625.893.193 | 2.594.983.963 | 1.273.657.584 | 1.336.751.761 | 1.273.678.703 | 1.336.789.108 |
34 | 17.179.869.184 | 10.487.954.229 | 5.273.856.591 | 5.214.097.638 | 2.560.836.019 | 2.683.145.996 | 2.560.850.108 | 2.683.122.106 |
35 | 34.359.738.368 | 21.062.734.110 | 10.589.307.634 | 10.473.426.476 | 5.147.029.626 | 5.384.359.632 | 5.146.961.504 | 5.384.383.348 |
36 | 68.719.476.736 | 42.288.802.816 | 21.256.877.985 | 21.031.924.831 | 10.341.694.390 | 10.802.754.866 | 10.341.609.721 | 10.802.743.839 |