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+32x+5
f(0)=5
f(1)=19
f(2)=73
f(3)=11
f(4)=149
f(5)=1
f(6)=233
f(7)=139
f(8)=13
f(9)=17
f(10)=1
f(11)=239
f(12)=41
f(13)=59
f(14)=1
f(15)=71
f(16)=773
f(17)=419
f(18)=181
f(19)=487
f(20)=1
f(21)=43
f(22)=1193
f(23)=127
f(24)=1
f(25)=1
f(26)=89
f(27)=47
f(28)=337
f(29)=887
f(30)=373
f(31)=1
f(32)=2053
f(33)=1
f(34)=173
f(35)=1
f(36)=223
f(37)=1279
f(38)=1
f(39)=1
f(40)=577
f(41)=1499
f(42)=283
f(43)=1
f(44)=197
f(45)=347
f(46)=3593
f(47)=1
f(48)=769
f(49)=1987
f(50)=821
f(51)=163
f(52)=4373
f(53)=1
f(54)=4649
f(55)=479
f(56)=4933
f(57)=2539
f(58)=1
f(59)=2687
f(60)=1
f(61)=167
f(62)=307
f(63)=599
f(64)=1
f(65)=631
f(66)=6473
f(67)=3319
f(68)=1361
f(69)=317
f(70)=1429
f(71)=3659
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=191
f(77)=1
f(78)=101
f(79)=107
f(80)=1
f(81)=241
f(82)=199
f(83)=1
f(84)=9749
f(85)=1
f(86)=1
f(87)=5179
f(88)=2113
f(89)=5387
f(90)=1
f(91)=509
f(92)=113
f(93)=1163
f(94)=1
f(95)=1
f(96)=647
f(97)=569
f(98)=2549
f(99)=499
b) Substitution of the polynom
The polynom f(x)=x^2+32x+5 could be written as f(y)= y^2-251 with x=y-16
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+16
f'(x)>2x+31
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 | 7 | 6 | 1 | 0.700000 | 0.600000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 65 | 28 | 37 | 0.650000 | 0.280000 | 0.370000 | 9.285714 | 4.666667 | 37.000000 |
3 | 1.000 | 655 | 198 | 457 | 0.655000 | 0.198000 | 0.457000 | 10.076923 | 7.071429 | 12.351352 |
4 | 10.000 | 6.733 | 1.373 | 5.360 | 0.673300 | 0.137300 | 0.536000 | 10.279389 | 6.934343 | 11.728665 |
5 | 100.000 | 67.760 | 10.361 | 57.399 | 0.677600 | 0.103610 | 0.573990 | 10.063865 | 7.546249 | 10.708769 |
6 | 1.000.000 | 680.117 | 84.294 | 595.823 | 0.680117 | 0.084294 | 0.595823 | 10.037146 | 8.135701 | 10.380372 |
7 | 10.000.000 | 6.819.350 | 711.622 | 6.107.728 | 0.681935 | 0.071162 | 0.610773 | 10.026731 | 8.442143 | 10.250910 |
8 | 100.000.000 | 68.325.254 | 6.152.451 | 62.172.803 | 0.683253 | 0.061525 | 0.621728 | 10.019320 | 8.645673 | 10.179367 |
9 | 1.000.000.000 | 684.278.786 | 54.227.951 | 630.050.835 | 0.684279 | 0.054228 | 0.630051 | 10.015019 | 8.814040 | 10.133865 |
10 | 10.000.000.000 | 6.851.087.823 | 484.815.507 | 6.366.272.316 | 0.685109 | 0.048482 | 0.636627 | 10.012130 | 8.940325 | 10.104380 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 7 | 6 | 1 | 0.875000 | 0.750000 | 0.125000 | 1.400000 | 1.500000 | 1.000000 |
4 | 16 | 12 | 8 | 4 | 0.750000 | 0.500000 | 0.250000 | 1.714286 | 1.333333 | 4.000000 |
5 | 32 | 23 | 13 | 10 | 0.718750 | 0.406250 | 0.312500 | 1.916667 | 1.625000 | 2.500000 |
6 | 64 | 45 | 22 | 23 | 0.703125 | 0.343750 | 0.359375 | 1.956522 | 1.692308 | 2.300000 |
7 | 128 | 80 | 37 | 43 | 0.625000 | 0.289062 | 0.335938 | 1.777778 | 1.681818 | 1.869565 |
8 | 256 | 163 | 64 | 99 | 0.636719 | 0.250000 | 0.386719 | 2.037500 | 1.729730 | 2.302325 |
9 | 512 | 333 | 109 | 224 | 0.650391 | 0.212891 | 0.437500 | 2.042945 | 1.703125 | 2.262626 |
10 | 1.024 | 672 | 200 | 472 | 0.656250 | 0.195312 | 0.460938 | 2.018018 | 1.834862 | 2.107143 |
11 | 2.048 | 1.361 | 355 | 1.006 | 0.664551 | 0.173340 | 0.491211 | 2.025298 | 1.775000 | 2.131356 |
12 | 4.096 | 2.732 | 628 | 2.104 | 0.666992 | 0.153320 | 0.513672 | 2.007348 | 1.769014 | 2.091451 |
13 | 8.192 | 5.506 | 1.155 | 4.351 | 0.672119 | 0.140991 | 0.531128 | 2.015373 | 1.839172 | 2.067966 |
14 | 16.384 | 11.066 | 2.085 | 8.981 | 0.675415 | 0.127258 | 0.548157 | 2.009808 | 1.805195 | 2.064123 |
15 | 32.768 | 22.158 | 3.857 | 18.301 | 0.676208 | 0.117706 | 0.558502 | 2.002350 | 1.849880 | 2.037746 |
16 | 65.536 | 44.322 | 7.112 | 37.210 | 0.676300 | 0.108521 | 0.567780 | 2.000271 | 1.843920 | 2.033222 |
17 | 131.072 | 88.870 | 13.201 | 75.669 | 0.678024 | 0.100716 | 0.577309 | 2.005099 | 1.856159 | 2.033566 |
18 | 262.144 | 177.942 | 24.701 | 153.241 | 0.678795 | 0.094227 | 0.584568 | 2.002273 | 1.871146 | 2.025149 |
19 | 524.288 | 356.202 | 46.572 | 309.630 | 0.679401 | 0.088829 | 0.590572 | 2.001787 | 1.885430 | 2.020543 |
20 | 1.048.576 | 713.172 | 88.035 | 625.137 | 0.680134 | 0.083957 | 0.596177 | 2.002156 | 1.890299 | 2.018981 |
21 | 2.097.152 | 1.427.807 | 166.794 | 1.261.013 | 0.680831 | 0.079534 | 0.601298 | 2.002051 | 1.894633 | 2.017179 |
22 | 4.194.304 | 2.858.297 | 316.555 | 2.541.742 | 0.681471 | 0.075473 | 0.605999 | 2.001879 | 1.897880 | 2.015635 |
23 | 8.388.608 | 5.719.731 | 603.728 | 5.116.003 | 0.681845 | 0.071970 | 0.609875 | 2.001097 | 1.907182 | 2.012794 |
24 | 16.777.216 | 11.446.696 | 1.153.447 | 10.293.249 | 0.682276 | 0.068751 | 0.613525 | 2.001265 | 1.910541 | 2.011971 |
25 | 33.554.432 | 22.906.933 | 2.206.084 | 20.700.849 | 0.682680 | 0.065746 | 0.616933 | 2.001183 | 1.912601 | 2.011109 |
26 | 67.108.864 | 45.839.689 | 4.227.915 | 41.611.774 | 0.683065 | 0.063001 | 0.620064 | 2.001127 | 1.916480 | 2.010148 |
27 | 134.217.728 | 91.722.939 | 8.118.320 | 83.604.619 | 0.683389 | 0.060486 | 0.622903 | 2.000950 | 1.920171 | 2.009158 |
28 | 268.435.456 | 183.533.240 | 15.615.308 | 167.917.932 | 0.683715 | 0.058172 | 0.625543 | 2.000953 | 1.923465 | 2.008477 |
29 | 536.870.912 | 367.229.678 | 30.076.059 | 337.153.619 | 0.684019 | 0.056021 | 0.627998 | 2.000889 | 1.926063 | 2.007848 |
30 | 1.073.741.824 | 734.769.036 | 58.014.245 | 676.754.791 | 0.684307 | 0.054030 | 0.630277 | 2.000843 | 1.928918 | 2.007259 |
31 | 2.147.483.648 | 1.470.101.313 | 112.043.426 | 1.358.057.887 | 0.684569 | 0.052174 | 0.632395 | 2.000767 | 1.931309 | 2.006721 |
32 | 4.294.967.296 | 2.941.286.357 | 216.653.409 | 2.724.632.948 | 0.684822 | 0.050444 | 0.634378 | 2.000737 | 1.933656 | 2.006272 |
33 | 8.589.934.592 | 5.884.612.357 | 419.378.982 | 5.465.233.375 | 0.685059 | 0.048822 | 0.636237 | 2.000694 | 1.935714 | 2.005861 |
34 | 17.179.869.184 | 11.773.070.330 | 812.682.708 | 10.960.387.622 | 0.685283 | 0.047304 | 0.637979 | 2.000654 | 1.937824 | 2.005475 |
35 | 34.359.738.368 | 23.553.412.866 | 1.576.366.984 | 21.977.045.882 | 0.685495 | 0.045878 | 0.639616 | 2.000618 | 1.939708 | 2.005134 |
36 | 68.719.476.736 | 47.120.652.365 | 3.060.380.548 | 44.060.271.817 | 0.685696 | 0.044534 | 0.641161 | 2.000587 | 1.941414 | 2.004831 |
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 | 3 | 2 | 1 | 1 | 1 | 1 | 0 |
2 | 4 | 4 | 2 | 2 | 1 | 1 | 2 | 0 |
3 | 8 | 6 | 3 | 3 | 2 | 2 | 2 | 0 |
4 | 16 | 8 | 3 | 5 | 2 | 2 | 3 | 1 |
5 | 32 | 13 | 5 | 8 | 3 | 3 | 4 | 3 |
6 | 64 | 22 | 9 | 13 | 5 | 6 | 6 | 5 |
7 | 128 | 37 | 16 | 21 | 10 | 10 | 8 | 9 |
8 | 256 | 64 | 29 | 35 | 16 | 14 | 16 | 18 |
9 | 512 | 109 | 51 | 58 | 26 | 28 | 26 | 29 |
10 | 1.024 | 200 | 95 | 105 | 51 | 47 | 49 | 53 |
11 | 2.048 | 355 | 175 | 180 | 90 | 94 | 81 | 90 |
12 | 4.096 | 628 | 309 | 319 | 150 | 168 | 152 | 158 |
13 | 8.192 | 1.155 | 587 | 568 | 273 | 297 | 286 | 299 |
14 | 16.384 | 2.085 | 1.048 | 1.037 | 506 | 535 | 507 | 537 |
15 | 32.768 | 3.857 | 1.915 | 1.942 | 946 | 972 | 964 | 975 |
16 | 65.536 | 7.112 | 3.576 | 3.536 | 1.717 | 1.837 | 1.750 | 1.808 |
17 | 131.072 | 13.201 | 6.657 | 6.544 | 3.196 | 3.393 | 3.273 | 3.339 |
18 | 262.144 | 24.701 | 12.433 | 12.268 | 6.088 | 6.283 | 6.099 | 6.231 |
19 | 524.288 | 46.572 | 23.405 | 23.167 | 11.512 | 11.807 | 11.499 | 11.754 |
20 | 1.048.576 | 88.035 | 44.341 | 43.694 | 21.742 | 22.313 | 21.830 | 22.150 |
21 | 2.097.152 | 166.794 | 83.983 | 82.811 | 41.119 | 42.272 | 41.263 | 42.140 |
22 | 4.194.304 | 316.555 | 159.480 | 157.075 | 77.926 | 80.184 | 78.261 | 80.184 |
23 | 8.388.608 | 603.728 | 303.523 | 300.205 | 148.942 | 152.791 | 149.457 | 152.538 |
24 | 16.777.216 | 1.153.447 | 579.472 | 573.975 | 284.401 | 291.752 | 285.474 | 291.820 |
25 | 33.554.432 | 2.206.084 | 1.107.116 | 1.098.968 | 545.107 | 557.624 | 545.722 | 557.631 |
26 | 67.108.864 | 4.227.915 | 2.121.173 | 2.106.742 | 1.045.566 | 1.067.361 | 1.046.926 | 1.068.062 |
27 | 134.217.728 | 8.118.320 | 4.073.171 | 4.045.149 | 2.007.817 | 2.048.713 | 2.011.921 | 2.049.869 |
28 | 268.435.456 | 15.615.308 | 7.833.236 | 7.782.072 | 3.865.840 | 3.938.722 | 3.869.770 | 3.940.976 |
29 | 536.870.912 | 30.076.059 | 15.085.321 | 14.990.738 | 7.450.572 | 7.584.397 | 7.451.314 | 7.589.776 |
30 | 1.073.741.824 | 58.014.245 | 29.090.744 | 28.923.501 | 14.376.853 | 14.628.835 | 14.377.387 | 14.631.170 |
31 | 2.147.483.648 | 112.043.426 | 56.182.710 | 55.860.716 | 27.771.856 | 28.252.195 | 27.772.170 | 28.247.205 |
32 | 4.294.967.296 | 216.653.409 | 108.622.315 | 108.031.094 | 53.715.867 | 54.610.088 | 53.718.582 | 54.608.872 |
33 | 8.589.934.592 | 419.378.982 | 210.251.612 | 209.127.370 | 104.004.720 | 105.684.412 | 104.007.419 | 105.682.431 |
34 | 17.179.869.184 | 812.682.708 | 407.395.342 | 405.287.366 | 201.596.418 | 204.744.087 | 201.598.970 | 204.743.233 |
35 | 34.359.738.368 | 1.576.366.984 | 790.166.413 | 786.200.571 | 391.129.206 | 397.057.017 | 391.124.107 | 397.056.654 |
36 | 68.719.476.736 | 3.060.380.548 | 1.533.928.548 | 1.526.452.000 | 759.513.007 | 770.702.351 | 759.484.567 | 770.680.623 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 16 | 4 | 0 | 4 | 1 | 2 | 0 | 1 |
5 | 32 | 10 | 5 | 5 | 3 | 3 | 2 | 2 |
6 | 64 | 23 | 11 | 12 | 5 | 7 | 5 | 6 |
7 | 128 | 43 | 20 | 23 | 10 | 11 | 10 | 12 |
8 | 256 | 99 | 49 | 50 | 20 | 25 | 25 | 29 |
9 | 512 | 224 | 110 | 114 | 49 | 58 | 61 | 56 |
10 | 1.024 | 472 | 232 | 240 | 108 | 112 | 121 | 131 |
11 | 2.048 | 1.006 | 495 | 511 | 231 | 252 | 267 | 256 |
12 | 4.096 | 2.104 | 1.044 | 1.060 | 508 | 536 | 530 | 530 |
13 | 8.192 | 4.351 | 2.186 | 2.165 | 1.067 | 1.120 | 1.091 | 1.073 |
14 | 16.384 | 8.981 | 4.523 | 4.458 | 2.209 | 2.264 | 2.271 | 2.237 |
15 | 32.768 | 18.301 | 9.189 | 9.112 | 4.507 | 4.672 | 4.577 | 4.545 |
16 | 65.536 | 37.210 | 18.571 | 18.639 | 9.200 | 9.479 | 9.282 | 9.249 |
17 | 131.072 | 75.669 | 37.836 | 37.833 | 18.827 | 19.040 | 18.933 | 18.869 |
18 | 262.144 | 153.241 | 76.545 | 76.696 | 38.118 | 38.440 | 38.256 | 38.427 |
19 | 524.288 | 309.630 | 154.572 | 155.058 | 77.460 | 77.470 | 77.089 | 77.611 |
20 | 1.048.576 | 625.137 | 312.086 | 313.051 | 156.255 | 156.283 | 156.153 | 156.446 |
21 | 2.097.152 | 1.261.013 | 630.172 | 630.841 | 315.479 | 315.279 | 314.808 | 315.447 |
22 | 4.194.304 | 2.541.742 | 1.270.718 | 1.271.024 | 635.337 | 635.646 | 635.549 | 635.210 |
23 | 8.388.608 | 5.116.003 | 2.556.672 | 2.559.331 | 1.278.079 | 1.279.755 | 1.277.792 | 1.280.377 |
24 | 16.777.216 | 10.293.249 | 5.141.317 | 5.151.932 | 2.571.931 | 2.574.389 | 2.571.546 | 2.575.383 |
25 | 33.554.432 | 20.700.849 | 10.345.479 | 10.355.370 | 5.171.737 | 5.179.574 | 5.171.777 | 5.177.761 |
26 | 67.108.864 | 41.611.774 | 20.799.997 | 20.811.777 | 10.399.051 | 10.405.940 | 10.398.265 | 10.408.518 |
27 | 134.217.728 | 83.604.619 | 41.793.910 | 41.810.709 | 20.893.845 | 20.909.501 | 20.890.587 | 20.910.686 |
28 | 268.435.456 | 167.917.932 | 83.943.443 | 83.974.489 | 41.959.534 | 41.998.147 | 41.959.193 | 42.001.058 |
29 | 536.870.912 | 337.153.619 | 168.544.631 | 168.608.988 | 84.254.097 | 84.316.153 | 84.257.497 | 84.325.872 |
30 | 1.073.741.824 | 676.754.791 | 338.324.256 | 338.430.535 | 169.120.644 | 169.250.657 | 169.140.186 | 169.243.304 |
31 | 2.147.483.648 | 1.358.057.887 | 678.961.178 | 679.096.709 | 339.379.744 | 339.625.387 | 339.431.267 | 339.621.489 |
32 | 4.294.967.296 | 2.724.632.948 | 1.362.138.534 | 1.362.494.414 | 680.943.519 | 681.372.011 | 680.950.057 | 681.367.361 |
33 | 8.589.934.592 | 5.465.233.375 | 2.732.307.198 | 2.732.926.177 | 1.365.877.083 | 1.366.719.963 | 1.365.920.945 | 1.366.715.384 |
34 | 17.179.869.184 | 10.960.387.622 | 5.479.585.007 | 5.480.802.615 | 2.739.316.171 | 2.740.866.017 | 2.739.333.517 | 2.740.871.917 |
35 | 34.359.738.368 | 21.977.045.882 | 10.987.405.852 | 10.989.640.030 | 5.492.800.810 | 5.495.728.098 | 5.492.804.269 | 5.495.712.705 |
36 | 68.719.476.736 | 44.060.271.817 | 22.027.980.582 | 22.032.291.235 | 11.012.349.752 | 11.017.691.958 | 11.012.437.902 | 11.017.792.205 |