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+21x-5
f(0)=5
f(1)=17
f(2)=41
f(3)=67
f(4)=19
f(5)=1
f(6)=157
f(7)=191
f(8)=227
f(9)=53
f(10)=61
f(11)=347
f(12)=23
f(13)=1
f(14)=97
f(15)=107
f(16)=587
f(17)=641
f(18)=1
f(19)=151
f(20)=163
f(21)=877
f(22)=941
f(23)=1
f(24)=43
f(25)=229
f(26)=1217
f(27)=1291
f(28)=1367
f(29)=1
f(30)=1
f(31)=1607
f(32)=89
f(33)=1777
f(34)=373
f(35)=1
f(36)=1
f(37)=2141
f(38)=2237
f(39)=467
f(40)=487
f(41)=59
f(42)=139
f(43)=1
f(44)=571
f(45)=593
f(46)=181
f(47)=3191
f(48)=3307
f(49)=137
f(50)=709
f(51)=193
f(52)=223
f(53)=3917
f(54)=809
f(55)=167
f(56)=73
f(57)=4441
f(58)=199
f(59)=1
f(60)=971
f(61)=263
f(62)=1
f(63)=311
f(64)=1087
f(65)=1117
f(66)=5737
f(67)=1
f(68)=6047
f(69)=1
f(70)=1
f(71)=1
f(72)=6691
f(73)=6857
f(74)=281
f(75)=1439
f(76)=1
f(77)=7541
f(78)=7717
f(79)=1579
f(80)=1
f(81)=359
f(82)=367
f(83)=8627
f(84)=1
f(85)=1801
f(86)=541
f(87)=9391
f(88)=9587
f(89)=103
f(90)=1997
f(91)=1
f(92)=10391
f(93)=10597
f(94)=2161
f(95)=2203
f(96)=109
f(97)=673
f(98)=11657
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+21x-5 could be written as f(y)= y^2-115.25 with x=y-10.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+10.5
f'(x)>2x+20
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 | 7 | 3 | 1.000000 | 0.700000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 74 | 35 | 39 | 0.740000 | 0.350000 | 0.390000 | 7.400000 | 5.000000 | 13.000000 |
3 | 1.000 | 711 | 232 | 479 | 0.711000 | 0.232000 | 0.479000 | 9.608109 | 6.628572 | 12.282051 |
4 | 10.000 | 7.127 | 1.646 | 5.481 | 0.712700 | 0.164600 | 0.548100 | 10.023910 | 7.094828 | 11.442589 |
5 | 100.000 | 70.972 | 12.673 | 58.299 | 0.709720 | 0.126730 | 0.582990 | 9.958187 | 7.699271 | 10.636562 |
6 | 1.000.000 | 706.646 | 103.108 | 603.538 | 0.706646 | 0.103108 | 0.603538 | 9.956687 | 8.136037 | 10.352459 |
7 | 10.000.000 | 7.045.768 | 873.693 | 6.172.075 | 0.704577 | 0.087369 | 0.617208 | 9.970718 | 8.473572 | 10.226489 |
8 | 100.000.000 | 70.300.829 | 7.572.785 | 62.728.044 | 0.703008 | 0.075728 | 0.627280 | 9.977738 | 8.667559 | 10.163202 |
9 | 1.000.000.000 | 701.794.127 | 66.811.132 | 634.982.995 | 0.701794 | 0.066811 | 0.634983 | 9.982728 | 8.822531 | 10.122792 |
10 | 10.000.000.000 | 7.008.364.583 | 597.929.330 | 6.410.435.253 | 0.700836 | 0.059793 | 0.641043 | 9.986354 | 8.949547 | 10.095444 |
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 | 25 | 16 | 9 | 0.781250 | 0.500000 | 0.281250 | 1.785714 | 1.777778 | 1.800000 |
6 | 64 | 50 | 23 | 27 | 0.781250 | 0.359375 | 0.421875 | 2.000000 | 1.437500 | 3.000000 |
7 | 128 | 90 | 44 | 46 | 0.703125 | 0.343750 | 0.359375 | 1.800000 | 1.913043 | 1.703704 |
8 | 256 | 181 | 73 | 108 | 0.707031 | 0.285156 | 0.421875 | 2.011111 | 1.659091 | 2.347826 |
9 | 512 | 365 | 131 | 234 | 0.712891 | 0.255859 | 0.457031 | 2.016575 | 1.794520 | 2.166667 |
10 | 1.024 | 725 | 236 | 489 | 0.708008 | 0.230469 | 0.477539 | 1.986301 | 1.801527 | 2.089744 |
11 | 2.048 | 1.458 | 416 | 1.042 | 0.711914 | 0.203125 | 0.508789 | 2.011034 | 1.762712 | 2.130879 |
12 | 4.096 | 2.925 | 738 | 2.187 | 0.714111 | 0.180176 | 0.533936 | 2.006173 | 1.774038 | 2.098848 |
13 | 8.192 | 5.845 | 1.375 | 4.470 | 0.713501 | 0.167847 | 0.545654 | 1.998291 | 1.863144 | 2.043896 |
14 | 16.384 | 11.670 | 2.542 | 9.128 | 0.712280 | 0.155151 | 0.557129 | 1.996578 | 1.848727 | 2.042058 |
15 | 32.768 | 23.302 | 4.710 | 18.592 | 0.711121 | 0.143738 | 0.567383 | 1.996744 | 1.852872 | 2.036810 |
16 | 65.536 | 46.546 | 8.666 | 37.880 | 0.710236 | 0.132233 | 0.578003 | 1.997511 | 1.839915 | 2.037436 |
17 | 131.072 | 93.012 | 16.157 | 76.855 | 0.709625 | 0.123268 | 0.586357 | 1.998281 | 1.864413 | 2.028907 |
18 | 262.144 | 185.752 | 30.199 | 155.553 | 0.708588 | 0.115200 | 0.593388 | 1.997076 | 1.869097 | 2.023980 |
19 | 524.288 | 371.028 | 56.998 | 314.030 | 0.707680 | 0.108715 | 0.598965 | 1.997437 | 1.887414 | 2.018797 |
20 | 1.048.576 | 740.876 | 107.777 | 633.099 | 0.706554 | 0.102784 | 0.603770 | 1.996820 | 1.890891 | 2.016046 |
21 | 2.097.152 | 1.480.278 | 204.502 | 1.275.776 | 0.705852 | 0.097514 | 0.608337 | 1.998011 | 1.897455 | 2.015129 |
22 | 4.194.304 | 2.958.077 | 389.238 | 2.568.839 | 0.705261 | 0.092802 | 0.612459 | 1.998325 | 1.903346 | 2.013550 |
23 | 8.388.608 | 5.911.517 | 741.592 | 5.169.925 | 0.704708 | 0.088405 | 0.616303 | 1.998432 | 1.905241 | 2.012553 |
24 | 16.777.216 | 11.814.484 | 1.416.641 | 10.397.843 | 0.704198 | 0.084438 | 0.619760 | 1.998554 | 1.910270 | 2.011217 |
25 | 33.554.432 | 23.611.693 | 2.711.909 | 20.899.784 | 0.703683 | 0.080821 | 0.622862 | 1.998538 | 1.914323 | 2.010011 |
26 | 67.108.864 | 47.194.545 | 5.201.747 | 41.992.798 | 0.703254 | 0.077512 | 0.625741 | 1.998779 | 1.918113 | 2.009246 |
27 | 134.217.728 | 94.334.318 | 9.991.485 | 84.342.833 | 0.702845 | 0.074442 | 0.628403 | 1.998839 | 1.920794 | 2.008507 |
28 | 268.435.456 | 188.562.277 | 19.225.224 | 169.337.053 | 0.702449 | 0.071620 | 0.630830 | 1.998872 | 1.924161 | 2.007723 |
29 | 536.870.912 | 376.935.722 | 37.046.238 | 339.889.484 | 0.702097 | 0.069004 | 0.633093 | 1.998999 | 1.926960 | 2.007177 |
30 | 1.073.741.824 | 753.512.047 | 71.478.900 | 682.033.147 | 0.701763 | 0.066570 | 0.635193 | 1.999047 | 1.929451 | 2.006632 |
31 | 2.147.483.648 | 1.506.347.406 | 138.096.387 | 1.368.251.019 | 0.701448 | 0.064306 | 0.637142 | 1.999102 | 1.931988 | 2.006136 |
32 | 4.294.967.296 | 3.011.458.534 | 267.113.243 | 2.744.345.291 | 0.701160 | 0.062192 | 0.638968 | 1.999179 | 1.934252 | 2.005732 |
33 | 8.589.934.592 | 6.020.623.976 | 517.207.619 | 5.503.416.357 | 0.700893 | 0.060211 | 0.640682 | 1.999238 | 1.936286 | 2.005366 |
34 | 17.179.869.184 | 12.036.917.470 | 1.002.471.366 | 11.034.446.104 | 0.700641 | 0.058352 | 0.642289 | 1.999281 | 1.938238 | 2.005018 |
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 | 0 | 3 | 2 | 0 | 1 | 0 |
2 | 4 | 4 | 1 | 3 | 2 | 1 | 1 | 0 |
3 | 8 | 7 | 2 | 5 | 2 | 2 | 2 | 1 |
4 | 16 | 9 | 2 | 7 | 2 | 4 | 2 | 1 |
5 | 32 | 16 | 4 | 12 | 4 | 5 | 4 | 3 |
6 | 64 | 23 | 7 | 16 | 6 | 6 | 7 | 4 |
7 | 128 | 44 | 16 | 28 | 11 | 12 | 13 | 8 |
8 | 256 | 73 | 25 | 48 | 16 | 17 | 21 | 19 |
9 | 512 | 131 | 39 | 92 | 31 | 29 | 35 | 36 |
10 | 1.024 | 236 | 76 | 160 | 56 | 60 | 57 | 63 |
11 | 2.048 | 416 | 136 | 280 | 107 | 110 | 94 | 105 |
12 | 4.096 | 738 | 247 | 491 | 183 | 191 | 184 | 180 |
13 | 8.192 | 1.375 | 457 | 918 | 342 | 355 | 340 | 338 |
14 | 16.384 | 2.542 | 837 | 1.705 | 658 | 641 | 609 | 634 |
15 | 32.768 | 4.710 | 1.574 | 3.136 | 1.193 | 1.189 | 1.177 | 1.151 |
16 | 65.536 | 8.666 | 2.889 | 5.777 | 2.160 | 2.174 | 2.191 | 2.141 |
17 | 131.072 | 16.157 | 5.380 | 10.777 | 3.968 | 4.062 | 4.129 | 3.998 |
18 | 262.144 | 30.199 | 10.066 | 20.133 | 7.547 | 7.557 | 7.644 | 7.451 |
19 | 524.288 | 56.998 | 19.078 | 37.920 | 14.258 | 14.200 | 14.378 | 14.162 |
20 | 1.048.576 | 107.777 | 35.967 | 71.810 | 26.960 | 26.893 | 27.070 | 26.854 |
21 | 2.097.152 | 204.502 | 68.192 | 136.310 | 51.092 | 51.067 | 51.288 | 51.055 |
22 | 4.194.304 | 389.238 | 129.944 | 259.294 | 97.197 | 97.147 | 97.474 | 97.420 |
23 | 8.388.608 | 741.592 | 247.511 | 494.081 | 185.451 | 185.387 | 185.234 | 185.520 |
24 | 16.777.216 | 1.416.641 | 472.508 | 944.133 | 353.989 | 354.456 | 354.130 | 354.066 |
25 | 33.554.432 | 2.711.909 | 904.314 | 1.807.595 | 677.838 | 678.506 | 677.542 | 678.023 |
26 | 67.108.864 | 5.201.747 | 1.733.367 | 3.468.380 | 1.299.448 | 1.301.660 | 1.299.502 | 1.301.137 |
27 | 134.217.728 | 9.991.485 | 3.329.008 | 6.662.477 | 2.496.641 | 2.498.504 | 2.497.682 | 2.498.658 |
28 | 268.435.456 | 19.225.224 | 6.408.104 | 12.817.120 | 4.805.285 | 4.807.115 | 4.805.372 | 4.807.452 |
29 | 536.870.912 | 37.046.238 | 12.350.238 | 24.696.000 | 9.262.828 | 9.261.699 | 9.259.257 | 9.262.454 |
30 | 1.073.741.824 | 71.478.900 | 23.827.732 | 47.651.168 | 17.871.368 | 17.870.127 | 17.864.567 | 17.872.838 |
31 | 2.147.483.648 | 138.096.387 | 46.034.457 | 92.061.930 | 34.526.689 | 34.524.520 | 34.517.609 | 34.527.569 |
32 | 4.294.967.296 | 267.113.243 | 89.037.679 | 178.075.564 | 66.781.551 | 66.781.001 | 66.775.352 | 66.775.339 |
33 | 8.589.934.592 | 517.207.619 | 172.394.646 | 344.812.973 | 129.298.356 | 129.300.853 | 129.304.131 | 129.304.279 |
34 | 17.179.869.184 | 1.002.471.366 | 334.151.496 | 668.319.870 | 250.611.187 | 250.618.291 | 250.625.664 | 250.616.224 |
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 | 1 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 5 | 3 | 2 | 1 | 2 | 2 | 0 |
5 | 32 | 9 | 6 | 3 | 2 | 3 | 3 | 1 |
6 | 64 | 27 | 16 | 11 | 6 | 7 | 6 | 8 |
7 | 128 | 46 | 29 | 17 | 11 | 10 | 11 | 14 |
8 | 256 | 108 | 63 | 45 | 23 | 28 | 27 | 30 |
9 | 512 | 234 | 128 | 106 | 50 | 67 | 56 | 61 |
10 | 1.024 | 489 | 263 | 226 | 115 | 120 | 121 | 133 |
11 | 2.048 | 1.042 | 545 | 497 | 260 | 240 | 266 | 276 |
12 | 4.096 | 2.187 | 1.153 | 1.034 | 540 | 532 | 549 | 566 |
13 | 8.192 | 4.470 | 2.342 | 2.128 | 1.116 | 1.094 | 1.123 | 1.137 |
14 | 16.384 | 9.128 | 4.776 | 4.352 | 2.273 | 2.250 | 2.300 | 2.305 |
15 | 32.768 | 18.592 | 9.672 | 8.920 | 4.648 | 4.571 | 4.663 | 4.710 |
16 | 65.536 | 37.880 | 19.552 | 18.328 | 9.533 | 9.363 | 9.473 | 9.511 |
17 | 131.072 | 76.855 | 39.677 | 37.178 | 19.259 | 19.201 | 19.159 | 19.236 |
18 | 262.144 | 155.553 | 80.123 | 75.430 | 38.864 | 39.017 | 38.803 | 38.869 |
19 | 524.288 | 314.030 | 161.841 | 152.189 | 78.245 | 78.543 | 78.604 | 78.638 |
20 | 1.048.576 | 633.099 | 325.841 | 307.258 | 157.986 | 158.212 | 158.450 | 158.451 |
21 | 2.097.152 | 1.275.776 | 654.936 | 620.840 | 317.922 | 319.141 | 319.350 | 319.363 |
22 | 4.194.304 | 2.568.839 | 1.317.225 | 1.251.614 | 640.450 | 643.588 | 642.485 | 642.316 |
23 | 8.388.608 | 5.169.925 | 2.646.787 | 2.523.138 | 1.291.251 | 1.293.942 | 1.292.429 | 1.292.303 |
24 | 16.777.216 | 10.397.843 | 5.317.197 | 5.080.646 | 2.596.678 | 2.601.604 | 2.600.064 | 2.599.497 |
25 | 33.554.432 | 20.899.784 | 10.674.009 | 10.225.775 | 5.222.565 | 5.227.638 | 5.227.002 | 5.222.579 |
26 | 67.108.864 | 41.992.798 | 21.429.075 | 20.563.723 | 10.496.768 | 10.500.754 | 10.501.445 | 10.493.831 |
27 | 134.217.728 | 84.342.833 | 42.999.438 | 41.343.395 | 21.080.285 | 21.088.100 | 21.088.325 | 21.086.123 |
28 | 268.435.456 | 169.337.053 | 86.256.806 | 83.080.247 | 42.322.838 | 42.335.653 | 42.343.448 | 42.335.114 |
29 | 536.870.912 | 339.889.484 | 173.007.339 | 166.882.145 | 84.964.325 | 84.968.807 | 84.977.441 | 84.978.911 |
30 | 1.073.741.824 | 682.033.147 | 346.924.253 | 335.108.894 | 170.507.786 | 170.507.399 | 170.506.691 | 170.511.271 |
31 | 2.147.483.648 | 1.368.251.019 | 695.518.117 | 672.732.902 | 342.055.949 | 342.064.929 | 342.053.314 | 342.076.827 |
32 | 4.294.967.296 | 2.744.345.291 | 1.394.216.718 | 1.350.128.573 | 686.068.401 | 686.087.307 | 686.097.836 | 686.091.747 |
33 | 8.589.934.592 | 5.503.416.357 | 2.794.344.470 | 2.709.071.887 | 1.375.875.898 | 1.375.881.260 | 1.375.857.192 | 1.375.802.007 |
34 | 17.179.869.184 | 11.034.446.104 | 5.599.786.771 | 5.434.659.333 | 2.758.651.022 | 2.758.656.675 | 2.758.568.936 | 2.758.569.471 |