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+16x-3
f(0)=3
f(1)=7
f(2)=11
f(3)=1
f(4)=1
f(5)=17
f(6)=43
f(7)=79
f(8)=1
f(9)=37
f(10)=257
f(11)=1
f(12)=1
f(13)=1
f(14)=139
f(15)=1
f(16)=509
f(17)=31
f(18)=29
f(19)=331
f(20)=239
f(21)=1
f(22)=1
f(23)=149
f(24)=1
f(25)=73
f(26)=1
f(27)=193
f(28)=1229
f(29)=1
f(30)=1
f(31)=727
f(32)=1
f(33)=269
f(34)=1697
f(35)=1
f(36)=89
f(37)=1
f(38)=683
f(39)=1
f(40)=2237
f(41)=389
f(42)=811
f(43)=181
f(44)=293
f(45)=457
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=157
f(51)=569
f(52)=3533
f(53)=1
f(54)=1259
f(55)=1951
f(56)=1
f(57)=1
f(58)=4289
f(59)=67
f(60)=1
f(61)=2347
f(62)=179
f(63)=829
f(64)=1
f(65)=877
f(66)=601
f(67)=397
f(68)=173
f(69)=977
f(70)=547
f(71)=1
f(72)=2111
f(73)=191
f(74)=317
f(75)=379
f(76)=241
f(77)=1193
f(78)=349
f(79)=1
f(80)=853
f(81)=1
f(82)=277
f(83)=1
f(84)=311
f(85)=613
f(86)=1
f(87)=1493
f(88)=1307
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=563
f(94)=10337
f(95)=251
f(96)=3583
f(97)=5479
f(98)=1
f(99)=271
b) Substitution of the polynom
The polynom f(x)=x^2+16x-3 could be written as f(y)= y^2-67 with x=y-8
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+8
f'(x)>2x+15
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 | 4 | 4 | 0.800000 | 0.400000 | 0.400000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 62 | 17 | 45 | 0.620000 | 0.170000 | 0.450000 | 7.750000 | 4.250000 | 11.250000 |
3 | 1.000 | 644 | 93 | 551 | 0.644000 | 0.093000 | 0.551000 | 10.387096 | 5.470588 | 12.244445 |
4 | 10.000 | 6.613 | 690 | 5.923 | 0.661300 | 0.069000 | 0.592300 | 10.268634 | 7.419355 | 10.749546 |
5 | 100.000 | 66.764 | 5.293 | 61.471 | 0.667640 | 0.052930 | 0.614710 | 10.095872 | 7.671014 | 10.378356 |
6 | 1.000.000 | 672.130 | 42.779 | 629.351 | 0.672130 | 0.042779 | 0.629351 | 10.067252 | 8.082184 | 10.238177 |
7 | 10.000.000 | 6.748.572 | 361.743 | 6.386.829 | 0.674857 | 0.036174 | 0.638683 | 10.040575 | 8.456088 | 10.148278 |
8 | 100.000.000 | 67.702.546 | 3.134.319 | 64.568.227 | 0.677025 | 0.031343 | 0.645682 | 10.032129 | 8.664491 | 10.109591 |
9 | 1.000.000.000 | 678.731.383 | 27.631.275 | 651.100.108 | 0.678731 | 0.027631 | 0.651100 | 10.025198 | 8.815720 | 10.083908 |
10 | 10.000.000.000 | 6.801.046.830 | 247.048.648 | 6.553.998.182 | 0.680105 | 0.024705 | 0.655400 | 10.020233 | 8.940906 | 10.066038 |
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 | 6 | 3 | 3 | 0.750000 | 0.375000 | 0.375000 | 2.000000 | 1.500000 | 3.000000 |
4 | 16 | 10 | 5 | 5 | 0.625000 | 0.312500 | 0.312500 | 1.666667 | 1.666667 | 1.666667 |
5 | 32 | 17 | 8 | 9 | 0.531250 | 0.250000 | 0.281250 | 1.700000 | 1.600000 | 1.800000 |
6 | 64 | 36 | 14 | 22 | 0.562500 | 0.218750 | 0.343750 | 2.117647 | 1.750000 | 2.444444 |
7 | 128 | 77 | 19 | 58 | 0.601562 | 0.148438 | 0.453125 | 2.138889 | 1.357143 | 2.636364 |
8 | 256 | 161 | 33 | 128 | 0.628906 | 0.128906 | 0.500000 | 2.090909 | 1.736842 | 2.206897 |
9 | 512 | 328 | 55 | 273 | 0.640625 | 0.107422 | 0.533203 | 2.037267 | 1.666667 | 2.132812 |
10 | 1.024 | 659 | 96 | 563 | 0.643555 | 0.093750 | 0.549805 | 2.009146 | 1.745455 | 2.062271 |
11 | 2.048 | 1.331 | 170 | 1.161 | 0.649902 | 0.083008 | 0.566895 | 2.019727 | 1.770833 | 2.062167 |
12 | 4.096 | 2.679 | 308 | 2.371 | 0.654053 | 0.075195 | 0.578857 | 2.012772 | 1.811765 | 2.042205 |
13 | 8.192 | 5.418 | 576 | 4.842 | 0.661377 | 0.070312 | 0.591064 | 2.022396 | 1.870130 | 2.042176 |
14 | 16.384 | 10.846 | 1.057 | 9.789 | 0.661987 | 0.064514 | 0.597473 | 2.001846 | 1.835069 | 2.021685 |
15 | 32.768 | 21.791 | 1.940 | 19.851 | 0.665009 | 0.059204 | 0.605804 | 2.009128 | 1.835383 | 2.027889 |
16 | 65.536 | 43.714 | 3.633 | 40.081 | 0.667023 | 0.055435 | 0.611588 | 2.006058 | 1.872680 | 2.019092 |
17 | 131.072 | 87.643 | 6.704 | 80.939 | 0.668663 | 0.051147 | 0.617516 | 2.004918 | 1.845307 | 2.019386 |
18 | 262.144 | 175.632 | 12.539 | 163.093 | 0.669983 | 0.047832 | 0.622150 | 2.003948 | 1.870376 | 2.015011 |
19 | 524.288 | 351.727 | 23.623 | 328.104 | 0.670866 | 0.045057 | 0.625809 | 2.002636 | 1.883962 | 2.011760 |
20 | 1.048.576 | 704.791 | 44.683 | 660.108 | 0.672141 | 0.042613 | 0.629528 | 2.003801 | 1.891504 | 2.011886 |
21 | 2.097.152 | 1.411.297 | 84.716 | 1.326.581 | 0.672959 | 0.040396 | 0.632563 | 2.002433 | 1.895934 | 2.009642 |
22 | 4.194.304 | 2.826.629 | 160.932 | 2.665.697 | 0.673921 | 0.038369 | 0.635552 | 2.002859 | 1.899665 | 2.009449 |
23 | 8.388.608 | 5.659.702 | 307.113 | 5.352.589 | 0.674689 | 0.036611 | 0.638078 | 2.002280 | 1.908340 | 2.007951 |
24 | 16.777.216 | 11.331.366 | 586.679 | 10.744.687 | 0.675402 | 0.034969 | 0.640433 | 2.002114 | 1.910303 | 2.007381 |
25 | 33.554.432 | 22.684.841 | 1.122.353 | 21.562.488 | 0.676061 | 0.033449 | 0.642612 | 2.001951 | 1.913061 | 2.006805 |
26 | 67.108.864 | 45.412.557 | 2.152.680 | 43.259.877 | 0.676700 | 0.032077 | 0.644622 | 2.001890 | 1.918006 | 2.006256 |
27 | 134.217.728 | 90.902.499 | 4.135.117 | 86.767.382 | 0.677276 | 0.030809 | 0.646467 | 2.001704 | 1.920916 | 2.005724 |
28 | 268.435.456 | 181.949.734 | 7.955.332 | 173.994.402 | 0.677816 | 0.029636 | 0.648180 | 2.001592 | 1.923847 | 2.005297 |
29 | 536.870.912 | 364.166.054 | 15.323.707 | 348.842.347 | 0.678312 | 0.028543 | 0.649769 | 2.001465 | 1.926218 | 2.004905 |
30 | 1.073.741.824 | 728.828.237 | 29.559.754 | 699.268.483 | 0.678774 | 0.027530 | 0.651245 | 2.001362 | 1.929021 | 2.004540 |
31 | 2.147.483.648 | 1.458.602.429 | 57.090.230 | 1.401.512.199 | 0.679215 | 0.026585 | 0.652630 | 2.001298 | 1.931350 | 2.004255 |
32 | 4.294.967.296 | 2.918.993.643 | 110.393.878 | 2.808.599.765 | 0.679631 | 0.025703 | 0.653928 | 2.001226 | 1.933674 | 2.003978 |
33 | 8.589.934.592 | 5.841.341.452 | 213.703.981 | 5.627.637.471 | 0.680022 | 0.024878 | 0.655143 | 2.001149 | 1.935832 | 2.003716 |
34 | 17.179.869.184 | 11.689.030.084 | 414.126.835 | 11.274.903.249 | 0.680391 | 0.024105 | 0.656286 | 2.001086 | 1.937853 | 2.003488 |
35 | 34.359.738.368 | 23.390.043.560 | 803.283.537 | 22.586.760.023 | 0.680740 | 0.023379 | 0.657361 | 2.001025 | 1.939704 | 2.003277 |
36 | 68.719.476.736 | 46.802.836.423 | 1.559.514.552 | 45.243.321.871 | 0.681071 | 0.022694 | 0.658377 | 2.000973 | 1.941425 | 2.003090 |
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 | 1 | 0 | 1 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 2 | 0 | 0 | 1 | 0 | 2 |
4 | 16 | 5 | 2 | 2 | 1 | 1 | 1 | 2 |
5 | 32 | 8 | 4 | 3 | 1 | 2 | 2 | 3 |
6 | 64 | 14 | 6 | 7 | 3 | 3 | 4 | 4 |
7 | 128 | 19 | 8 | 10 | 5 | 3 | 5 | 6 |
8 | 256 | 33 | 17 | 15 | 8 | 9 | 7 | 9 |
9 | 512 | 55 | 30 | 24 | 12 | 16 | 12 | 15 |
10 | 1.024 | 96 | 48 | 47 | 24 | 22 | 23 | 27 |
11 | 2.048 | 170 | 87 | 82 | 41 | 43 | 41 | 45 |
12 | 4.096 | 308 | 156 | 151 | 78 | 77 | 73 | 80 |
13 | 8.192 | 576 | 289 | 286 | 152 | 145 | 134 | 145 |
14 | 16.384 | 1.057 | 530 | 526 | 276 | 269 | 250 | 262 |
15 | 32.768 | 1.940 | 984 | 955 | 478 | 505 | 477 | 480 |
16 | 65.536 | 3.633 | 1.849 | 1.783 | 907 | 952 | 876 | 898 |
17 | 131.072 | 6.704 | 3.402 | 3.301 | 1.674 | 1.720 | 1.627 | 1.683 |
18 | 262.144 | 12.539 | 6.357 | 6.181 | 3.095 | 3.190 | 3.086 | 3.168 |
19 | 524.288 | 23.623 | 11.933 | 11.689 | 5.839 | 5.957 | 5.850 | 5.977 |
20 | 1.048.576 | 44.683 | 22.646 | 22.036 | 11.086 | 11.401 | 10.950 | 11.246 |
21 | 2.097.152 | 84.716 | 42.857 | 41.858 | 20.989 | 21.463 | 20.869 | 21.395 |
22 | 4.194.304 | 160.932 | 81.486 | 79.445 | 39.708 | 40.773 | 39.737 | 40.714 |
23 | 8.388.608 | 307.113 | 155.328 | 151.784 | 75.780 | 77.909 | 76.004 | 77.420 |
24 | 16.777.216 | 586.679 | 296.550 | 290.128 | 145.012 | 148.473 | 145.116 | 148.078 |
25 | 33.554.432 | 1.122.353 | 567.378 | 554.974 | 277.205 | 283.978 | 277.769 | 283.401 |
26 | 67.108.864 | 2.152.680 | 1.087.703 | 1.064.976 | 532.885 | 544.137 | 532.091 | 543.567 |
27 | 134.217.728 | 4.135.117 | 2.087.699 | 2.047.417 | 1.023.842 | 1.044.172 | 1.023.575 | 1.043.528 |
28 | 268.435.456 | 7.955.332 | 4.015.691 | 3.939.640 | 1.970.548 | 2.008.279 | 1.969.092 | 2.007.413 |
29 | 536.870.912 | 15.323.707 | 7.732.838 | 7.590.868 | 3.796.429 | 3.867.343 | 3.794.439 | 3.865.496 |
30 | 1.073.741.824 | 29.559.754 | 14.909.279 | 14.650.474 | 7.325.354 | 7.454.335 | 7.325.120 | 7.454.945 |
31 | 2.147.483.648 | 57.090.230 | 28.792.301 | 28.297.928 | 14.150.164 | 14.394.374 | 14.147.764 | 14.397.928 |
32 | 4.294.967.296 | 110.393.878 | 55.658.580 | 54.735.297 | 27.371.933 | 27.827.301 | 27.363.364 | 27.831.280 |
33 | 8.589.934.592 | 213.703.981 | 107.708.536 | 105.995.444 | 53.006.245 | 53.851.709 | 52.989.199 | 53.856.828 |
34 | 17.179.869.184 | 414.126.835 | 208.671.113 | 205.455.721 | 102.734.998 | 104.338.214 | 102.720.723 | 104.332.900 |
35 | 34.359.738.368 | 803.283.537 | 404.676.431 | 398.607.105 | 199.312.561 | 202.340.498 | 199.294.544 | 202.335.934 |
36 | 68.719.476.736 | 1.559.514.552 | 785.461.842 | 774.052.709 | 387.038.094 | 392.741.150 | 387.014.615 | 392.720.693 |
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 | 3 | 1 | 2 | 1 | 2 | 0 | 0 |
4 | 16 | 5 | 3 | 2 | 1 | 3 | 1 | 0 |
5 | 32 | 9 | 5 | 4 | 3 | 3 | 2 | 1 |
6 | 64 | 22 | 10 | 12 | 6 | 7 | 8 | 1 |
7 | 128 | 58 | 28 | 30 | 13 | 14 | 20 | 11 |
8 | 256 | 128 | 61 | 67 | 30 | 32 | 33 | 33 |
9 | 512 | 273 | 136 | 137 | 70 | 70 | 67 | 66 |
10 | 1.024 | 563 | 270 | 293 | 141 | 135 | 145 | 142 |
11 | 2.048 | 1.161 | 568 | 593 | 285 | 291 | 296 | 289 |
12 | 4.096 | 2.371 | 1.174 | 1.197 | 572 | 601 | 603 | 595 |
13 | 8.192 | 4.842 | 2.436 | 2.406 | 1.193 | 1.227 | 1.232 | 1.190 |
14 | 16.384 | 9.789 | 4.901 | 4.888 | 2.409 | 2.458 | 2.506 | 2.416 |
15 | 32.768 | 19.851 | 9.918 | 9.933 | 4.883 | 4.941 | 5.038 | 4.989 |
16 | 65.536 | 40.081 | 19.909 | 20.172 | 9.889 | 9.993 | 10.155 | 10.044 |
17 | 131.072 | 80.939 | 40.340 | 40.599 | 20.090 | 20.192 | 20.419 | 20.238 |
18 | 262.144 | 163.093 | 81.432 | 81.661 | 40.696 | 40.824 | 40.797 | 40.776 |
19 | 524.288 | 328.104 | 164.090 | 164.014 | 81.795 | 82.139 | 82.296 | 81.874 |
20 | 1.048.576 | 660.108 | 329.734 | 330.374 | 165.076 | 164.940 | 165.491 | 164.601 |
21 | 2.097.152 | 1.326.581 | 662.471 | 664.110 | 331.968 | 331.102 | 332.579 | 330.932 |
22 | 4.194.304 | 2.665.697 | 1.332.245 | 1.333.452 | 667.384 | 665.809 | 666.893 | 665.611 |
23 | 8.388.608 | 5.352.589 | 2.675.347 | 2.677.242 | 1.340.113 | 1.336.897 | 1.338.811 | 1.336.768 |
24 | 16.777.216 | 10.744.687 | 5.370.821 | 5.373.866 | 2.687.655 | 2.684.185 | 2.687.923 | 2.684.924 |
25 | 33.554.432 | 21.562.488 | 10.781.508 | 10.780.980 | 5.393.756 | 5.388.399 | 5.391.681 | 5.388.652 |
26 | 67.108.864 | 43.259.877 | 21.628.775 | 21.631.102 | 10.821.339 | 10.812.348 | 10.818.690 | 10.807.500 |
27 | 134.217.728 | 86.767.382 | 43.382.106 | 43.385.276 | 21.698.880 | 21.684.710 | 21.702.162 | 21.681.630 |
28 | 268.435.456 | 173.994.402 | 86.996.852 | 86.997.550 | 43.517.135 | 43.479.346 | 43.515.740 | 43.482.181 |
29 | 536.870.912 | 348.842.347 | 174.428.021 | 174.414.326 | 87.238.521 | 87.183.636 | 87.239.737 | 87.180.453 |
30 | 1.073.741.824 | 699.268.483 | 349.648.809 | 349.619.674 | 174.874.091 | 174.760.681 | 174.879.406 | 174.754.305 |
31 | 2.147.483.648 | 1.401.512.199 | 700.781.839 | 700.730.360 | 350.486.205 | 350.256.225 | 350.509.412 | 350.260.357 |
32 | 4.294.967.296 | 2.808.599.765 | 1.404.341.534 | 1.404.258.231 | 702.380.077 | 701.896.492 | 702.411.816 | 701.911.380 |
33 | 8.589.934.592 | 5.627.637.471 | 2.813.916.846 | 2.813.720.625 | 1.407.326.777 | 1.406.435.155 | 1.407.421.274 | 1.406.454.265 |
34 | 17.179.869.184 | 11.274.903.249 | 5.637.581.501 | 5.637.321.748 | 2.819.573.214 | 2.817.868.468 | 2.819.554.958 | 2.817.906.609 |
35 | 34.359.738.368 | 22.586.760.023 | 11.293.725.023 | 11.293.035.000 | 5.648.279.057 | 5.645.072.133 | 5.648.256.091 | 5.645.152.742 |
36 | 68.719.476.736 | 45.243.321.871 | 22.622.488.270 | 22.620.833.601 | 11.313.843.605 | 11.307.848.877 | 11.313.674.569 | 11.307.954.820 |