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+28x-67
f(0)=67
f(1)=19
f(2)=7
f(3)=13
f(4)=61
f(5)=1
f(6)=137
f(7)=89
f(8)=17
f(9)=1
f(10)=313
f(11)=181
f(12)=59
f(13)=233
f(14)=521
f(15)=1
f(16)=1
f(17)=349
f(18)=761
f(19)=1
f(20)=47
f(21)=37
f(22)=1033
f(23)=79
f(24)=1181
f(25)=1
f(26)=191
f(27)=709
f(28)=1
f(29)=1
f(30)=239
f(31)=881
f(32)=109
f(33)=139
f(34)=157
f(35)=1069
f(36)=2237
f(37)=167
f(38)=2441
f(39)=1
f(40)=379
f(41)=1381
f(42)=1
f(43)=1493
f(44)=443
f(45)=1609
f(46)=71
f(47)=1
f(48)=3581
f(49)=1
f(50)=3833
f(51)=283
f(52)=4093
f(53)=2113
f(54)=1
f(55)=173
f(56)=4637
f(57)=2389
f(58)=1
f(59)=149
f(60)=401
f(61)=383
f(62)=1
f(63)=2833
f(64)=5821
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=3313
f(70)=6793
f(71)=1
f(72)=1019
f(73)=281
f(74)=7481
f(75)=547
f(76)=461
f(77)=211
f(78)=1
f(79)=599
f(80)=8573
f(81)=337
f(82)=1279
f(83)=269
f(84)=9341
f(85)=251
f(86)=107
f(87)=4969
f(88)=10141
f(89)=739
f(90)=1
f(91)=5381
f(92)=10973
f(93)=1
f(94)=877
f(95)=1
f(96)=1
f(97)=6029
f(98)=12281
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+28x-67 could be written as f(y)= y^2-263 with x=y-14
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+14
f'(x)>2x+27
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 | 8 | 1 | 0.900000 | 0.800000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 71 | 42 | 29 | 0.710000 | 0.420000 | 0.290000 | 7.888889 | 5.250000 | 29.000000 |
3 | 1.000 | 686 | 264 | 422 | 0.686000 | 0.264000 | 0.422000 | 9.661972 | 6.285714 | 14.551724 |
4 | 10.000 | 6.960 | 1.874 | 5.086 | 0.696000 | 0.187400 | 0.508600 | 10.145773 | 7.098485 | 12.052133 |
5 | 100.000 | 69.659 | 14.478 | 55.181 | 0.696590 | 0.144780 | 0.551810 | 10.008477 | 7.725720 | 10.849587 |
6 | 1.000.000 | 695.897 | 117.283 | 578.614 | 0.695897 | 0.117283 | 0.578614 | 9.990051 | 8.100774 | 10.485747 |
7 | 10.000.000 | 6.950.591 | 988.996 | 5.961.595 | 0.695059 | 0.098900 | 0.596160 | 9.987960 | 8.432561 | 10.303233 |
8 | 100.000.000 | 69.471.731 | 8.557.228 | 60.914.503 | 0.694717 | 0.085572 | 0.609145 | 9.995082 | 8.652439 | 10.217820 |
9 | 1.000.000.000 | 694.427.695 | 75.430.135 | 618.997.560 | 0.694428 | 0.075430 | 0.618998 | 9.995831 | 8.814786 | 10.161743 |
10 | 10.000.000.000 | 6.942.217.112 | 674.438.852 | 6.267.778.260 | 0.694222 | 0.067444 | 0.626778 | 9.997034 | 8.941238 | 10.125690 |
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 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 13 | 11 | 2 | 0.812500 | 0.687500 | 0.125000 | 1.625000 | 1.571429 | 2.000000 |
5 | 32 | 24 | 17 | 7 | 0.750000 | 0.531250 | 0.218750 | 1.846154 | 1.545455 | 3.500000 |
6 | 64 | 48 | 31 | 17 | 0.750000 | 0.484375 | 0.265625 | 2.000000 | 1.823529 | 2.428571 |
7 | 128 | 90 | 50 | 40 | 0.703125 | 0.390625 | 0.312500 | 1.875000 | 1.612903 | 2.352941 |
8 | 256 | 174 | 87 | 87 | 0.679688 | 0.339844 | 0.339844 | 1.933333 | 1.740000 | 2.175000 |
9 | 512 | 345 | 149 | 196 | 0.673828 | 0.291016 | 0.382812 | 1.982759 | 1.712644 | 2.252874 |
10 | 1.024 | 705 | 268 | 437 | 0.688477 | 0.261719 | 0.426758 | 2.043478 | 1.798658 | 2.229592 |
11 | 2.048 | 1.408 | 481 | 927 | 0.687500 | 0.234863 | 0.452637 | 1.997163 | 1.794776 | 2.121281 |
12 | 4.096 | 2.834 | 871 | 1.963 | 0.691895 | 0.212646 | 0.479248 | 2.012784 | 1.810811 | 2.117584 |
13 | 8.192 | 5.688 | 1.590 | 4.098 | 0.694336 | 0.194092 | 0.500244 | 2.007057 | 1.825488 | 2.087621 |
14 | 16.384 | 11.410 | 2.893 | 8.517 | 0.696411 | 0.176575 | 0.519836 | 2.005977 | 1.819497 | 2.078331 |
15 | 32.768 | 22.814 | 5.321 | 17.493 | 0.696228 | 0.162384 | 0.533844 | 1.999474 | 1.839267 | 2.053892 |
16 | 65.536 | 45.644 | 9.920 | 35.724 | 0.696472 | 0.151367 | 0.545105 | 2.000701 | 1.864311 | 2.042188 |
17 | 131.072 | 91.287 | 18.432 | 72.855 | 0.696465 | 0.140625 | 0.555840 | 1.999978 | 1.858065 | 2.039385 |
18 | 262.144 | 182.497 | 34.564 | 147.933 | 0.696171 | 0.131851 | 0.564320 | 1.999156 | 1.875217 | 2.030513 |
19 | 524.288 | 364.824 | 65.013 | 299.811 | 0.695847 | 0.124002 | 0.571844 | 1.999068 | 1.880945 | 2.026668 |
20 | 1.048.576 | 729.629 | 122.441 | 607.188 | 0.695828 | 0.116769 | 0.579060 | 1.999948 | 1.883331 | 2.025236 |
21 | 2.097.152 | 1.458.356 | 232.038 | 1.226.318 | 0.695398 | 0.110644 | 0.584754 | 1.998764 | 1.895100 | 2.019668 |
22 | 4.194.304 | 2.915.904 | 440.540 | 2.475.364 | 0.695206 | 0.105033 | 0.590173 | 1.999446 | 1.898568 | 2.018533 |
23 | 8.388.608 | 5.830.601 | 839.217 | 4.991.384 | 0.695062 | 0.100042 | 0.595019 | 1.999586 | 1.904973 | 2.016424 |
24 | 16.777.216 | 11.659.322 | 1.604.033 | 10.055.289 | 0.694950 | 0.095608 | 0.599342 | 1.999678 | 1.911345 | 2.014529 |
25 | 33.554.432 | 23.315.479 | 3.068.371 | 20.247.108 | 0.694855 | 0.091445 | 0.603411 | 1.999729 | 1.912910 | 2.013578 |
26 | 67.108.864 | 46.623.777 | 5.880.262 | 40.743.515 | 0.694748 | 0.087623 | 0.607126 | 1.999692 | 1.916412 | 2.012313 |
27 | 134.217.728 | 93.237.114 | 11.291.011 | 81.946.103 | 0.694671 | 0.084125 | 0.610546 | 1.999776 | 1.920154 | 2.011267 |
28 | 268.435.456 | 186.449.147 | 21.716.589 | 164.732.558 | 0.694577 | 0.080901 | 0.613677 | 1.999731 | 1.923352 | 2.010255 |
29 | 536.870.912 | 372.855.633 | 41.833.998 | 331.021.635 | 0.694498 | 0.077922 | 0.616576 | 1.999771 | 1.926362 | 2.009449 |
30 | 1.073.741.824 | 745.627.575 | 80.701.316 | 664.926.259 | 0.694420 | 0.075159 | 0.619261 | 1.999776 | 1.929084 | 2.008709 |
31 | 2.147.483.648 | 1.491.110.391 | 155.858.870 | 1.335.251.521 | 0.694352 | 0.072577 | 0.621775 | 1.999806 | 1.931305 | 2.008120 |
32 | 4.294.967.296 | 2.981.955.794 | 301.379.232 | 2.680.576.562 | 0.694291 | 0.070170 | 0.624120 | 1.999822 | 1.933668 | 2.007544 |
33 | 8.589.934.592 | 5.963.415.074 | 583.419.906 | 5.379.995.168 | 0.694233 | 0.067919 | 0.626314 | 1.999833 | 1.935833 | 2.007029 |
34 | 17.179.869.184 | 11.925.925.415 | 1.130.528.571 | 10.795.396.844 | 0.694180 | 0.065805 | 0.628375 | 1.999848 | 1.937761 | 2.006581 |
35 | 34.359.738.368 | 23.850.283.397 | 2.192.819.863 | 21.657.463.534 | 0.694135 | 0.063819 | 0.630315 | 1.999869 | 1.939641 | 2.006176 |
36 | 68.719.476.736 | 47.697.568.766 | 4.257.235.159 | 43.440.333.607 | 0.694091 | 0.061951 | 0.632140 | 1.999874 | 1.941443 | 2.005790 |
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 | 3 | 0 | 0 | 2 | 0 | 1 |
2 | 4 | 5 | 5 | 0 | 0 | 2 | 2 | 1 |
3 | 8 | 7 | 5 | 2 | 2 | 2 | 2 | 1 |
4 | 16 | 11 | 7 | 4 | 5 | 2 | 3 | 1 |
5 | 32 | 17 | 10 | 7 | 8 | 2 | 6 | 1 |
6 | 64 | 31 | 18 | 13 | 13 | 2 | 15 | 1 |
7 | 128 | 50 | 27 | 23 | 23 | 2 | 24 | 1 |
8 | 256 | 87 | 52 | 35 | 43 | 2 | 41 | 1 |
9 | 512 | 149 | 80 | 69 | 76 | 2 | 70 | 1 |
10 | 1.024 | 268 | 149 | 119 | 127 | 2 | 138 | 1 |
11 | 2.048 | 481 | 255 | 226 | 242 | 2 | 236 | 1 |
12 | 4.096 | 871 | 451 | 420 | 437 | 2 | 431 | 1 |
13 | 8.192 | 1.590 | 795 | 795 | 796 | 2 | 791 | 1 |
14 | 16.384 | 2.893 | 1.466 | 1.427 | 1.465 | 2 | 1.425 | 1 |
15 | 32.768 | 5.321 | 2.689 | 2.632 | 2.664 | 2 | 2.654 | 1 |
16 | 65.536 | 9.920 | 5.011 | 4.909 | 4.932 | 2 | 4.985 | 1 |
17 | 131.072 | 18.432 | 9.284 | 9.148 | 9.203 | 2 | 9.226 | 1 |
18 | 262.144 | 34.564 | 17.374 | 17.190 | 17.274 | 2 | 17.287 | 1 |
19 | 524.288 | 65.013 | 32.665 | 32.348 | 32.507 | 2 | 32.503 | 1 |
20 | 1.048.576 | 122.441 | 61.616 | 60.825 | 61.343 | 2 | 61.095 | 1 |
21 | 2.097.152 | 232.038 | 116.543 | 115.495 | 116.084 | 2 | 115.951 | 1 |
22 | 4.194.304 | 440.540 | 221.167 | 219.373 | 220.329 | 2 | 220.208 | 1 |
23 | 8.388.608 | 839.217 | 420.666 | 418.551 | 419.687 | 2 | 419.527 | 1 |
24 | 16.777.216 | 1.604.033 | 804.818 | 799.215 | 801.724 | 2 | 802.306 | 1 |
25 | 33.554.432 | 3.068.371 | 1.539.262 | 1.529.109 | 1.534.498 | 2 | 1.533.870 | 1 |
26 | 67.108.864 | 5.880.262 | 2.949.961 | 2.930.301 | 2.940.231 | 2 | 2.940.028 | 1 |
27 | 134.217.728 | 11.291.011 | 5.664.193 | 5.626.818 | 5.645.046 | 2 | 5.645.962 | 1 |
28 | 268.435.456 | 21.716.589 | 10.892.263 | 10.824.326 | 10.859.234 | 2 | 10.857.352 | 1 |
29 | 536.870.912 | 41.833.998 | 20.977.661 | 20.856.337 | 20.919.334 | 2 | 20.914.661 | 1 |
30 | 1.073.741.824 | 80.701.316 | 40.466.162 | 40.235.154 | 40.350.569 | 2 | 40.350.744 | 1 |
31 | 2.147.483.648 | 155.858.870 | 78.153.506 | 77.705.364 | 77.924.083 | 2 | 77.934.784 | 1 |
32 | 4.294.967.296 | 301.379.232 | 151.116.084 | 150.263.148 | 150.685.119 | 2 | 150.694.110 | 1 |
33 | 8.589.934.592 | 583.419.906 | 292.511.191 | 290.908.715 | 291.699.813 | 2 | 291.720.090 | 1 |
34 | 17.179.869.184 | 1.130.528.571 | 566.765.517 | 563.763.054 | 565.250.341 | 2 | 565.278.227 | 1 |
35 | 34.359.738.368 | 2.192.819.863 | 1.099.213.771 | 1.093.606.092 | 1.096.382.002 | 2 | 1.096.437.858 | 1 |
36 | 68.719.476.736 | 4.257.235.159 | 2.133.863.888 | 2.123.371.271 | 2.128.591.133 | 2 | 2.128.644.023 | 1 |
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 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 2 | 0 | 2 | 1 | 1 | 0 | 0 |
5 | 32 | 7 | 2 | 5 | 1 | 1 | 1 | 4 |
6 | 64 | 17 | 6 | 11 | 2 | 5 | 4 | 6 |
7 | 128 | 40 | 17 | 23 | 7 | 13 | 9 | 11 |
8 | 256 | 87 | 37 | 50 | 17 | 25 | 19 | 26 |
9 | 512 | 196 | 94 | 102 | 42 | 59 | 39 | 56 |
10 | 1.024 | 437 | 199 | 238 | 93 | 125 | 91 | 128 |
11 | 2.048 | 927 | 452 | 475 | 201 | 263 | 193 | 270 |
12 | 4.096 | 1.963 | 972 | 991 | 421 | 542 | 442 | 558 |
13 | 8.192 | 4.098 | 2.042 | 2.056 | 911 | 1.133 | 909 | 1.145 |
14 | 16.384 | 8.517 | 4.253 | 4.264 | 1.890 | 2.320 | 1.962 | 2.345 |
15 | 32.768 | 17.493 | 8.800 | 8.693 | 3.944 | 4.739 | 4.041 | 4.769 |
16 | 65.536 | 35.724 | 17.918 | 17.806 | 8.204 | 9.609 | 8.286 | 9.625 |
17 | 131.072 | 72.855 | 36.453 | 36.402 | 16.932 | 19.445 | 16.935 | 19.543 |
18 | 262.144 | 147.933 | 74.189 | 73.744 | 34.451 | 39.373 | 34.644 | 39.465 |
19 | 524.288 | 299.811 | 150.099 | 149.712 | 70.427 | 79.644 | 70.453 | 79.287 |
20 | 1.048.576 | 607.188 | 303.969 | 303.219 | 143.275 | 160.186 | 143.606 | 160.121 |
21 | 2.097.152 | 1.226.318 | 613.391 | 612.927 | 290.879 | 322.008 | 290.824 | 322.607 |
22 | 4.194.304 | 2.475.364 | 1.238.198 | 1.237.166 | 589.423 | 647.942 | 590.009 | 647.990 |
23 | 8.388.608 | 4.991.384 | 2.496.808 | 2.494.576 | 1.191.761 | 1.304.188 | 1.193.315 | 1.302.120 |
24 | 16.777.216 | 10.055.289 | 5.031.167 | 5.024.122 | 2.405.742 | 2.621.649 | 2.409.212 | 2.618.686 |
25 | 33.554.432 | 20.247.108 | 10.128.757 | 10.118.351 | 4.857.509 | 5.264.773 | 4.860.820 | 5.264.006 |
26 | 67.108.864 | 40.743.515 | 20.380.008 | 20.363.507 | 9.796.892 | 10.573.944 | 9.803.643 | 10.569.036 |
27 | 134.217.728 | 81.946.103 | 40.981.427 | 40.964.676 | 19.743.184 | 21.228.017 | 19.752.558 | 21.222.344 |
28 | 268.435.456 | 164.732.558 | 82.387.088 | 82.345.470 | 39.763.944 | 42.596.011 | 39.777.123 | 42.595.480 |
29 | 536.870.912 | 331.021.635 | 165.558.167 | 165.463.468 | 80.031.503 | 85.471.102 | 80.044.790 | 85.474.240 |
30 | 1.073.741.824 | 664.926.259 | 332.553.582 | 332.372.677 | 161.013.170 | 171.452.494 | 161.014.790 | 171.445.805 |
31 | 2.147.483.648 | 1.335.251.521 | 667.766.744 | 667.484.777 | 323.759.578 | 343.862.759 | 323.769.899 | 343.859.285 |
32 | 4.294.967.296 | 2.680.576.562 | 1.340.574.749 | 1.340.001.813 | 650.736.318 | 689.549.371 | 650.752.583 | 689.538.290 |
33 | 8.589.934.592 | 5.379.995.168 | 2.690.501.690 | 2.689.493.478 | 1.307.515.819 | 1.382.489.723 | 1.307.532.396 | 1.382.457.230 |
34 | 17.179.869.184 | 10.795.396.844 | 5.398.627.510 | 5.396.769.334 | 2.626.373.614 | 2.771.338.227 | 2.626.417.190 | 2.771.267.813 |
35 | 34.359.738.368 | 21.657.463.534 | 10.830.469.421 | 10.826.994.113 | 5.274.053.351 | 5.554.657.345 | 5.274.052.980 | 5.554.699.858 |
36 | 68.719.476.736 | 43.440.333.607 | 21.723.472.314 | 21.716.861.293 | 10.588.063.583 | 11.132.038.957 | 10.588.041.326 | 11.132.189.741 |