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+21x+11
f(0)=11
f(1)=3
f(2)=19
f(3)=83
f(4)=37
f(5)=47
f(6)=173
f(7)=23
f(8)=1
f(9)=281
f(10)=107
f(11)=1
f(12)=1
f(13)=151
f(14)=167
f(15)=29
f(16)=67
f(17)=73
f(18)=31
f(19)=257
f(20)=277
f(21)=1
f(22)=1
f(23)=1
f(24)=1091
f(25)=43
f(26)=137
f(27)=1307
f(28)=461
f(29)=487
f(30)=1
f(31)=541
f(32)=569
f(33)=163
f(34)=1
f(35)=1
f(36)=2063
f(37)=719
f(38)=751
f(39)=2351
f(40)=1
f(41)=1
f(42)=2657
f(43)=307
f(44)=1
f(45)=271
f(46)=1031
f(47)=1069
f(48)=3323
f(49)=1
f(50)=1187
f(51)=127
f(52)=1
f(53)=1
f(54)=131
f(55)=1
f(56)=1
f(57)=4457
f(58)=1531
f(59)=1
f(60)=4871
f(61)=557
f(62)=191
f(63)=5303
f(64)=79
f(65)=1867
f(66)=523
f(67)=179
f(68)=1
f(69)=6221
f(70)=709
f(71)=727
f(72)=353
f(73)=1
f(74)=2347
f(75)=7211
f(76)=1
f(77)=229
f(78)=1
f(79)=293
f(80)=1
f(81)=8273
f(82)=2819
f(83)=1
f(84)=8831
f(85)=97
f(86)=1
f(87)=409
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=3469
f(93)=10613
f(94)=3607
f(95)=3677
f(96)=11243
f(97)=1
f(98)=1297
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+21x+11 could be written as f(y)= y^2-99.25 with x=y-10.5
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+10.5
f'(x)>2x+20
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 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 65 | 19 | 46 | 0.650000 | 0.190000 | 0.460000 | 6.500000 | 4.750000 | 7.666667 |
3 | 1.000 | 682 | 113 | 569 | 0.682000 | 0.113000 | 0.569000 | 10.492308 | 5.947369 | 12.369565 |
4 | 10.000 | 6.860 | 800 | 6.060 | 0.686000 | 0.080000 | 0.606000 | 10.058651 | 7.079646 | 10.650264 |
5 | 100.000 | 68.744 | 6.241 | 62.503 | 0.687440 | 0.062410 | 0.625030 | 10.020991 | 7.801250 | 10.314027 |
6 | 1.000.000 | 688.723 | 50.716 | 638.007 | 0.688723 | 0.050716 | 0.638007 | 10.018663 | 8.126262 | 10.207622 |
7 | 10.000.000 | 6.893.174 | 429.102 | 6.464.072 | 0.689317 | 0.042910 | 0.646407 | 10.008631 | 8.460880 | 10.131663 |
8 | 100.000.000 | 68.964.248 | 3.715.283 | 65.248.965 | 0.689642 | 0.037153 | 0.652490 | 10.004716 | 8.658275 | 10.094096 |
9 | 1.000.000.000 | 689.937.315 | 32.778.824 | 657.158.491 | 0.689937 | 0.032779 | 0.657158 | 10.004275 | 8.822700 | 10.071554 |
10 | 10.000.000.000 | 6.901.791.160 | 293.324.149 | 6.608.467.011 | 0.690179 | 0.029332 | 0.660847 | 10.003505 | 8.948587 | 10.056124 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 13 | 4 | 9 | 0.812500 | 0.250000 | 0.562500 | 1.625000 | 1.333333 | 1.800000 |
5 | 32 | 23 | 6 | 17 | 0.718750 | 0.187500 | 0.531250 | 1.769231 | 1.500000 | 1.888889 |
6 | 64 | 43 | 13 | 30 | 0.671875 | 0.203125 | 0.468750 | 1.869565 | 2.166667 | 1.764706 |
7 | 128 | 85 | 22 | 63 | 0.664062 | 0.171875 | 0.492188 | 1.976744 | 1.692308 | 2.100000 |
8 | 256 | 170 | 36 | 134 | 0.664062 | 0.140625 | 0.523438 | 2.000000 | 1.636364 | 2.126984 |
9 | 512 | 347 | 60 | 287 | 0.677734 | 0.117188 | 0.560547 | 2.041177 | 1.666667 | 2.141791 |
10 | 1.024 | 695 | 115 | 580 | 0.678711 | 0.112305 | 0.566406 | 2.002882 | 1.916667 | 2.020906 |
11 | 2.048 | 1.404 | 191 | 1.213 | 0.685547 | 0.093262 | 0.592285 | 2.020144 | 1.660870 | 2.091379 |
12 | 4.096 | 2.819 | 353 | 2.466 | 0.688232 | 0.086182 | 0.602051 | 2.007835 | 1.848168 | 2.032976 |
13 | 8.192 | 5.626 | 672 | 4.954 | 0.686768 | 0.082031 | 0.604736 | 1.995743 | 1.903683 | 2.008921 |
14 | 16.384 | 11.265 | 1.223 | 10.042 | 0.687561 | 0.074646 | 0.612915 | 2.002311 | 1.819940 | 2.027049 |
15 | 32.768 | 22.499 | 2.322 | 20.177 | 0.686615 | 0.070862 | 0.615753 | 1.997248 | 1.898610 | 2.009261 |
16 | 65.536 | 45.016 | 4.285 | 40.731 | 0.686890 | 0.065384 | 0.621506 | 2.000800 | 1.845392 | 2.018685 |
17 | 131.072 | 90.159 | 7.936 | 82.223 | 0.687859 | 0.060547 | 0.627312 | 2.002821 | 1.852042 | 2.018684 |
18 | 262.144 | 180.402 | 14.929 | 165.473 | 0.688179 | 0.056950 | 0.631229 | 2.000932 | 1.881174 | 2.012491 |
19 | 524.288 | 360.962 | 28.134 | 332.828 | 0.688480 | 0.053661 | 0.634819 | 2.000876 | 1.884520 | 2.011374 |
20 | 1.048.576 | 722.297 | 52.981 | 669.316 | 0.688836 | 0.050527 | 0.638309 | 2.001033 | 1.883166 | 2.010997 |
21 | 2.097.152 | 1.444.871 | 100.548 | 1.344.323 | 0.688968 | 0.047945 | 0.641023 | 2.000384 | 1.897812 | 2.008503 |
22 | 4.194.304 | 2.890.454 | 191.215 | 2.699.239 | 0.689138 | 0.045589 | 0.643549 | 2.000493 | 1.901729 | 2.007880 |
23 | 8.388.608 | 5.782.122 | 364.242 | 5.417.880 | 0.689283 | 0.043421 | 0.645862 | 2.000420 | 1.904882 | 2.007188 |
24 | 16.777.216 | 11.565.667 | 696.109 | 10.869.558 | 0.689367 | 0.041491 | 0.647876 | 2.000246 | 1.911117 | 2.006238 |
25 | 33.554.432 | 23.135.881 | 1.331.030 | 21.804.851 | 0.689503 | 0.039668 | 0.649835 | 2.000393 | 1.912100 | 2.006048 |
26 | 67.108.864 | 46.277.279 | 2.552.969 | 43.724.310 | 0.689585 | 0.038042 | 0.651543 | 2.000239 | 1.918040 | 2.005256 |
27 | 134.217.728 | 92.569.774 | 4.901.990 | 87.667.784 | 0.689699 | 0.036523 | 0.653176 | 2.000329 | 1.920113 | 2.005012 |
28 | 268.435.456 | 185.161.934 | 9.431.884 | 175.730.050 | 0.689782 | 0.035137 | 0.654645 | 2.000242 | 1.924093 | 2.004500 |
29 | 536.870.912 | 370.366.034 | 18.176.160 | 352.189.874 | 0.689861 | 0.033856 | 0.656005 | 2.000228 | 1.927097 | 2.004153 |
30 | 1.073.741.824 | 740.824.186 | 35.069.079 | 705.755.107 | 0.689946 | 0.032661 | 0.657286 | 2.000249 | 1.929400 | 2.003905 |
31 | 2.147.483.648 | 1.481.822.646 | 67.746.552 | 1.414.076.094 | 0.690027 | 0.031547 | 0.658480 | 2.000235 | 1.931803 | 2.003635 |
32 | 4.294.967.296 | 2.963.938.746 | 131.038.995 | 2.832.899.751 | 0.690096 | 0.030510 | 0.659586 | 2.000198 | 1.934253 | 2.003357 |
33 | 8.589.934.592 | 5.928.471.454 | 253.725.547 | 5.674.745.907 | 0.690165 | 0.029538 | 0.660627 | 2.000200 | 1.936260 | 2.003158 |
34 | 17.179.869.184 | 11.858.073.984 | 491.787.196 | 11.366.286.788 | 0.690231 | 0.028626 | 0.661605 | 2.000191 | 1.938264 | 2.002959 |
35 | 34.359.738.368 | 23.718.383.203 | 954.136.247 | 22.764.246.956 | 0.690296 | 0.027769 | 0.662527 | 2.000189 | 1.940140 | 2.002787 |
36 | 68.719.476.736 | 47.441.043.562 | 1.852.868.110 | 45.588.175.452 | 0.690358 | 0.026963 | 0.663395 | 2.000180 | 1.941932 | 2.002622 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 0 | 3 | 0 | 2 | 1 | 0 |
4 | 16 | 4 | 0 | 4 | 1 | 2 | 1 | 0 |
5 | 32 | 6 | 0 | 6 | 1 | 4 | 1 | 0 |
6 | 64 | 13 | 0 | 13 | 3 | 5 | 1 | 4 |
7 | 128 | 22 | 0 | 22 | 6 | 8 | 3 | 5 |
8 | 256 | 36 | 0 | 35 | 8 | 12 | 6 | 10 |
9 | 512 | 60 | 0 | 59 | 17 | 19 | 12 | 12 |
10 | 1.024 | 115 | 0 | 114 | 26 | 32 | 29 | 28 |
11 | 2.048 | 191 | 0 | 190 | 48 | 47 | 47 | 49 |
12 | 4.096 | 353 | 0 | 352 | 92 | 82 | 93 | 86 |
13 | 8.192 | 672 | 0 | 671 | 178 | 159 | 169 | 166 |
14 | 16.384 | 1.223 | 0 | 1.222 | 327 | 291 | 300 | 305 |
15 | 32.768 | 2.322 | 0 | 2.321 | 626 | 570 | 560 | 566 |
16 | 65.536 | 4.285 | 0 | 4.284 | 1.138 | 1.046 | 1.034 | 1.067 |
17 | 131.072 | 7.936 | 0 | 7.935 | 2.054 | 1.964 | 1.948 | 1.970 |
18 | 262.144 | 14.929 | 0 | 14.928 | 3.811 | 3.700 | 3.670 | 3.748 |
19 | 524.288 | 28.134 | 0 | 28.133 | 7.113 | 7.043 | 6.918 | 7.060 |
20 | 1.048.576 | 52.981 | 0 | 52.980 | 13.364 | 13.193 | 13.074 | 13.350 |
21 | 2.097.152 | 100.548 | 0 | 100.547 | 25.255 | 25.124 | 24.944 | 25.225 |
22 | 4.194.304 | 191.215 | 0 | 191.214 | 47.886 | 47.907 | 47.512 | 47.910 |
23 | 8.388.608 | 364.242 | 0 | 364.241 | 91.121 | 91.158 | 90.741 | 91.222 |
24 | 16.777.216 | 696.109 | 0 | 696.108 | 174.217 | 174.387 | 173.520 | 173.985 |
25 | 33.554.432 | 1.331.030 | 0 | 1.331.029 | 332.519 | 332.999 | 332.456 | 333.056 |
26 | 67.108.864 | 2.552.969 | 0 | 2.552.968 | 637.680 | 638.447 | 638.532 | 638.310 |
27 | 134.217.728 | 4.901.990 | 0 | 4.901.989 | 1.225.561 | 1.224.935 | 1.226.420 | 1.225.074 |
28 | 268.435.456 | 9.431.884 | 0 | 9.431.883 | 2.357.996 | 2.357.955 | 2.358.408 | 2.357.525 |
29 | 536.870.912 | 18.176.160 | 0 | 18.176.159 | 4.545.251 | 4.543.793 | 4.544.284 | 4.542.832 |
30 | 1.073.741.824 | 35.069.079 | 0 | 35.069.078 | 8.767.302 | 8.769.544 | 8.767.418 | 8.764.815 |
31 | 2.147.483.648 | 67.746.552 | 0 | 67.746.551 | 16.933.359 | 16.942.886 | 16.935.745 | 16.934.562 |
32 | 4.294.967.296 | 131.038.995 | 0 | 131.038.994 | 32.757.861 | 32.761.484 | 32.762.880 | 32.756.770 |
33 | 8.589.934.592 | 253.725.547 | 0 | 253.725.546 | 63.430.401 | 63.426.030 | 63.432.744 | 63.436.372 |
34 | 17.179.869.184 | 491.787.196 | 0 | 491.787.195 | 122.947.678 | 122.947.781 | 122.946.082 | 122.945.655 |
35 | 34.359.738.368 | 954.136.247 | 0 | 954.136.246 | 238.529.901 | 238.541.192 | 238.533.487 | 238.531.667 |
36 | 68.719.476.736 | 1.852.868.110 | 0 | 1.852.868.109 | 463.219.519 | 463.213.118 | 463.204.401 | 463.231.072 |
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 | 2 | 0 | 0 |
2 | 4 | 3 | 2 | 0 | 0 | 2 | 1 | 0 |
3 | 8 | 5 | 2 | 2 | 0 | 2 | 1 | 2 |
4 | 16 | 9 | 4 | 4 | 0 | 4 | 1 | 4 |
5 | 32 | 17 | 8 | 8 | 4 | 4 | 4 | 5 |
6 | 64 | 30 | 15 | 14 | 4 | 9 | 6 | 11 |
7 | 128 | 63 | 35 | 27 | 12 | 17 | 15 | 19 |
8 | 256 | 134 | 66 | 67 | 28 | 32 | 34 | 40 |
9 | 512 | 287 | 135 | 151 | 67 | 70 | 71 | 79 |
10 | 1.024 | 580 | 283 | 296 | 135 | 140 | 145 | 160 |
11 | 2.048 | 1.213 | 602 | 610 | 300 | 308 | 297 | 308 |
12 | 4.096 | 2.466 | 1.249 | 1.216 | 633 | 618 | 598 | 617 |
13 | 8.192 | 4.954 | 2.508 | 2.445 | 1.237 | 1.259 | 1.212 | 1.246 |
14 | 16.384 | 10.042 | 5.078 | 4.963 | 2.497 | 2.560 | 2.477 | 2.508 |
15 | 32.768 | 20.177 | 10.181 | 9.995 | 5.071 | 5.045 | 5.083 | 4.978 |
16 | 65.536 | 40.731 | 20.523 | 20.207 | 10.224 | 10.213 | 10.099 | 10.195 |
17 | 131.072 | 82.223 | 41.426 | 40.796 | 20.492 | 20.606 | 20.539 | 20.586 |
18 | 262.144 | 165.473 | 83.698 | 81.774 | 41.260 | 41.241 | 41.607 | 41.365 |
19 | 524.288 | 332.828 | 168.291 | 164.536 | 83.104 | 83.154 | 83.342 | 83.228 |
20 | 1.048.576 | 669.316 | 338.163 | 331.152 | 166.902 | 167.203 | 167.639 | 167.572 |
21 | 2.097.152 | 1.344.323 | 678.445 | 665.877 | 335.684 | 335.732 | 336.192 | 336.715 |
22 | 4.194.304 | 2.699.239 | 1.362.148 | 1.337.090 | 674.166 | 674.426 | 674.859 | 675.788 |
23 | 8.388.608 | 5.417.880 | 2.732.562 | 2.685.317 | 1.353.979 | 1.354.316 | 1.354.348 | 1.355.237 |
24 | 16.777.216 | 10.869.558 | 5.478.460 | 5.391.097 | 2.715.661 | 2.718.456 | 2.716.962 | 2.718.479 |
25 | 33.554.432 | 21.804.851 | 10.986.720 | 10.818.130 | 5.450.963 | 5.451.555 | 5.451.135 | 5.451.198 |
26 | 67.108.864 | 43.724.310 | 22.023.180 | 21.701.129 | 10.928.313 | 10.934.233 | 10.930.113 | 10.931.651 |
27 | 134.217.728 | 87.667.784 | 44.140.380 | 43.527.403 | 21.915.974 | 21.919.266 | 21.914.998 | 21.917.546 |
28 | 268.435.456 | 175.730.050 | 88.450.647 | 87.279.402 | 43.936.587 | 43.939.840 | 43.926.585 | 43.927.038 |
29 | 536.870.912 | 352.189.874 | 177.205.759 | 174.984.114 | 88.046.613 | 88.063.935 | 88.044.438 | 88.034.888 |
30 | 1.073.741.824 | 705.755.107 | 355.019.245 | 350.735.861 | 176.439.154 | 176.452.456 | 176.443.363 | 176.420.134 |
31 | 2.147.483.648 | 1.414.076.094 | 711.164.942 | 702.911.151 | 353.523.696 | 353.524.305 | 353.537.997 | 353.490.096 |
32 | 4.294.967.296 | 2.832.899.751 | 1.424.427.873 | 1.408.471.877 | 708.245.413 | 708.238.715 | 708.225.708 | 708.189.915 |
33 | 8.589.934.592 | 5.674.745.907 | 2.852.762.311 | 2.821.983.595 | 1.418.698.988 | 1.418.655.775 | 1.418.705.348 | 1.418.685.796 |
34 | 17.179.869.184 | 11.366.286.788 | 5.712.920.079 | 5.653.366.708 | 2.841.617.239 | 2.841.573.782 | 2.841.530.800 | 2.841.564.967 |
35 | 34.359.738.368 | 22.764.246.956 | 11.439.666.157 | 11.324.580.798 | 5.691.098.991 | 5.691.024.803 | 5.691.034.334 | 5.691.088.828 |
36 | 68.719.476.736 | 45.588.175.452 | 22.905.611.451 | 22.682.564.000 | 11.397.117.999 | 11.397.118.131 | 11.396.877.790 | 11.397.061.532 |