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+12x-19
f(0)=19
f(1)=3
f(2)=1
f(3)=13
f(4)=5
f(5)=11
f(6)=89
f(7)=1
f(8)=47
f(9)=17
f(10)=67
f(11)=1
f(12)=269
f(13)=1
f(14)=23
f(15)=193
f(16)=1
f(17)=79
f(18)=521
f(19)=1
f(20)=1
f(21)=337
f(22)=1
f(23)=131
f(24)=1
f(25)=151
f(26)=1
f(27)=1
f(28)=367
f(29)=1
f(30)=73
f(31)=1
f(32)=463
f(33)=733
f(34)=103
f(35)=271
f(36)=1709
f(37)=1
f(38)=1
f(39)=197
f(40)=229
f(41)=359
f(42)=173
f(43)=1
f(44)=163
f(45)=1
f(46)=883
f(47)=1
f(48)=2861
f(49)=1
f(50)=1
f(51)=1597
f(52)=1103
f(53)=571
f(54)=709
f(55)=1
f(56)=421
f(57)=1
f(58)=449
f(59)=139
f(60)=1
f(61)=739
f(62)=1523
f(63)=181
f(64)=1
f(65)=277
f(66)=223
f(67)=293
f(68)=1
f(69)=557
f(70)=1907
f(71)=1
f(72)=6029
f(73)=1031
f(74)=1
f(75)=3253
f(76)=1
f(77)=1
f(78)=7001
f(79)=239
f(80)=2447
f(81)=1
f(82)=233
f(83)=1
f(84)=1609
f(85)=457
f(86)=2803
f(87)=4297
f(88)=2927
f(89)=1
f(90)=9161
f(91)=1559
f(92)=1061
f(93)=443
f(94)=1
f(95)=1
f(96)=1
f(97)=1759
f(98)=211
f(99)=1097
b) Substitution of the polynom
The polynom f(x)=x^2+12x-19 could be written as f(y)= y^2-55 with x=y-6
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+6
f'(x)>2x+11
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 | 8 | 3 | 5 | 0.800000 | 0.300000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 10 | 54 | 0.640000 | 0.100000 | 0.640000 | 8.000000 | 3.333333 | 10.800000 |
3 | 1.000 | 651 | 48 | 603 | 0.651000 | 0.048000 | 0.651000 | 10.171875 | 4.800000 | 11.166667 |
4 | 10.000 | 6.629 | 351 | 6.278 | 0.662900 | 0.035100 | 0.662900 | 10.182796 | 7.312500 | 10.411277 |
5 | 100.000 | 67.007 | 2.602 | 64.405 | 0.670070 | 0.026020 | 0.670070 | 10.108161 | 7.413105 | 10.258841 |
6 | 1.000.000 | 673.849 | 21.514 | 652.335 | 0.673849 | 0.021514 | 0.673849 | 10.056397 | 8.268255 | 10.128639 |
7 | 10.000.000 | 6.764.024 | 180.078 | 6.583.946 | 0.676402 | 0.018008 | 0.676402 | 10.037892 | 8.370271 | 10.092891 |
8 | 100.000.000 | 67.836.502 | 1.560.025 | 66.276.477 | 0.678365 | 0.015600 | 0.678365 | 10.029016 | 8.663052 | 10.066376 |
9 | 1.000.000.000 | 679.904.419 | 13.768.058 | 666.136.361 | 0.679904 | 0.013768 | 0.679904 | 10.022693 | 8.825537 | 10.050872 |
10 | 10.000.000.000 | 6.811.578.458 | 123.227.946 | 6.688.350.512 | 0.681158 | 0.012323 | 0.681158 | 10.018435 | 8.950278 | 10.040512 |
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 | 2 | 1 | 1 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 2.000000 | 2.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
4 | 16 | 10 | 4 | 6 | 0.625000 | 0.250000 | 0.375000 | 1.428571 | 1.333333 | 1.500000 |
5 | 32 | 18 | 5 | 13 | 0.562500 | 0.156250 | 0.406250 | 1.800000 | 1.250000 | 2.166667 |
6 | 64 | 39 | 7 | 32 | 0.609375 | 0.109375 | 0.500000 | 2.166667 | 1.400000 | 2.461539 |
7 | 128 | 80 | 11 | 69 | 0.625000 | 0.085938 | 0.539062 | 2.051282 | 1.571429 | 2.156250 |
8 | 256 | 165 | 18 | 147 | 0.644531 | 0.070312 | 0.574219 | 2.062500 | 1.636364 | 2.130435 |
9 | 512 | 335 | 29 | 306 | 0.654297 | 0.056641 | 0.597656 | 2.030303 | 1.611111 | 2.081633 |
10 | 1.024 | 669 | 50 | 619 | 0.653320 | 0.048828 | 0.604492 | 1.997015 | 1.724138 | 2.022876 |
11 | 2.048 | 1.343 | 95 | 1.248 | 0.655762 | 0.046387 | 0.609375 | 2.007474 | 1.900000 | 2.016155 |
12 | 4.096 | 2.692 | 157 | 2.535 | 0.657227 | 0.038330 | 0.618896 | 2.004468 | 1.652632 | 2.031250 |
13 | 8.192 | 5.430 | 299 | 5.131 | 0.662842 | 0.036499 | 0.626343 | 2.017088 | 1.904459 | 2.024063 |
14 | 16.384 | 10.920 | 520 | 10.400 | 0.666504 | 0.031738 | 0.634766 | 2.011050 | 1.739130 | 2.026895 |
15 | 32.768 | 21.887 | 965 | 20.922 | 0.667938 | 0.029449 | 0.638489 | 2.004304 | 1.855769 | 2.011731 |
16 | 65.536 | 43.854 | 1.785 | 42.069 | 0.669159 | 0.027237 | 0.641922 | 2.003655 | 1.849741 | 2.010754 |
17 | 131.072 | 87.869 | 3.304 | 84.565 | 0.670387 | 0.025208 | 0.645180 | 2.003671 | 1.850980 | 2.010150 |
18 | 262.144 | 176.005 | 6.293 | 169.712 | 0.671406 | 0.024006 | 0.647400 | 2.003039 | 1.904661 | 2.006882 |
19 | 524.288 | 352.598 | 11.892 | 340.706 | 0.672527 | 0.022682 | 0.649845 | 2.003341 | 1.889719 | 2.007554 |
20 | 1.048.576 | 706.665 | 22.484 | 684.181 | 0.673928 | 0.021442 | 0.652486 | 2.004166 | 1.890683 | 2.008127 |
21 | 2.097.152 | 1.414.929 | 42.493 | 1.372.436 | 0.674691 | 0.020262 | 0.654428 | 2.002263 | 1.889922 | 2.005955 |
22 | 4.194.304 | 2.833.295 | 80.440 | 2.752.855 | 0.675510 | 0.019178 | 0.656332 | 2.002429 | 1.893018 | 2.005817 |
23 | 8.388.608 | 5.672.179 | 152.856 | 5.519.323 | 0.676176 | 0.018222 | 0.657955 | 2.001973 | 1.900249 | 2.004945 |
24 | 16.777.216 | 11.356.374 | 291.629 | 11.064.745 | 0.676893 | 0.017382 | 0.659510 | 2.002118 | 1.907868 | 2.004729 |
25 | 33.554.432 | 22.733.293 | 558.736 | 22.174.557 | 0.677505 | 0.016652 | 0.660853 | 2.001809 | 1.915914 | 2.004073 |
26 | 67.108.864 | 45.504.513 | 1.071.463 | 44.433.050 | 0.678070 | 0.015966 | 0.662104 | 2.001668 | 1.917655 | 2.003785 |
27 | 134.217.728 | 91.077.754 | 2.058.389 | 89.019.365 | 0.678582 | 0.015336 | 0.663246 | 2.001510 | 1.921101 | 2.003449 |
28 | 268.435.456 | 182.286.192 | 3.962.030 | 178.324.162 | 0.679069 | 0.014760 | 0.664309 | 2.001435 | 1.924821 | 2.003206 |
29 | 536.870.912 | 364.814.492 | 7.634.771 | 357.179.721 | 0.679520 | 0.014221 | 0.665299 | 2.001328 | 1.926985 | 2.002980 |
30 | 1.073.741.824 | 730.089.915 | 14.729.608 | 715.360.307 | 0.679949 | 0.013718 | 0.666231 | 2.001263 | 1.929280 | 2.002802 |
31 | 2.147.483.648 | 1.461.030.540 | 28.458.495 | 1.432.572.045 | 0.680345 | 0.013252 | 0.667093 | 2.001165 | 1.932061 | 2.002588 |
32 | 4.294.967.296 | 2.923.692.079 | 55.043.768 | 2.868.648.311 | 0.680725 | 0.012816 | 0.667909 | 2.001116 | 1.934177 | 2.002446 |
33 | 8.589.934.592 | 5.850.452.516 | 106.583.367 | 5.743.869.149 | 0.681082 | 0.012408 | 0.668674 | 2.001050 | 1.936339 | 2.002291 |
34 | 17.179.869.184 | 11.706.654.799 | 206.603.321 | 11.500.051.478 | 0.681417 | 0.012026 | 0.669391 | 2.000983 | 1.938420 | 2.002144 |
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 | 1 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 1 | 1 | 1 | 0 |
4 | 16 | 4 | 1 | 2 | 1 | 1 | 2 | 0 |
5 | 32 | 5 | 1 | 3 | 2 | 1 | 2 | 0 |
6 | 64 | 7 | 1 | 5 | 2 | 1 | 4 | 0 |
7 | 128 | 11 | 1 | 9 | 4 | 1 | 6 | 0 |
8 | 256 | 18 | 1 | 16 | 9 | 1 | 8 | 0 |
9 | 512 | 29 | 1 | 27 | 15 | 1 | 13 | 0 |
10 | 1.024 | 50 | 1 | 48 | 25 | 1 | 24 | 0 |
11 | 2.048 | 95 | 1 | 93 | 50 | 1 | 44 | 0 |
12 | 4.096 | 157 | 1 | 155 | 82 | 1 | 74 | 0 |
13 | 8.192 | 299 | 1 | 297 | 154 | 1 | 144 | 0 |
14 | 16.384 | 520 | 1 | 518 | 271 | 1 | 248 | 0 |
15 | 32.768 | 965 | 1 | 963 | 490 | 1 | 474 | 0 |
16 | 65.536 | 1.785 | 1 | 1.783 | 879 | 1 | 905 | 0 |
17 | 131.072 | 3.304 | 1 | 3.302 | 1.653 | 1 | 1.650 | 0 |
18 | 262.144 | 6.293 | 1 | 6.291 | 3.145 | 1 | 3.147 | 0 |
19 | 524.288 | 11.892 | 1 | 11.890 | 5.937 | 1 | 5.954 | 0 |
20 | 1.048.576 | 22.484 | 1 | 22.482 | 11.265 | 1 | 11.218 | 0 |
21 | 2.097.152 | 42.493 | 1 | 42.491 | 21.301 | 1 | 21.191 | 0 |
22 | 4.194.304 | 80.440 | 1 | 80.438 | 40.403 | 1 | 40.036 | 0 |
23 | 8.388.608 | 152.856 | 1 | 152.854 | 76.628 | 1 | 76.227 | 0 |
24 | 16.777.216 | 291.629 | 1 | 291.627 | 146.085 | 1 | 145.543 | 0 |
25 | 33.554.432 | 558.736 | 1 | 558.734 | 279.556 | 1 | 279.179 | 0 |
26 | 67.108.864 | 1.071.463 | 1 | 1.071.461 | 535.834 | 1 | 535.628 | 0 |
27 | 134.217.728 | 2.058.389 | 1 | 2.058.387 | 1.029.145 | 1 | 1.029.243 | 0 |
28 | 268.435.456 | 3.962.030 | 1 | 3.962.028 | 1.981.107 | 1 | 1.980.922 | 0 |
29 | 536.870.912 | 7.634.771 | 1 | 7.634.769 | 3.817.737 | 1 | 3.817.033 | 0 |
30 | 1.073.741.824 | 14.729.608 | 1 | 14.729.606 | 7.364.693 | 1 | 7.364.914 | 0 |
31 | 2.147.483.648 | 28.458.495 | 1 | 28.458.493 | 14.228.970 | 1 | 14.229.524 | 0 |
32 | 4.294.967.296 | 55.043.768 | 1 | 55.043.766 | 27.521.826 | 1 | 27.521.941 | 0 |
33 | 8.589.934.592 | 106.583.367 | 1 | 106.583.365 | 53.293.702 | 1 | 53.289.664 | 0 |
34 | 17.179.869.184 | 206.603.321 | 1 | 206.603.319 | 103.303.241 | 1 | 103.300.079 | 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 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 1 | 1 | 1 | 1 | 1 |
4 | 16 | 6 | 3 | 1 | 2 | 2 | 1 | 1 |
5 | 32 | 13 | 9 | 2 | 4 | 3 | 1 | 5 |
6 | 64 | 32 | 22 | 8 | 5 | 9 | 9 | 9 |
7 | 128 | 69 | 42 | 25 | 14 | 19 | 16 | 20 |
8 | 256 | 147 | 84 | 61 | 29 | 40 | 33 | 45 |
9 | 512 | 306 | 161 | 143 | 67 | 85 | 67 | 87 |
10 | 1.024 | 619 | 320 | 297 | 134 | 174 | 140 | 171 |
11 | 2.048 | 1.248 | 655 | 591 | 267 | 346 | 298 | 337 |
12 | 4.096 | 2.535 | 1.337 | 1.196 | 598 | 690 | 586 | 661 |
13 | 8.192 | 5.131 | 2.629 | 2.500 | 1.203 | 1.376 | 1.203 | 1.349 |
14 | 16.384 | 10.400 | 5.396 | 5.002 | 2.411 | 2.782 | 2.500 | 2.707 |
15 | 32.768 | 20.922 | 10.880 | 10.040 | 5.016 | 5.408 | 4.972 | 5.526 |
16 | 65.536 | 42.069 | 21.970 | 20.097 | 10.058 | 10.935 | 10.029 | 11.047 |
17 | 131.072 | 84.565 | 43.911 | 40.652 | 20.201 | 21.959 | 20.166 | 22.239 |
18 | 262.144 | 169.712 | 87.977 | 81.733 | 40.754 | 44.091 | 40.623 | 44.244 |
19 | 524.288 | 340.706 | 176.330 | 164.374 | 81.971 | 88.319 | 81.986 | 88.430 |
20 | 1.048.576 | 684.181 | 353.097 | 331.082 | 164.774 | 177.237 | 164.995 | 177.175 |
21 | 2.097.152 | 1.372.436 | 707.564 | 664.870 | 331.572 | 355.007 | 331.819 | 354.038 |
22 | 4.194.304 | 2.752.855 | 1.417.654 | 1.335.199 | 666.422 | 709.958 | 667.284 | 709.191 |
23 | 8.388.608 | 5.519.323 | 2.837.559 | 2.681.762 | 1.338.051 | 1.421.540 | 1.340.203 | 1.419.529 |
24 | 16.777.216 | 11.064.745 | 5.680.250 | 5.384.493 | 2.688.750 | 2.844.771 | 2.688.539 | 2.842.685 |
25 | 33.554.432 | 22.174.557 | 11.369.208 | 10.805.347 | 5.395.563 | 5.692.353 | 5.395.220 | 5.691.421 |
26 | 67.108.864 | 44.433.050 | 22.757.960 | 21.675.088 | 10.825.837 | 11.394.433 | 10.826.614 | 11.386.166 |
27 | 134.217.728 | 89.019.365 | 45.555.346 | 43.464.017 | 21.715.181 | 22.798.892 | 21.716.119 | 22.789.173 |
28 | 268.435.456 | 178.324.162 | 91.175.421 | 87.148.739 | 43.537.070 | 45.625.389 | 43.544.390 | 45.617.313 |
29 | 536.870.912 | 357.179.721 | 182.467.603 | 174.712.116 | 87.288.690 | 91.296.556 | 87.298.447 | 91.296.028 |
30 | 1.073.741.824 | 715.360.307 | 365.142.409 | 350.217.896 | 174.980.187 | 182.692.070 | 174.987.083 | 182.700.967 |
31 | 2.147.483.648 | 1.432.572.045 | 730.685.959 | 701.886.084 | 350.697.996 | 365.586.196 | 350.711.095 | 365.576.758 |
32 | 4.294.967.296 | 2.868.648.311 | 1.462.178.858 | 1.406.469.451 | 702.769.606 | 731.526.267 | 702.803.695 | 731.548.743 |
33 | 8.589.934.592 | 5.743.869.149 | 2.925.854.533 | 2.818.014.614 | 1.408.171.400 | 1.463.756.792 | 1.408.186.783 | 1.463.754.174 |
34 | 17.179.869.184 | 11.500.051.478 | 5.854.595.695 | 5.645.455.781 | 2.821.214.704 | 2.928.803.844 | 2.821.245.452 | 2.928.787.478 |