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-144x+191
f(0)=191
f(1)=3
f(2)=31
f(3)=29
f(4)=41
f(5)=7
f(6)=13
f(7)=1
f(8)=23
f(9)=1
f(10)=383
f(11)=53
f(12)=199
f(13)=1
f(14)=181
f(15)=109
f(16)=619
f(17)=1
f(18)=67
f(19)=1
f(20)=1
f(21)=1
f(22)=277
f(23)=1
f(24)=2689
f(25)=1
f(26)=137
f(27)=1
f(28)=1019
f(29)=131
f(30)=3229
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=151
f(36)=3697
f(37)=157
f(38)=1279
f(39)=61
f(40)=1
f(41)=1
f(42)=4093
f(43)=173
f(44)=1
f(45)=1
f(46)=1439
f(47)=1
f(48)=631
f(49)=1
f(50)=167
f(51)=569
f(52)=1531
f(53)=193
f(54)=1
f(55)=1
f(56)=1579
f(57)=149
f(58)=1
f(59)=1
f(60)=373
f(61)=1
f(62)=233
f(63)=307
f(64)=1
f(65)=103
f(66)=4957
f(67)=1
f(68)=79
f(69)=89
f(70)=1663
f(71)=1
f(72)=4993
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-144x+191 could be written as f(y)= y^2-4993 with x=y+72
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-72
f'(x)>2x-145 with x > 71
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 | 40 | 13 | 27 | 0.400000 | 0.130000 | 0.270000 | 5.000000 | 4.333333 | 5.400000 |
3 | 1.000 | 479 | 99 | 380 | 0.479000 | 0.099000 | 0.380000 | 11.975000 | 7.615385 | 14.074074 |
4 | 10.000 | 5.860 | 760 | 5.100 | 0.586000 | 0.076000 | 0.510000 | 12.233821 | 7.676768 | 13.421053 |
5 | 100.000 | 61.536 | 5.816 | 55.720 | 0.615360 | 0.058160 | 0.557200 | 10.501024 | 7.652632 | 10.925490 |
6 | 1.000.000 | 630.520 | 46.828 | 583.692 | 0.630520 | 0.046828 | 0.583692 | 10.246360 | 8.051581 | 10.475449 |
7 | 10.000.000 | 6.399.201 | 391.485 | 6.007.716 | 0.639920 | 0.039148 | 0.600772 | 10.149085 | 8.360063 | 10.292613 |
8 | 100.000.000 | 64.685.608 | 3.366.747 | 61.318.861 | 0.646856 | 0.033667 | 0.613189 | 10.108388 | 8.599938 | 10.206684 |
9 | 1.000.000.000 | 652.192.488 | 29.558.273 | 622.634.215 | 0.652193 | 0.029558 | 0.622634 | 10.082498 | 8.779475 | 10.154041 |
10 | 10.000.000.000 | 6.564.048.041 | 263.411.600 | 6.300.636.441 | 0.656405 | 0.026341 | 0.630064 | 10.064587 | 8.911604 | 10.119323 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.400000 | 1.000000 | 2.000000 |
4 | 16 | 13 | 4 | 9 | 0.812500 | 0.250000 | 0.562500 | 1.857143 | 1.333333 | 2.250000 |
5 | 32 | 20 | 6 | 14 | 0.625000 | 0.187500 | 0.437500 | 1.538462 | 1.500000 | 1.555556 |
6 | 64 | 37 | 11 | 26 | 0.578125 | 0.171875 | 0.406250 | 1.850000 | 1.833333 | 1.857143 |
7 | 128 | 40 | 13 | 27 | 0.312500 | 0.101562 | 0.210938 | 1.081081 | 1.181818 | 1.038462 |
8 | 256 | 77 | 25 | 52 | 0.300781 | 0.097656 | 0.203125 | 1.925000 | 1.923077 | 1.925926 |
9 | 512 | 208 | 52 | 156 | 0.406250 | 0.101562 | 0.304688 | 2.701299 | 2.080000 | 3.000000 |
10 | 1.024 | 491 | 102 | 389 | 0.479492 | 0.099609 | 0.379883 | 2.360577 | 1.961538 | 2.493590 |
11 | 2.048 | 1.079 | 191 | 888 | 0.526855 | 0.093262 | 0.433594 | 2.197556 | 1.872549 | 2.282776 |
12 | 4.096 | 2.291 | 354 | 1.937 | 0.559326 | 0.086426 | 0.472900 | 2.123262 | 1.853403 | 2.181306 |
13 | 8.192 | 4.753 | 638 | 4.115 | 0.580200 | 0.077881 | 0.502319 | 2.074640 | 1.802260 | 2.124419 |
14 | 16.384 | 9.740 | 1.172 | 8.568 | 0.594482 | 0.071533 | 0.522949 | 2.049232 | 1.836991 | 2.082139 |
15 | 32.768 | 19.804 | 2.142 | 17.662 | 0.604370 | 0.065369 | 0.539001 | 2.033265 | 1.827645 | 2.061391 |
16 | 65.536 | 40.058 | 3.986 | 36.072 | 0.611237 | 0.060822 | 0.550415 | 2.022723 | 1.860878 | 2.042351 |
17 | 131.072 | 80.968 | 7.406 | 73.562 | 0.617737 | 0.056503 | 0.561234 | 2.021269 | 1.858003 | 2.039310 |
18 | 262.144 | 163.277 | 13.874 | 149.403 | 0.622852 | 0.052925 | 0.569927 | 2.016562 | 1.873346 | 2.030981 |
19 | 524.288 | 328.635 | 26.004 | 302.631 | 0.626822 | 0.049599 | 0.577223 | 2.012745 | 1.874297 | 2.025602 |
20 | 1.048.576 | 661.381 | 48.864 | 612.517 | 0.630742 | 0.046600 | 0.584142 | 2.012509 | 1.879096 | 2.023973 |
21 | 2.097.152 | 1.329.244 | 92.587 | 1.236.657 | 0.633833 | 0.044149 | 0.589684 | 2.009801 | 1.894790 | 2.018976 |
22 | 4.194.304 | 2.670.957 | 175.223 | 2.495.734 | 0.636806 | 0.041776 | 0.595029 | 2.009381 | 1.892523 | 2.018130 |
23 | 8.388.608 | 5.362.869 | 332.634 | 5.030.235 | 0.639304 | 0.039653 | 0.599651 | 2.007845 | 1.898347 | 2.015533 |
24 | 16.777.216 | 10.765.466 | 633.465 | 10.132.001 | 0.641672 | 0.037757 | 0.603914 | 2.007408 | 1.904390 | 2.014220 |
25 | 33.554.432 | 21.602.438 | 1.209.886 | 20.392.552 | 0.643803 | 0.036057 | 0.607745 | 2.006642 | 1.909949 | 2.012687 |
26 | 67.108.864 | 43.337.404 | 2.314.726 | 41.022.678 | 0.645778 | 0.034492 | 0.611286 | 2.006135 | 1.913177 | 2.011650 |
27 | 134.217.728 | 86.923.978 | 4.440.552 | 82.483.426 | 0.647634 | 0.033085 | 0.614549 | 2.005749 | 1.918392 | 2.010679 |
28 | 268.435.456 | 174.302.810 | 8.528.366 | 165.774.444 | 0.649329 | 0.031771 | 0.617558 | 2.005233 | 1.920564 | 2.009791 |
29 | 536.870.912 | 349.443.811 | 16.411.234 | 333.032.577 | 0.650890 | 0.030568 | 0.620322 | 2.004809 | 1.924312 | 2.008950 |
30 | 1.073.741.824 | 700.442.654 | 31.617.104 | 668.825.550 | 0.652338 | 0.029446 | 0.622892 | 2.004450 | 1.926553 | 2.008289 |
31 | 2.147.483.648 | 1.403.792.401 | 61.002.572 | 1.342.789.829 | 0.653692 | 0.028407 | 0.625285 | 2.004150 | 1.929417 | 2.007683 |
32 | 4.294.967.296 | 2.813.031.291 | 117.843.033 | 2.695.188.258 | 0.654960 | 0.027437 | 0.627522 | 2.003880 | 1.931772 | 2.007156 |
33 | 8.589.934.592 | 5.636.303.595 | 227.903.004 | 5.408.400.591 | 0.656152 | 0.026531 | 0.629621 | 2.003641 | 1.933954 | 2.006687 |
34 | 17.179.869.184 | 11.291.842.444 | 441.276.967 | 10.850.565.477 | 0.657272 | 0.025686 | 0.631586 | 2.003413 | 1.936249 | 2.006243 |
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 | 0 | 2 | 0 | 1 | 1 | 1 |
3 | 8 | 3 | 0 | 2 | 0 | 1 | 1 | 1 |
4 | 16 | 4 | 1 | 2 | 0 | 1 | 2 | 1 |
5 | 32 | 6 | 3 | 2 | 1 | 1 | 3 | 1 |
6 | 64 | 11 | 6 | 4 | 3 | 2 | 5 | 1 |
7 | 128 | 13 | 8 | 4 | 4 | 2 | 6 | 1 |
8 | 256 | 25 | 13 | 11 | 6 | 6 | 7 | 6 |
9 | 512 | 52 | 24 | 27 | 9 | 15 | 12 | 16 |
10 | 1.024 | 102 | 45 | 56 | 21 | 30 | 17 | 34 |
11 | 2.048 | 191 | 75 | 115 | 32 | 64 | 27 | 68 |
12 | 4.096 | 354 | 130 | 223 | 56 | 122 | 50 | 126 |
13 | 8.192 | 638 | 227 | 410 | 93 | 235 | 83 | 227 |
14 | 16.384 | 1.172 | 431 | 740 | 157 | 434 | 162 | 419 |
15 | 32.768 | 2.142 | 779 | 1.362 | 296 | 803 | 284 | 759 |
16 | 65.536 | 3.986 | 1.434 | 2.551 | 557 | 1.454 | 536 | 1.439 |
17 | 131.072 | 7.406 | 2.613 | 4.792 | 1.020 | 2.704 | 971 | 2.711 |
18 | 262.144 | 13.874 | 4.866 | 9.007 | 1.872 | 5.061 | 1.849 | 5.092 |
19 | 524.288 | 26.004 | 9.129 | 16.874 | 3.447 | 9.578 | 3.422 | 9.557 |
20 | 1.048.576 | 48.864 | 17.257 | 31.606 | 6.472 | 17.972 | 6.512 | 17.908 |
21 | 2.097.152 | 92.587 | 32.432 | 60.154 | 12.226 | 33.931 | 12.231 | 34.199 |
22 | 4.194.304 | 175.223 | 60.948 | 114.274 | 23.011 | 64.456 | 23.159 | 64.597 |
23 | 8.388.608 | 332.634 | 115.413 | 217.220 | 43.681 | 122.430 | 43.752 | 122.771 |
24 | 16.777.216 | 633.465 | 219.302 | 414.162 | 82.729 | 233.588 | 83.158 | 233.990 |
25 | 33.554.432 | 1.209.886 | 418.227 | 791.658 | 157.619 | 446.875 | 158.369 | 447.023 |
26 | 67.108.864 | 2.314.726 | 798.878 | 1.515.847 | 301.331 | 855.196 | 302.180 | 856.019 |
27 | 134.217.728 | 4.440.552 | 1.530.589 | 2.909.962 | 577.416 | 1.642.030 | 578.757 | 1.642.349 |
28 | 268.435.456 | 8.528.366 | 2.936.919 | 5.591.446 | 1.107.844 | 3.156.550 | 1.108.570 | 3.155.402 |
29 | 536.870.912 | 16.411.234 | 5.641.746 | 10.769.487 | 2.130.679 | 6.075.987 | 2.129.023 | 6.075.545 |
30 | 1.073.741.824 | 31.617.104 | 10.856.660 | 20.760.443 | 4.099.855 | 11.710.649 | 4.096.723 | 11.709.877 |
31 | 2.147.483.648 | 61.002.572 | 20.926.448 | 40.076.123 | 7.897.241 | 22.606.139 | 7.894.837 | 22.604.355 |
32 | 4.294.967.296 | 117.843.033 | 40.391.205 | 77.451.827 | 15.237.812 | 43.686.249 | 15.233.254 | 43.685.718 |
33 | 8.589.934.592 | 227.903.004 | 78.043.779 | 149.859.224 | 29.434.954 | 84.516.668 | 29.429.137 | 84.522.245 |
34 | 17.179.869.184 | 441.276.967 | 150.978.568 | 290.298.398 | 56.934.458 | 163.708.433 | 56.926.771 | 163.707.305 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 0 | 1 | 2 |
4 | 16 | 9 | 5 | 4 | 1 | 1 | 3 | 4 |
5 | 32 | 14 | 7 | 7 | 2 | 4 | 4 | 4 |
6 | 64 | 26 | 15 | 11 | 4 | 6 | 7 | 9 |
7 | 128 | 27 | 16 | 11 | 4 | 6 | 7 | 10 |
8 | 256 | 52 | 28 | 24 | 10 | 11 | 16 | 15 |
9 | 512 | 156 | 77 | 79 | 39 | 33 | 47 | 37 |
10 | 1.024 | 389 | 189 | 200 | 101 | 86 | 112 | 90 |
11 | 2.048 | 888 | 435 | 453 | 245 | 192 | 247 | 204 |
12 | 4.096 | 1.937 | 947 | 990 | 512 | 436 | 554 | 435 |
13 | 8.192 | 4.115 | 2.008 | 2.107 | 1.071 | 957 | 1.102 | 985 |
14 | 16.384 | 8.568 | 4.199 | 4.369 | 2.194 | 2.037 | 2.303 | 2.034 |
15 | 32.768 | 17.662 | 8.614 | 9.048 | 4.612 | 4.145 | 4.701 | 4.204 |
16 | 65.536 | 36.072 | 17.633 | 18.439 | 9.379 | 8.503 | 9.629 | 8.561 |
17 | 131.072 | 73.562 | 36.221 | 37.341 | 19.185 | 17.416 | 19.350 | 17.611 |
18 | 262.144 | 149.403 | 73.686 | 75.717 | 39.064 | 35.475 | 39.048 | 35.816 |
19 | 524.288 | 302.631 | 149.472 | 153.159 | 78.587 | 72.498 | 78.734 | 72.812 |
20 | 1.048.576 | 612.517 | 302.173 | 310.344 | 158.470 | 147.551 | 159.067 | 147.429 |
21 | 2.097.152 | 1.236.657 | 610.677 | 625.980 | 319.533 | 298.438 | 320.763 | 297.923 |
22 | 4.194.304 | 2.495.734 | 1.233.985 | 1.261.749 | 645.119 | 603.020 | 645.204 | 602.391 |
23 | 8.388.608 | 5.030.235 | 2.489.216 | 2.541.019 | 1.297.715 | 1.217.129 | 1.299.755 | 1.215.636 |
24 | 16.777.216 | 10.132.001 | 5.015.713 | 5.116.288 | 2.609.692 | 2.455.144 | 2.613.763 | 2.453.402 |
25 | 33.554.432 | 20.392.552 | 10.100.776 | 10.291.776 | 5.245.759 | 4.950.453 | 5.248.529 | 4.947.811 |
26 | 67.108.864 | 41.022.678 | 20.328.606 | 20.694.072 | 10.539.094 | 9.974.030 | 10.538.893 | 9.970.661 |
27 | 134.217.728 | 82.483.426 | 40.892.180 | 41.591.246 | 21.159.821 | 20.080.779 | 21.165.689 | 20.077.137 |
28 | 268.435.456 | 165.774.444 | 82.210.813 | 83.563.631 | 42.480.802 | 40.404.837 | 42.491.149 | 40.397.656 |
29 | 536.870.912 | 333.032.577 | 165.210.517 | 167.822.060 | 85.258.571 | 81.263.510 | 85.269.141 | 81.241.355 |
30 | 1.073.741.824 | 668.825.550 | 331.893.442 | 336.932.108 | 171.079.153 | 163.347.938 | 171.085.731 | 163.312.728 |
31 | 2.147.483.648 | 1.342.789.829 | 666.541.151 | 676.248.678 | 343.177.820 | 328.239.932 | 343.175.415 | 328.196.662 |
32 | 4.294.967.296 | 2.695.188.258 | 1.338.218.208 | 1.356.970.050 | 688.246.887 | 659.358.995 | 688.250.994 | 659.331.382 |
33 | 8.589.934.592 | 5.408.400.591 | 2.686.076.777 | 2.722.323.814 | 1.380.081.879 | 1.324.110.414 | 1.380.099.318 | 1.324.108.980 |
34 | 17.179.869.184 | 10.850.565.477 | 5.390.148.292 | 5.460.417.185 | 2.766.796.455 | 2.658.439.826 | 2.766.919.189 | 2.658.410.007 |