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-188x+139
f(0)=139
f(1)=3
f(2)=233
f(3)=13
f(4)=199
f(5)=97
f(6)=953
f(7)=47
f(8)=1301
f(9)=23
f(10)=547
f(11)=113
f(12)=1973
f(13)=89
f(14)=2297
f(15)=307
f(16)=67
f(17)=173
f(18)=127
f(19)=1
f(20)=3221
f(21)=421
f(22)=1171
f(23)=457
f(24)=3797
f(25)=41
f(26)=4073
f(27)=263
f(28)=1447
f(29)=43
f(30)=107
f(31)=197
f(32)=211
f(33)=311
f(34)=1699
f(35)=163
f(36)=5333
f(37)=227
f(38)=83
f(39)=709
f(40)=1
f(41)=1
f(42)=461
f(43)=1
f(44)=6197
f(45)=787
f(46)=2131
f(47)=811
f(48)=6581
f(49)=1
f(50)=6761
f(51)=1
f(52)=2311
f(53)=877
f(54)=151
f(55)=1
f(56)=7253
f(57)=229
f(58)=2467
f(59)=467
f(60)=7541
f(61)=317
f(62)=7673
f(63)=967
f(64)=1
f(65)=491
f(66)=193
f(67)=1
f(68)=617
f(69)=1009
f(70)=2707
f(71)=1021
f(72)=191
f(73)=1
f(74)=8297
f(75)=521
f(76)=2791
f(77)=1051
f(78)=367
f(79)=353
f(80)=8501
f(81)=1
f(82)=2851
f(83)=1
f(84)=8597
f(85)=359
f(86)=1
f(87)=1
f(88)=2887
f(89)=271
f(90)=8681
f(91)=181
f(92)=8693
f(93)=1087
f(94)=223
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-188x+139 could be written as f(y)= y^2-8697 with x=y+94
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-94
f'(x)>2x-189 with x > 93
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 | 11 | 4 | 7 | 1.100000 | 0.400000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 83 | 23 | 60 | 0.830000 | 0.230000 | 0.830000 | 7.545455 | 5.750000 | 8.571428 |
3 | 1.000 | 913 | 321 | 592 | 0.913000 | 0.321000 | 0.913000 | 11.000000 | 13.956522 | 9.866667 |
4 | 10.000 | 9.885 | 3.320 | 6.565 | 0.988500 | 0.332000 | 0.988500 | 10.826944 | 10.342679 | 11.089527 |
5 | 100.000 | 99.848 | 33.309 | 66.539 | 0.998480 | 0.333090 | 0.998480 | 10.100961 | 10.032831 | 10.135415 |
6 | 1.000.000 | 999.803 | 333.206 | 666.597 | 0.999803 | 0.333206 | 0.999803 | 10.013250 | 10.003483 | 10.018140 |
7 | 10.000.000 | 9.999.760 | 3.332.171 | 6.667.589 | 0.999976 | 0.333217 | 0.999976 | 10.001730 | 10.000333 | 10.002429 |
8 | 100.000.000 | 99.999.715 | 33.321.823 | 66.677.892 | 0.999997 | 0.333218 | 0.999997 | 10.000211 | 10.000034 | 10.000300 |
9 | 1.000.000.000 | 999.999.669 | 333.218.339 | 666.781.330 | 1.000000 | 0.333218 | 1.000000 | 10.000026 | 10.000003 | 10.000036 |
10 | 10.000.000.000 | 9.999.999.625 | 3.332.183.498 | 6.667.816.127 | 1.000000 | 0.333218 | 1.000000 | 10.000003 | 10.000001 | 10.000004 |
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 | 9 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 2.000000 | 1.666667 |
4 | 16 | 17 | 6 | 11 | 1.062500 | 0.375000 | 0.687500 | 1.888889 | 1.500000 | 2.200000 |
5 | 32 | 30 | 9 | 21 | 0.937500 | 0.281250 | 0.656250 | 1.764706 | 1.500000 | 1.909091 |
6 | 64 | 55 | 16 | 39 | 0.859375 | 0.250000 | 0.609375 | 1.833333 | 1.777778 | 1.857143 |
7 | 128 | 108 | 33 | 75 | 0.843750 | 0.257812 | 0.585938 | 1.963636 | 2.062500 | 1.923077 |
8 | 256 | 191 | 73 | 118 | 0.746094 | 0.285156 | 0.460938 | 1.768519 | 2.212121 | 1.573333 |
9 | 512 | 433 | 159 | 274 | 0.845703 | 0.310547 | 0.535156 | 2.267016 | 2.178082 | 2.322034 |
10 | 1.024 | 937 | 329 | 608 | 0.915039 | 0.321289 | 0.593750 | 2.163972 | 2.069182 | 2.218978 |
11 | 2.048 | 1.955 | 671 | 1.284 | 0.954590 | 0.327637 | 0.626953 | 2.086446 | 2.039514 | 2.111842 |
12 | 4.096 | 3.992 | 1.353 | 2.639 | 0.974609 | 0.330322 | 0.644287 | 2.041944 | 2.016393 | 2.055296 |
13 | 8.192 | 8.079 | 2.718 | 5.361 | 0.986206 | 0.331787 | 0.654419 | 2.023798 | 2.008869 | 2.031451 |
14 | 16.384 | 16.262 | 5.447 | 10.815 | 0.992554 | 0.332458 | 0.660095 | 2.012873 | 2.004047 | 2.017348 |
15 | 32.768 | 32.635 | 10.907 | 21.728 | 0.995941 | 0.332855 | 0.663086 | 2.006826 | 2.002387 | 2.009062 |
16 | 65.536 | 65.394 | 21.825 | 43.569 | 0.997833 | 0.333023 | 0.664810 | 2.003800 | 2.001009 | 2.005201 |
17 | 131.072 | 130.914 | 43.664 | 87.250 | 0.998795 | 0.333130 | 0.665665 | 2.001927 | 2.000642 | 2.002571 |
18 | 262.144 | 261.973 | 87.339 | 174.634 | 0.999348 | 0.333172 | 0.666176 | 2.001108 | 2.000252 | 2.001536 |
19 | 524.288 | 524.104 | 174.691 | 349.413 | 0.999649 | 0.333197 | 0.666452 | 2.000603 | 2.000149 | 2.000830 |
20 | 1.048.576 | 1.048.378 | 349.393 | 698.985 | 0.999811 | 0.333207 | 0.666604 | 2.000324 | 2.000063 | 2.000455 |
21 | 2.097.152 | 2.096.942 | 698.798 | 1.398.144 | 0.999900 | 0.333213 | 0.666687 | 2.000177 | 2.000034 | 2.000249 |
22 | 4.194.304 | 4.194.082 | 1.397.607 | 2.796.475 | 0.999947 | 0.333215 | 0.666732 | 2.000094 | 2.000016 | 2.000134 |
23 | 8.388.608 | 8.388.370 | 2.795.227 | 5.593.143 | 0.999972 | 0.333217 | 0.666755 | 2.000049 | 2.000009 | 2.000069 |
24 | 16.777.216 | 16.776.965 | 5.590.464 | 11.186.501 | 0.999985 | 0.333218 | 0.666767 | 2.000027 | 2.000004 | 2.000038 |
25 | 33.554.432 | 33.554.168 | 11.180.941 | 22.373.227 | 0.999992 | 0.333218 | 0.666774 | 2.000014 | 2.000002 | 2.000020 |
26 | 67.108.864 | 67.108.586 | 22.361.893 | 44.746.693 | 0.999996 | 0.333218 | 0.666778 | 2.000007 | 2.000001 | 2.000010 |
27 | 134.217.728 | 134.217.438 | 44.723.799 | 89.493.639 | 0.999998 | 0.333218 | 0.666780 | 2.000004 | 2.000001 | 2.000006 |
28 | 268.435.456 | 268.435.153 | 89.447.608 | 178.987.545 | 0.999999 | 0.333218 | 0.666781 | 2.000002 | 2.000000 | 2.000003 |
29 | 536.870.912 | 536.870.593 | 178.895.229 | 357.975.364 | 0.999999 | 0.333218 | 0.666781 | 2.000001 | 2.000000 | 2.000001 |
30 | 1.073.741.824 | 1.073.741.492 | 357.790.468 | 715.951.024 | 1.000000 | 0.333218 | 0.666781 | 2.000001 | 2.000000 | 2.000001 |
31 | 2.147.483.648 | 2.147.483.303 | 715.580.949 | 1.431.902.354 | 1.000000 | 0.333218 | 0.666781 | 2.000000 | 2.000000 | 2.000000 |
32 | 4.294.967.296 | 4.294.966.940 | 1.431.161.908 | 2.863.805.032 | 1.000000 | 0.333218 | 0.666782 | 2.000000 | 2.000000 | 2.000000 |
33 | 8.589.934.592 | 8.589.934.221 | 2.862.323.828 | 5.727.610.393 | 1.000000 | 0.333218 | 0.666782 | 2.000000 | 2.000000 | 2.000000 |
34 | 17.179.869.184 | 17.179.868.791 | 5.724.647.665 | 11.455.221.126 | 1.000000 | 0.333218 | 0.666782 | 2.000000 | 2.000000 | 2.000000 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 4 | 1 | 3 | 2 | 1 | 1 | 0 |
4 | 16 | 6 | 1 | 5 | 3 | 1 | 2 | 0 |
5 | 32 | 9 | 1 | 8 | 4 | 1 | 4 | 0 |
6 | 64 | 16 | 1 | 15 | 6 | 1 | 9 | 0 |
7 | 128 | 33 | 1 | 32 | 14 | 1 | 18 | 0 |
8 | 256 | 73 | 23 | 50 | 23 | 12 | 27 | 11 |
9 | 512 | 159 | 109 | 50 | 23 | 55 | 27 | 54 |
10 | 1.024 | 329 | 279 | 50 | 23 | 140 | 27 | 139 |
11 | 2.048 | 671 | 621 | 50 | 23 | 311 | 27 | 310 |
12 | 4.096 | 1.353 | 1.303 | 50 | 23 | 652 | 27 | 651 |
13 | 8.192 | 2.718 | 2.668 | 50 | 23 | 1.334 | 27 | 1.334 |
14 | 16.384 | 5.447 | 5.397 | 50 | 23 | 2.699 | 27 | 2.698 |
15 | 32.768 | 10.907 | 10.857 | 50 | 23 | 5.429 | 27 | 5.428 |
16 | 65.536 | 21.825 | 21.775 | 50 | 23 | 10.888 | 27 | 10.887 |
17 | 131.072 | 43.664 | 43.614 | 50 | 23 | 21.808 | 27 | 21.806 |
18 | 262.144 | 87.339 | 87.289 | 50 | 23 | 43.645 | 27 | 43.644 |
19 | 524.288 | 174.691 | 174.641 | 50 | 23 | 87.321 | 27 | 87.320 |
20 | 1.048.576 | 349.393 | 349.343 | 50 | 23 | 174.672 | 27 | 174.671 |
21 | 2.097.152 | 698.798 | 698.748 | 50 | 23 | 349.374 | 27 | 349.374 |
22 | 4.194.304 | 1.397.607 | 1.397.557 | 50 | 23 | 698.779 | 27 | 698.778 |
23 | 8.388.608 | 2.795.227 | 2.795.177 | 50 | 23 | 1.397.589 | 27 | 1.397.588 |
24 | 16.777.216 | 5.590.464 | 5.590.414 | 50 | 23 | 2.795.207 | 27 | 2.795.207 |
25 | 33.554.432 | 11.180.941 | 11.180.891 | 50 | 23 | 5.590.446 | 27 | 5.590.445 |
26 | 67.108.864 | 22.361.893 | 22.361.843 | 50 | 23 | 11.180.922 | 27 | 11.180.921 |
27 | 134.217.728 | 44.723.799 | 44.723.749 | 50 | 23 | 22.361.875 | 27 | 22.361.874 |
28 | 268.435.456 | 89.447.608 | 89.447.558 | 50 | 23 | 44.723.779 | 27 | 44.723.779 |
29 | 536.870.912 | 178.895.229 | 178.895.179 | 50 | 23 | 89.447.590 | 27 | 89.447.589 |
30 | 1.073.741.824 | 357.790.468 | 357.790.418 | 50 | 23 | 178.895.209 | 27 | 178.895.209 |
31 | 2.147.483.648 | 715.580.949 | 715.580.899 | 50 | 23 | 357.790.450 | 27 | 357.790.449 |
32 | 4.294.967.296 | 1.431.161.908 | 1.431.161.858 | 50 | 23 | 715.580.929 | 27 | 715.580.929 |
33 | 8.589.934.592 | 2.862.323.828 | 2.862.323.778 | 50 | 23 | 1.431.161.889 | 27 | 1.431.161.889 |
34 | 17.179.869.184 | 5.724.647.665 | 5.724.647.615 | 50 | 23 | 2.862.323.808 | 27 | 2.862.323.807 |
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 | 2 | 0 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 3 | 1 | 1 | 1 | 1 | 2 |
4 | 16 | 11 | 6 | 4 | 3 | 4 | 1 | 3 |
5 | 32 | 21 | 12 | 8 | 4 | 7 | 4 | 6 |
6 | 64 | 39 | 24 | 14 | 4 | 16 | 9 | 10 |
7 | 128 | 75 | 48 | 26 | 13 | 25 | 13 | 24 |
8 | 256 | 118 | 68 | 49 | 23 | 38 | 26 | 31 |
9 | 512 | 274 | 118 | 155 | 71 | 65 | 75 | 63 |
10 | 1.024 | 608 | 228 | 379 | 176 | 127 | 181 | 124 |
11 | 2.048 | 1.284 | 451 | 832 | 386 | 255 | 393 | 250 |
12 | 4.096 | 2.639 | 901 | 1.737 | 813 | 507 | 816 | 503 |
13 | 8.192 | 5.361 | 1.806 | 3.554 | 1.660 | 1.020 | 1.668 | 1.013 |
14 | 16.384 | 10.815 | 3.624 | 7.190 | 3.369 | 2.037 | 3.372 | 2.037 |
15 | 32.768 | 21.728 | 7.263 | 14.464 | 6.775 | 4.088 | 6.782 | 4.083 |
16 | 65.536 | 43.569 | 14.545 | 29.023 | 13.606 | 8.178 | 13.609 | 8.176 |
17 | 131.072 | 87.250 | 29.106 | 58.143 | 27.251 | 16.373 | 27.261 | 16.365 |
18 | 262.144 | 174.634 | 58.242 | 116.391 | 54.560 | 32.755 | 54.568 | 32.751 |
19 | 524.288 | 349.413 | 116.518 | 232.894 | 109.181 | 65.524 | 109.182 | 65.526 |
20 | 1.048.576 | 698.985 | 233.079 | 465.905 | 218.415 | 131.073 | 218.422 | 131.075 |
21 | 2.097.152 | 1.398.144 | 466.212 | 931.931 | 436.895 | 262.172 | 436.903 | 262.174 |
22 | 4.194.304 | 2.796.475 | 932.482 | 1.863.992 | 873.860 | 524.374 | 873.871 | 524.370 |
23 | 8.388.608 | 5.593.143 | 1.865.024 | 3.728.118 | 1.747.791 | 1.048.778 | 1.747.797 | 1.048.777 |
24 | 16.777.216 | 11.186.501 | 3.730.118 | 7.456.382 | 3.495.659 | 2.097.590 | 3.495.665 | 2.097.587 |
25 | 33.554.432 | 22.373.227 | 7.460.309 | 14.912.917 | 6.991.390 | 4.195.221 | 6.991.389 | 4.195.227 |
26 | 67.108.864 | 44.746.693 | 14.920.701 | 29.825.991 | 13.982.850 | 8.390.491 | 13.982.861 | 8.390.491 |
27 | 134.217.728 | 89.493.639 | 29.841.492 | 59.652.146 | 27.965.798 | 16.781.016 | 27.965.799 | 16.781.026 |
28 | 268.435.456 | 178.987.545 | 59.683.080 | 119.304.464 | 55.931.661 | 33.562.108 | 55.931.688 | 33.562.088 |
29 | 536.870.912 | 357.975.364 | 119.366.259 | 238.609.104 | 111.863.440 | 67.124.237 | 111.863.448 | 67.124.239 |
30 | 1.073.741.824 | 715.951.024 | 238.732.631 | 477.218.392 | 223.726.974 | 134.248.533 | 223.726.988 | 134.248.529 |
31 | 2.147.483.648 | 1.431.902.354 | 477.465.379 | 954.436.974 | 447.454.052 | 268.497.118 | 447.454.059 | 268.497.125 |
32 | 4.294.967.296 | 2.863.805.032 | 954.930.887 | 1.908.874.144 | 894.908.195 | 536.994.316 | 894.908.214 | 536.994.307 |
33 | 8.589.934.592 | 5.727.610.393 | 1.909.861.898 | 3.817.748.494 | 1.789.816.519 | 1.073.988.671 | 1.789.816.523 | 1.073.988.680 |
34 | 17.179.869.184 | 11.455.221.126 | 3.819.723.938 | 7.635.497.187 | 3.579.633.142 | 2.147.977.417 | 3.579.633.153 | 2.147.977.414 |