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-28x+37
f(0)=37
f(1)=5
f(2)=3
f(3)=19
f(4)=59
f(5)=13
f(6)=1
f(7)=11
f(8)=41
f(9)=67
f(10)=1
f(11)=1
f(12)=31
f(13)=79
f(14)=53
f(15)=1
f(16)=1
f(17)=1
f(18)=1
f(19)=1
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=97
f(31)=1
f(32)=1
f(33)=101
f(34)=241
f(35)=47
f(36)=1
f(37)=1
f(38)=139
f(39)=233
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=401
f(46)=173
f(47)=1
f(48)=997
f(49)=1
f(50)=379
f(51)=1
f(52)=257
f(53)=227
f(54)=131
f(55)=761
f(56)=107
f(57)=1
f(58)=1777
f(59)=311
f(60)=103
f(61)=1
f(62)=1
f(63)=1
f(64)=2341
f(65)=1
f(66)=509
f(67)=1
f(68)=919
f(69)=1433
f(70)=229
f(71)=1
f(72)=641
f(73)=151
f(74)=1
f(75)=137
f(76)=1
f(77)=127
f(78)=1
f(79)=1
f(80)=1399
f(81)=433
f(82)=1
f(83)=1
f(84)=431
f(85)=2441
f(86)=1
f(87)=1
f(88)=409
f(89)=911
f(90)=1
f(91)=577
f(92)=1
f(93)=3041
f(94)=1
f(95)=1
f(96)=1
f(97)=673
f(98)=1
f(99)=3533
b) Substitution of the polynom
The polynom f(x)=x^2-28x+37 could be written as f(y)= y^2-159 with x=y+14
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-14
f'(x)>2x-29 with x > 13
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.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 44 | 9 | 35 | 0.440000 | 0.090000 | 0.440000 | 5.500000 | 3.000000 | 7.000000 |
3 | 1.000 | 626 | 62 | 564 | 0.626000 | 0.062000 | 0.626000 | 14.227273 | 6.888889 | 16.114286 |
4 | 10.000 | 6.628 | 446 | 6.182 | 0.662800 | 0.044600 | 0.662800 | 10.587859 | 7.193548 | 10.960993 |
5 | 100.000 | 66.976 | 3.618 | 63.358 | 0.669760 | 0.036180 | 0.669760 | 10.105009 | 8.112107 | 10.248787 |
6 | 1.000.000 | 673.862 | 29.487 | 644.375 | 0.673862 | 0.029487 | 0.673862 | 10.061246 | 8.150083 | 10.170381 |
7 | 10.000.000 | 6.763.987 | 250.279 | 6.513.708 | 0.676399 | 0.025028 | 0.676399 | 10.037644 | 8.487774 | 10.108567 |
8 | 100.000.000 | 67.844.443 | 2.172.557 | 65.671.886 | 0.678444 | 0.021726 | 0.678444 | 10.030244 | 8.680540 | 10.082105 |
9 | 1.000.000.000 | 680.006.512 | 19.154.498 | 660.852.014 | 0.680007 | 0.019154 | 0.680007 | 10.023026 | 8.816568 | 10.062937 |
10 | 10.000.000.000 | 6.812.678.720 | 171.447.278 | 6.641.231.442 | 0.681268 | 0.017145 | 0.681268 | 10.018549 | 8.950758 | 10.049499 |
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 | 11 | 3 | 8 | 0.687500 | 0.187500 | 0.500000 | 1.571429 | 1.000000 | 2.000000 |
5 | 32 | 12 | 4 | 8 | 0.375000 | 0.125000 | 0.250000 | 1.090909 | 1.333333 | 1.000000 |
6 | 64 | 27 | 8 | 19 | 0.421875 | 0.125000 | 0.296875 | 2.250000 | 2.000000 | 2.375000 |
7 | 128 | 62 | 12 | 50 | 0.484375 | 0.093750 | 0.390625 | 2.296296 | 1.500000 | 2.631579 |
8 | 256 | 141 | 22 | 119 | 0.550781 | 0.085938 | 0.464844 | 2.274194 | 1.833333 | 2.380000 |
9 | 512 | 308 | 33 | 275 | 0.601562 | 0.064453 | 0.537109 | 2.184397 | 1.500000 | 2.310924 |
10 | 1.024 | 642 | 63 | 579 | 0.626953 | 0.061523 | 0.565430 | 2.084416 | 1.909091 | 2.105454 |
11 | 2.048 | 1.323 | 109 | 1.214 | 0.645996 | 0.053223 | 0.592773 | 2.060748 | 1.730159 | 2.096719 |
12 | 4.096 | 2.678 | 201 | 2.477 | 0.653809 | 0.049072 | 0.604736 | 2.024188 | 1.844037 | 2.040362 |
13 | 8.192 | 5.421 | 381 | 5.040 | 0.661743 | 0.046509 | 0.615234 | 2.024272 | 1.895522 | 2.034719 |
14 | 16.384 | 10.879 | 708 | 10.171 | 0.664001 | 0.043213 | 0.620789 | 2.006825 | 1.858268 | 2.018055 |
15 | 32.768 | 21.826 | 1.321 | 20.505 | 0.666077 | 0.040314 | 0.625763 | 2.006251 | 1.865819 | 2.016026 |
16 | 65.536 | 43.793 | 2.477 | 41.316 | 0.668228 | 0.037796 | 0.630432 | 2.006460 | 1.875095 | 2.014923 |
17 | 131.072 | 87.810 | 4.608 | 83.202 | 0.669937 | 0.035156 | 0.634781 | 2.005115 | 1.860315 | 2.013796 |
18 | 262.144 | 176.022 | 8.644 | 167.378 | 0.671471 | 0.032974 | 0.638496 | 2.004578 | 1.875868 | 2.011706 |
19 | 524.288 | 352.772 | 16.246 | 336.526 | 0.672859 | 0.030987 | 0.641872 | 2.004136 | 1.879454 | 2.010575 |
20 | 1.048.576 | 706.627 | 30.825 | 675.802 | 0.673892 | 0.029397 | 0.644495 | 2.003070 | 1.897390 | 2.008172 |
21 | 2.097.152 | 1.414.948 | 58.607 | 1.356.341 | 0.674700 | 0.027946 | 0.646754 | 2.002397 | 1.901281 | 2.007010 |
22 | 4.194.304 | 2.833.066 | 111.445 | 2.721.621 | 0.675456 | 0.026571 | 0.648885 | 2.002240 | 1.901565 | 2.006591 |
23 | 8.388.608 | 5.672.553 | 212.300 | 5.460.253 | 0.676221 | 0.025308 | 0.650913 | 2.002266 | 1.904976 | 2.006250 |
24 | 16.777.216 | 11.356.500 | 405.752 | 10.950.748 | 0.676900 | 0.024185 | 0.652715 | 2.002009 | 1.911220 | 2.005538 |
25 | 33.554.432 | 22.735.529 | 777.135 | 21.958.394 | 0.677572 | 0.023160 | 0.654411 | 2.001984 | 1.915296 | 2.005196 |
26 | 67.108.864 | 45.508.195 | 1.491.828 | 44.016.367 | 0.678125 | 0.022230 | 0.655895 | 2.001634 | 1.919651 | 2.004535 |
27 | 134.217.728 | 91.088.762 | 2.864.820 | 88.223.942 | 0.678664 | 0.021345 | 0.657320 | 2.001590 | 1.920342 | 2.004344 |
28 | 268.435.456 | 182.309.811 | 5.512.522 | 176.797.289 | 0.679157 | 0.020536 | 0.658621 | 2.001452 | 1.924212 | 2.003960 |
29 | 536.870.912 | 364.868.775 | 10.621.703 | 354.247.072 | 0.679621 | 0.019784 | 0.659837 | 2.001367 | 1.926832 | 2.003690 |
30 | 1.073.741.824 | 730.197.676 | 20.492.549 | 709.705.127 | 0.680050 | 0.019085 | 0.660964 | 2.001261 | 1.929309 | 2.003418 |
31 | 2.147.483.648 | 1.461.261.449 | 39.595.028 | 1.421.666.421 | 0.680453 | 0.018438 | 0.662015 | 2.001186 | 1.932167 | 2.003179 |
32 | 4.294.967.296 | 2.924.163.852 | 76.585.789 | 2.847.578.063 | 0.680835 | 0.017832 | 0.663003 | 2.001123 | 1.934227 | 2.002986 |
33 | 8.589.934.592 | 5.851.388.337 | 148.297.772 | 5.703.090.565 | 0.681191 | 0.017264 | 0.663927 | 2.001047 | 1.936361 | 2.002786 |
34 | 17.179.869.184 | 11.708.632.288 | 287.439.847 | 11.421.192.441 | 0.681532 | 0.016731 | 0.664801 | 2.001001 | 1.938261 | 2.002632 |
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 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
5 | 32 | 4 | 2 | 1 | 1 | 1 | 1 | 1 |
6 | 64 | 8 | 6 | 1 | 3 | 1 | 3 | 1 |
7 | 128 | 12 | 10 | 1 | 4 | 1 | 6 | 1 |
8 | 256 | 22 | 20 | 1 | 10 | 1 | 10 | 1 |
9 | 512 | 33 | 31 | 1 | 16 | 1 | 15 | 1 |
10 | 1.024 | 63 | 61 | 1 | 31 | 1 | 30 | 1 |
11 | 2.048 | 109 | 107 | 1 | 54 | 1 | 53 | 1 |
12 | 4.096 | 201 | 199 | 1 | 97 | 1 | 102 | 1 |
13 | 8.192 | 381 | 379 | 1 | 184 | 1 | 195 | 1 |
14 | 16.384 | 708 | 706 | 1 | 359 | 1 | 347 | 1 |
15 | 32.768 | 1.321 | 1.319 | 1 | 680 | 1 | 639 | 1 |
16 | 65.536 | 2.477 | 2.475 | 1 | 1.262 | 1 | 1.213 | 1 |
17 | 131.072 | 4.608 | 4.606 | 1 | 2.293 | 1 | 2.313 | 1 |
18 | 262.144 | 8.644 | 8.642 | 1 | 4.305 | 1 | 4.337 | 1 |
19 | 524.288 | 16.246 | 16.244 | 1 | 8.060 | 1 | 8.184 | 1 |
20 | 1.048.576 | 30.825 | 30.823 | 1 | 15.347 | 1 | 15.476 | 1 |
21 | 2.097.152 | 58.607 | 58.605 | 1 | 29.301 | 1 | 29.304 | 1 |
22 | 4.194.304 | 111.445 | 111.443 | 1 | 55.750 | 1 | 55.693 | 1 |
23 | 8.388.608 | 212.300 | 212.298 | 1 | 106.350 | 1 | 105.948 | 1 |
24 | 16.777.216 | 405.752 | 405.750 | 1 | 202.878 | 1 | 202.872 | 1 |
25 | 33.554.432 | 777.135 | 777.133 | 1 | 388.849 | 1 | 388.284 | 1 |
26 | 67.108.864 | 1.491.828 | 1.491.826 | 1 | 746.012 | 1 | 745.814 | 1 |
27 | 134.217.728 | 2.864.820 | 2.864.818 | 1 | 1.432.206 | 1 | 1.432.612 | 1 |
28 | 268.435.456 | 5.512.522 | 5.512.520 | 1 | 2.756.125 | 1 | 2.756.395 | 1 |
29 | 536.870.912 | 10.621.703 | 10.621.701 | 1 | 5.311.744 | 1 | 5.309.957 | 1 |
30 | 1.073.741.824 | 20.492.549 | 20.492.547 | 1 | 10.246.045 | 1 | 10.246.502 | 1 |
31 | 2.147.483.648 | 39.595.028 | 39.595.026 | 1 | 19.798.956 | 1 | 19.796.070 | 1 |
32 | 4.294.967.296 | 76.585.789 | 76.585.787 | 1 | 38.294.570 | 1 | 38.291.217 | 1 |
33 | 8.589.934.592 | 148.297.772 | 148.297.770 | 1 | 74.150.882 | 1 | 74.146.888 | 1 |
34 | 17.179.869.184 | 287.439.847 | 287.439.845 | 1 | 143.719.264 | 1 | 143.720.581 | 1 |
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 | 1 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 2 | 0 |
4 | 16 | 8 | 5 | 3 | 1 | 2 | 3 | 2 |
5 | 32 | 8 | 5 | 3 | 1 | 2 | 3 | 2 |
6 | 64 | 19 | 7 | 12 | 5 | 6 | 5 | 3 |
7 | 128 | 50 | 20 | 30 | 16 | 11 | 13 | 10 |
8 | 256 | 119 | 48 | 71 | 31 | 28 | 31 | 29 |
9 | 512 | 275 | 115 | 160 | 79 | 59 | 66 | 71 |
10 | 1.024 | 579 | 243 | 336 | 145 | 131 | 160 | 143 |
11 | 2.048 | 1.214 | 526 | 688 | 303 | 274 | 317 | 320 |
12 | 4.096 | 2.477 | 1.120 | 1.357 | 609 | 577 | 638 | 653 |
13 | 8.192 | 5.040 | 2.299 | 2.741 | 1.271 | 1.218 | 1.269 | 1.282 |
14 | 16.384 | 10.171 | 4.680 | 5.491 | 2.578 | 2.435 | 2.564 | 2.594 |
15 | 32.768 | 20.505 | 9.556 | 10.949 | 5.159 | 5.002 | 5.194 | 5.150 |
16 | 65.536 | 41.316 | 19.304 | 22.012 | 10.476 | 10.035 | 10.526 | 10.279 |
17 | 131.072 | 83.202 | 39.169 | 44.033 | 20.911 | 20.549 | 21.184 | 20.558 |
18 | 262.144 | 167.378 | 78.994 | 88.384 | 42.381 | 41.264 | 42.396 | 41.337 |
19 | 524.288 | 336.526 | 159.629 | 176.897 | 85.108 | 82.969 | 85.208 | 83.241 |
20 | 1.048.576 | 675.802 | 321.619 | 354.183 | 170.650 | 167.169 | 170.544 | 167.439 |
21 | 2.097.152 | 1.356.341 | 647.688 | 708.653 | 342.399 | 335.583 | 342.565 | 335.794 |
22 | 4.194.304 | 2.721.621 | 1.302.705 | 1.418.916 | 685.868 | 674.372 | 688.105 | 673.276 |
23 | 8.388.608 | 5.460.253 | 2.620.260 | 2.839.993 | 1.377.301 | 1.352.971 | 1.378.509 | 1.351.472 |
24 | 16.777.216 | 10.950.748 | 5.266.681 | 5.684.067 | 2.762.649 | 2.713.109 | 2.763.785 | 2.711.205 |
25 | 33.554.432 | 21.958.394 | 10.582.284 | 11.376.110 | 5.540.081 | 5.437.907 | 5.539.799 | 5.440.607 |
26 | 67.108.864 | 44.016.367 | 21.247.614 | 22.768.753 | 11.104.927 | 10.903.967 | 11.099.414 | 10.908.059 |
27 | 134.217.728 | 88.223.942 | 42.649.169 | 45.574.773 | 22.250.464 | 21.864.039 | 22.245.722 | 21.863.717 |
28 | 268.435.456 | 176.797.289 | 85.589.914 | 91.207.375 | 44.571.026 | 43.832.553 | 44.565.312 | 43.828.398 |
29 | 536.870.912 | 354.247.072 | 171.721.185 | 182.525.887 | 89.274.401 | 87.858.051 | 89.264.645 | 87.849.975 |
30 | 1.073.741.824 | 709.705.127 | 344.455.489 | 365.249.638 | 178.817.216 | 176.066.156 | 178.789.676 | 176.032.079 |
31 | 2.147.483.648 | 1.421.666.421 | 690.749.306 | 730.917.115 | 358.096.263 | 352.776.375 | 358.060.918 | 352.732.865 |
32 | 4.294.967.296 | 2.847.578.063 | 1.384.942.669 | 1.462.635.394 | 717.060.387 | 706.743.254 | 717.039.920 | 706.734.502 |
33 | 8.589.934.592 | 5.703.090.565 | 2.776.397.372 | 2.926.693.193 | 1.435.834.618 | 1.415.720.905 | 1.435.799.621 | 1.415.735.421 |
34 | 17.179.869.184 | 11.421.192.441 | 5.564.969.992 | 5.856.222.449 | 2.874.799.408 | 2.835.742.099 | 2.874.882.779 | 2.835.768.155 |