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+13x-37
f(0)=37
f(1)=23
f(2)=7
f(3)=11
f(4)=31
f(5)=53
f(6)=1
f(7)=103
f(8)=131
f(9)=1
f(10)=193
f(11)=227
f(12)=263
f(13)=43
f(14)=1
f(15)=383
f(16)=61
f(17)=1
f(18)=521
f(19)=571
f(20)=89
f(21)=677
f(22)=733
f(23)=113
f(24)=1
f(25)=83
f(26)=977
f(27)=149
f(28)=101
f(29)=1181
f(30)=179
f(31)=1327
f(32)=1
f(33)=1481
f(34)=223
f(35)=1
f(36)=157
f(37)=1
f(38)=1901
f(39)=181
f(40)=2083
f(41)=311
f(42)=2273
f(43)=2371
f(44)=353
f(45)=1
f(46)=2677
f(47)=1
f(48)=59
f(49)=3001
f(50)=283
f(51)=461
f(52)=3343
f(53)=3461
f(54)=3581
f(55)=1
f(56)=1
f(57)=67
f(58)=1
f(59)=4211
f(60)=1
f(61)=1
f(62)=659
f(63)=4751
f(64)=73
f(65)=719
f(66)=167
f(67)=5323
f(68)=5471
f(69)=1
f(70)=251
f(71)=5927
f(72)=79
f(73)=1
f(74)=173
f(75)=6563
f(76)=1
f(77)=1
f(78)=307
f(79)=1033
f(80)=673
f(81)=7577
f(82)=7753
f(83)=1
f(84)=8111
f(85)=8293
f(86)=1
f(87)=8663
f(88)=1
f(89)=9041
f(90)=1319
f(91)=857
f(92)=9623
f(93)=1
f(94)=911
f(95)=10223
f(96)=10427
f(97)=1
f(98)=293
f(99)=257
b) Substitution of the polynom
The polynom f(x)=x^2+13x-37 could be written as f(y)= y^2-79.25 with x=y-6.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+6.5
f'(x)>2x+12
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 | 9 | 0 | 0.900000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 73 | 44 | 29 | 0.730000 | 0.440000 | 0.290000 | 8.111111 | 4.888889 | inf |
3 | 1.000 | 720 | 268 | 452 | 0.720000 | 0.268000 | 0.452000 | 9.863013 | 6.090909 | 15.586206 |
4 | 10.000 | 7.190 | 1.900 | 5.290 | 0.719000 | 0.190000 | 0.529000 | 9.986111 | 7.089552 | 11.703540 |
5 | 100.000 | 71.505 | 14.486 | 57.019 | 0.715050 | 0.144860 | 0.570190 | 9.945063 | 7.624210 | 10.778639 |
6 | 1.000.000 | 710.901 | 118.287 | 592.614 | 0.710901 | 0.118287 | 0.592614 | 9.941977 | 8.165608 | 10.393272 |
7 | 10.000.000 | 7.082.011 | 1.000.642 | 6.081.369 | 0.708201 | 0.100064 | 0.608137 | 9.962022 | 8.459442 | 10.261939 |
8 | 100.000.000 | 70.619.004 | 8.667.108 | 61.951.896 | 0.706190 | 0.086671 | 0.619519 | 9.971603 | 8.661548 | 10.187162 |
9 | 1.000.000.000 | 704.597.584 | 76.468.469 | 628.129.115 | 0.704598 | 0.076468 | 0.628129 | 9.977449 | 8.822836 | 10.138981 |
10 | 10.000.000.000 | 7.033.575.687 | 684.325.201 | 6.349.250.486 | 0.703358 | 0.068433 | 0.634925 | 9.982402 | 8.949116 | 10.108193 |
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 | 8 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.600000 | 1.600000 | -nan |
4 | 16 | 14 | 12 | 2 | 0.875000 | 0.750000 | 0.125000 | 1.750000 | 1.500000 | inf |
5 | 32 | 27 | 19 | 8 | 0.843750 | 0.593750 | 0.250000 | 1.928571 | 1.583333 | 4.000000 |
6 | 64 | 47 | 31 | 16 | 0.734375 | 0.484375 | 0.250000 | 1.740741 | 1.631579 | 2.000000 |
7 | 128 | 93 | 53 | 40 | 0.726562 | 0.414062 | 0.312500 | 1.978723 | 1.709677 | 2.500000 |
8 | 256 | 186 | 85 | 101 | 0.726562 | 0.332031 | 0.394531 | 2.000000 | 1.603774 | 2.525000 |
9 | 512 | 369 | 158 | 211 | 0.720703 | 0.308594 | 0.412109 | 1.983871 | 1.858824 | 2.089109 |
10 | 1.024 | 734 | 271 | 463 | 0.716797 | 0.264648 | 0.452148 | 1.989160 | 1.715190 | 2.194313 |
11 | 2.048 | 1.470 | 496 | 974 | 0.717773 | 0.242188 | 0.475586 | 2.002725 | 1.830258 | 2.103672 |
12 | 4.096 | 2.948 | 890 | 2.058 | 0.719727 | 0.217285 | 0.502441 | 2.005442 | 1.794355 | 2.112936 |
13 | 8.192 | 5.878 | 1.601 | 4.277 | 0.717529 | 0.195435 | 0.522095 | 1.993894 | 1.798876 | 2.078231 |
14 | 16.384 | 11.774 | 2.913 | 8.861 | 0.718628 | 0.177795 | 0.540833 | 2.003062 | 1.819488 | 2.071779 |
15 | 32.768 | 23.480 | 5.365 | 18.115 | 0.716553 | 0.163727 | 0.552826 | 1.994225 | 1.841744 | 2.044352 |
16 | 65.536 | 46.914 | 9.922 | 36.992 | 0.715851 | 0.151398 | 0.564453 | 1.998041 | 1.849394 | 2.042065 |
17 | 131.072 | 93.729 | 18.474 | 75.255 | 0.715096 | 0.140945 | 0.574150 | 1.997890 | 1.861923 | 2.034359 |
18 | 262.144 | 186.948 | 34.711 | 152.237 | 0.713150 | 0.132412 | 0.580738 | 1.994559 | 1.878911 | 2.022949 |
19 | 524.288 | 373.220 | 65.298 | 307.922 | 0.711861 | 0.124546 | 0.587315 | 1.996384 | 1.881190 | 2.022649 |
20 | 1.048.576 | 745.311 | 123.649 | 621.662 | 0.710784 | 0.117921 | 0.592863 | 1.996975 | 1.893611 | 2.018894 |
21 | 2.097.152 | 1.488.904 | 234.260 | 1.254.644 | 0.709965 | 0.111704 | 0.598261 | 1.997695 | 1.894556 | 2.018209 |
22 | 4.194.304 | 2.974.679 | 445.550 | 2.529.129 | 0.709219 | 0.106227 | 0.602991 | 1.997898 | 1.901947 | 2.015814 |
23 | 8.388.608 | 5.942.210 | 849.145 | 5.093.065 | 0.708367 | 0.101226 | 0.607141 | 1.997597 | 1.905836 | 2.013762 |
24 | 16.777.216 | 11.873.193 | 1.622.297 | 10.250.896 | 0.707697 | 0.096696 | 0.611001 | 1.998111 | 1.910506 | 2.012717 |
25 | 33.554.432 | 23.725.653 | 3.104.895 | 20.620.758 | 0.707080 | 0.092533 | 0.614546 | 1.998254 | 1.913888 | 2.011606 |
26 | 67.108.864 | 47.413.014 | 5.954.032 | 41.458.982 | 0.706509 | 0.088722 | 0.617787 | 1.998386 | 1.917627 | 2.010546 |
27 | 134.217.728 | 94.755.232 | 11.434.597 | 83.320.635 | 0.705981 | 0.085194 | 0.620787 | 1.998507 | 1.920480 | 2.009712 |
28 | 268.435.456 | 189.369.169 | 22.004.547 | 167.364.622 | 0.705455 | 0.081973 | 0.623482 | 1.998509 | 1.924383 | 2.008682 |
29 | 536.870.912 | 378.488.595 | 42.400.215 | 336.088.380 | 0.704990 | 0.078977 | 0.626013 | 1.998681 | 1.926884 | 2.008121 |
30 | 1.073.741.824 | 756.511.345 | 81.809.881 | 674.701.464 | 0.704556 | 0.076191 | 0.628365 | 1.998769 | 1.929469 | 2.007512 |
31 | 2.147.483.648 | 1.512.164.202 | 158.047.215 | 1.354.116.987 | 0.704156 | 0.073596 | 0.630560 | 1.998865 | 1.931884 | 2.006987 |
32 | 4.294.967.296 | 3.022.723.923 | 305.703.815 | 2.717.020.108 | 0.703783 | 0.071177 | 0.632606 | 1.998939 | 1.934256 | 2.006489 |
33 | 8.589.934.592 | 6.042.421.600 | 591.943.414 | 5.450.478.186 | 0.703430 | 0.068911 | 0.634519 | 1.998999 | 1.936330 | 2.006050 |
34 | 17.179.869.184 | 12.079.243.801 | 1.147.359.118 | 10.931.884.683 | 0.703105 | 0.066785 | 0.636319 | 1.999073 | 1.938292 | 2.005675 |
35 | 34.359.738.368 | 24.147.917.560 | 2.226.045.573 | 21.921.871.987 | 0.702797 | 0.064786 | 0.638010 | 1.999125 | 1.940147 | 2.005315 |
36 | 68.719.476.736 | 48.276.045.992 | 4.322.597.613 | 43.953.448.379 | 0.702509 | 0.062902 | 0.639607 | 1.999181 | 1.941828 | 2.005004 |
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 | 0 | 1 | 2 |
2 | 4 | 5 | 3 | 2 | 0 | 1 | 1 | 3 |
3 | 8 | 8 | 4 | 4 | 0 | 2 | 2 | 4 |
4 | 16 | 12 | 5 | 7 | 1 | 3 | 2 | 6 |
5 | 32 | 19 | 8 | 11 | 3 | 4 | 5 | 7 |
6 | 64 | 31 | 13 | 18 | 6 | 7 | 9 | 9 |
7 | 128 | 53 | 19 | 34 | 11 | 14 | 12 | 16 |
8 | 256 | 85 | 29 | 56 | 16 | 23 | 23 | 23 |
9 | 512 | 158 | 53 | 105 | 36 | 42 | 39 | 41 |
10 | 1.024 | 271 | 94 | 177 | 60 | 76 | 64 | 71 |
11 | 2.048 | 496 | 170 | 326 | 117 | 127 | 125 | 127 |
12 | 4.096 | 890 | 304 | 586 | 213 | 221 | 221 | 235 |
13 | 8.192 | 1.601 | 534 | 1.067 | 397 | 393 | 407 | 404 |
14 | 16.384 | 2.913 | 988 | 1.925 | 731 | 716 | 732 | 734 |
15 | 32.768 | 5.365 | 1.797 | 3.568 | 1.336 | 1.337 | 1.352 | 1.340 |
16 | 65.536 | 9.922 | 3.290 | 6.632 | 2.513 | 2.446 | 2.474 | 2.489 |
17 | 131.072 | 18.474 | 6.190 | 12.284 | 4.632 | 4.603 | 4.586 | 4.653 |
18 | 262.144 | 34.711 | 11.649 | 23.062 | 8.703 | 8.648 | 8.686 | 8.674 |
19 | 524.288 | 65.298 | 21.842 | 43.456 | 16.307 | 16.365 | 16.223 | 16.403 |
20 | 1.048.576 | 123.649 | 41.288 | 82.361 | 30.859 | 30.977 | 30.866 | 30.947 |
21 | 2.097.152 | 234.260 | 78.065 | 156.195 | 58.522 | 58.602 | 58.527 | 58.609 |
22 | 4.194.304 | 445.550 | 148.496 | 297.054 | 111.464 | 111.414 | 111.135 | 111.537 |
23 | 8.388.608 | 849.145 | 283.043 | 566.102 | 212.497 | 212.361 | 211.782 | 212.505 |
24 | 16.777.216 | 1.622.297 | 540.801 | 1.081.496 | 405.260 | 405.729 | 405.091 | 406.217 |
25 | 33.554.432 | 3.104.895 | 1.035.229 | 2.069.666 | 776.363 | 776.392 | 775.579 | 776.561 |
26 | 67.108.864 | 5.954.032 | 1.984.181 | 3.969.851 | 1.488.702 | 1.488.282 | 1.488.022 | 1.489.026 |
27 | 134.217.728 | 11.434.597 | 3.810.169 | 7.624.428 | 2.858.934 | 2.856.819 | 2.858.183 | 2.860.661 |
28 | 268.435.456 | 22.004.547 | 7.334.325 | 14.670.222 | 5.502.547 | 5.499.867 | 5.500.598 | 5.501.535 |
29 | 536.870.912 | 42.400.215 | 14.133.940 | 28.266.275 | 10.599.956 | 10.600.110 | 10.600.415 | 10.599.734 |
30 | 1.073.741.824 | 81.809.881 | 27.270.241 | 54.539.640 | 20.453.062 | 20.452.503 | 20.454.039 | 20.450.277 |
31 | 2.147.483.648 | 158.047.215 | 52.682.993 | 105.364.222 | 39.515.315 | 39.510.926 | 39.513.112 | 39.507.862 |
32 | 4.294.967.296 | 305.703.815 | 101.900.030 | 203.803.785 | 76.421.733 | 76.433.613 | 76.422.917 | 76.425.552 |
33 | 8.589.934.592 | 591.943.414 | 197.308.184 | 394.635.230 | 147.985.904 | 147.984.612 | 147.992.958 | 147.979.940 |
34 | 17.179.869.184 | 1.147.359.118 | 382.439.852 | 764.919.266 | 286.844.215 | 286.836.538 | 286.850.319 | 286.828.046 |
35 | 34.359.738.368 | 2.226.045.573 | 741.990.158 | 1.484.055.415 | 556.506.132 | 556.505.317 | 556.535.043 | 556.499.081 |
36 | 68.719.476.736 | 4.322.597.613 | 1.440.832.694 | 2.881.764.919 | 1.080.661.480 | 1.080.631.800 | 1.080.673.262 | 1.080.631.071 |
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 | 1 | 0 |
5 | 32 | 8 | 2 | 6 | 2 | 3 | 3 | 0 |
6 | 64 | 16 | 6 | 10 | 3 | 5 | 6 | 2 |
7 | 128 | 40 | 17 | 23 | 8 | 12 | 11 | 9 |
8 | 256 | 101 | 46 | 55 | 29 | 27 | 25 | 20 |
9 | 512 | 211 | 97 | 114 | 57 | 51 | 57 | 46 |
10 | 1.024 | 463 | 219 | 244 | 119 | 121 | 112 | 111 |
11 | 2.048 | 974 | 473 | 501 | 242 | 251 | 240 | 241 |
12 | 4.096 | 2.058 | 1.006 | 1.052 | 501 | 510 | 535 | 512 |
13 | 8.192 | 4.277 | 2.116 | 2.161 | 1.036 | 1.057 | 1.093 | 1.091 |
14 | 16.384 | 8.861 | 4.377 | 4.484 | 2.191 | 2.207 | 2.235 | 2.228 |
15 | 32.768 | 18.115 | 8.869 | 9.246 | 4.464 | 4.503 | 4.582 | 4.566 |
16 | 65.536 | 36.992 | 18.244 | 18.748 | 9.059 | 9.188 | 9.310 | 9.435 |
17 | 131.072 | 75.255 | 37.241 | 38.014 | 18.707 | 18.701 | 18.910 | 18.937 |
18 | 262.144 | 152.237 | 75.330 | 76.907 | 37.851 | 38.153 | 38.121 | 38.112 |
19 | 524.288 | 307.922 | 152.698 | 155.224 | 76.517 | 77.348 | 76.922 | 77.135 |
20 | 1.048.576 | 621.662 | 308.153 | 313.509 | 155.030 | 155.701 | 155.196 | 155.735 |
21 | 2.097.152 | 1.254.644 | 622.711 | 631.933 | 312.977 | 314.228 | 313.331 | 314.108 |
22 | 4.194.304 | 2.529.129 | 1.255.996 | 1.273.133 | 631.852 | 632.905 | 632.058 | 632.314 |
23 | 8.388.608 | 5.093.065 | 2.529.576 | 2.563.489 | 1.272.703 | 1.272.946 | 1.273.778 | 1.273.638 |
24 | 16.777.216 | 10.250.896 | 5.090.939 | 5.159.957 | 2.563.066 | 2.562.178 | 2.562.519 | 2.563.133 |
25 | 33.554.432 | 20.620.758 | 10.247.052 | 10.373.706 | 5.158.048 | 5.152.266 | 5.154.262 | 5.156.182 |
26 | 67.108.864 | 41.458.982 | 20.606.318 | 20.852.664 | 10.366.038 | 10.362.879 | 10.362.909 | 10.367.156 |
27 | 134.217.728 | 83.320.635 | 41.428.359 | 41.892.276 | 20.832.148 | 20.826.468 | 20.825.428 | 20.836.591 |
28 | 268.435.456 | 167.364.622 | 83.230.929 | 84.133.693 | 41.838.873 | 41.841.032 | 41.840.353 | 41.844.364 |
29 | 536.870.912 | 336.088.380 | 167.180.814 | 168.907.566 | 84.021.208 | 84.018.113 | 84.026.536 | 84.022.523 |
30 | 1.073.741.824 | 674.701.464 | 335.684.874 | 339.016.590 | 168.682.531 | 168.675.134 | 168.676.914 | 168.666.885 |
31 | 2.147.483.648 | 1.354.116.987 | 673.822.716 | 680.294.271 | 338.533.766 | 338.520.465 | 338.541.736 | 338.521.020 |
32 | 4.294.967.296 | 2.717.020.108 | 1.352.285.174 | 1.364.734.934 | 679.271.477 | 679.237.888 | 679.243.599 | 679.267.144 |
33 | 8.589.934.592 | 5.450.478.186 | 2.713.144.685 | 2.737.333.501 | 1.362.649.802 | 1.362.579.568 | 1.362.606.682 | 1.362.642.134 |
34 | 17.179.869.184 | 10.931.884.683 | 5.442.441.267 | 5.489.443.416 | 2.732.986.538 | 2.732.953.314 | 2.732.971.975 | 2.732.972.856 |
35 | 34.359.738.368 | 21.921.871.987 | 10.915.457.728 | 11.006.414.259 | 5.480.490.543 | 5.480.433.470 | 5.480.420.538 | 5.480.527.436 |
36 | 68.719.476.736 | 43.953.448.379 | 21.888.432.332 | 22.065.016.047 | 10.988.403.210 | 10.988.359.232 | 10.988.316.402 | 10.988.369.535 |