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-104x+191
f(0)=191
f(1)=11
f(2)=13
f(3)=7
f(4)=19
f(5)=1
f(6)=397
f(7)=61
f(8)=577
f(9)=83
f(10)=107
f(11)=1
f(12)=1
f(13)=31
f(14)=1069
f(15)=1
f(16)=1217
f(17)=23
f(18)=59
f(19)=89
f(20)=1489
f(21)=97
f(22)=1613
f(23)=1
f(24)=1
f(25)=223
f(26)=167
f(27)=1
f(28)=149
f(29)=1
f(30)=2029
f(31)=37
f(32)=2113
f(33)=269
f(34)=199
f(35)=139
f(36)=1
f(37)=1
f(38)=331
f(39)=293
f(40)=103
f(41)=1
f(42)=127
f(43)=1
f(44)=79
f(45)=1
f(46)=2477
f(47)=311
f(48)=227
f(49)=313
f(50)=193
f(51)=157
f(52)=359
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
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-104x+191 could be written as f(y)= y^2-2513 with x=y+52
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-52
f'(x)>2x-105 with x > 50
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 | 10 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 37 | 11 | 26 | 0.370000 | 0.110000 | 0.370000 | 3.700000 | 2.750000 | 4.333333 |
3 | 1.000 | 554 | 128 | 426 | 0.554000 | 0.128000 | 0.554000 | 14.972973 | 11.636364 | 16.384615 |
4 | 10.000 | 6.338 | 963 | 5.375 | 0.633800 | 0.096300 | 0.633800 | 11.440434 | 7.523438 | 12.617371 |
5 | 100.000 | 65.305 | 7.372 | 57.933 | 0.653050 | 0.073720 | 0.653050 | 10.303723 | 7.655244 | 10.778233 |
6 | 1.000.000 | 660.534 | 60.222 | 600.312 | 0.660534 | 0.060222 | 0.660534 | 10.114601 | 8.169018 | 10.362177 |
7 | 10.000.000 | 6.653.385 | 511.738 | 6.141.647 | 0.665339 | 0.051174 | 0.665339 | 10.072737 | 8.497526 | 10.230759 |
8 | 100.000.000 | 66.892.183 | 4.437.342 | 62.454.841 | 0.668922 | 0.044373 | 0.668922 | 10.053858 | 8.671121 | 10.169070 |
9 | 1.000.000.000 | 671.651.090 | 39.156.382 | 632.494.708 | 0.671651 | 0.039156 | 0.671651 | 10.040800 | 8.824288 | 10.127234 |
10 | 10.000.000.000 | 6.738.268.597 | 350.422.668 | 6.387.845.929 | 0.673827 | 0.035042 | 0.673827 | 10.032394 | 8.949311 | 10.099445 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 2.000000 | 1.333333 |
4 | 16 | 13 | 6 | 7 | 0.812500 | 0.375000 | 0.437500 | 1.625000 | 1.500000 | 1.750000 |
5 | 32 | 23 | 10 | 13 | 0.718750 | 0.312500 | 0.406250 | 1.769231 | 1.666667 | 1.857143 |
6 | 64 | 37 | 11 | 26 | 0.578125 | 0.171875 | 0.406250 | 1.608696 | 1.100000 | 2.000000 |
7 | 128 | 44 | 16 | 28 | 0.343750 | 0.125000 | 0.218750 | 1.189189 | 1.454545 | 1.076923 |
8 | 256 | 108 | 41 | 67 | 0.421875 | 0.160156 | 0.261719 | 2.454545 | 2.562500 | 2.392857 |
9 | 512 | 251 | 71 | 180 | 0.490234 | 0.138672 | 0.351562 | 2.324074 | 1.731707 | 2.686567 |
10 | 1.024 | 569 | 131 | 438 | 0.555664 | 0.127930 | 0.427734 | 2.266932 | 1.845070 | 2.433333 |
11 | 2.048 | 1.215 | 234 | 981 | 0.593262 | 0.114258 | 0.479004 | 2.135325 | 1.786260 | 2.239726 |
12 | 4.096 | 2.532 | 437 | 2.095 | 0.618164 | 0.106689 | 0.511475 | 2.083951 | 1.867521 | 2.135576 |
13 | 8.192 | 5.168 | 815 | 4.353 | 0.630859 | 0.099487 | 0.531372 | 2.041074 | 1.864989 | 2.077804 |
14 | 16.384 | 10.480 | 1.506 | 8.974 | 0.639648 | 0.091919 | 0.547729 | 2.027864 | 1.847853 | 2.061567 |
15 | 32.768 | 21.174 | 2.704 | 18.470 | 0.646179 | 0.082520 | 0.563660 | 2.020420 | 1.795485 | 2.058168 |
16 | 65.536 | 42.682 | 5.022 | 37.660 | 0.651276 | 0.076630 | 0.574646 | 2.015774 | 1.857249 | 2.038982 |
17 | 131.072 | 85.719 | 9.432 | 76.287 | 0.653984 | 0.071960 | 0.582024 | 2.008317 | 1.878136 | 2.025677 |
18 | 262.144 | 172.167 | 17.571 | 154.596 | 0.656765 | 0.067028 | 0.589737 | 2.008505 | 1.862913 | 2.026505 |
19 | 524.288 | 345.383 | 33.205 | 312.178 | 0.658766 | 0.063334 | 0.595432 | 2.006093 | 1.889762 | 2.019315 |
20 | 1.048.576 | 692.721 | 62.913 | 629.808 | 0.660630 | 0.059999 | 0.600632 | 2.005660 | 1.894685 | 2.017464 |
21 | 2.097.152 | 1.388.664 | 119.807 | 1.268.857 | 0.662167 | 0.057128 | 0.605038 | 2.004651 | 1.904328 | 2.014673 |
22 | 4.194.304 | 2.783.787 | 227.706 | 2.556.081 | 0.663707 | 0.054289 | 0.609417 | 2.004651 | 1.900607 | 2.014475 |
23 | 8.388.608 | 5.578.740 | 434.310 | 5.144.430 | 0.665038 | 0.051774 | 0.613264 | 2.004011 | 1.907328 | 2.012624 |
24 | 16.777.216 | 11.177.099 | 830.585 | 10.346.514 | 0.666207 | 0.049507 | 0.616700 | 2.003517 | 1.912424 | 2.011207 |
25 | 33.554.432 | 22.392.390 | 1.589.366 | 20.803.024 | 0.667345 | 0.047367 | 0.619978 | 2.003417 | 1.913550 | 2.010631 |
26 | 67.108.864 | 44.853.390 | 3.048.186 | 41.805.204 | 0.668368 | 0.045422 | 0.622946 | 2.003064 | 1.917863 | 2.009573 |
27 | 134.217.728 | 89.832.887 | 5.855.225 | 83.977.662 | 0.669307 | 0.043625 | 0.625682 | 2.002811 | 1.920888 | 2.008785 |
28 | 268.435.456 | 179.895.457 | 11.264.683 | 168.630.774 | 0.670163 | 0.041964 | 0.628199 | 2.002557 | 1.923869 | 2.008043 |
29 | 536.870.912 | 360.226.400 | 21.708.247 | 338.518.153 | 0.670974 | 0.040435 | 0.630539 | 2.002421 | 1.927107 | 2.007452 |
30 | 1.073.741.824 | 721.258.983 | 41.891.214 | 679.367.769 | 0.671725 | 0.039014 | 0.632711 | 2.002238 | 1.929737 | 2.006887 |
31 | 2.147.483.648 | 1.444.020.601 | 80.932.606 | 1.363.087.995 | 0.672424 | 0.037687 | 0.634737 | 2.002083 | 1.931971 | 2.006407 |
32 | 4.294.967.296 | 2.890.865.124 | 156.545.944 | 2.734.319.180 | 0.673082 | 0.036449 | 0.636633 | 2.001956 | 1.934275 | 2.005974 |
33 | 8.589.934.592 | 5.787.009.150 | 303.110.605 | 5.483.898.545 | 0.673697 | 0.035287 | 0.638410 | 2.001826 | 1.936240 | 2.005581 |
34 | 17.179.869.184 | 11.584.015.940 | 587.497.333 | 10.996.518.607 | 0.674278 | 0.034197 | 0.640082 | 2.001728 | 1.938228 | 2.005238 |
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 | 1 | 0 | 0 | 1 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 3 | 1 | 1 | 0 | 2 | 1 |
4 | 16 | 6 | 4 | 2 | 2 | 0 | 3 | 1 |
5 | 32 | 10 | 7 | 3 | 4 | 0 | 5 | 1 |
6 | 64 | 11 | 7 | 4 | 4 | 0 | 6 | 1 |
7 | 128 | 16 | 9 | 7 | 4 | 1 | 6 | 5 |
8 | 256 | 41 | 19 | 22 | 4 | 14 | 6 | 17 |
9 | 512 | 71 | 24 | 47 | 4 | 31 | 6 | 30 |
10 | 1.024 | 131 | 42 | 89 | 4 | 62 | 6 | 59 |
11 | 2.048 | 234 | 72 | 162 | 4 | 111 | 6 | 113 |
12 | 4.096 | 437 | 154 | 283 | 4 | 213 | 6 | 214 |
13 | 8.192 | 815 | 285 | 530 | 4 | 406 | 6 | 399 |
14 | 16.384 | 1.506 | 507 | 999 | 4 | 769 | 6 | 727 |
15 | 32.768 | 2.704 | 916 | 1.788 | 4 | 1.374 | 6 | 1.320 |
16 | 65.536 | 5.022 | 1.688 | 3.334 | 4 | 2.508 | 6 | 2.504 |
17 | 131.072 | 9.432 | 3.168 | 6.264 | 4 | 4.728 | 6 | 4.694 |
18 | 262.144 | 17.571 | 5.865 | 11.706 | 4 | 8.808 | 6 | 8.753 |
19 | 524.288 | 33.205 | 11.047 | 22.158 | 4 | 16.555 | 6 | 16.640 |
20 | 1.048.576 | 62.913 | 20.860 | 42.053 | 4 | 31.388 | 6 | 31.515 |
21 | 2.097.152 | 119.807 | 39.979 | 79.828 | 4 | 59.707 | 6 | 60.090 |
22 | 4.194.304 | 227.706 | 75.844 | 151.862 | 4 | 113.689 | 6 | 114.007 |
23 | 8.388.608 | 434.310 | 144.626 | 289.684 | 4 | 216.839 | 6 | 217.461 |
24 | 16.777.216 | 830.585 | 276.815 | 553.770 | 4 | 415.000 | 6 | 415.575 |
25 | 33.554.432 | 1.589.366 | 530.022 | 1.059.344 | 4 | 794.605 | 6 | 794.751 |
26 | 67.108.864 | 3.048.186 | 1.016.453 | 2.031.733 | 4 | 1.523.994 | 6 | 1.524.182 |
27 | 134.217.728 | 5.855.225 | 1.951.358 | 3.903.867 | 4 | 2.927.395 | 6 | 2.927.820 |
28 | 268.435.456 | 11.264.683 | 3.754.505 | 7.510.178 | 4 | 5.633.115 | 6 | 5.631.558 |
29 | 536.870.912 | 21.708.247 | 7.237.297 | 14.470.950 | 4 | 10.855.227 | 6 | 10.853.010 |
30 | 1.073.741.824 | 41.891.214 | 13.962.503 | 27.928.711 | 4 | 20.945.893 | 6 | 20.945.311 |
31 | 2.147.483.648 | 80.932.606 | 26.977.975 | 53.954.631 | 4 | 40.467.684 | 6 | 40.464.912 |
32 | 4.294.967.296 | 156.545.944 | 52.177.651 | 104.368.293 | 4 | 78.275.026 | 6 | 78.270.908 |
33 | 8.589.934.592 | 303.110.605 | 101.035.153 | 202.075.452 | 4 | 151.560.921 | 6 | 151.549.674 |
34 | 17.179.869.184 | 587.497.333 | 195.825.309 | 391.672.024 | 4 | 293.758.648 | 6 | 293.738.675 |
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 | 3 | 2 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 3 | 1 | 0 | 2 | 1 | 1 |
4 | 16 | 7 | 4 | 3 | 0 | 4 | 1 | 2 |
5 | 32 | 13 | 6 | 7 | 2 | 5 | 2 | 4 |
6 | 64 | 26 | 14 | 12 | 4 | 8 | 5 | 9 |
7 | 128 | 28 | 14 | 14 | 5 | 8 | 6 | 9 |
8 | 256 | 67 | 34 | 33 | 18 | 17 | 16 | 16 |
9 | 512 | 180 | 89 | 91 | 45 | 45 | 53 | 37 |
10 | 1.024 | 438 | 226 | 212 | 119 | 99 | 124 | 96 |
11 | 2.048 | 981 | 504 | 477 | 284 | 206 | 276 | 215 |
12 | 4.096 | 2.095 | 1.048 | 1.047 | 611 | 457 | 580 | 447 |
13 | 8.192 | 4.353 | 2.168 | 2.185 | 1.186 | 978 | 1.189 | 1.000 |
14 | 16.384 | 8.974 | 4.476 | 4.498 | 2.363 | 2.105 | 2.418 | 2.088 |
15 | 32.768 | 18.470 | 9.289 | 9.181 | 4.826 | 4.368 | 4.963 | 4.313 |
16 | 65.536 | 37.660 | 18.994 | 18.666 | 9.934 | 8.873 | 10.046 | 8.807 |
17 | 131.072 | 76.287 | 38.384 | 37.903 | 19.972 | 18.181 | 20.231 | 17.903 |
18 | 262.144 | 154.596 | 77.774 | 76.822 | 40.357 | 36.857 | 40.780 | 36.602 |
19 | 524.288 | 312.178 | 156.780 | 155.398 | 81.277 | 74.566 | 81.993 | 74.342 |
20 | 1.048.576 | 629.808 | 316.538 | 313.270 | 163.717 | 150.537 | 164.771 | 150.783 |
21 | 2.097.152 | 1.268.857 | 637.366 | 631.491 | 328.985 | 304.278 | 330.626 | 304.968 |
22 | 4.194.304 | 2.556.081 | 1.284.014 | 1.272.067 | 661.962 | 615.259 | 664.011 | 614.849 |
23 | 8.388.608 | 5.144.430 | 2.583.758 | 2.560.672 | 1.330.592 | 1.240.925 | 1.332.100 | 1.240.813 |
24 | 16.777.216 | 10.346.514 | 5.196.779 | 5.149.735 | 2.671.197 | 2.499.998 | 2.674.459 | 2.500.860 |
25 | 33.554.432 | 20.803.024 | 10.443.959 | 10.359.065 | 5.363.401 | 5.036.108 | 5.368.647 | 5.034.868 |
26 | 67.108.864 | 41.805.204 | 20.982.545 | 20.822.659 | 10.766.953 | 10.132.206 | 10.771.713 | 10.134.332 |
27 | 134.217.728 | 83.977.662 | 42.145.316 | 41.832.346 | 21.602.475 | 20.384.864 | 21.604.610 | 20.385.713 |
28 | 268.435.456 | 168.630.774 | 84.614.432 | 84.016.342 | 43.331.504 | 40.991.096 | 43.330.101 | 40.978.073 |
29 | 536.870.912 | 338.518.153 | 169.832.956 | 168.685.197 | 86.885.109 | 82.382.920 | 86.880.648 | 82.369.476 |
30 | 1.073.741.824 | 679.367.769 | 340.786.239 | 338.581.530 | 174.181.876 | 165.508.585 | 174.181.264 | 165.496.044 |
31 | 2.147.483.648 | 1.363.087.995 | 683.671.000 | 679.416.995 | 349.146.997 | 332.412.043 | 349.131.444 | 332.397.511 |
32 | 4.294.967.296 | 2.734.319.180 | 1.371.250.393 | 1.363.068.787 | 699.744.625 | 667.418.115 | 699.762.323 | 667.394.117 |
33 | 8.589.934.592 | 5.483.898.545 | 2.749.862.130 | 2.734.036.415 | 1.402.212.087 | 1.339.736.072 | 1.402.270.546 | 1.339.679.840 |
34 | 17.179.869.184 | 10.996.518.607 | 5.513.556.870 | 5.482.961.737 | 2.809.625.557 | 2.688.645.032 | 2.809.701.098 | 2.688.546.920 |