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+28x-53
f(0)=53
f(1)=3
f(2)=7
f(3)=5
f(4)=1
f(5)=1
f(6)=151
f(7)=1
f(8)=47
f(9)=1
f(10)=109
f(11)=1
f(12)=61
f(13)=1
f(14)=107
f(15)=37
f(16)=31
f(17)=89
f(18)=1
f(19)=1
f(20)=907
f(21)=1
f(22)=349
f(23)=1
f(24)=239
f(25)=1
f(26)=193
f(27)=179
f(28)=101
f(29)=1
f(30)=241
f(31)=1
f(32)=1867
f(33)=1
f(34)=137
f(35)=269
f(36)=2251
f(37)=1
f(38)=491
f(39)=1
f(40)=127
f(41)=347
f(42)=2887
f(43)=1
f(44)=1
f(45)=1
f(46)=1117
f(47)=1
f(48)=719
f(49)=1
f(50)=3847
f(51)=71
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=4651
f(57)=599
f(58)=1
f(59)=1
f(60)=5227
f(61)=1
f(62)=5527
f(63)=1
f(64)=389
f(65)=1
f(66)=6151
f(67)=263
f(68)=1
f(69)=83
f(70)=2269
f(71)=1
f(72)=1021
f(73)=1
f(74)=1499
f(75)=1
f(76)=2617
f(77)=251
f(78)=1
f(79)=1
f(80)=277
f(81)=1097
f(82)=1
f(83)=229
f(84)=1871
f(85)=199
f(86)=1
f(87)=311
f(88)=677
f(89)=1
f(90)=10567
f(91)=449
f(92)=10987
f(93)=1
f(94)=761
f(95)=727
f(96)=1693
f(97)=503
f(98)=2459
f(99)=313
b) Substitution of the polynom
The polynom f(x)=x^2+28x-53 could be written as f(y)= y^2-249 with x=y-14
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+14
f'(x)>2x+27
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 | 6 | 3 | 3 | 0.600000 | 0.300000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 14 | 44 | 0.580000 | 0.140000 | 0.580000 | 9.666667 | 4.666667 | 14.666667 |
3 | 1.000 | 610 | 79 | 531 | 0.610000 | 0.079000 | 0.610000 | 10.517241 | 5.642857 | 12.068182 |
4 | 10.000 | 6.360 | 537 | 5.823 | 0.636000 | 0.053700 | 0.636000 | 10.426229 | 6.797468 | 10.966102 |
5 | 100.000 | 64.899 | 4.236 | 60.663 | 0.648990 | 0.042360 | 0.648990 | 10.204246 | 7.888268 | 10.417826 |
6 | 1.000.000 | 656.299 | 34.992 | 621.307 | 0.656299 | 0.034992 | 0.656299 | 10.112621 | 8.260623 | 10.241943 |
7 | 10.000.000 | 6.618.146 | 293.709 | 6.324.437 | 0.661815 | 0.029371 | 0.661815 | 10.084041 | 8.393604 | 10.179246 |
8 | 100.000.000 | 66.574.839 | 2.544.278 | 64.030.561 | 0.665748 | 0.025443 | 0.665748 | 10.059440 | 8.662581 | 10.124310 |
9 | 1.000.000.000 | 668.796.779 | 22.447.548 | 646.349.231 | 0.668797 | 0.022448 | 0.668797 | 10.045789 | 8.822758 | 10.094387 |
10 | 10.000.000.000 | 6.712.311.060 | 200.894.027 | 6.511.417.033 | 0.671231 | 0.020089 | 0.671231 | 10.036399 | 8.949487 | 10.074146 |
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 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 5 | 3 | 2 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.500000 | 2.000000 |
4 | 16 | 9 | 3 | 6 | 0.562500 | 0.187500 | 0.375000 | 1.800000 | 1.000000 | 3.000000 |
5 | 32 | 18 | 5 | 13 | 0.562500 | 0.156250 | 0.406250 | 2.000000 | 1.666667 | 2.166667 |
6 | 64 | 33 | 11 | 22 | 0.515625 | 0.171875 | 0.343750 | 1.833333 | 2.200000 | 1.692308 |
7 | 128 | 74 | 16 | 58 | 0.578125 | 0.125000 | 0.453125 | 2.242424 | 1.454545 | 2.636364 |
8 | 256 | 149 | 25 | 124 | 0.582031 | 0.097656 | 0.484375 | 2.013514 | 1.562500 | 2.137931 |
9 | 512 | 304 | 44 | 260 | 0.593750 | 0.085938 | 0.507812 | 2.040268 | 1.760000 | 2.096774 |
10 | 1.024 | 626 | 80 | 546 | 0.611328 | 0.078125 | 0.533203 | 2.059211 | 1.818182 | 2.100000 |
11 | 2.048 | 1.279 | 137 | 1.142 | 0.624512 | 0.066895 | 0.557617 | 2.043131 | 1.712500 | 2.091575 |
12 | 4.096 | 2.581 | 249 | 2.332 | 0.630127 | 0.060791 | 0.569336 | 2.017983 | 1.817518 | 2.042032 |
13 | 8.192 | 5.207 | 451 | 4.756 | 0.635620 | 0.055054 | 0.580566 | 2.017435 | 1.811245 | 2.039451 |
14 | 16.384 | 10.481 | 835 | 9.646 | 0.639709 | 0.050964 | 0.588745 | 2.012867 | 1.851441 | 2.028175 |
15 | 32.768 | 21.101 | 1.551 | 19.550 | 0.643951 | 0.047333 | 0.596619 | 2.013262 | 1.857485 | 2.026747 |
16 | 65.536 | 42.403 | 2.936 | 39.467 | 0.647018 | 0.044800 | 0.602219 | 2.009526 | 1.892972 | 2.018772 |
17 | 131.072 | 85.200 | 5.430 | 79.770 | 0.650024 | 0.041428 | 0.608597 | 2.009292 | 1.849455 | 2.021182 |
18 | 262.144 | 171.106 | 10.212 | 160.894 | 0.652718 | 0.038956 | 0.613762 | 2.008286 | 1.880663 | 2.016974 |
19 | 524.288 | 343.245 | 19.321 | 323.924 | 0.654688 | 0.036852 | 0.617836 | 2.006037 | 1.891990 | 2.013276 |
20 | 1.048.576 | 688.288 | 36.549 | 651.739 | 0.656403 | 0.034856 | 0.621547 | 2.005238 | 1.891672 | 2.012012 |
21 | 2.097.152 | 1.380.621 | 69.078 | 1.311.543 | 0.658331 | 0.032939 | 0.625392 | 2.005877 | 1.890011 | 2.012375 |
22 | 4.194.304 | 2.767.955 | 130.824 | 2.637.131 | 0.659932 | 0.031191 | 0.628741 | 2.004862 | 1.893859 | 2.010709 |
23 | 8.388.608 | 5.548.718 | 249.527 | 5.299.191 | 0.661459 | 0.029746 | 0.631713 | 2.004627 | 1.907349 | 2.009453 |
24 | 16.777.216 | 11.119.719 | 476.129 | 10.643.590 | 0.662787 | 0.028379 | 0.634407 | 2.004016 | 1.908126 | 2.008531 |
25 | 33.554.432 | 22.281.195 | 910.537 | 21.370.658 | 0.664031 | 0.027136 | 0.636895 | 2.003755 | 1.912375 | 2.007843 |
26 | 67.108.864 | 44.637.028 | 1.747.173 | 42.889.855 | 0.665144 | 0.026035 | 0.639109 | 2.003350 | 1.918838 | 2.006951 |
27 | 134.217.728 | 89.412.958 | 3.357.452 | 86.055.506 | 0.666178 | 0.025015 | 0.641163 | 2.003112 | 1.921648 | 2.006430 |
28 | 268.435.456 | 179.084.921 | 6.458.901 | 172.626.020 | 0.667143 | 0.024061 | 0.643082 | 2.002897 | 1.923751 | 2.005985 |
29 | 536.870.912 | 358.652.914 | 12.446.589 | 346.206.325 | 0.668043 | 0.023184 | 0.644860 | 2.002697 | 1.927044 | 2.005528 |
30 | 1.073.741.824 | 718.204.371 | 24.014.980 | 694.189.391 | 0.668880 | 0.022366 | 0.646514 | 2.002505 | 1.929443 | 2.005132 |
31 | 2.147.483.648 | 1.438.085.386 | 46.397.536 | 1.391.687.850 | 0.669661 | 0.021606 | 0.648055 | 2.002335 | 1.932025 | 2.004767 |
32 | 4.294.967.296 | 2.879.320.333 | 89.742.242 | 2.789.578.091 | 0.670394 | 0.020895 | 0.649499 | 2.002190 | 1.934203 | 2.004457 |
33 | 8.589.934.592 | 5.764.574.067 | 173.767.618 | 5.590.806.449 | 0.671085 | 0.020229 | 0.650856 | 2.002061 | 1.936297 | 2.004176 |
34 | 17.179.869.184 | 11.540.280.309 | 336.832.451 | 11.203.447.858 | 0.671733 | 0.019606 | 0.652126 | 2.001931 | 1.938408 | 2.003906 |
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 | 3 | 2 | 1 | 0 | 0 | 1 | 2 |
4 | 16 | 3 | 2 | 1 | 0 | 0 | 1 | 2 |
5 | 32 | 5 | 4 | 1 | 0 | 2 | 1 | 2 |
6 | 64 | 11 | 10 | 1 | 0 | 5 | 1 | 5 |
7 | 128 | 16 | 15 | 1 | 0 | 8 | 1 | 7 |
8 | 256 | 25 | 24 | 1 | 0 | 12 | 1 | 12 |
9 | 512 | 44 | 43 | 1 | 0 | 24 | 1 | 19 |
10 | 1.024 | 80 | 79 | 1 | 0 | 39 | 1 | 40 |
11 | 2.048 | 137 | 136 | 1 | 0 | 67 | 1 | 69 |
12 | 4.096 | 249 | 248 | 1 | 0 | 123 | 1 | 125 |
13 | 8.192 | 451 | 450 | 1 | 0 | 216 | 1 | 234 |
14 | 16.384 | 835 | 834 | 1 | 0 | 407 | 1 | 427 |
15 | 32.768 | 1.551 | 1.550 | 1 | 0 | 772 | 1 | 778 |
16 | 65.536 | 2.936 | 2.935 | 1 | 0 | 1.459 | 1 | 1.476 |
17 | 131.072 | 5.430 | 5.429 | 1 | 0 | 2.679 | 1 | 2.750 |
18 | 262.144 | 10.212 | 10.211 | 1 | 0 | 5.068 | 1 | 5.143 |
19 | 524.288 | 19.321 | 19.320 | 1 | 0 | 9.641 | 1 | 9.679 |
20 | 1.048.576 | 36.549 | 36.548 | 1 | 0 | 18.234 | 1 | 18.314 |
21 | 2.097.152 | 69.078 | 69.077 | 1 | 0 | 34.468 | 1 | 34.609 |
22 | 4.194.304 | 130.824 | 130.823 | 1 | 0 | 65.199 | 1 | 65.624 |
23 | 8.388.608 | 249.527 | 249.526 | 1 | 0 | 124.613 | 1 | 124.913 |
24 | 16.777.216 | 476.129 | 476.128 | 1 | 0 | 237.748 | 1 | 238.380 |
25 | 33.554.432 | 910.537 | 910.536 | 1 | 0 | 454.378 | 1 | 456.158 |
26 | 67.108.864 | 1.747.173 | 1.747.172 | 1 | 0 | 872.962 | 1 | 874.210 |
27 | 134.217.728 | 3.357.452 | 3.357.451 | 1 | 0 | 1.678.220 | 1 | 1.679.231 |
28 | 268.435.456 | 6.458.901 | 6.458.900 | 1 | 0 | 3.229.918 | 1 | 3.228.982 |
29 | 536.870.912 | 12.446.589 | 12.446.588 | 1 | 0 | 6.224.088 | 1 | 6.222.500 |
30 | 1.073.741.824 | 24.014.980 | 24.014.979 | 1 | 0 | 12.009.527 | 1 | 12.005.452 |
31 | 2.147.483.648 | 46.397.536 | 46.397.535 | 1 | 0 | 23.199.520 | 1 | 23.198.015 |
32 | 4.294.967.296 | 89.742.242 | 89.742.241 | 1 | 0 | 44.871.855 | 1 | 44.870.386 |
33 | 8.589.934.592 | 173.767.618 | 173.767.617 | 1 | 0 | 86.884.692 | 1 | 86.882.925 |
34 | 17.179.869.184 | 336.832.451 | 336.832.450 | 1 | 0 | 168.417.206 | 1 | 168.415.244 |
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 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 6 | 3 | 2 | 0 | 2 | 3 | 1 |
5 | 32 | 13 | 6 | 6 | 3 | 3 | 5 | 2 |
6 | 64 | 22 | 8 | 13 | 4 | 5 | 8 | 5 |
7 | 128 | 58 | 27 | 30 | 15 | 12 | 16 | 15 |
8 | 256 | 124 | 58 | 65 | 27 | 34 | 36 | 27 |
9 | 512 | 260 | 126 | 133 | 62 | 61 | 73 | 64 |
10 | 1.024 | 546 | 260 | 285 | 138 | 124 | 145 | 139 |
11 | 2.048 | 1.142 | 549 | 592 | 287 | 277 | 295 | 283 |
12 | 4.096 | 2.332 | 1.108 | 1.223 | 602 | 580 | 589 | 561 |
13 | 8.192 | 4.756 | 2.307 | 2.448 | 1.237 | 1.154 | 1.226 | 1.139 |
14 | 16.384 | 9.646 | 4.669 | 4.976 | 2.527 | 2.321 | 2.468 | 2.330 |
15 | 32.768 | 19.550 | 9.465 | 10.084 | 5.109 | 4.694 | 5.054 | 4.693 |
16 | 65.536 | 39.467 | 19.237 | 20.229 | 10.359 | 9.441 | 10.167 | 9.500 |
17 | 131.072 | 79.770 | 39.022 | 40.747 | 20.742 | 19.335 | 20.338 | 19.355 |
18 | 262.144 | 160.894 | 78.915 | 81.978 | 41.497 | 39.001 | 41.407 | 38.989 |
19 | 524.288 | 323.924 | 159.039 | 164.884 | 83.161 | 79.020 | 83.104 | 78.639 |
20 | 1.048.576 | 651.739 | 320.554 | 331.184 | 166.963 | 159.390 | 166.857 | 158.529 |
21 | 2.097.152 | 1.311.543 | 645.700 | 665.842 | 335.209 | 321.153 | 335.116 | 320.065 |
22 | 4.194.304 | 2.637.131 | 1.299.212 | 1.337.918 | 673.111 | 646.582 | 673.575 | 643.863 |
23 | 8.388.608 | 5.299.191 | 2.613.763 | 2.685.427 | 1.351.395 | 1.298.523 | 1.351.259 | 1.298.014 |
24 | 16.777.216 | 10.643.590 | 5.255.543 | 5.388.046 | 2.711.787 | 2.610.051 | 2.711.916 | 2.609.836 |
25 | 33.554.432 | 21.370.658 | 10.557.464 | 10.813.193 | 5.439.061 | 5.244.096 | 5.442.160 | 5.245.341 |
26 | 67.108.864 | 42.889.855 | 21.200.412 | 21.689.442 | 10.909.489 | 10.534.325 | 10.910.491 | 10.535.550 |
27 | 134.217.728 | 86.055.506 | 42.557.065 | 43.498.440 | 21.873.414 | 21.155.965 | 21.871.899 | 21.154.228 |
28 | 268.435.456 | 172.626.020 | 85.413.249 | 87.212.770 | 43.843.953 | 42.472.648 | 43.842.445 | 42.466.974 |
29 | 536.870.912 | 346.206.325 | 171.374.319 | 174.832.005 | 87.874.507 | 85.236.310 | 87.873.626 | 85.221.882 |
30 | 1.073.741.824 | 694.189.391 | 343.771.735 | 350.417.655 | 176.102.408 | 170.994.884 | 176.097.188 | 170.994.911 |
31 | 2.147.483.648 | 1.391.687.850 | 689.431.809 | 702.256.040 | 352.835.403 | 343.005.208 | 352.844.819 | 343.002.420 |
32 | 4.294.967.296 | 2.789.578.091 | 1.382.442.784 | 1.407.135.306 | 706.886.849 | 687.905.835 | 706.881.414 | 687.903.993 |
33 | 8.589.934.592 | 5.590.806.449 | 2.771.600.263 | 2.819.206.185 | 1.416.059.455 | 1.379.344.000 | 1.416.074.602 | 1.379.328.392 |
34 | 17.179.869.184 | 11.203.447.858 | 5.555.694.005 | 5.647.753.852 | 2.836.457.089 | 2.765.310.993 | 2.836.419.389 | 2.765.260.387 |