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-36x+5
f(0)=5
f(1)=3
f(2)=7
f(3)=47
f(4)=41
f(5)=1
f(6)=1
f(7)=11
f(8)=73
f(9)=17
f(10)=1
f(11)=1
f(12)=283
f(13)=1
f(14)=101
f(15)=31
f(16)=1
f(17)=53
f(18)=29
f(19)=1
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=61
f(40)=1
f(41)=1
f(42)=257
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=83
f(49)=107
f(50)=1
f(51)=1
f(52)=1
f(53)=151
f(54)=977
f(55)=1
f(56)=1
f(57)=601
f(58)=1
f(59)=227
f(60)=1
f(61)=1
f(62)=1
f(63)=853
f(64)=599
f(65)=1
f(66)=397
f(67)=347
f(68)=727
f(69)=163
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=313
f(75)=293
f(76)=1
f(77)=1
f(78)=193
f(79)=1
f(80)=1
f(81)=1
f(82)=1259
f(83)=1
f(84)=367
f(85)=139
f(86)=1
f(87)=2221
f(88)=509
f(89)=787
f(90)=1
f(91)=167
f(92)=191
f(93)=379
f(94)=1
f(95)=1
f(96)=1153
f(97)=1
f(98)=2027
f(99)=3121
b) Substitution of the polynom
The polynom f(x)=x^2-36x+5 could be written as f(y)= y^2-319 with x=y+18
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-18
f'(x)>2x-37 with x > 18
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 | 7 | 1 | 6 | 0.700000 | 0.100000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 37 | 4 | 33 | 0.370000 | 0.040000 | 0.370000 | 5.285714 | 4.000000 | 5.500000 |
3 | 1.000 | 582 | 33 | 549 | 0.582000 | 0.033000 | 0.582000 | 15.729730 | 8.250000 | 16.636364 |
4 | 10.000 | 6.239 | 225 | 6.014 | 0.623900 | 0.022500 | 0.623900 | 10.719932 | 6.818182 | 10.954463 |
5 | 100.000 | 64.133 | 1.742 | 62.391 | 0.641330 | 0.017420 | 0.641330 | 10.279371 | 7.742222 | 10.374293 |
6 | 1.000.000 | 650.484 | 14.143 | 636.341 | 0.650484 | 0.014143 | 0.650484 | 10.142735 | 8.118829 | 10.199244 |
7 | 10.000.000 | 6.566.385 | 120.062 | 6.446.323 | 0.656639 | 0.012006 | 0.656639 | 10.094614 | 8.489146 | 10.130297 |
8 | 100.000.000 | 66.123.431 | 1.038.520 | 65.084.911 | 0.661234 | 0.010385 | 0.661234 | 10.069990 | 8.649864 | 10.096439 |
9 | 1.000.000.000 | 664.802.703 | 9.154.686 | 655.648.017 | 0.664803 | 0.009155 | 0.664803 | 10.053966 | 8.815127 | 10.073732 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 1 | 4 | 1.250000 | 0.250000 | 1.000000 | 1.666667 | 1.000000 | 2.000000 |
3 | 8 | 7 | 1 | 6 | 0.875000 | 0.125000 | 0.750000 | 1.400000 | 1.000000 | 1.500000 |
4 | 16 | 10 | 2 | 8 | 0.625000 | 0.125000 | 0.500000 | 1.428571 | 2.000000 | 1.333333 |
5 | 32 | 12 | 2 | 10 | 0.375000 | 0.062500 | 0.312500 | 1.200000 | 1.000000 | 1.250000 |
6 | 64 | 20 | 4 | 16 | 0.312500 | 0.062500 | 0.250000 | 1.666667 | 2.000000 | 1.600000 |
7 | 128 | 50 | 5 | 45 | 0.390625 | 0.039062 | 0.351562 | 2.500000 | 1.250000 | 2.812500 |
8 | 256 | 128 | 9 | 119 | 0.500000 | 0.035156 | 0.464844 | 2.560000 | 1.800000 | 2.644444 |
9 | 512 | 281 | 20 | 261 | 0.548828 | 0.039062 | 0.509766 | 2.195312 | 2.222222 | 2.193277 |
10 | 1.024 | 598 | 34 | 564 | 0.583984 | 0.033203 | 0.550781 | 2.128114 | 1.700000 | 2.160919 |
11 | 2.048 | 1.223 | 59 | 1.164 | 0.597168 | 0.028809 | 0.568359 | 2.045151 | 1.735294 | 2.063830 |
12 | 4.096 | 2.512 | 99 | 2.413 | 0.613281 | 0.024170 | 0.589111 | 2.053966 | 1.677966 | 2.073024 |
13 | 8.192 | 5.096 | 184 | 4.912 | 0.622070 | 0.022461 | 0.599609 | 2.028662 | 1.858586 | 2.035640 |
14 | 16.384 | 10.338 | 337 | 10.001 | 0.630981 | 0.020569 | 0.610413 | 2.028650 | 1.831522 | 2.036034 |
15 | 32.768 | 20.794 | 637 | 20.157 | 0.634583 | 0.019440 | 0.615143 | 2.011414 | 1.890208 | 2.015498 |
16 | 65.536 | 41.883 | 1.151 | 40.732 | 0.639084 | 0.017563 | 0.621521 | 2.014187 | 1.806907 | 2.020737 |
17 | 131.072 | 84.261 | 2.208 | 82.053 | 0.642860 | 0.016846 | 0.626015 | 2.011819 | 1.918332 | 2.014460 |
18 | 262.144 | 169.228 | 4.128 | 165.100 | 0.645554 | 0.015747 | 0.629807 | 2.008379 | 1.869565 | 2.012114 |
19 | 524.288 | 339.798 | 7.773 | 332.025 | 0.648113 | 0.014826 | 0.633287 | 2.007930 | 1.882994 | 2.011054 |
20 | 1.048.576 | 682.246 | 14.784 | 667.462 | 0.650640 | 0.014099 | 0.636541 | 2.007799 | 1.901968 | 2.010276 |
21 | 2.097.152 | 1.368.863 | 28.108 | 1.340.755 | 0.652725 | 0.013403 | 0.639322 | 2.006407 | 1.901245 | 2.008736 |
22 | 4.194.304 | 2.745.307 | 53.368 | 2.691.939 | 0.654532 | 0.012724 | 0.641808 | 2.005538 | 1.898677 | 2.007778 |
23 | 8.388.608 | 5.504.823 | 101.886 | 5.402.937 | 0.656226 | 0.012146 | 0.644080 | 2.005176 | 1.909122 | 2.007080 |
24 | 16.777.216 | 11.036.356 | 194.524 | 10.841.832 | 0.657818 | 0.011595 | 0.646224 | 2.004852 | 1.909232 | 2.006655 |
25 | 33.554.432 | 22.119.701 | 372.305 | 21.747.396 | 0.659218 | 0.011096 | 0.648123 | 2.004258 | 1.913928 | 2.005878 |
26 | 67.108.864 | 44.328.176 | 713.558 | 43.614.618 | 0.660541 | 0.010633 | 0.649908 | 2.004014 | 1.916595 | 2.005510 |
27 | 134.217.728 | 88.818.717 | 1.370.024 | 87.448.693 | 0.661751 | 0.010207 | 0.651544 | 2.003663 | 1.919990 | 2.005032 |
28 | 268.435.456 | 177.939.437 | 2.636.257 | 175.303.180 | 0.662876 | 0.009821 | 0.653055 | 2.003400 | 1.924241 | 2.004640 |
29 | 536.870.912 | 356.438.434 | 5.078.643 | 351.359.791 | 0.663918 | 0.009460 | 0.654459 | 2.003145 | 1.926460 | 2.004298 |
30 | 1.073.741.824 | 713.931.201 | 9.793.096 | 704.138.105 | 0.664900 | 0.009121 | 0.655780 | 2.002958 | 1.928290 | 2.004037 |
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 | 1 | 0 | 0 | 1 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
4 | 16 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
5 | 32 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
6 | 64 | 4 | 1 | 3 | 2 | 1 | 1 | 0 |
7 | 128 | 5 | 1 | 4 | 3 | 1 | 1 | 0 |
8 | 256 | 9 | 1 | 8 | 5 | 1 | 3 | 0 |
9 | 512 | 20 | 1 | 19 | 12 | 1 | 7 | 0 |
10 | 1.024 | 34 | 1 | 33 | 17 | 1 | 16 | 0 |
11 | 2.048 | 59 | 1 | 58 | 26 | 1 | 32 | 0 |
12 | 4.096 | 99 | 1 | 98 | 45 | 1 | 53 | 0 |
13 | 8.192 | 184 | 1 | 183 | 87 | 1 | 96 | 0 |
14 | 16.384 | 337 | 1 | 336 | 165 | 1 | 171 | 0 |
15 | 32.768 | 637 | 1 | 636 | 306 | 1 | 330 | 0 |
16 | 65.536 | 1.151 | 1 | 1.150 | 571 | 1 | 579 | 0 |
17 | 131.072 | 2.208 | 1 | 2.207 | 1.093 | 1 | 1.114 | 0 |
18 | 262.144 | 4.128 | 1 | 4.127 | 2.050 | 1 | 2.077 | 0 |
19 | 524.288 | 7.773 | 1 | 7.772 | 3.853 | 1 | 3.919 | 0 |
20 | 1.048.576 | 14.784 | 1 | 14.783 | 7.387 | 1 | 7.396 | 0 |
21 | 2.097.152 | 28.108 | 1 | 28.107 | 14.059 | 1 | 14.048 | 0 |
22 | 4.194.304 | 53.368 | 1 | 53.367 | 26.646 | 1 | 26.721 | 0 |
23 | 8.388.608 | 101.886 | 1 | 101.885 | 50.892 | 1 | 50.993 | 0 |
24 | 16.777.216 | 194.524 | 1 | 194.523 | 97.205 | 1 | 97.318 | 0 |
25 | 33.554.432 | 372.305 | 1 | 372.304 | 186.212 | 1 | 186.092 | 0 |
26 | 67.108.864 | 713.558 | 1 | 713.557 | 356.706 | 1 | 356.851 | 0 |
27 | 134.217.728 | 1.370.024 | 1 | 1.370.023 | 684.699 | 1 | 685.324 | 0 |
28 | 268.435.456 | 2.636.257 | 1 | 2.636.256 | 1.318.072 | 1 | 1.318.184 | 0 |
29 | 536.870.912 | 5.078.643 | 1 | 5.078.642 | 2.538.352 | 1 | 2.540.290 | 0 |
30 | 1.073.741.824 | 9.793.096 | 1 | 9.793.095 | 4.897.519 | 1 | 4.895.576 | 0 |
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 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 4 | 1 | 2 | 1 | 1 | 0 | 2 |
3 | 8 | 6 | 2 | 2 | 2 | 2 | 0 | 2 |
4 | 16 | 8 | 3 | 3 | 2 | 2 | 1 | 3 |
5 | 32 | 10 | 3 | 5 | 2 | 2 | 3 | 3 |
6 | 64 | 16 | 6 | 8 | 3 | 4 | 4 | 5 |
7 | 128 | 45 | 24 | 19 | 9 | 14 | 11 | 11 |
8 | 256 | 119 | 62 | 55 | 29 | 31 | 26 | 33 |
9 | 512 | 261 | 140 | 119 | 58 | 73 | 63 | 67 |
10 | 1.024 | 564 | 295 | 267 | 123 | 151 | 151 | 139 |
11 | 2.048 | 1.164 | 617 | 545 | 256 | 316 | 292 | 300 |
12 | 4.096 | 2.413 | 1.242 | 1.169 | 567 | 629 | 595 | 622 |
13 | 8.192 | 4.912 | 2.557 | 2.353 | 1.170 | 1.252 | 1.205 | 1.285 |
14 | 16.384 | 10.001 | 5.177 | 4.822 | 2.406 | 2.580 | 2.427 | 2.588 |
15 | 32.768 | 20.157 | 10.379 | 9.776 | 4.866 | 5.263 | 4.854 | 5.174 |
16 | 65.536 | 40.732 | 21.039 | 19.691 | 9.938 | 10.552 | 9.840 | 10.402 |
17 | 131.072 | 82.053 | 42.268 | 39.783 | 19.991 | 21.097 | 19.867 | 21.098 |
18 | 262.144 | 165.100 | 84.986 | 80.112 | 40.183 | 42.305 | 40.291 | 42.321 |
19 | 524.288 | 332.025 | 170.041 | 161.982 | 80.637 | 85.114 | 81.221 | 85.053 |
20 | 1.048.576 | 667.462 | 341.238 | 326.222 | 162.597 | 170.614 | 163.545 | 170.706 |
21 | 2.097.152 | 1.340.755 | 684.790 | 655.963 | 327.190 | 342.553 | 328.706 | 342.306 |
22 | 4.194.304 | 2.691.939 | 1.372.706 | 1.319.231 | 657.845 | 687.178 | 659.801 | 687.115 |
23 | 8.388.608 | 5.402.937 | 2.752.406 | 2.650.529 | 1.322.707 | 1.377.905 | 1.324.874 | 1.377.451 |
24 | 16.777.216 | 10.841.832 | 5.517.168 | 5.324.662 | 2.657.173 | 2.762.745 | 2.659.576 | 2.762.338 |
25 | 33.554.432 | 21.747.396 | 11.059.490 | 10.687.904 | 5.337.869 | 5.534.251 | 5.338.660 | 5.536.616 |
26 | 67.108.864 | 43.614.618 | 22.166.592 | 21.448.024 | 10.714.838 | 11.089.770 | 10.717.126 | 11.092.884 |
27 | 134.217.728 | 87.448.693 | 44.415.846 | 43.032.845 | 21.498.924 | 22.224.639 | 21.501.940 | 22.223.190 |
28 | 268.435.456 | 175.303.180 | 88.982.287 | 86.320.891 | 43.126.236 | 44.519.782 | 43.134.346 | 44.522.816 |
29 | 536.870.912 | 351.359.791 | 178.233.448 | 173.126.341 | 86.496.440 | 89.171.287 | 86.511.039 | 89.181.025 |
30 | 1.073.741.824 | 704.138.105 | 356.988.354 | 347.149.749 | 173.453.886 | 178.601.865 | 173.486.046 | 178.596.308 |