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+40x-47
f(0)=47
f(1)=3
f(2)=37
f(3)=41
f(4)=43
f(5)=89
f(6)=229
f(7)=1
f(8)=337
f(9)=197
f(10)=151
f(11)=257
f(12)=577
f(13)=107
f(14)=709
f(15)=389
f(16)=283
f(17)=461
f(18)=997
f(19)=179
f(20)=1153
f(21)=617
f(22)=439
f(23)=701
f(24)=1489
f(25)=263
f(26)=1669
f(27)=881
f(28)=619
f(29)=977
f(30)=2053
f(31)=359
f(32)=61
f(33)=1181
f(34)=823
f(35)=1289
f(36)=2689
f(37)=467
f(38)=2917
f(39)=1
f(40)=1051
f(41)=1637
f(42)=79
f(43)=587
f(44)=1
f(45)=1889
f(46)=1303
f(47)=1
f(48)=4177
f(49)=719
f(50)=73
f(51)=2297
f(52)=1579
f(53)=2441
f(54)=1
f(55)=863
f(56)=1
f(57)=2741
f(58)=1879
f(59)=2897
f(60)=5953
f(61)=1019
f(62)=6277
f(63)=3221
f(64)=2203
f(65)=3389
f(66)=6949
f(67)=1187
f(68)=7297
f(69)=101
f(70)=2551
f(71)=3917
f(72)=8017
f(73)=1367
f(74)=8389
f(75)=4289
f(76)=1
f(77)=4481
f(78)=9157
f(79)=1559
f(80)=233
f(81)=4877
f(82)=3319
f(83)=5081
f(84)=10369
f(85)=1
f(86)=10789
f(87)=5501
f(88)=3739
f(89)=5717
f(90)=271
f(91)=1979
f(92)=12097
f(93)=1
f(94)=1
f(95)=6389
f(96)=13009
f(97)=2207
f(98)=13477
f(99)=6857
b) Substitution of the polynom
The polynom f(x)=x^2+40x-47 could be written as f(y)= y^2-447 with x=y-20
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+20
f'(x)>2x+39
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 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 87 | 26 | 61 | 0.870000 | 0.260000 | 0.870000 | 8.700000 | 6.500000 | 10.166667 |
3 | 1.000 | 804 | 170 | 634 | 0.804000 | 0.170000 | 0.804000 | 9.241380 | 6.538462 | 10.393442 |
4 | 10.000 | 7.739 | 1.269 | 6.470 | 0.773900 | 0.126900 | 0.773900 | 9.625622 | 7.464706 | 10.205048 |
5 | 100.000 | 75.546 | 9.721 | 65.825 | 0.755460 | 0.097210 | 0.755460 | 9.761726 | 7.660363 | 10.173880 |
6 | 1.000.000 | 744.253 | 79.365 | 664.888 | 0.744253 | 0.079365 | 0.744253 | 9.851653 | 8.164284 | 10.100843 |
7 | 10.000.000 | 7.363.713 | 672.251 | 6.691.462 | 0.736371 | 0.067225 | 0.736371 | 9.894099 | 8.470371 | 10.064044 |
8 | 100.000.000 | 73.076.480 | 5.824.228 | 67.252.252 | 0.730765 | 0.058242 | 0.730765 | 9.923863 | 8.663770 | 10.050458 |
9 | 1.000.000.000 | 726.386.540 | 51.381.997 | 675.004.543 | 0.726387 | 0.051382 | 0.726387 | 9.940087 | 8.822113 | 10.036905 |
10 | 10.000.000.000 | 7.229.081.703 | 459.830.003 | 6.769.251.700 | 0.722908 | 0.045983 | 0.722908 | 9.952114 | 8.949244 | 10.028454 |
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 | 2 | 1 | 1.500000 | 1.000000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 2.000000 | 1.333333 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.500000 | 2.500000 |
5 | 32 | 31 | 11 | 20 | 0.968750 | 0.343750 | 0.625000 | 1.937500 | 1.833333 | 2.000000 |
6 | 64 | 56 | 16 | 40 | 0.875000 | 0.250000 | 0.625000 | 1.806452 | 1.454545 | 2.000000 |
7 | 128 | 108 | 33 | 75 | 0.843750 | 0.257812 | 0.585938 | 1.928571 | 2.062500 | 1.875000 |
8 | 256 | 210 | 55 | 155 | 0.820312 | 0.214844 | 0.605469 | 1.944444 | 1.666667 | 2.066667 |
9 | 512 | 417 | 100 | 317 | 0.814453 | 0.195312 | 0.619141 | 1.985714 | 1.818182 | 2.045161 |
10 | 1.024 | 821 | 176 | 645 | 0.801758 | 0.171875 | 0.629883 | 1.968825 | 1.760000 | 2.034700 |
11 | 2.048 | 1.633 | 322 | 1.311 | 0.797363 | 0.157227 | 0.640137 | 1.989038 | 1.829545 | 2.032558 |
12 | 4.096 | 3.220 | 584 | 2.636 | 0.786133 | 0.142578 | 0.643555 | 1.971831 | 1.813665 | 2.010679 |
13 | 8.192 | 6.363 | 1.083 | 5.280 | 0.776733 | 0.132202 | 0.644531 | 1.976087 | 1.854452 | 2.003035 |
14 | 16.384 | 12.595 | 1.944 | 10.651 | 0.768738 | 0.118652 | 0.650085 | 1.979412 | 1.795014 | 2.017235 |
15 | 32.768 | 24.969 | 3.599 | 21.370 | 0.761993 | 0.109833 | 0.652161 | 1.982453 | 1.851337 | 2.006384 |
16 | 65.536 | 49.660 | 6.654 | 43.006 | 0.757751 | 0.101532 | 0.656219 | 1.988866 | 1.848847 | 2.012447 |
17 | 131.072 | 98.853 | 12.395 | 86.458 | 0.754189 | 0.094566 | 0.659622 | 1.990596 | 1.862789 | 2.010371 |
18 | 262.144 | 196.725 | 23.210 | 173.515 | 0.750446 | 0.088539 | 0.661907 | 1.990076 | 1.872529 | 2.006928 |
19 | 524.288 | 391.729 | 43.757 | 347.972 | 0.747164 | 0.083460 | 0.663704 | 1.991252 | 1.885265 | 2.005429 |
20 | 1.048.576 | 780.182 | 82.917 | 697.265 | 0.744040 | 0.079076 | 0.664964 | 1.991637 | 1.894943 | 2.003796 |
21 | 2.097.152 | 1.554.791 | 157.417 | 1.397.374 | 0.741382 | 0.075062 | 0.666320 | 1.992857 | 1.898489 | 2.004079 |
22 | 4.194.304 | 3.099.871 | 299.226 | 2.800.645 | 0.739067 | 0.071341 | 0.667726 | 1.993754 | 1.900849 | 2.004220 |
23 | 8.388.608 | 6.181.585 | 570.745 | 5.610.840 | 0.736902 | 0.068038 | 0.668864 | 1.994143 | 1.907404 | 2.003410 |
24 | 16.777.216 | 12.331.063 | 1.090.091 | 11.240.972 | 0.734989 | 0.064974 | 0.670014 | 1.994806 | 1.909944 | 2.003438 |
25 | 33.554.432 | 24.603.136 | 2.085.848 | 22.517.288 | 0.733231 | 0.062163 | 0.671067 | 1.995216 | 1.913462 | 2.003144 |
26 | 67.108.864 | 49.099.546 | 3.999.671 | 45.099.875 | 0.731640 | 0.059600 | 0.672041 | 1.995662 | 1.917528 | 2.002900 |
27 | 134.217.728 | 97.997.730 | 7.685.140 | 90.312.590 | 0.730140 | 0.057259 | 0.672881 | 1.995899 | 1.921443 | 2.002502 |
28 | 268.435.456 | 195.625.004 | 14.787.875 | 180.837.129 | 0.728760 | 0.055089 | 0.673671 | 1.996220 | 1.924217 | 2.002347 |
29 | 536.870.912 | 390.555.802 | 28.486.986 | 362.068.816 | 0.727467 | 0.053061 | 0.674406 | 1.996451 | 1.926375 | 2.002182 |
30 | 1.073.741.824 | 779.822.952 | 54.972.553 | 724.850.399 | 0.726267 | 0.051197 | 0.675070 | 1.996701 | 1.929743 | 2.001969 |
31 | 2.147.483.648 | 1.557.238.403 | 106.198.152 | 1.451.040.251 | 0.725146 | 0.049452 | 0.675693 | 1.996913 | 1.931840 | 2.001848 |
32 | 4.294.967.296 | 3.109.971.875 | 205.421.098 | 2.904.550.777 | 0.724097 | 0.047828 | 0.676268 | 1.997107 | 1.934319 | 2.001702 |
33 | 8.589.934.592 | 6.211.509.154 | 397.762.685 | 5.813.746.469 | 0.723115 | 0.046306 | 0.676809 | 1.997288 | 1.936328 | 2.001599 |
34 | 17.179.869.184 | 12.407.234.049 | 770.920.197 | 11.636.313.852 | 0.722196 | 0.044873 | 0.677323 | 1.997459 | 1.938141 | 2.001517 |
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 | 0 | 1 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 3 | 1 | 1 | 0 | 2 | 1 |
4 | 16 | 6 | 5 | 1 | 2 | 0 | 3 | 1 |
5 | 32 | 11 | 10 | 1 | 4 | 0 | 6 | 1 |
6 | 64 | 16 | 15 | 1 | 7 | 0 | 8 | 1 |
7 | 128 | 33 | 32 | 1 | 15 | 0 | 17 | 1 |
8 | 256 | 55 | 54 | 1 | 27 | 0 | 27 | 1 |
9 | 512 | 100 | 99 | 1 | 49 | 0 | 50 | 1 |
10 | 1.024 | 176 | 175 | 1 | 88 | 0 | 87 | 1 |
11 | 2.048 | 322 | 321 | 1 | 161 | 0 | 160 | 1 |
12 | 4.096 | 584 | 583 | 1 | 286 | 0 | 297 | 1 |
13 | 8.192 | 1.083 | 1.082 | 1 | 535 | 0 | 547 | 1 |
14 | 16.384 | 1.944 | 1.943 | 1 | 969 | 0 | 974 | 1 |
15 | 32.768 | 3.599 | 3.598 | 1 | 1.799 | 0 | 1.799 | 1 |
16 | 65.536 | 6.654 | 6.653 | 1 | 3.307 | 0 | 3.346 | 1 |
17 | 131.072 | 12.395 | 12.394 | 1 | 6.150 | 0 | 6.244 | 1 |
18 | 262.144 | 23.210 | 23.209 | 1 | 11.625 | 0 | 11.584 | 1 |
19 | 524.288 | 43.757 | 43.756 | 1 | 21.885 | 0 | 21.871 | 1 |
20 | 1.048.576 | 82.917 | 82.916 | 1 | 41.355 | 0 | 41.561 | 1 |
21 | 2.097.152 | 157.417 | 157.416 | 1 | 78.585 | 0 | 78.831 | 1 |
22 | 4.194.304 | 299.226 | 299.225 | 1 | 149.601 | 0 | 149.624 | 1 |
23 | 8.388.608 | 570.745 | 570.744 | 1 | 285.353 | 0 | 285.391 | 1 |
24 | 16.777.216 | 1.090.091 | 1.090.090 | 1 | 545.069 | 0 | 545.021 | 1 |
25 | 33.554.432 | 2.085.848 | 2.085.847 | 1 | 1.043.453 | 0 | 1.042.394 | 1 |
26 | 67.108.864 | 3.999.671 | 3.999.670 | 1 | 2.000.633 | 0 | 1.999.037 | 1 |
27 | 134.217.728 | 7.685.140 | 7.685.139 | 1 | 3.843.133 | 0 | 3.842.006 | 1 |
28 | 268.435.456 | 14.787.875 | 14.787.874 | 1 | 7.393.606 | 0 | 7.394.268 | 1 |
29 | 536.870.912 | 28.486.986 | 28.486.985 | 1 | 14.242.761 | 0 | 14.244.224 | 1 |
30 | 1.073.741.824 | 54.972.553 | 54.972.552 | 1 | 27.485.786 | 0 | 27.486.766 | 1 |
31 | 2.147.483.648 | 106.198.152 | 106.198.151 | 1 | 53.100.600 | 0 | 53.097.551 | 1 |
32 | 4.294.967.296 | 205.421.098 | 205.421.097 | 1 | 102.713.389 | 0 | 102.707.708 | 1 |
33 | 8.589.934.592 | 397.762.685 | 397.762.684 | 1 | 198.883.658 | 0 | 198.879.026 | 1 |
34 | 17.179.869.184 | 770.920.197 | 770.920.196 | 1 | 385.461.507 | 0 | 385.458.689 | 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 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 1 | 1 | 2 | 0 | 0 |
3 | 8 | 4 | 1 | 2 | 2 | 2 | 0 | 0 |
4 | 16 | 10 | 3 | 6 | 3 | 4 | 2 | 1 |
5 | 32 | 20 | 5 | 14 | 6 | 6 | 4 | 4 |
6 | 64 | 40 | 11 | 28 | 11 | 12 | 8 | 9 |
7 | 128 | 75 | 20 | 54 | 19 | 21 | 17 | 18 |
8 | 256 | 155 | 45 | 109 | 38 | 41 | 38 | 38 |
9 | 512 | 317 | 106 | 210 | 81 | 83 | 80 | 73 |
10 | 1.024 | 645 | 224 | 420 | 151 | 168 | 169 | 157 |
11 | 2.048 | 1.311 | 476 | 834 | 310 | 333 | 335 | 333 |
12 | 4.096 | 2.636 | 1.001 | 1.634 | 619 | 683 | 671 | 663 |
13 | 8.192 | 5.280 | 2.057 | 3.222 | 1.274 | 1.353 | 1.343 | 1.310 |
14 | 16.384 | 10.651 | 4.256 | 6.394 | 2.619 | 2.686 | 2.665 | 2.681 |
15 | 32.768 | 21.370 | 8.738 | 12.631 | 5.253 | 5.381 | 5.307 | 5.429 |
16 | 65.536 | 43.006 | 17.952 | 25.053 | 10.647 | 10.810 | 10.673 | 10.876 |
17 | 131.072 | 86.458 | 36.664 | 49.793 | 21.362 | 21.744 | 21.389 | 21.963 |
18 | 262.144 | 173.515 | 74.660 | 98.854 | 42.975 | 43.711 | 43.017 | 43.812 |
19 | 524.288 | 347.972 | 151.008 | 196.963 | 86.154 | 87.407 | 86.734 | 87.677 |
20 | 1.048.576 | 697.265 | 305.315 | 391.949 | 172.835 | 175.293 | 173.957 | 175.180 |
21 | 2.097.152 | 1.397.374 | 617.132 | 780.241 | 347.155 | 351.147 | 347.948 | 351.124 |
22 | 4.194.304 | 2.800.645 | 1.244.601 | 1.556.043 | 695.516 | 703.896 | 697.942 | 703.291 |
23 | 8.388.608 | 5.610.840 | 2.509.334 | 3.101.505 | 1.395.673 | 1.409.004 | 1.398.021 | 1.408.142 |
24 | 16.777.216 | 11.240.972 | 5.055.891 | 6.185.080 | 2.798.694 | 2.820.976 | 2.799.898 | 2.821.404 |
25 | 33.554.432 | 22.517.288 | 10.181.691 | 12.335.596 | 5.609.422 | 5.647.882 | 5.610.234 | 5.649.750 |
26 | 67.108.864 | 45.099.875 | 20.486.427 | 24.613.447 | 11.239.855 | 11.310.764 | 11.240.945 | 11.308.311 |
27 | 134.217.728 | 90.312.590 | 41.198.353 | 49.114.236 | 22.513.276 | 22.642.445 | 22.513.354 | 22.643.515 |
28 | 268.435.456 | 180.837.129 | 82.809.279 | 98.027.849 | 45.094.196 | 45.326.898 | 45.087.841 | 45.328.194 |
29 | 536.870.912 | 362.068.816 | 166.397.105 | 195.671.710 | 90.290.666 | 90.743.031 | 90.289.561 | 90.745.558 |
30 | 1.073.741.824 | 724.850.399 | 334.206.081 | 390.644.317 | 180.791.958 | 181.626.062 | 180.795.429 | 181.636.950 |
31 | 2.147.483.648 | 1.451.040.251 | 671.023.352 | 780.016.898 | 361.975.750 | 363.537.718 | 361.973.713 | 363.553.070 |
32 | 4.294.967.296 | 2.904.550.777 | 1.346.969.994 | 1.557.580.782 | 724.648.004 | 727.606.669 | 724.665.185 | 727.630.919 |
33 | 8.589.934.592 | 5.813.746.469 | 2.703.145.720 | 3.110.600.748 | 1.450.621.783 | 1.456.212.004 | 1.450.665.205 | 1.456.247.477 |
34 | 17.179.869.184 | 11.636.313.852 | 5.423.628.784 | 6.212.685.067 | 2.903.727.106 | 2.914.360.178 | 2.903.891.410 | 2.914.335.158 |