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+23x-181
f(0)=181
f(1)=157
f(2)=131
f(3)=103
f(4)=73
f(5)=41
f(6)=7
f(7)=29
f(8)=67
f(9)=107
f(10)=149
f(11)=193
f(12)=239
f(13)=1
f(14)=337
f(15)=389
f(16)=443
f(17)=499
f(18)=557
f(19)=617
f(20)=97
f(21)=743
f(22)=809
f(23)=877
f(24)=947
f(25)=1019
f(26)=1093
f(27)=167
f(28)=43
f(29)=1327
f(30)=1409
f(31)=1493
f(32)=1579
f(33)=1667
f(34)=251
f(35)=1
f(36)=1
f(37)=2039
f(38)=2137
f(39)=2237
f(40)=2339
f(41)=349
f(42)=2549
f(43)=2657
f(44)=2767
f(45)=2879
f(46)=1
f(47)=3109
f(48)=461
f(49)=3347
f(50)=3469
f(51)=3593
f(52)=3719
f(53)=3847
f(54)=1
f(55)=587
f(56)=4243
f(57)=151
f(58)=4517
f(59)=4657
f(60)=4799
f(61)=4943
f(62)=727
f(63)=5237
f(64)=5387
f(65)=191
f(66)=5693
f(67)=5849
f(68)=6007
f(69)=881
f(70)=6329
f(71)=1
f(72)=6659
f(73)=6827
f(74)=6997
f(75)=1
f(76)=1049
f(77)=1
f(78)=179
f(79)=7877
f(80)=8059
f(81)=8243
f(82)=8429
f(83)=1231
f(84)=8807
f(85)=8999
f(86)=317
f(87)=229
f(88)=9587
f(89)=9787
f(90)=1427
f(91)=10193
f(92)=10399
f(93)=10607
f(94)=373
f(95)=269
f(96)=11243
f(97)=1637
f(98)=11677
f(99)=11897
b) Substitution of the polynom
The polynom f(x)=x^2+23x-181 could be written as f(y)= y^2-313.25 with x=y-11.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+11.5
f'(x)>2x+22
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 | 92 | 74 | 18 | 0.920000 | 0.740000 | 0.920000 | 8.363636 | 6.727273 | inf |
3 | 1.000 | 844 | 475 | 369 | 0.844000 | 0.475000 | 0.844000 | 9.173913 | 6.418919 | 20.500000 |
4 | 10.000 | 8.101 | 3.411 | 4.690 | 0.810100 | 0.341100 | 0.810100 | 9.598341 | 7.181053 | 12.710027 |
5 | 100.000 | 78.431 | 26.365 | 52.066 | 0.784310 | 0.263650 | 0.784310 | 9.681644 | 7.729405 | 11.101493 |
6 | 1.000.000 | 767.971 | 215.195 | 552.776 | 0.767971 | 0.215195 | 0.767971 | 9.791677 | 8.162147 | 10.616833 |
7 | 10.000.000 | 7.569.121 | 1.815.758 | 5.753.363 | 0.756912 | 0.181576 | 0.756912 | 9.855998 | 8.437734 | 10.408128 |
8 | 100.000.000 | 74.856.170 | 15.754.773 | 59.101.397 | 0.748562 | 0.157548 | 0.748562 | 9.889678 | 8.676692 | 10.272495 |
9 | 1.000.000.000 | 742.221.694 | 139.011.762 | 603.209.932 | 0.742222 | 0.139012 | 0.742222 | 9.915304 | 8.823469 | 10.206357 |
10 | 10.000.000.000 | 7.371.798.955 | 1.244.065.311 | 6.127.733.644 | 0.737180 | 0.124407 | 0.737180 | 9.932072 | 8.949353 | 10.158543 |
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 | 29 | 2 | 0.968750 | 0.906250 | 0.062500 | 1.937500 | 1.812500 | inf |
6 | 64 | 59 | 51 | 8 | 0.921875 | 0.796875 | 0.125000 | 1.903226 | 1.758621 | 4.000000 |
7 | 128 | 115 | 88 | 27 | 0.898438 | 0.687500 | 0.210938 | 1.949153 | 1.725490 | 3.375000 |
8 | 256 | 222 | 162 | 60 | 0.867188 | 0.632812 | 0.234375 | 1.930435 | 1.840909 | 2.222222 |
9 | 512 | 436 | 274 | 162 | 0.851562 | 0.535156 | 0.316406 | 1.963964 | 1.691358 | 2.700000 |
10 | 1.024 | 866 | 483 | 383 | 0.845703 | 0.471680 | 0.374023 | 1.986238 | 1.762774 | 2.364197 |
11 | 2.048 | 1.710 | 863 | 847 | 0.834961 | 0.421387 | 0.413574 | 1.974596 | 1.786749 | 2.211488 |
12 | 4.096 | 3.364 | 1.586 | 1.778 | 0.821289 | 0.387207 | 0.434082 | 1.967251 | 1.837775 | 2.099174 |
13 | 8.192 | 6.662 | 2.877 | 3.785 | 0.813232 | 0.351196 | 0.462036 | 1.980381 | 1.813998 | 2.128796 |
14 | 16.384 | 13.140 | 5.269 | 7.871 | 0.802002 | 0.321594 | 0.480408 | 1.972381 | 1.831422 | 2.079525 |
15 | 32.768 | 26.063 | 9.679 | 16.384 | 0.795380 | 0.295380 | 0.500000 | 1.983486 | 1.836971 | 2.081565 |
16 | 65.536 | 51.691 | 17.928 | 33.763 | 0.788742 | 0.273560 | 0.515182 | 1.983310 | 1.852257 | 2.060730 |
17 | 131.072 | 102.410 | 33.793 | 68.617 | 0.781326 | 0.257820 | 0.523506 | 1.981196 | 1.884929 | 2.032314 |
18 | 262.144 | 203.656 | 63.071 | 140.585 | 0.776886 | 0.240597 | 0.536289 | 1.988634 | 1.866392 | 2.048836 |
19 | 524.288 | 404.588 | 118.877 | 285.711 | 0.771690 | 0.226740 | 0.544950 | 1.986624 | 1.884812 | 2.032301 |
20 | 1.048.576 | 805.009 | 224.795 | 580.214 | 0.767716 | 0.214381 | 0.553335 | 1.989701 | 1.890988 | 2.030772 |
21 | 2.097.152 | 1.602.195 | 425.391 | 1.176.804 | 0.763986 | 0.202842 | 0.561144 | 1.990282 | 1.892351 | 2.028224 |
22 | 4.194.304 | 3.190.784 | 808.740 | 2.382.044 | 0.760742 | 0.192819 | 0.567924 | 1.991508 | 1.901169 | 2.024164 |
23 | 8.388.608 | 6.355.596 | 1.541.676 | 4.813.920 | 0.757646 | 0.183782 | 0.573864 | 1.991860 | 1.906269 | 2.020920 |
24 | 16.777.216 | 12.663.289 | 2.946.463 | 9.716.826 | 0.754791 | 0.175623 | 0.579168 | 1.992463 | 1.911208 | 2.018485 |
25 | 33.554.432 | 25.239.267 | 5.643.478 | 19.595.789 | 0.752189 | 0.168189 | 0.584000 | 1.993105 | 1.915340 | 2.016686 |
26 | 67.108.864 | 50.319.466 | 10.824.818 | 39.494.648 | 0.749818 | 0.161302 | 0.588516 | 1.993697 | 1.918111 | 2.015466 |
27 | 134.217.728 | 100.348.135 | 20.793.338 | 79.554.797 | 0.747652 | 0.154922 | 0.592729 | 1.994221 | 1.920895 | 2.014318 |
28 | 268.435.456 | 200.161.887 | 40.005.512 | 160.156.375 | 0.745661 | 0.149032 | 0.596629 | 1.994675 | 1.923958 | 2.013158 |
29 | 536.870.912 | 399.319.845 | 77.079.934 | 322.239.911 | 0.743791 | 0.143573 | 0.600219 | 1.994984 | 1.926733 | 2.012033 |
30 | 1.073.741.824 | 796.772.665 | 148.720.709 | 648.051.956 | 0.742052 | 0.138507 | 0.603545 | 1.995324 | 1.929435 | 2.011086 |
31 | 2.147.483.648 | 1.590.062.080 | 287.315.008 | 1.302.747.072 | 0.740430 | 0.133791 | 0.606639 | 1.995628 | 1.931910 | 2.010251 |
32 | 4.294.967.296 | 3.173.580.831 | 555.734.472 | 2.617.846.359 | 0.738907 | 0.129392 | 0.609515 | 1.995885 | 1.934234 | 2.009481 |
33 | 8.589.934.592 | 6.334.916.791 | 1.076.100.111 | 5.258.816.680 | 0.737481 | 0.125275 | 0.612207 | 1.996142 | 1.936357 | 2.008833 |
34 | 17.179.869.184 | 12.646.810.383 | 2.085.746.261 | 10.561.064.122 | 0.736141 | 0.121406 | 0.614735 | 1.996366 | 1.938246 | 2.008259 |
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 | 2 | 0 |
2 | 4 | 5 | 4 | 1 | 1 | 1 | 2 | 1 |
3 | 8 | 9 | 6 | 3 | 2 | 2 | 3 | 2 |
4 | 16 | 16 | 8 | 8 | 4 | 4 | 5 | 3 |
5 | 32 | 29 | 13 | 16 | 7 | 8 | 9 | 5 |
6 | 64 | 51 | 20 | 31 | 11 | 13 | 15 | 12 |
7 | 128 | 88 | 31 | 57 | 20 | 24 | 22 | 22 |
8 | 256 | 162 | 55 | 107 | 39 | 42 | 40 | 41 |
9 | 512 | 274 | 91 | 183 | 67 | 71 | 72 | 64 |
10 | 1.024 | 483 | 155 | 328 | 125 | 118 | 124 | 116 |
11 | 2.048 | 863 | 283 | 580 | 215 | 225 | 218 | 205 |
12 | 4.096 | 1.586 | 526 | 1.060 | 394 | 412 | 392 | 388 |
13 | 8.192 | 2.877 | 969 | 1.908 | 716 | 739 | 730 | 692 |
14 | 16.384 | 5.269 | 1.746 | 3.523 | 1.296 | 1.327 | 1.328 | 1.318 |
15 | 32.768 | 9.679 | 3.197 | 6.482 | 2.390 | 2.424 | 2.461 | 2.404 |
16 | 65.536 | 17.928 | 5.961 | 11.967 | 4.465 | 4.462 | 4.536 | 4.465 |
17 | 131.072 | 33.793 | 11.310 | 22.483 | 8.425 | 8.384 | 8.548 | 8.436 |
18 | 262.144 | 63.071 | 21.080 | 41.991 | 15.672 | 15.728 | 15.874 | 15.797 |
19 | 524.288 | 118.877 | 39.579 | 79.298 | 29.651 | 29.606 | 29.874 | 29.746 |
20 | 1.048.576 | 224.795 | 74.949 | 149.846 | 56.267 | 55.974 | 56.341 | 56.213 |
21 | 2.097.152 | 425.391 | 141.763 | 283.628 | 106.419 | 106.063 | 106.381 | 106.528 |
22 | 4.194.304 | 808.740 | 269.041 | 539.699 | 202.007 | 202.188 | 202.248 | 202.297 |
23 | 8.388.608 | 1.541.676 | 513.275 | 1.028.401 | 385.733 | 385.302 | 385.221 | 385.420 |
24 | 16.777.216 | 2.946.463 | 981.351 | 1.965.112 | 736.436 | 736.470 | 736.731 | 736.826 |
25 | 33.554.432 | 5.643.478 | 1.880.575 | 3.762.903 | 1.410.624 | 1.411.069 | 1.411.037 | 1.410.748 |
26 | 67.108.864 | 10.824.818 | 3.608.511 | 7.216.307 | 2.705.519 | 2.707.079 | 2.706.586 | 2.705.634 |
27 | 134.217.728 | 20.793.338 | 6.931.359 | 13.861.979 | 5.197.166 | 5.200.407 | 5.196.722 | 5.199.043 |
28 | 268.435.456 | 40.005.512 | 13.335.081 | 26.670.431 | 10.001.440 | 10.001.515 | 9.999.255 | 10.003.302 |
29 | 536.870.912 | 77.079.934 | 25.692.577 | 51.387.357 | 19.273.352 | 19.267.148 | 19.265.631 | 19.273.803 |
30 | 1.073.741.824 | 148.720.709 | 49.576.188 | 99.144.521 | 37.179.185 | 37.182.041 | 37.177.933 | 37.181.550 |
31 | 2.147.483.648 | 287.315.008 | 95.775.285 | 191.539.723 | 71.827.627 | 71.830.848 | 71.824.276 | 71.832.257 |
32 | 4.294.967.296 | 555.734.472 | 185.245.659 | 370.488.813 | 138.932.961 | 138.933.657 | 138.934.252 | 138.933.602 |
33 | 8.589.934.592 | 1.076.100.111 | 358.710.154 | 717.389.957 | 269.005.883 | 269.030.011 | 269.025.362 | 269.038.855 |
34 | 17.179.869.184 | 2.085.746.261 | 695.262.152 | 1.390.484.109 | 521.422.986 | 521.444.197 | 521.435.550 | 521.443.528 |
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 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
6 | 64 | 8 | 4 | 4 | 1 | 2 | 2 | 3 |
7 | 128 | 27 | 11 | 16 | 5 | 5 | 10 | 7 |
8 | 256 | 60 | 24 | 36 | 13 | 15 | 16 | 16 |
9 | 512 | 162 | 71 | 91 | 35 | 45 | 44 | 38 |
10 | 1.024 | 383 | 177 | 206 | 98 | 94 | 100 | 91 |
11 | 2.048 | 847 | 403 | 444 | 209 | 209 | 212 | 217 |
12 | 4.096 | 1.778 | 850 | 928 | 430 | 460 | 450 | 438 |
13 | 8.192 | 3.785 | 1.808 | 1.977 | 899 | 961 | 973 | 952 |
14 | 16.384 | 7.871 | 3.852 | 4.019 | 1.886 | 1.973 | 2.026 | 1.986 |
15 | 32.768 | 16.384 | 8.017 | 8.367 | 3.982 | 4.101 | 4.142 | 4.159 |
16 | 65.536 | 33.763 | 16.493 | 17.270 | 8.323 | 8.429 | 8.525 | 8.486 |
17 | 131.072 | 68.617 | 33.560 | 35.057 | 17.060 | 17.246 | 17.166 | 17.145 |
18 | 262.144 | 140.585 | 68.894 | 71.691 | 34.996 | 35.290 | 35.109 | 35.190 |
19 | 524.288 | 285.711 | 140.443 | 145.268 | 71.491 | 71.472 | 71.494 | 71.254 |
20 | 1.048.576 | 580.214 | 285.665 | 294.549 | 144.804 | 145.585 | 145.119 | 144.706 |
21 | 2.097.152 | 1.176.804 | 579.499 | 597.305 | 293.999 | 294.756 | 293.988 | 294.061 |
22 | 4.194.304 | 2.382.044 | 1.174.082 | 1.207.962 | 595.654 | 596.351 | 595.035 | 595.004 |
23 | 8.388.608 | 4.813.920 | 2.374.469 | 2.439.451 | 1.204.120 | 1.203.352 | 1.203.573 | 1.202.875 |
24 | 16.777.216 | 9.716.826 | 4.795.354 | 4.921.472 | 2.429.511 | 2.428.906 | 2.429.838 | 2.428.571 |
25 | 33.554.432 | 19.595.789 | 9.679.637 | 9.916.152 | 4.899.800 | 4.898.172 | 4.899.756 | 4.898.061 |
26 | 67.108.864 | 39.494.648 | 19.522.277 | 19.972.371 | 9.874.024 | 9.873.348 | 9.873.643 | 9.873.633 |
27 | 134.217.728 | 79.554.797 | 39.343.416 | 40.211.381 | 19.889.617 | 19.890.183 | 19.886.084 | 19.888.913 |
28 | 268.435.456 | 160.156.375 | 79.248.009 | 80.908.366 | 40.037.877 | 40.043.778 | 40.035.027 | 40.039.693 |
29 | 536.870.912 | 322.239.911 | 159.526.964 | 162.712.947 | 80.558.840 | 80.554.279 | 80.560.324 | 80.566.468 |
30 | 1.073.741.824 | 648.051.956 | 320.940.546 | 327.111.410 | 162.015.672 | 162.015.315 | 162.004.194 | 162.016.775 |
31 | 2.147.483.648 | 1.302.747.072 | 645.431.366 | 657.315.706 | 325.679.741 | 325.696.535 | 325.674.791 | 325.696.005 |
32 | 4.294.967.296 | 2.617.846.359 | 1.297.413.621 | 1.320.432.738 | 654.444.275 | 654.446.643 | 654.466.662 | 654.488.779 |
33 | 8.589.934.592 | 5.258.816.680 | 2.607.134.950 | 2.651.681.730 | 1.314.704.458 | 1.314.677.305 | 1.314.707.559 | 1.314.727.358 |
34 | 17.179.869.184 | 10.561.064.122 | 5.237.368.519 | 5.323.695.603 | 2.640.253.753 | 2.640.244.748 | 2.640.263.887 | 2.640.301.734 |