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+179
f(0)=179
f(1)=3
f(2)=23
f(3)=7
f(4)=1
f(5)=11
f(6)=41
f(7)=13
f(8)=113
f(9)=1
f(10)=19
f(11)=1
f(12)=467
f(13)=1
f(14)=181
f(15)=73
f(16)=1
f(17)=1
f(18)=719
f(19)=1
f(20)=1
f(21)=109
f(22)=103
f(23)=1
f(24)=149
f(25)=1
f(26)=389
f(27)=1
f(28)=433
f(29)=1
f(30)=1439
f(31)=1
f(32)=1
f(33)=1
f(34)=83
f(35)=1
f(36)=1907
f(37)=1
f(38)=1
f(39)=271
f(40)=251
f(41)=1
f(42)=2447
f(43)=53
f(44)=881
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1093
f(51)=1
f(52)=167
f(53)=151
f(54)=197
f(55)=1
f(56)=443
f(57)=257
f(58)=157
f(59)=1
f(60)=409
f(61)=193
f(62)=227
f(63)=613
f(64)=1
f(65)=1
f(66)=761
f(67)=1
f(68)=1873
f(69)=1
f(70)=1973
f(71)=1
f(72)=479
f(73)=1
f(74)=727
f(75)=419
f(76)=1
f(77)=293
f(78)=313
f(79)=307
f(80)=359
f(81)=241
f(82)=239
f(83)=1
f(84)=8243
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=191
f(90)=1
f(91)=199
f(92)=1
f(93)=1
f(94)=1
f(95)=431
f(96)=1
f(97)=1
f(98)=281
f(99)=349
b) Substitution of the polynom
The polynom f(x)=x^2+12x+179 could be written as f(y)= y^2+143 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 | 1 | 7 | 0.800000 | 0.100000 | 0.800000 | |||
2 | 100 | 54 | 7 | 47 | 0.540000 | 0.070000 | 0.540000 | 6.750000 | 7.000000 | 6.714286 |
3 | 1.000 | 567 | 45 | 522 | 0.567000 | 0.045000 | 0.567000 | 10.500000 | 6.428571 | 11.106383 |
4 | 10.000 | 6.059 | 351 | 5.708 | 0.605900 | 0.035100 | 0.605900 | 10.686067 | 7.800000 | 10.934866 |
5 | 100.000 | 62.483 | 2.812 | 59.671 | 0.624830 | 0.028120 | 0.624830 | 10.312428 | 8.011396 | 10.453924 |
6 | 1.000.000 | 637.200 | 22.772 | 614.428 | 0.637200 | 0.022772 | 0.637200 | 10.197974 | 8.098151 | 10.296928 |
7 | 10.000.000 | 6.455.896 | 192.724 | 6.263.172 | 0.645590 | 0.019272 | 0.645590 | 10.131663 | 8.463201 | 10.193501 |
8 | 100.000.000 | 65.171.122 | 1.670.470 | 63.500.652 | 0.651711 | 0.016705 | 0.651711 | 10.094822 | 8.667680 | 10.138737 |
9 | 1.000.000.000 | 656.438.436 | 14.733.015 | 641.705.421 | 0.656438 | 0.014733 | 0.656438 | 10.072536 | 8.819682 | 10.105494 |
10 | 10.000.000.000 | 6.601.865.964 | 131.850.442 | 6.470.015.522 | 0.660187 | 0.013185 | 0.660187 | 10.057097 | 8.949318 | 10.082532 |
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 | |||
2 | 4 | 4 | 1 | 3 | 1.000000 | 0.250000 | 0.750000 | 1.333333 | 1.000000 | 1.500000 |
3 | 8 | 8 | 1 | 7 | 1.000000 | 0.125000 | 0.875000 | 2.000000 | 1.000000 | 2.333333 |
4 | 16 | 11 | 2 | 9 | 0.687500 | 0.125000 | 0.562500 | 1.375000 | 2.000000 | 1.285714 |
5 | 32 | 18 | 4 | 14 | 0.562500 | 0.125000 | 0.437500 | 1.636364 | 2.000000 | 1.555556 |
6 | 64 | 35 | 6 | 29 | 0.546875 | 0.093750 | 0.453125 | 1.944444 | 1.500000 | 2.071429 |
7 | 128 | 69 | 9 | 60 | 0.539062 | 0.070312 | 0.468750 | 1.971429 | 1.500000 | 2.068965 |
8 | 256 | 139 | 17 | 122 | 0.542969 | 0.066406 | 0.476562 | 2.014493 | 1.888889 | 2.033333 |
9 | 512 | 287 | 25 | 262 | 0.560547 | 0.048828 | 0.511719 | 2.064748 | 1.470588 | 2.147541 |
10 | 1.024 | 587 | 46 | 541 | 0.573242 | 0.044922 | 0.528320 | 2.045296 | 1.840000 | 2.064885 |
11 | 2.048 | 1.194 | 78 | 1.116 | 0.583008 | 0.038086 | 0.544922 | 2.034071 | 1.695652 | 2.062847 |
12 | 4.096 | 2.452 | 149 | 2.303 | 0.598633 | 0.036377 | 0.562256 | 2.053601 | 1.910256 | 2.063620 |
13 | 8.192 | 4.946 | 295 | 4.651 | 0.603760 | 0.036011 | 0.567749 | 2.017129 | 1.979866 | 2.019540 |
14 | 16.384 | 9.995 | 553 | 9.442 | 0.610046 | 0.033752 | 0.576294 | 2.020825 | 1.874576 | 2.030101 |
15 | 32.768 | 20.203 | 1.033 | 19.170 | 0.616547 | 0.031525 | 0.585022 | 2.021311 | 1.867993 | 2.030290 |
16 | 65.536 | 40.758 | 1.940 | 38.818 | 0.621918 | 0.029602 | 0.592316 | 2.017423 | 1.878025 | 2.024935 |
17 | 131.072 | 82.101 | 3.600 | 78.501 | 0.626381 | 0.027466 | 0.598915 | 2.014353 | 1.855670 | 2.022284 |
18 | 262.144 | 165.365 | 6.688 | 158.677 | 0.630817 | 0.025513 | 0.605305 | 2.014165 | 1.857778 | 2.021337 |
19 | 524.288 | 332.553 | 12.614 | 319.939 | 0.634295 | 0.024059 | 0.610235 | 2.011024 | 1.886065 | 2.016291 |
20 | 1.048.576 | 668.358 | 23.805 | 644.553 | 0.637396 | 0.022702 | 0.614694 | 2.009779 | 1.887189 | 2.014612 |
21 | 2.097.152 | 1.342.631 | 45.178 | 1.297.453 | 0.640216 | 0.021543 | 0.618674 | 2.008850 | 1.897837 | 2.012950 |
22 | 4.194.304 | 2.695.854 | 85.889 | 2.609.965 | 0.642742 | 0.020478 | 0.622264 | 2.007889 | 1.901124 | 2.011607 |
23 | 8.388.608 | 5.410.986 | 163.526 | 5.247.460 | 0.645040 | 0.019494 | 0.625546 | 2.007151 | 1.903923 | 2.010548 |
24 | 16.777.216 | 10.856.540 | 312.595 | 10.543.945 | 0.647100 | 0.018632 | 0.628468 | 2.006388 | 1.911592 | 2.009343 |
25 | 33.554.432 | 21.777.451 | 597.904 | 21.179.547 | 0.649019 | 0.017819 | 0.631200 | 2.005929 | 1.912711 | 2.008693 |
26 | 67.108.864 | 43.672.077 | 1.147.584 | 42.524.493 | 0.650765 | 0.017100 | 0.633664 | 2.005380 | 1.919345 | 2.007809 |
27 | 134.217.728 | 87.561.222 | 2.204.248 | 85.356.974 | 0.652382 | 0.016423 | 0.635959 | 2.004971 | 1.920773 | 2.007243 |
28 | 268.435.456 | 175.523.886 | 4.239.783 | 171.284.103 | 0.653877 | 0.015794 | 0.638083 | 2.004585 | 1.923460 | 2.006680 |
29 | 536.870.912 | 351.792.638 | 8.169.449 | 343.623.189 | 0.655265 | 0.015217 | 0.640048 | 2.004244 | 1.926855 | 2.006159 |
30 | 1.073.741.824 | 704.980.409 | 15.763.189 | 689.217.220 | 0.656564 | 0.014681 | 0.641884 | 2.003966 | 1.929529 | 2.005735 |
31 | 2.147.483.648 | 1.412.550.770 | 30.451.906 | 1.382.098.864 | 0.657770 | 0.014180 | 0.643590 | 2.003674 | 1.931837 | 2.005317 |
32 | 4.294.967.296 | 2.829.957.490 | 58.900.322 | 2.771.057.168 | 0.658901 | 0.013714 | 0.645187 | 2.003438 | 1.934208 | 2.004963 |
33 | 8.589.934.592 | 5.669.038.543 | 114.049.499 | 5.554.989.044 | 0.659963 | 0.013277 | 0.646686 | 2.003224 | 1.936314 | 2.004646 |
34 | 17.179.869.184 | 11.355.196.270 | 221.063.690 | 11.134.132.580 | 0.660959 | 0.012868 | 0.648092 | 2.003020 | 1.938314 | 2.004348 |
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 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 16 | 2 | 0 | 2 | 0 | 2 | 0 | 0 |
5 | 32 | 4 | 0 | 4 | 0 | 2 | 0 | 2 |
6 | 64 | 6 | 0 | 6 | 0 | 3 | 0 | 3 |
7 | 128 | 9 | 0 | 9 | 0 | 4 | 0 | 5 |
8 | 256 | 17 | 0 | 17 | 0 | 8 | 0 | 9 |
9 | 512 | 25 | 0 | 25 | 0 | 14 | 0 | 11 |
10 | 1.024 | 46 | 0 | 46 | 0 | 25 | 0 | 21 |
11 | 2.048 | 78 | 0 | 78 | 0 | 43 | 0 | 35 |
12 | 4.096 | 149 | 0 | 149 | 0 | 79 | 0 | 70 |
13 | 8.192 | 295 | 0 | 295 | 0 | 149 | 0 | 146 |
14 | 16.384 | 553 | 0 | 553 | 0 | 279 | 0 | 274 |
15 | 32.768 | 1.033 | 0 | 1.033 | 0 | 518 | 0 | 515 |
16 | 65.536 | 1.940 | 0 | 1.940 | 0 | 972 | 0 | 968 |
17 | 131.072 | 3.600 | 0 | 3.600 | 0 | 1.819 | 0 | 1.781 |
18 | 262.144 | 6.688 | 0 | 6.688 | 0 | 3.342 | 0 | 3.346 |
19 | 524.288 | 12.614 | 0 | 12.614 | 0 | 6.307 | 0 | 6.307 |
20 | 1.048.576 | 23.805 | 0 | 23.805 | 0 | 11.932 | 0 | 11.873 |
21 | 2.097.152 | 45.178 | 0 | 45.178 | 0 | 22.650 | 0 | 22.528 |
22 | 4.194.304 | 85.889 | 0 | 85.889 | 0 | 43.008 | 0 | 42.881 |
23 | 8.388.608 | 163.526 | 0 | 163.526 | 0 | 81.952 | 0 | 81.574 |
24 | 16.777.216 | 312.595 | 0 | 312.595 | 0 | 156.736 | 0 | 155.859 |
25 | 33.554.432 | 597.904 | 0 | 597.904 | 0 | 299.187 | 0 | 298.717 |
26 | 67.108.864 | 1.147.584 | 0 | 1.147.584 | 0 | 574.384 | 0 | 573.200 |
27 | 134.217.728 | 2.204.248 | 0 | 2.204.248 | 0 | 1.102.785 | 0 | 1.101.463 |
28 | 268.435.456 | 4.239.783 | 0 | 4.239.783 | 0 | 2.120.544 | 0 | 2.119.239 |
29 | 536.870.912 | 8.169.449 | 0 | 8.169.449 | 0 | 4.084.555 | 0 | 4.084.894 |
30 | 1.073.741.824 | 15.763.189 | 0 | 15.763.189 | 0 | 7.881.128 | 0 | 7.882.061 |
31 | 2.147.483.648 | 30.451.906 | 0 | 30.451.906 | 0 | 15.225.558 | 0 | 15.226.348 |
32 | 4.294.967.296 | 58.900.322 | 0 | 58.900.322 | 0 | 29.450.986 | 0 | 29.449.336 |
33 | 8.589.934.592 | 114.049.499 | 0 | 114.049.499 | 0 | 57.026.514 | 0 | 57.022.985 |
34 | 17.179.869.184 | 221.063.690 | 0 | 221.063.690 | 0 | 110.530.544 | 0 | 110.533.146 |
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 | 0 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 0 | 2 |
3 | 8 | 7 | 1 | 3 | 3 | 1 | 0 | 3 |
4 | 16 | 9 | 3 | 3 | 4 | 1 | 1 | 3 |
5 | 32 | 14 | 6 | 5 | 5 | 1 | 4 | 4 |
6 | 64 | 29 | 13 | 13 | 9 | 5 | 8 | 7 |
7 | 128 | 60 | 25 | 32 | 18 | 10 | 16 | 16 |
8 | 256 | 122 | 62 | 57 | 37 | 22 | 33 | 30 |
9 | 512 | 262 | 132 | 127 | 75 | 53 | 73 | 61 |
10 | 1.024 | 541 | 270 | 268 | 146 | 121 | 147 | 127 |
11 | 2.048 | 1.116 | 551 | 562 | 300 | 257 | 313 | 246 |
12 | 4.096 | 2.303 | 1.156 | 1.144 | 610 | 543 | 620 | 530 |
13 | 8.192 | 4.651 | 2.345 | 2.303 | 1.195 | 1.110 | 1.227 | 1.119 |
14 | 16.384 | 9.442 | 4.796 | 4.643 | 2.441 | 2.246 | 2.509 | 2.246 |
15 | 32.768 | 19.170 | 9.764 | 9.403 | 4.998 | 4.560 | 5.024 | 4.588 |
16 | 65.536 | 38.818 | 19.699 | 19.116 | 10.222 | 9.162 | 10.226 | 9.208 |
17 | 131.072 | 78.501 | 39.611 | 38.887 | 20.479 | 18.754 | 20.634 | 18.634 |
18 | 262.144 | 158.677 | 80.039 | 78.635 | 41.340 | 37.943 | 41.429 | 37.965 |
19 | 524.288 | 319.939 | 161.228 | 158.708 | 83.162 | 76.704 | 83.242 | 76.831 |
20 | 1.048.576 | 644.553 | 324.296 | 320.254 | 167.209 | 155.084 | 167.081 | 155.179 |
21 | 2.097.152 | 1.297.453 | 653.199 | 644.251 | 335.367 | 312.617 | 336.269 | 313.200 |
22 | 4.194.304 | 2.609.965 | 1.313.238 | 1.296.724 | 673.891 | 630.627 | 674.264 | 631.183 |
23 | 8.388.608 | 5.247.460 | 2.639.680 | 2.607.777 | 1.352.069 | 1.270.226 | 1.354.218 | 1.270.947 |
24 | 16.777.216 | 10.543.945 | 5.303.946 | 5.239.996 | 2.715.257 | 2.556.848 | 2.714.632 | 2.557.208 |
25 | 33.554.432 | 21.179.547 | 10.647.688 | 10.531.856 | 5.446.534 | 5.141.825 | 5.447.371 | 5.143.817 |
26 | 67.108.864 | 42.524.493 | 21.376.794 | 21.147.696 | 10.921.447 | 10.336.284 | 10.924.809 | 10.341.953 |
27 | 134.217.728 | 85.356.974 | 42.892.256 | 42.464.715 | 21.899.493 | 20.775.138 | 21.901.874 | 20.780.469 |
28 | 268.435.456 | 171.284.103 | 86.048.860 | 85.235.240 | 43.895.725 | 41.742.774 | 43.901.266 | 41.744.338 |
29 | 536.870.912 | 343.623.189 | 172.589.172 | 171.034.014 | 87.978.426 | 83.837.169 | 87.973.734 | 83.833.860 |
30 | 1.073.741.824 | 689.217.220 | 346.102.660 | 343.114.557 | 176.290.276 | 168.314.233 | 176.297.872 | 168.314.839 |
31 | 2.147.483.648 | 1.382.098.864 | 693.915.393 | 688.183.468 | 353.221.907 | 337.818.729 | 353.234.759 | 337.823.469 |
32 | 4.294.967.296 | 2.771.057.168 | 1.391.013.515 | 1.380.043.650 | 707.652.021 | 677.873.455 | 707.649.024 | 677.882.668 |
33 | 8.589.934.592 | 5.554.989.044 | 2.788.101.611 | 2.766.887.430 | 1.417.540.932 | 1.359.922.984 | 1.417.591.064 | 1.359.934.064 |
34 | 17.179.869.184 | 11.134.132.580 | 5.587.619.752 | 5.546.512.825 | 2.839.350.648 | 2.727.687.217 | 2.839.434.583 | 2.727.660.132 |