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+64x+3
f(0)=3
f(1)=17
f(2)=5
f(3)=1
f(4)=11
f(5)=29
f(6)=47
f(7)=1
f(8)=193
f(9)=1
f(10)=743
f(11)=23
f(12)=61
f(13)=251
f(14)=73
f(15)=1
f(16)=1283
f(17)=1
f(18)=1
f(19)=79
f(20)=1
f(21)=149
f(22)=379
f(23)=167
f(24)=1
f(25)=557
f(26)=71
f(27)=41
f(28)=2579
f(29)=1
f(30)=941
f(31)=67
f(32)=1
f(33)=89
f(34)=1
f(35)=1
f(36)=1201
f(37)=1
f(38)=431
f(39)=1
f(40)=181
f(41)=359
f(42)=1
f(43)=1151
f(44)=317
f(45)=409
f(46)=83
f(47)=1
f(48)=163
f(49)=277
f(50)=1901
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1637
f(56)=1
f(57)=1
f(58)=7079
f(59)=1
f(60)=827
f(61)=1907
f(62)=521
f(63)=1
f(64)=1
f(65)=233
f(66)=2861
f(67)=439
f(68)=1
f(69)=1
f(70)=853
f(71)=1
f(72)=653
f(73)=1
f(74)=227
f(75)=1
f(76)=367
f(77)=1
f(78)=1231
f(79)=113
f(80)=1
f(81)=1
f(82)=479
f(83)=1
f(84)=829
f(85)=3167
f(86)=1
f(87)=1
f(88)=787
f(89)=1
f(90)=4621
f(91)=3527
f(92)=1
f(93)=1217
f(94)=2971
f(95)=1259
f(96)=569
f(97)=1
f(98)=1
f(99)=269
b) Substitution of the polynom
The polynom f(x)=x^2+64x+3 could be written as f(y)= y^2-1021 with x=y-32
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+32
f'(x)>2x+63
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.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 13 | 45 | 0.580000 | 0.130000 | 0.450000 | 7.250000 | 4.333333 | 9.000000 |
3 | 1.000 | 582 | 75 | 507 | 0.582000 | 0.075000 | 0.507000 | 10.034483 | 5.769231 | 11.266666 |
4 | 10.000 | 6.140 | 549 | 5.591 | 0.614000 | 0.054900 | 0.559100 | 10.549829 | 7.320000 | 11.027614 |
5 | 100.000 | 62.959 | 4.118 | 58.841 | 0.629590 | 0.041180 | 0.588410 | 10.253909 | 7.500911 | 10.524236 |
6 | 1.000.000 | 641.070 | 33.604 | 607.466 | 0.641070 | 0.033604 | 0.607466 | 10.182341 | 8.160272 | 10.323855 |
7 | 10.000.000 | 6.486.663 | 283.001 | 6.203.662 | 0.648666 | 0.028300 | 0.620366 | 10.118494 | 8.421646 | 10.212360 |
8 | 100.000.000 | 65.438.922 | 2.444.340 | 62.994.582 | 0.654389 | 0.024443 | 0.629946 | 10.088225 | 8.637214 | 10.154419 |
9 | 1.000.000.000 | 658.757.798 | 21.511.795 | 637.246.003 | 0.658758 | 0.021512 | 0.637246 | 10.066759 | 8.800656 | 10.115886 |
10 | 10.000.000.000 | 6.622.420.042 | 192.124.480 | 6.430.295.562 | 0.662242 | 0.019212 | 0.643030 | 10.052890 | 8.931122 | 10.090758 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 7 | 2 | 5 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 1.000000 | 2.500000 |
4 | 16 | 13 | 5 | 8 | 0.812500 | 0.312500 | 0.500000 | 1.857143 | 2.500000 | 1.600000 |
5 | 32 | 22 | 7 | 15 | 0.687500 | 0.218750 | 0.468750 | 1.692308 | 1.400000 | 1.875000 |
6 | 64 | 38 | 11 | 27 | 0.593750 | 0.171875 | 0.421875 | 1.727273 | 1.571429 | 1.800000 |
7 | 128 | 74 | 14 | 60 | 0.578125 | 0.109375 | 0.468750 | 1.947368 | 1.272727 | 2.222222 |
8 | 256 | 143 | 27 | 116 | 0.558594 | 0.105469 | 0.453125 | 1.932432 | 1.928571 | 1.933333 |
9 | 512 | 294 | 51 | 243 | 0.574219 | 0.099609 | 0.474609 | 2.055944 | 1.888889 | 2.094828 |
10 | 1.024 | 596 | 77 | 519 | 0.582031 | 0.075195 | 0.506836 | 2.027211 | 1.509804 | 2.135803 |
11 | 2.048 | 1.229 | 141 | 1.088 | 0.600098 | 0.068848 | 0.531250 | 2.062081 | 1.831169 | 2.096339 |
12 | 4.096 | 2.469 | 249 | 2.220 | 0.602783 | 0.060791 | 0.541992 | 2.008950 | 1.765957 | 2.040441 |
13 | 8.192 | 5.027 | 465 | 4.562 | 0.613647 | 0.056763 | 0.556885 | 2.036047 | 1.867470 | 2.054955 |
14 | 16.384 | 10.125 | 858 | 9.267 | 0.617981 | 0.052368 | 0.565613 | 2.014124 | 1.845161 | 2.031346 |
15 | 32.768 | 20.374 | 1.545 | 18.829 | 0.621765 | 0.047150 | 0.574615 | 2.012247 | 1.800699 | 2.031833 |
16 | 65.536 | 41.039 | 2.858 | 38.181 | 0.626205 | 0.043610 | 0.582596 | 2.014283 | 1.849838 | 2.027776 |
17 | 131.072 | 82.734 | 5.248 | 77.486 | 0.631210 | 0.040039 | 0.591171 | 2.015985 | 1.836249 | 2.029439 |
18 | 262.144 | 166.459 | 9.835 | 156.624 | 0.634991 | 0.037518 | 0.597473 | 2.011978 | 1.874047 | 2.021320 |
19 | 524.288 | 334.712 | 18.632 | 316.080 | 0.638412 | 0.035538 | 0.602875 | 2.010777 | 1.894459 | 2.018081 |
20 | 1.048.576 | 672.327 | 35.091 | 637.236 | 0.641181 | 0.033465 | 0.607716 | 2.008673 | 1.883373 | 2.016059 |
21 | 2.097.152 | 1.350.178 | 66.314 | 1.283.864 | 0.643815 | 0.031621 | 0.612194 | 2.008216 | 1.889772 | 2.014739 |
22 | 4.194.304 | 2.709.887 | 126.121 | 2.583.766 | 0.646087 | 0.030070 | 0.616018 | 2.007059 | 1.901876 | 2.012492 |
23 | 8.388.608 | 5.437.145 | 240.407 | 5.196.738 | 0.648158 | 0.028659 | 0.619499 | 2.006410 | 1.906162 | 2.011304 |
24 | 16.777.216 | 10.907.833 | 458.269 | 10.449.564 | 0.650158 | 0.027315 | 0.622843 | 2.006169 | 1.906222 | 2.010793 |
25 | 33.554.432 | 21.873.234 | 876.765 | 20.996.469 | 0.651873 | 0.026130 | 0.625744 | 2.005278 | 1.913210 | 2.009315 |
26 | 67.108.864 | 43.856.091 | 1.679.790 | 42.176.301 | 0.653507 | 0.025031 | 0.628476 | 2.005012 | 1.915895 | 2.008733 |
27 | 134.217.728 | 87.913.789 | 3.224.606 | 84.689.183 | 0.655009 | 0.024025 | 0.630984 | 2.004597 | 1.919648 | 2.007980 |
28 | 268.435.456 | 176.199.238 | 6.199.440 | 169.999.798 | 0.656393 | 0.023095 | 0.633299 | 2.004227 | 1.922542 | 2.007338 |
29 | 536.870.912 | 353.084.974 | 11.936.892 | 341.148.082 | 0.657672 | 0.022234 | 0.635438 | 2.003896 | 1.925479 | 2.006756 |
30 | 1.073.741.824 | 707.466.380 | 23.013.194 | 684.453.186 | 0.658879 | 0.021433 | 0.637447 | 2.003672 | 1.927905 | 2.006323 |
31 | 2.147.483.648 | 1.417.341.188 | 44.426.105 | 1.372.915.083 | 0.660001 | 0.020688 | 0.639313 | 2.003404 | 1.930462 | 2.005857 |
32 | 4.294.967.296 | 2.839.187.658 | 85.875.536 | 2.753.312.122 | 0.661050 | 0.019994 | 0.641055 | 2.003179 | 1.932997 | 2.005450 |
33 | 8.589.934.592 | 5.686.834.431 | 166.203.138 | 5.520.631.293 | 0.662035 | 0.019349 | 0.642686 | 2.002979 | 1.935396 | 2.005087 |
34 | 17.179.869.184 | 11.389.608.500 | 321.999.574 | 11.067.608.926 | 0.662962 | 0.018743 | 0.644220 | 2.002803 | 1.937386 | 2.004772 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 5 | 0 | 4 | 1 | 3 | 0 | 1 |
5 | 32 | 7 | 0 | 6 | 1 | 4 | 1 | 1 |
6 | 64 | 11 | 0 | 10 | 1 | 5 | 2 | 3 |
7 | 128 | 14 | 0 | 13 | 1 | 6 | 2 | 5 |
8 | 256 | 27 | 0 | 26 | 5 | 9 | 3 | 10 |
9 | 512 | 51 | 0 | 50 | 9 | 15 | 5 | 22 |
10 | 1.024 | 77 | 0 | 76 | 12 | 25 | 8 | 32 |
11 | 2.048 | 141 | 0 | 140 | 19 | 49 | 18 | 55 |
12 | 4.096 | 249 | 0 | 248 | 36 | 88 | 29 | 96 |
13 | 8.192 | 465 | 0 | 464 | 62 | 153 | 56 | 194 |
14 | 16.384 | 858 | 0 | 857 | 118 | 299 | 107 | 334 |
15 | 32.768 | 1.545 | 0 | 1.544 | 210 | 543 | 204 | 588 |
16 | 65.536 | 2.858 | 0 | 2.857 | 373 | 1.059 | 384 | 1.042 |
17 | 131.072 | 5.248 | 0 | 5.247 | 670 | 1.946 | 685 | 1.947 |
18 | 262.144 | 9.835 | 0 | 9.834 | 1.308 | 3.642 | 1.256 | 3.629 |
19 | 524.288 | 18.632 | 0 | 18.631 | 2.446 | 6.902 | 2.402 | 6.882 |
20 | 1.048.576 | 35.091 | 0 | 35.090 | 4.506 | 13.027 | 4.507 | 13.051 |
21 | 2.097.152 | 66.314 | 0 | 66.313 | 8.541 | 24.707 | 8.493 | 24.573 |
22 | 4.194.304 | 126.121 | 0 | 126.120 | 16.109 | 46.999 | 16.182 | 46.831 |
23 | 8.388.608 | 240.407 | 0 | 240.406 | 30.720 | 89.743 | 30.772 | 89.172 |
24 | 16.777.216 | 458.269 | 0 | 458.268 | 58.635 | 170.900 | 58.559 | 170.175 |
25 | 33.554.432 | 876.765 | 0 | 876.764 | 112.038 | 326.672 | 112.194 | 325.861 |
26 | 67.108.864 | 1.679.790 | 0 | 1.679.789 | 214.129 | 625.770 | 214.590 | 625.301 |
27 | 134.217.728 | 3.224.606 | 0 | 3.224.605 | 410.604 | 1.201.064 | 411.508 | 1.201.430 |
28 | 268.435.456 | 6.199.440 | 0 | 6.199.439 | 789.388 | 2.309.630 | 790.600 | 2.309.822 |
29 | 536.870.912 | 11.936.892 | 0 | 11.936.891 | 1.519.277 | 4.448.326 | 1.519.211 | 4.450.078 |
30 | 1.073.741.824 | 23.013.194 | 0 | 23.013.193 | 2.928.044 | 8.578.991 | 2.928.193 | 8.577.966 |
31 | 2.147.483.648 | 44.426.105 | 0 | 44.426.104 | 5.649.127 | 16.563.613 | 5.649.378 | 16.563.987 |
32 | 4.294.967.296 | 85.875.536 | 0 | 85.875.535 | 10.911.584 | 32.024.272 | 10.915.909 | 32.023.771 |
33 | 8.589.934.592 | 166.203.138 | 0 | 166.203.137 | 21.110.904 | 61.990.924 | 21.113.391 | 61.987.919 |
34 | 17.179.869.184 | 321.999.574 | 0 | 321.999.573 | 40.881.574 | 120.118.069 | 40.879.430 | 120.120.501 |
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 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 5 | 1 | 4 | 1 | 1 | 2 | 1 |
4 | 16 | 8 | 3 | 5 | 2 | 1 | 3 | 2 |
5 | 32 | 15 | 6 | 9 | 2 | 3 | 5 | 5 |
6 | 64 | 27 | 11 | 16 | 6 | 5 | 9 | 7 |
7 | 128 | 60 | 30 | 30 | 14 | 14 | 18 | 14 |
8 | 256 | 116 | 61 | 55 | 33 | 26 | 30 | 27 |
9 | 512 | 243 | 130 | 113 | 69 | 47 | 71 | 56 |
10 | 1.024 | 519 | 278 | 241 | 133 | 115 | 149 | 122 |
11 | 2.048 | 1.088 | 595 | 493 | 275 | 254 | 298 | 261 |
12 | 4.096 | 2.220 | 1.221 | 999 | 577 | 526 | 580 | 537 |
13 | 8.192 | 4.562 | 2.448 | 2.114 | 1.185 | 1.094 | 1.195 | 1.088 |
14 | 16.384 | 9.267 | 4.912 | 4.355 | 2.397 | 2.224 | 2.414 | 2.232 |
15 | 32.768 | 18.829 | 9.953 | 8.876 | 4.866 | 4.479 | 4.914 | 4.570 |
16 | 65.536 | 38.181 | 20.136 | 18.045 | 9.932 | 9.138 | 9.884 | 9.227 |
17 | 131.072 | 77.486 | 40.607 | 36.879 | 20.037 | 18.604 | 20.120 | 18.725 |
18 | 262.144 | 156.624 | 81.948 | 74.676 | 40.394 | 37.577 | 40.484 | 38.169 |
19 | 524.288 | 316.080 | 164.775 | 151.305 | 81.480 | 76.395 | 81.200 | 77.005 |
20 | 1.048.576 | 637.236 | 331.282 | 305.954 | 164.010 | 154.434 | 163.307 | 155.485 |
21 | 2.097.152 | 1.283.864 | 665.708 | 618.156 | 329.765 | 312.286 | 328.610 | 313.203 |
22 | 4.194.304 | 2.583.766 | 1.337.712 | 1.246.054 | 662.686 | 629.709 | 661.421 | 629.950 |
23 | 8.388.608 | 5.196.738 | 2.686.455 | 2.510.283 | 1.330.614 | 1.268.058 | 1.329.493 | 1.268.573 |
24 | 16.777.216 | 10.449.564 | 5.393.927 | 5.055.637 | 2.671.190 | 2.554.035 | 2.670.021 | 2.554.318 |
25 | 33.554.432 | 20.996.469 | 10.816.965 | 10.179.504 | 5.359.030 | 5.136.714 | 5.364.081 | 5.136.644 |
26 | 67.108.864 | 42.176.301 | 21.700.176 | 20.476.125 | 10.755.633 | 10.329.192 | 10.761.123 | 10.330.353 |
27 | 134.217.728 | 84.689.183 | 43.517.549 | 41.171.634 | 21.579.012 | 20.759.838 | 21.584.130 | 20.766.203 |
28 | 268.435.456 | 169.999.798 | 87.248.846 | 82.750.952 | 43.284.688 | 41.707.384 | 43.292.716 | 41.715.010 |
29 | 536.870.912 | 341.148.082 | 174.897.257 | 166.250.825 | 86.797.204 | 83.768.264 | 86.805.380 | 83.777.234 |
30 | 1.073.741.824 | 684.453.186 | 350.554.060 | 333.899.126 | 174.028.959 | 168.185.235 | 174.035.829 | 168.203.163 |
31 | 2.147.483.648 | 1.372.915.083 | 702.519.107 | 670.395.976 | 348.849.340 | 337.592.497 | 348.853.202 | 337.620.044 |
32 | 4.294.967.296 | 2.753.312.122 | 1.407.669.896 | 1.345.642.226 | 699.171.698 | 677.485.590 | 699.209.800 | 677.445.034 |
33 | 8.589.934.592 | 5.520.631.293 | 2.820.241.452 | 2.700.389.841 | 1.401.184.657 | 1.359.111.851 | 1.401.220.603 | 1.359.114.182 |
34 | 17.179.869.184 | 11.067.608.926 | 5.649.742.438 | 5.417.866.488 | 2.807.596.686 | 2.726.160.705 | 2.807.644.863 | 2.726.206.672 |