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-238x-3
f(0)=3
f(1)=5
f(2)=19
f(3)=59
f(4)=313
f(5)=73
f(6)=31
f(7)=1
f(8)=97
f(9)=43
f(10)=761
f(11)=1
f(12)=181
f(13)=61
f(14)=1
f(15)=1
f(16)=79
f(17)=47
f(18)=1321
f(19)=347
f(20)=4363
f(21)=1
f(22)=317
f(23)=1237
f(24)=571
f(25)=37
f(26)=1103
f(27)=1
f(28)=53
f(29)=379
f(30)=2081
f(31)=107
f(32)=1319
f(33)=1
f(34)=257
f(35)=1777
f(36)=1
f(37)=1
f(38)=7603
f(39)=647
f(40)=139
f(41)=101
f(42)=1
f(43)=233
f(44)=8539
f(45)=1
f(46)=1
f(47)=449
f(48)=3041
f(49)=193
f(50)=9403
f(51)=1
f(52)=1
f(53)=613
f(54)=3313
f(55)=839
f(56)=2039
f(57)=1
f(58)=1
f(59)=1
f(60)=1187
f(61)=1
f(62)=1
f(63)=919
f(64)=1
f(65)=1
f(66)=757
f(67)=191
f(68)=373
f(69)=1
f(70)=1307
f(71)=593
f(72)=797
f(73)=251
f(74)=199
f(75)=1019
f(76)=821
f(77)=1
f(78)=1
f(79)=349
f(80)=269
f(81)=1
f(82)=853
f(83)=3217
f(84)=227
f(85)=271
f(86)=523
f(87)=1
f(88)=163
f(89)=829
f(90)=4441
f(91)=223
f(92)=2687
f(93)=281
f(94)=4513
f(95)=1
f(96)=1
f(97)=1
f(98)=13723
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-238x-3 could be written as f(y)= y^2-14164 with x=y+119
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-119
f'(x)>2x-239 with x > 119
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 | 2 | 8 | 1.000000 | 0.200000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 13 | 54 | 0.670000 | 0.130000 | 0.540000 | 6.700000 | 6.500000 | 6.750000 |
3 | 1.000 | 457 | 91 | 366 | 0.457000 | 0.091000 | 0.366000 | 6.820896 | 7.000000 | 6.777778 |
4 | 10.000 | 5.858 | 657 | 5.201 | 0.585800 | 0.065700 | 0.520100 | 12.818380 | 7.219780 | 14.210382 |
5 | 100.000 | 62.173 | 5.001 | 57.172 | 0.621730 | 0.050010 | 0.571720 | 10.613349 | 7.611872 | 10.992501 |
6 | 1.000.000 | 635.855 | 40.703 | 595.152 | 0.635855 | 0.040703 | 0.595152 | 10.227189 | 8.138972 | 10.409851 |
7 | 10.000.000 | 6.444.841 | 342.984 | 6.101.857 | 0.644484 | 0.034298 | 0.610186 | 10.135709 | 8.426504 | 10.252603 |
8 | 100.000.000 | 65.087.391 | 2.955.417 | 62.131.974 | 0.650874 | 0.029554 | 0.621320 | 10.099146 | 8.616778 | 10.182470 |
9 | 1.000.000.000 | 655.729.955 | 25.965.818 | 629.764.137 | 0.655730 | 0.025966 | 0.629764 | 10.074609 | 8.785839 | 10.135911 |
10 | 10.000.000.000 | 6.595.730.590 | 231.647.038 | 6.364.083.552 | 0.659573 | 0.023165 | 0.636408 | 10.058607 | 8.921230 | 10.105503 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 1 | 4 | 1.250000 | 0.250000 | 1.000000 | 1.666667 | 1.000000 | 2.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 2.000000 | 1.500000 |
4 | 16 | 13 | 2 | 11 | 0.812500 | 0.125000 | 0.687500 | 1.625000 | 1.000000 | 1.833333 |
5 | 32 | 25 | 5 | 20 | 0.781250 | 0.156250 | 0.625000 | 1.923077 | 2.500000 | 1.818182 |
6 | 64 | 43 | 10 | 33 | 0.671875 | 0.156250 | 0.515625 | 1.720000 | 2.000000 | 1.650000 |
7 | 128 | 77 | 16 | 61 | 0.601562 | 0.125000 | 0.476562 | 1.790698 | 1.600000 | 1.848485 |
8 | 256 | 78 | 17 | 61 | 0.304688 | 0.066406 | 0.238281 | 1.012987 | 1.062500 | 1.000000 |
9 | 512 | 189 | 45 | 144 | 0.369141 | 0.087891 | 0.281250 | 2.423077 | 2.647059 | 2.360656 |
10 | 1.024 | 467 | 92 | 375 | 0.456055 | 0.089844 | 0.366211 | 2.470900 | 2.044445 | 2.604167 |
11 | 2.048 | 1.059 | 166 | 893 | 0.517090 | 0.081055 | 0.436035 | 2.267666 | 1.804348 | 2.381333 |
12 | 4.096 | 2.277 | 299 | 1.978 | 0.555908 | 0.072998 | 0.482910 | 2.150142 | 1.801205 | 2.215006 |
13 | 8.192 | 4.773 | 552 | 4.221 | 0.582642 | 0.067383 | 0.515259 | 2.096179 | 1.846154 | 2.133974 |
14 | 16.384 | 9.799 | 1.001 | 8.798 | 0.598083 | 0.061096 | 0.536987 | 2.053006 | 1.813406 | 2.084340 |
15 | 32.768 | 19.961 | 1.848 | 18.113 | 0.609161 | 0.056396 | 0.552765 | 2.037045 | 1.846154 | 2.058763 |
16 | 65.536 | 40.520 | 3.430 | 37.090 | 0.618286 | 0.052338 | 0.565948 | 2.029958 | 1.856061 | 2.047701 |
17 | 131.072 | 81.824 | 6.393 | 75.431 | 0.624268 | 0.048775 | 0.575493 | 2.019348 | 1.863848 | 2.033729 |
18 | 262.144 | 164.865 | 11.967 | 152.898 | 0.628910 | 0.045650 | 0.583260 | 2.014874 | 1.871891 | 2.026992 |
19 | 524.288 | 331.757 | 22.604 | 309.153 | 0.632776 | 0.043114 | 0.589663 | 2.012295 | 1.888861 | 2.021956 |
20 | 1.048.576 | 667.060 | 42.495 | 624.565 | 0.636158 | 0.040526 | 0.595632 | 2.010689 | 1.879977 | 2.020246 |
21 | 2.097.152 | 1.340.076 | 80.508 | 1.259.568 | 0.638998 | 0.038389 | 0.600609 | 2.008929 | 1.894529 | 2.016712 |
22 | 4.194.304 | 2.691.350 | 153.025 | 2.538.325 | 0.641668 | 0.036484 | 0.605184 | 2.008356 | 1.900743 | 2.015234 |
23 | 8.388.608 | 5.401.688 | 291.357 | 5.110.331 | 0.643931 | 0.034732 | 0.609199 | 2.007055 | 1.903983 | 2.013269 |
24 | 16.777.216 | 10.840.330 | 555.288 | 10.285.042 | 0.646134 | 0.033098 | 0.613036 | 2.006841 | 1.905868 | 2.012598 |
25 | 33.554.432 | 21.746.869 | 1.060.942 | 20.685.927 | 0.648107 | 0.031619 | 0.616489 | 2.006108 | 1.910616 | 2.011263 |
26 | 67.108.864 | 43.615.045 | 2.031.425 | 41.583.620 | 0.649915 | 0.030271 | 0.619644 | 2.005578 | 1.914737 | 2.010237 |
27 | 134.217.728 | 87.450.563 | 3.897.458 | 83.553.105 | 0.651557 | 0.029038 | 0.622519 | 2.005055 | 1.918583 | 2.009279 |
28 | 268.435.456 | 175.316.728 | 7.489.387 | 167.827.341 | 0.653106 | 0.027900 | 0.625206 | 2.004753 | 1.921608 | 2.008631 |
29 | 536.870.912 | 351.403.320 | 14.409.408 | 336.993.912 | 0.654540 | 0.026840 | 0.627700 | 2.004391 | 1.923977 | 2.007980 |
30 | 1.073.741.824 | 704.228.439 | 27.777.898 | 676.450.541 | 0.655864 | 0.025870 | 0.629994 | 2.004046 | 1.927761 | 2.007308 |
31 | 2.147.483.648 | 1.411.115.173 | 53.604.629 | 1.357.510.544 | 0.657102 | 0.024962 | 0.632140 | 2.003775 | 1.929758 | 2.006814 |
32 | 4.294.967.296 | 2.827.189.000 | 103.591.722 | 2.723.597.278 | 0.658256 | 0.024119 | 0.634137 | 2.003514 | 1.932514 | 2.006318 |
33 | 8.589.934.592 | 5.663.718.241 | 200.408.039 | 5.463.310.202 | 0.659344 | 0.023331 | 0.636013 | 2.003304 | 1.934595 | 2.005917 |
34 | 17.179.869.184 | 11.344.974.775 | 388.130.297 | 10.956.844.478 | 0.660364 | 0.022592 | 0.637772 | 2.003097 | 1.936700 | 2.005532 |
35 | 34.359.738.368 | 22.722.906.028 | 752.426.076 | 21.970.479.952 | 0.661324 | 0.021898 | 0.639425 | 2.002905 | 1.938591 | 2.005183 |
36 | 68.719.476.736 | 45.508.095.434 | 1.460.097.866 | 44.047.997.568 | 0.662230 | 0.021247 | 0.640983 | 2.002741 | 1.940520 | 2.004872 |
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 | 0 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 1 | 0 | 1 | 1 | 0 | 0 |
4 | 16 | 2 | 1 | 0 | 1 | 1 | 0 | 0 |
5 | 32 | 5 | 4 | 0 | 1 | 3 | 1 | 0 |
6 | 64 | 10 | 9 | 0 | 2 | 6 | 2 | 0 |
7 | 128 | 16 | 15 | 0 | 3 | 9 | 4 | 0 |
8 | 256 | 17 | 15 | 1 | 3 | 9 | 5 | 0 |
9 | 512 | 45 | 15 | 29 | 4 | 15 | 19 | 7 |
10 | 1.024 | 92 | 15 | 76 | 8 | 20 | 48 | 16 |
11 | 2.048 | 166 | 15 | 150 | 14 | 33 | 92 | 27 |
12 | 4.096 | 299 | 15 | 283 | 23 | 60 | 165 | 51 |
13 | 8.192 | 552 | 15 | 536 | 43 | 107 | 307 | 95 |
14 | 16.384 | 1.001 | 15 | 985 | 75 | 200 | 540 | 186 |
15 | 32.768 | 1.848 | 15 | 1.832 | 137 | 369 | 992 | 350 |
16 | 65.536 | 3.430 | 15 | 3.414 | 241 | 651 | 1.869 | 669 |
17 | 131.072 | 6.393 | 15 | 6.377 | 457 | 1.198 | 3.505 | 1.233 |
18 | 262.144 | 11.967 | 15 | 11.951 | 835 | 2.293 | 6.523 | 2.316 |
19 | 524.288 | 22.604 | 15 | 22.588 | 1.558 | 4.377 | 12.367 | 4.302 |
20 | 1.048.576 | 42.495 | 15 | 42.479 | 2.850 | 8.216 | 23.261 | 8.168 |
21 | 2.097.152 | 80.508 | 15 | 80.492 | 5.344 | 15.558 | 44.027 | 15.579 |
22 | 4.194.304 | 153.025 | 15 | 153.009 | 10.100 | 29.655 | 83.864 | 29.406 |
23 | 8.388.608 | 291.357 | 15 | 291.341 | 19.196 | 56.338 | 159.823 | 56.000 |
24 | 16.777.216 | 555.288 | 15 | 555.272 | 36.793 | 107.103 | 304.831 | 106.561 |
25 | 33.554.432 | 1.060.942 | 15 | 1.060.926 | 69.825 | 204.133 | 583.264 | 203.720 |
26 | 67.108.864 | 2.031.425 | 15 | 2.031.409 | 133.689 | 390.321 | 1.117.287 | 390.128 |
27 | 134.217.728 | 3.897.458 | 15 | 3.897.442 | 256.141 | 747.547 | 2.145.559 | 748.211 |
28 | 268.435.456 | 7.489.387 | 15 | 7.489.371 | 491.308 | 1.435.872 | 4.125.424 | 1.436.783 |
29 | 536.870.912 | 14.409.408 | 15 | 14.409.392 | 944.274 | 2.760.603 | 7.944.075 | 2.760.456 |
30 | 1.073.741.824 | 27.777.898 | 15 | 27.777.882 | 1.816.439 | 5.317.700 | 15.326.573 | 5.317.186 |
31 | 2.147.483.648 | 53.604.629 | 15 | 53.604.613 | 3.500.378 | 10.252.304 | 29.594.970 | 10.256.977 |
32 | 4.294.967.296 | 103.591.722 | 15 | 103.591.706 | 6.752.572 | 19.800.506 | 57.229.569 | 19.809.075 |
33 | 8.589.934.592 | 200.408.039 | 15 | 200.408.023 | 13.045.743 | 38.282.115 | 110.782.204 | 38.297.977 |
34 | 17.179.869.184 | 388.130.297 | 15 | 388.130.281 | 25.233.633 | 74.095.676 | 214.676.147 | 74.124.841 |
35 | 34.359.738.368 | 752.426.076 | 15 | 752.426.060 | 48.865.205 | 143.575.661 | 416.388.059 | 143.597.151 |
36 | 68.719.476.736 | 1.460.097.866 | 15 | 1.460.097.850 | 94.718.670 | 278.477.071 | 808.404.829 | 278.497.296 |
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 | 0 | 1 | 1 | 0 |
2 | 4 | 4 | 2 | 2 | 1 | 2 | 1 | 0 |
3 | 8 | 6 | 4 | 2 | 2 | 2 | 1 | 1 |
4 | 16 | 11 | 8 | 3 | 3 | 3 | 3 | 2 |
5 | 32 | 20 | 10 | 10 | 5 | 6 | 4 | 5 |
6 | 64 | 33 | 14 | 19 | 11 | 8 | 5 | 9 |
7 | 128 | 61 | 24 | 37 | 16 | 14 | 15 | 16 |
8 | 256 | 61 | 24 | 37 | 16 | 14 | 15 | 16 |
9 | 512 | 144 | 65 | 79 | 40 | 25 | 34 | 45 |
10 | 1.024 | 375 | 193 | 182 | 95 | 85 | 92 | 103 |
11 | 2.048 | 893 | 461 | 432 | 224 | 198 | 206 | 265 |
12 | 4.096 | 1.978 | 1.015 | 963 | 495 | 450 | 444 | 589 |
13 | 8.192 | 4.221 | 2.178 | 2.043 | 1.034 | 979 | 989 | 1.219 |
14 | 16.384 | 8.798 | 4.565 | 4.233 | 2.204 | 2.057 | 2.065 | 2.472 |
15 | 32.768 | 18.113 | 9.338 | 8.775 | 4.490 | 4.276 | 4.364 | 4.983 |
16 | 65.536 | 37.090 | 19.141 | 17.949 | 9.186 | 8.849 | 8.954 | 10.101 |
17 | 131.072 | 75.431 | 38.803 | 36.628 | 18.623 | 18.175 | 18.178 | 20.455 |
18 | 262.144 | 152.898 | 78.452 | 74.446 | 38.042 | 36.714 | 36.834 | 41.308 |
19 | 524.288 | 309.153 | 158.295 | 150.858 | 76.963 | 74.294 | 74.815 | 83.081 |
20 | 1.048.576 | 624.565 | 319.522 | 305.043 | 155.502 | 150.457 | 151.826 | 166.780 |
21 | 2.097.152 | 1.259.568 | 643.637 | 615.931 | 313.313 | 304.250 | 306.426 | 335.579 |
22 | 4.194.304 | 2.538.325 | 1.295.534 | 1.242.791 | 632.351 | 613.691 | 618.695 | 673.588 |
23 | 8.388.608 | 5.110.331 | 2.603.637 | 2.506.694 | 1.273.912 | 1.236.716 | 1.247.786 | 1.351.917 |
24 | 16.777.216 | 10.285.042 | 5.234.778 | 5.050.264 | 2.564.957 | 2.493.072 | 2.513.132 | 2.713.881 |
25 | 33.554.432 | 20.685.927 | 10.517.318 | 10.168.609 | 5.156.580 | 5.023.594 | 5.061.161 | 5.444.592 |
26 | 67.108.864 | 41.583.620 | 21.128.399 | 20.455.221 | 10.365.279 | 10.113.663 | 10.183.557 | 10.921.121 |
27 | 134.217.728 | 83.553.105 | 42.422.964 | 41.130.141 | 20.830.406 | 20.347.811 | 20.480.521 | 21.894.367 |
28 | 268.435.456 | 167.827.341 | 85.158.394 | 82.668.947 | 41.849.566 | 40.913.206 | 41.165.652 | 43.898.917 |
29 | 536.870.912 | 336.993.912 | 170.895.163 | 166.098.749 | 84.033.842 | 82.234.525 | 82.728.581 | 87.996.964 |
30 | 1.073.741.824 | 676.450.541 | 342.839.305 | 333.611.236 | 168.695.066 | 165.229.696 | 166.186.932 | 176.338.847 |
31 | 2.147.483.648 | 1.357.510.544 | 687.637.256 | 669.873.288 | 338.565.443 | 331.883.405 | 333.717.869 | 353.343.827 |
32 | 4.294.967.296 | 2.723.597.278 | 1.378.924.514 | 1.344.672.764 | 679.324.312 | 666.426.352 | 669.938.693 | 707.907.921 |
33 | 8.589.934.592 | 5.463.310.202 | 2.764.763.431 | 2.698.546.771 | 1.362.764.432 | 1.337.812.364 | 1.344.618.013 | 1.418.115.393 |
34 | 17.179.869.184 | 10.956.844.478 | 5.542.558.041 | 5.414.286.437 | 2.733.259.374 | 2.684.883.262 | 2.698.096.093 | 2.840.605.749 |
35 | 34.359.738.368 | 21.970.479.952 | 11.109.438.521 | 10.861.041.431 | 5.481.065.849 | 5.387.172.320 | 5.412.916.035 | 5.689.325.748 |
36 | 68.719.476.736 | 44.047.997.568 | 22.264.693.121 | 21.783.304.447 | 10.989.464.020 | 10.807.270.439 | 10.857.321.764 | 11.393.941.345 |