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+25x-31
f(0)=31
f(1)=5
f(2)=23
f(3)=53
f(4)=17
f(5)=7
f(6)=1
f(7)=193
f(8)=233
f(9)=11
f(10)=29
f(11)=73
f(12)=59
f(13)=463
f(14)=103
f(15)=569
f(16)=1
f(17)=683
f(18)=743
f(19)=1
f(20)=79
f(21)=1
f(22)=1
f(23)=37
f(24)=229
f(25)=1
f(26)=1
f(27)=1373
f(28)=1453
f(29)=307
f(30)=1619
f(31)=1
f(32)=163
f(33)=269
f(34)=1
f(35)=2069
f(36)=433
f(37)=1
f(38)=139
f(39)=1
f(40)=367
f(41)=107
f(42)=1
f(43)=263
f(44)=601
f(45)=3119
f(46)=647
f(47)=479
f(48)=151
f(49)=719
f(50)=3719
f(51)=769
f(52)=137
f(53)=373
f(54)=1
f(55)=257
f(56)=1
f(57)=4643
f(58)=4783
f(59)=197
f(60)=1
f(61)=149
f(62)=173
f(63)=1
f(64)=1
f(65)=1
f(66)=239
f(67)=6133
f(68)=1
f(69)=1291
f(70)=6619
f(71)=1
f(72)=409
f(73)=419
f(74)=1459
f(75)=97
f(76)=1
f(77)=7823
f(78)=1
f(79)=1637
f(80)=8369
f(81)=1
f(82)=1249
f(83)=8933
f(84)=1
f(85)=9319
f(86)=1
f(87)=883
f(88)=431
f(89)=1
f(90)=607
f(91)=421
f(92)=10733
f(93)=353
f(94)=1
f(95)=11369
f(96)=331
f(97)=1
f(98)=1093
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+25x-31 could be written as f(y)= y^2-187.25 with x=y-12.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+12.5
f'(x)>2x+24
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 | 7 | 2 | 0.900000 | 0.700000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 69 | 28 | 41 | 0.690000 | 0.280000 | 0.690000 | 7.666667 | 4.000000 | 20.500000 |
3 | 1.000 | 680 | 174 | 506 | 0.680000 | 0.174000 | 0.680000 | 9.855072 | 6.214286 | 12.341463 |
4 | 10.000 | 6.916 | 1.251 | 5.665 | 0.691600 | 0.125100 | 0.691600 | 10.170588 | 7.189655 | 11.195652 |
5 | 100.000 | 69.020 | 9.750 | 59.270 | 0.690200 | 0.097500 | 0.690200 | 9.979757 | 7.793765 | 10.462489 |
6 | 1.000.000 | 690.888 | 78.856 | 612.032 | 0.690888 | 0.078856 | 0.690888 | 10.009968 | 8.087795 | 10.326168 |
7 | 10.000.000 | 6.909.844 | 669.070 | 6.240.774 | 0.690984 | 0.066907 | 0.690984 | 10.001395 | 8.484706 | 10.196810 |
8 | 100.000.000 | 69.108.276 | 5.799.586 | 63.308.690 | 0.691083 | 0.057996 | 0.691083 | 10.001423 | 8.668130 | 10.144364 |
9 | 1.000.000.000 | 691.202.393 | 51.198.906 | 640.003.487 | 0.691202 | 0.051199 | 0.691202 | 10.001731 | 8.828028 | 10.109252 |
10 | 10.000.000.000 | 6.913.317.235 | 458.174.797 | 6.455.142.438 | 0.691332 | 0.045817 | 0.691332 | 10.001872 | 8.948917 | 10.086105 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 14 | 9 | 5 | 0.875000 | 0.562500 | 0.312500 | 1.750000 | 1.285714 | 5.000000 |
5 | 32 | 23 | 14 | 9 | 0.718750 | 0.437500 | 0.281250 | 1.642857 | 1.555556 | 1.800000 |
6 | 64 | 46 | 20 | 26 | 0.718750 | 0.312500 | 0.406250 | 2.000000 | 1.428571 | 2.888889 |
7 | 128 | 89 | 37 | 52 | 0.695312 | 0.289062 | 0.406250 | 1.934783 | 1.850000 | 2.000000 |
8 | 256 | 170 | 57 | 113 | 0.664062 | 0.222656 | 0.441406 | 1.910112 | 1.540541 | 2.173077 |
9 | 512 | 342 | 99 | 243 | 0.667969 | 0.193359 | 0.474609 | 2.011765 | 1.736842 | 2.150442 |
10 | 1.024 | 698 | 178 | 520 | 0.681641 | 0.173828 | 0.507812 | 2.040936 | 1.797980 | 2.139918 |
11 | 2.048 | 1.398 | 328 | 1.070 | 0.682617 | 0.160156 | 0.522461 | 2.002865 | 1.842697 | 2.057692 |
12 | 4.096 | 2.828 | 586 | 2.242 | 0.690430 | 0.143066 | 0.547363 | 2.022890 | 1.786585 | 2.095327 |
13 | 8.192 | 5.655 | 1.065 | 4.590 | 0.690308 | 0.130005 | 0.560303 | 1.999646 | 1.817406 | 2.047279 |
14 | 16.384 | 11.299 | 1.907 | 9.392 | 0.689636 | 0.116394 | 0.573242 | 1.998055 | 1.790610 | 2.046187 |
15 | 32.768 | 22.627 | 3.563 | 19.064 | 0.690521 | 0.108734 | 0.581787 | 2.002567 | 1.868380 | 2.029813 |
16 | 65.536 | 45.265 | 6.623 | 38.642 | 0.690689 | 0.101059 | 0.589630 | 2.000486 | 1.858827 | 2.026962 |
17 | 131.072 | 90.550 | 12.360 | 78.190 | 0.690842 | 0.094299 | 0.596542 | 2.000442 | 1.866224 | 2.023446 |
18 | 262.144 | 181.053 | 23.120 | 157.933 | 0.690662 | 0.088196 | 0.602467 | 1.999481 | 1.870550 | 2.019862 |
19 | 524.288 | 362.197 | 43.635 | 318.562 | 0.690836 | 0.083227 | 0.607609 | 2.000503 | 1.887327 | 2.017071 |
20 | 1.048.576 | 724.554 | 82.415 | 642.139 | 0.690989 | 0.078597 | 0.612391 | 2.000442 | 1.888736 | 2.015743 |
21 | 2.097.152 | 1.448.881 | 156.700 | 1.292.181 | 0.690880 | 0.074720 | 0.616160 | 1.999687 | 1.901353 | 2.012307 |
22 | 4.194.304 | 2.898.170 | 297.913 | 2.600.257 | 0.690978 | 0.071028 | 0.619950 | 2.000282 | 1.901168 | 2.012301 |
23 | 8.388.608 | 5.796.470 | 567.908 | 5.228.562 | 0.690993 | 0.067700 | 0.623293 | 2.000045 | 1.906288 | 2.010787 |
24 | 16.777.216 | 11.593.596 | 1.084.729 | 10.508.867 | 0.691032 | 0.064655 | 0.626377 | 2.000113 | 1.910043 | 2.009896 |
25 | 33.554.432 | 23.187.011 | 2.077.459 | 21.109.552 | 0.691027 | 0.061913 | 0.629114 | 1.999985 | 1.915187 | 2.008737 |
26 | 67.108.864 | 46.376.038 | 3.983.847 | 42.392.191 | 0.691057 | 0.059364 | 0.631693 | 2.000087 | 1.917654 | 2.008199 |
27 | 134.217.728 | 92.757.323 | 7.655.157 | 85.102.166 | 0.691096 | 0.057035 | 0.634061 | 2.000113 | 1.921549 | 2.007496 |
28 | 268.435.456 | 185.523.130 | 14.730.499 | 170.792.631 | 0.691128 | 0.054875 | 0.636252 | 2.000092 | 1.924258 | 2.006913 |
29 | 536.870.912 | 371.067.237 | 28.384.869 | 342.682.368 | 0.691167 | 0.052871 | 0.638296 | 2.000113 | 1.926945 | 2.006424 |
30 | 1.073.741.824 | 742.179.875 | 54.774.905 | 687.404.970 | 0.691209 | 0.051013 | 0.640196 | 2.000123 | 1.929722 | 2.005954 |
31 | 2.147.483.648 | 1.484.447.403 | 105.823.034 | 1.378.624.369 | 0.691250 | 0.049278 | 0.641972 | 2.000118 | 1.931962 | 2.005549 |
32 | 4.294.967.296 | 2.969.068.881 | 204.674.042 | 2.764.394.839 | 0.691290 | 0.047654 | 0.643636 | 2.000117 | 1.934116 | 2.005183 |
33 | 8.589.934.592 | 5.938.439.440 | 396.306.384 | 5.542.133.056 | 0.691325 | 0.046136 | 0.645189 | 2.000102 | 1.936280 | 2.004827 |
34 | 17.179.869.184 | 11.877.483.394 | 768.167.931 | 11.109.315.463 | 0.691361 | 0.044713 | 0.646647 | 2.000102 | 1.938318 | 2.004520 |
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 | 0 | 0 | 1 | 2 |
2 | 4 | 4 | 1 | 3 | 0 | 0 | 2 | 2 |
3 | 8 | 7 | 2 | 5 | 2 | 0 | 2 | 3 |
4 | 16 | 9 | 3 | 6 | 3 | 0 | 2 | 4 |
5 | 32 | 14 | 4 | 10 | 3 | 2 | 4 | 5 |
6 | 64 | 20 | 5 | 15 | 3 | 4 | 5 | 8 |
7 | 128 | 37 | 12 | 25 | 8 | 8 | 9 | 12 |
8 | 256 | 57 | 20 | 37 | 12 | 14 | 14 | 17 |
9 | 512 | 99 | 32 | 67 | 22 | 24 | 26 | 27 |
10 | 1.024 | 178 | 57 | 121 | 40 | 46 | 47 | 45 |
11 | 2.048 | 328 | 105 | 223 | 79 | 84 | 83 | 82 |
12 | 4.096 | 586 | 199 | 387 | 148 | 151 | 147 | 140 |
13 | 8.192 | 1.065 | 363 | 702 | 259 | 279 | 259 | 268 |
14 | 16.384 | 1.907 | 659 | 1.248 | 472 | 491 | 467 | 477 |
15 | 32.768 | 3.563 | 1.191 | 2.372 | 906 | 881 | 889 | 887 |
16 | 65.536 | 6.623 | 2.190 | 4.433 | 1.662 | 1.650 | 1.655 | 1.656 |
17 | 131.072 | 12.360 | 4.099 | 8.261 | 3.122 | 3.072 | 3.071 | 3.095 |
18 | 262.144 | 23.120 | 7.662 | 15.458 | 5.795 | 5.753 | 5.785 | 5.787 |
19 | 524.288 | 43.635 | 14.572 | 29.063 | 10.930 | 10.853 | 11.003 | 10.849 |
20 | 1.048.576 | 82.415 | 27.455 | 54.960 | 20.631 | 20.556 | 20.779 | 20.449 |
21 | 2.097.152 | 156.700 | 52.459 | 104.241 | 39.334 | 39.064 | 39.275 | 39.027 |
22 | 4.194.304 | 297.913 | 99.683 | 198.230 | 74.781 | 74.374 | 74.523 | 74.235 |
23 | 8.388.608 | 567.908 | 189.605 | 378.303 | 142.175 | 142.001 | 142.046 | 141.686 |
24 | 16.777.216 | 1.084.729 | 361.500 | 723.229 | 271.440 | 271.281 | 271.176 | 270.832 |
25 | 33.554.432 | 2.077.459 | 692.699 | 1.384.760 | 519.542 | 519.073 | 519.678 | 519.166 |
26 | 67.108.864 | 3.983.847 | 1.328.520 | 2.655.327 | 995.707 | 995.702 | 996.698 | 995.740 |
27 | 134.217.728 | 7.655.157 | 2.552.411 | 5.102.746 | 1.913.180 | 1.913.815 | 1.914.002 | 1.914.160 |
28 | 268.435.456 | 14.730.499 | 4.912.069 | 9.818.430 | 3.681.001 | 3.682.439 | 3.683.021 | 3.684.038 |
29 | 536.870.912 | 28.384.869 | 9.462.041 | 18.922.828 | 7.094.648 | 7.096.116 | 7.096.393 | 7.097.712 |
30 | 1.073.741.824 | 54.774.905 | 18.258.455 | 36.516.450 | 13.691.154 | 13.693.170 | 13.696.406 | 13.694.175 |
31 | 2.147.483.648 | 105.823.034 | 35.271.736 | 70.551.298 | 26.454.233 | 26.455.181 | 26.456.867 | 26.456.753 |
32 | 4.294.967.296 | 204.674.042 | 68.220.855 | 136.453.187 | 51.165.873 | 51.167.167 | 51.170.425 | 51.170.577 |
33 | 8.589.934.592 | 396.306.384 | 132.100.677 | 264.205.707 | 99.074.043 | 99.073.307 | 99.082.140 | 99.076.894 |
34 | 17.179.869.184 | 768.167.931 | 256.053.970 | 512.113.961 | 192.040.301 | 192.041.105 | 192.045.648 | 192.040.877 |
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 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 5 | 2 | 3 | 2 | 1 | 1 | 1 |
5 | 32 | 9 | 6 | 3 | 2 | 3 | 2 | 2 |
6 | 64 | 26 | 13 | 13 | 7 | 4 | 7 | 8 |
7 | 128 | 52 | 31 | 21 | 11 | 12 | 14 | 15 |
8 | 256 | 113 | 71 | 42 | 26 | 33 | 28 | 26 |
9 | 512 | 243 | 137 | 106 | 55 | 66 | 57 | 65 |
10 | 1.024 | 520 | 275 | 245 | 129 | 148 | 118 | 125 |
11 | 2.048 | 1.070 | 578 | 492 | 261 | 289 | 261 | 259 |
12 | 4.096 | 2.242 | 1.167 | 1.075 | 570 | 577 | 548 | 547 |
13 | 8.192 | 4.590 | 2.347 | 2.243 | 1.174 | 1.177 | 1.110 | 1.129 |
14 | 16.384 | 9.392 | 4.866 | 4.526 | 2.389 | 2.330 | 2.362 | 2.311 |
15 | 32.768 | 19.064 | 9.837 | 9.227 | 4.733 | 4.795 | 4.822 | 4.714 |
16 | 65.536 | 38.642 | 19.858 | 18.784 | 9.669 | 9.647 | 9.746 | 9.580 |
17 | 131.072 | 78.190 | 40.166 | 38.024 | 19.456 | 19.510 | 19.751 | 19.473 |
18 | 262.144 | 157.933 | 81.142 | 76.791 | 39.339 | 39.397 | 39.661 | 39.536 |
19 | 524.288 | 318.562 | 163.449 | 155.113 | 79.489 | 79.408 | 79.897 | 79.768 |
20 | 1.048.576 | 642.139 | 329.180 | 312.959 | 160.426 | 160.447 | 160.697 | 160.569 |
21 | 2.097.152 | 1.292.181 | 661.285 | 630.896 | 322.797 | 322.732 | 323.480 | 323.172 |
22 | 4.194.304 | 2.600.257 | 1.329.103 | 1.271.154 | 649.614 | 649.534 | 650.740 | 650.369 |
23 | 8.388.608 | 5.228.562 | 2.669.205 | 2.559.357 | 1.306.156 | 1.307.234 | 1.307.460 | 1.307.712 |
24 | 16.777.216 | 10.508.867 | 5.360.745 | 5.148.122 | 2.626.460 | 2.627.152 | 2.627.204 | 2.628.051 |
25 | 33.554.432 | 21.109.552 | 10.753.866 | 10.355.686 | 5.276.957 | 5.277.138 | 5.277.748 | 5.277.709 |
26 | 67.108.864 | 42.392.191 | 21.578.555 | 20.813.636 | 10.596.412 | 10.598.976 | 10.600.424 | 10.596.379 |
27 | 134.217.728 | 85.102.166 | 43.279.706 | 41.822.460 | 21.274.589 | 21.280.600 | 21.271.508 | 21.275.469 |
28 | 268.435.456 | 170.792.631 | 86.797.730 | 83.994.901 | 42.689.757 | 42.698.548 | 42.699.168 | 42.705.158 |
29 | 536.870.912 | 342.682.368 | 174.036.760 | 168.645.608 | 85.662.618 | 85.670.551 | 85.670.008 | 85.679.191 |
30 | 1.073.741.824 | 687.404.970 | 348.908.732 | 338.496.238 | 171.844.879 | 171.846.314 | 171.861.292 | 171.852.485 |
31 | 2.147.483.648 | 1.378.624.369 | 699.329.500 | 679.294.869 | 344.628.987 | 344.641.413 | 344.668.468 | 344.685.501 |
32 | 4.294.967.296 | 2.764.394.839 | 1.401.552.121 | 1.362.842.718 | 691.076.657 | 691.082.892 | 691.096.050 | 691.139.240 |
33 | 8.589.934.592 | 5.542.133.056 | 2.808.514.982 | 2.733.618.074 | 1.385.514.110 | 1.385.516.733 | 1.385.523.702 | 1.385.578.511 |
34 | 17.179.869.184 | 11.109.315.463 | 5.627.199.350 | 5.482.116.113 | 2.777.299.062 | 2.777.332.266 | 2.777.304.798 | 2.777.379.337 |