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-44x+53
f(0)=53
f(1)=5
f(2)=31
f(3)=7
f(4)=107
f(5)=71
f(6)=1
f(7)=103
f(8)=47
f(9)=131
f(10)=41
f(11)=1
f(12)=331
f(13)=1
f(14)=367
f(15)=191
f(16)=79
f(17)=29
f(18)=83
f(19)=211
f(20)=61
f(21)=43
f(22)=431
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=97
f(48)=1
f(49)=149
f(50)=353
f(51)=1
f(52)=67
f(53)=1
f(54)=593
f(55)=1
f(56)=1
f(57)=397
f(58)=173
f(59)=1
f(60)=1013
f(61)=109
f(62)=167
f(63)=1
f(64)=1
f(65)=709
f(66)=1
f(67)=797
f(68)=337
f(69)=127
f(70)=1873
f(71)=197
f(72)=2069
f(73)=1
f(74)=2273
f(75)=1
f(76)=1
f(77)=1297
f(78)=541
f(79)=1409
f(80)=419
f(81)=1
f(82)=3169
f(83)=1
f(84)=3413
f(85)=1
f(86)=733
f(87)=271
f(88)=157
f(89)=2029
f(90)=599
f(91)=433
f(92)=1
f(93)=461
f(94)=1
f(95)=1
f(96)=1009
f(97)=1
f(98)=1069
f(99)=2749
b) Substitution of the polynom
The polynom f(x)=x^2-44x+53 could be written as f(y)= y^2-431 with x=y+22
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-22
f'(x)>2x-45 with x > 21
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 | 7 | 3 | 1.000000 | 0.700000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 50 | 30 | 20 | 0.500000 | 0.300000 | 0.200000 | 5.000000 | 4.285714 | 6.666667 |
3 | 1.000 | 635 | 197 | 438 | 0.635000 | 0.197000 | 0.438000 | 12.700000 | 6.566667 | 21.900000 |
4 | 10.000 | 6.762 | 1.394 | 5.368 | 0.676200 | 0.139400 | 0.536800 | 10.648819 | 7.076142 | 12.255708 |
5 | 100.000 | 68.328 | 10.940 | 57.388 | 0.683280 | 0.109400 | 0.573880 | 10.104703 | 7.847919 | 10.690760 |
6 | 1.000.000 | 685.096 | 88.455 | 596.641 | 0.685096 | 0.088455 | 0.596641 | 10.026578 | 8.085466 | 10.396616 |
7 | 10.000.000 | 6.861.878 | 747.158 | 6.114.720 | 0.686188 | 0.074716 | 0.611472 | 10.015937 | 8.446758 | 10.248575 |
8 | 100.000.000 | 68.694.972 | 6.461.337 | 62.233.635 | 0.686950 | 0.064613 | 0.622336 | 10.011105 | 8.647885 | 10.177675 |
9 | 1.000.000.000 | 687.566.543 | 56.935.184 | 630.631.359 | 0.687567 | 0.056935 | 0.630631 | 10.008978 | 8.811672 | 10.133288 |
10 | 10.000.000.000 | 6.880.684.635 | 509.091.394 | 6.371.593.241 | 0.688068 | 0.050909 | 0.637159 | 10.007300 | 8.941596 | 10.103515 |
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 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 1.600000 | 1.500000 | 2.000000 |
4 | 16 | 14 | 10 | 4 | 0.875000 | 0.625000 | 0.250000 | 1.750000 | 1.666667 | 2.000000 |
5 | 32 | 19 | 12 | 7 | 0.593750 | 0.375000 | 0.218750 | 1.357143 | 1.200000 | 1.750000 |
6 | 64 | 27 | 18 | 9 | 0.421875 | 0.281250 | 0.140625 | 1.421053 | 1.500000 | 1.285714 |
7 | 128 | 65 | 36 | 29 | 0.507812 | 0.281250 | 0.226562 | 2.407408 | 2.000000 | 3.222222 |
8 | 256 | 144 | 64 | 80 | 0.562500 | 0.250000 | 0.312500 | 2.215385 | 1.777778 | 2.758621 |
9 | 512 | 312 | 112 | 200 | 0.609375 | 0.218750 | 0.390625 | 2.166667 | 1.750000 | 2.500000 |
10 | 1.024 | 652 | 201 | 451 | 0.636719 | 0.196289 | 0.440430 | 2.089744 | 1.794643 | 2.255000 |
11 | 2.048 | 1.343 | 365 | 978 | 0.655762 | 0.178223 | 0.477539 | 2.059816 | 1.815920 | 2.168514 |
12 | 4.096 | 2.734 | 660 | 2.074 | 0.667480 | 0.161133 | 0.506348 | 2.035741 | 1.808219 | 2.120654 |
13 | 8.192 | 5.536 | 1.168 | 4.368 | 0.675781 | 0.142578 | 0.533203 | 2.024872 | 1.769697 | 2.106075 |
14 | 16.384 | 11.126 | 2.178 | 8.948 | 0.679077 | 0.132935 | 0.546143 | 2.009754 | 1.864726 | 2.048535 |
15 | 32.768 | 22.347 | 4.030 | 18.317 | 0.681976 | 0.122986 | 0.558990 | 2.008538 | 1.850321 | 2.047050 |
16 | 65.536 | 44.795 | 7.464 | 37.331 | 0.683517 | 0.113892 | 0.569626 | 2.004520 | 1.852109 | 2.038052 |
17 | 131.072 | 89.596 | 13.940 | 75.656 | 0.683563 | 0.106354 | 0.577209 | 2.000134 | 1.867631 | 2.026627 |
18 | 262.144 | 179.423 | 26.053 | 153.370 | 0.684444 | 0.099384 | 0.585060 | 2.002578 | 1.868938 | 2.027202 |
19 | 524.288 | 359.063 | 48.858 | 310.205 | 0.684858 | 0.093189 | 0.591669 | 2.001209 | 1.875331 | 2.022592 |
20 | 1.048.576 | 718.380 | 92.398 | 625.982 | 0.685101 | 0.088118 | 0.596983 | 2.000707 | 1.891154 | 2.017962 |
21 | 2.097.152 | 1.437.574 | 174.959 | 1.262.615 | 0.685489 | 0.083427 | 0.602062 | 2.001133 | 1.893537 | 2.017015 |
22 | 4.194.304 | 2.876.586 | 332.484 | 2.544.102 | 0.685832 | 0.079270 | 0.606561 | 2.001000 | 1.900354 | 2.014947 |
23 | 8.388.608 | 5.755.245 | 634.271 | 5.120.974 | 0.686079 | 0.075611 | 0.610468 | 2.000721 | 1.907674 | 2.012881 |
24 | 16.777.216 | 11.514.548 | 1.210.550 | 10.303.998 | 0.686321 | 0.072154 | 0.614166 | 2.000705 | 1.908569 | 2.012117 |
25 | 33.554.432 | 23.037.749 | 2.316.459 | 20.721.290 | 0.686578 | 0.069036 | 0.617543 | 2.000751 | 1.913559 | 2.010995 |
26 | 67.108.864 | 46.093.727 | 4.439.787 | 41.653.940 | 0.686850 | 0.066158 | 0.620692 | 2.000791 | 1.916627 | 2.010200 |
27 | 134.217.728 | 92.213.981 | 8.524.490 | 83.689.491 | 0.687048 | 0.063512 | 0.623535 | 2.000576 | 1.920022 | 2.009161 |
28 | 268.435.456 | 184.479.331 | 16.393.287 | 168.086.044 | 0.687239 | 0.061070 | 0.626169 | 2.000557 | 1.923081 | 2.008449 |
29 | 536.870.912 | 369.053.747 | 31.578.802 | 337.474.945 | 0.687416 | 0.058820 | 0.628596 | 2.000515 | 1.926325 | 2.007751 |
30 | 1.073.741.824 | 738.287.513 | 60.911.847 | 677.375.666 | 0.687584 | 0.056729 | 0.630855 | 2.000488 | 1.928884 | 2.007188 |
31 | 2.147.483.648 | 1.476.919.763 | 117.653.783 | 1.359.265.980 | 0.687744 | 0.054787 | 0.632958 | 2.000467 | 1.931542 | 2.006665 |
32 | 4.294.967.296 | 2.954.489.315 | 227.501.129 | 2.726.988.186 | 0.687896 | 0.052969 | 0.634926 | 2.000440 | 1.933649 | 2.006221 |
33 | 8.589.934.592 | 5.910.201.656 | 440.384.516 | 5.469.817.140 | 0.688038 | 0.051268 | 0.636771 | 2.000414 | 1.935746 | 2.005809 |
34 | 17.179.869.184 | 11.822.739.692 | 853.380.169 | 10.969.359.523 | 0.688174 | 0.049673 | 0.638501 | 2.000395 | 1.937807 | 2.005434 |
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 | 1 | 2 | 0 | 0 | 2 | 1 |
2 | 4 | 4 | 1 | 3 | 0 | 1 | 2 | 1 |
3 | 8 | 6 | 2 | 4 | 0 | 1 | 2 | 3 |
4 | 16 | 10 | 4 | 6 | 0 | 3 | 2 | 5 |
5 | 32 | 12 | 5 | 7 | 0 | 4 | 2 | 6 |
6 | 64 | 18 | 7 | 11 | 3 | 4 | 5 | 6 |
7 | 128 | 36 | 18 | 18 | 10 | 4 | 16 | 6 |
8 | 256 | 64 | 28 | 36 | 24 | 4 | 30 | 6 |
9 | 512 | 112 | 52 | 60 | 51 | 4 | 51 | 6 |
10 | 1.024 | 201 | 100 | 101 | 98 | 4 | 93 | 6 |
11 | 2.048 | 365 | 185 | 180 | 176 | 4 | 179 | 6 |
12 | 4.096 | 660 | 344 | 316 | 322 | 4 | 328 | 6 |
13 | 8.192 | 1.168 | 604 | 564 | 565 | 4 | 593 | 6 |
14 | 16.384 | 2.178 | 1.115 | 1.063 | 1.080 | 4 | 1.088 | 6 |
15 | 32.768 | 4.030 | 2.039 | 1.991 | 1.991 | 4 | 2.029 | 6 |
16 | 65.536 | 7.464 | 3.766 | 3.698 | 3.708 | 4 | 3.746 | 6 |
17 | 131.072 | 13.940 | 7.050 | 6.890 | 6.962 | 4 | 6.968 | 6 |
18 | 262.144 | 26.053 | 13.140 | 12.913 | 13.060 | 4 | 12.983 | 6 |
19 | 524.288 | 48.858 | 24.580 | 24.278 | 24.497 | 4 | 24.351 | 6 |
20 | 1.048.576 | 92.398 | 46.504 | 45.894 | 46.291 | 4 | 46.097 | 6 |
21 | 2.097.152 | 174.959 | 87.872 | 87.087 | 87.648 | 4 | 87.301 | 6 |
22 | 4.194.304 | 332.484 | 166.873 | 165.611 | 166.318 | 4 | 166.156 | 6 |
23 | 8.388.608 | 634.271 | 318.364 | 315.907 | 317.458 | 4 | 316.803 | 6 |
24 | 16.777.216 | 1.210.550 | 607.391 | 603.159 | 605.022 | 4 | 605.518 | 6 |
25 | 33.554.432 | 2.316.459 | 1.163.002 | 1.153.457 | 1.157.212 | 4 | 1.159.237 | 6 |
26 | 67.108.864 | 4.439.787 | 2.228.238 | 2.211.549 | 2.219.514 | 4 | 2.220.263 | 6 |
27 | 134.217.728 | 8.524.490 | 4.277.388 | 4.247.102 | 4.263.079 | 4 | 4.261.401 | 6 |
28 | 268.435.456 | 16.393.287 | 8.222.864 | 8.170.423 | 8.198.865 | 4 | 8.194.412 | 6 |
29 | 536.870.912 | 31.578.802 | 15.838.937 | 15.739.865 | 15.792.396 | 4 | 15.786.396 | 6 |
30 | 1.073.741.824 | 60.911.847 | 30.549.083 | 30.362.764 | 30.456.937 | 4 | 30.454.900 | 6 |
31 | 2.147.483.648 | 117.653.783 | 58.992.535 | 58.661.248 | 58.826.883 | 4 | 58.826.890 | 6 |
32 | 4.294.967.296 | 227.501.129 | 114.059.846 | 113.441.283 | 113.752.413 | 4 | 113.748.706 | 6 |
33 | 8.589.934.592 | 440.384.516 | 220.777.408 | 219.607.108 | 220.196.664 | 4 | 220.187.842 | 6 |
34 | 17.179.869.184 | 853.380.169 | 427.785.507 | 425.594.662 | 426.701.198 | 4 | 426.678.961 | 6 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
4 | 16 | 4 | 2 | 2 | 1 | 0 | 0 | 3 |
5 | 32 | 7 | 4 | 3 | 1 | 2 | 1 | 3 |
6 | 64 | 9 | 4 | 5 | 1 | 2 | 2 | 4 |
7 | 128 | 29 | 16 | 13 | 7 | 5 | 9 | 8 |
8 | 256 | 80 | 42 | 38 | 20 | 18 | 21 | 21 |
9 | 512 | 200 | 101 | 99 | 46 | 48 | 61 | 45 |
10 | 1.024 | 451 | 226 | 225 | 105 | 111 | 132 | 103 |
11 | 2.048 | 978 | 493 | 485 | 244 | 228 | 259 | 247 |
12 | 4.096 | 2.074 | 1.025 | 1.049 | 517 | 505 | 509 | 543 |
13 | 8.192 | 4.368 | 2.157 | 2.211 | 1.079 | 1.074 | 1.106 | 1.109 |
14 | 16.384 | 8.948 | 4.429 | 4.519 | 2.222 | 2.207 | 2.263 | 2.256 |
15 | 32.768 | 18.317 | 9.120 | 9.197 | 4.590 | 4.577 | 4.586 | 4.564 |
16 | 65.536 | 37.331 | 18.615 | 18.716 | 9.329 | 9.330 | 9.366 | 9.306 |
17 | 131.072 | 75.656 | 37.831 | 37.825 | 18.999 | 18.841 | 18.944 | 18.872 |
18 | 262.144 | 153.370 | 76.822 | 76.548 | 38.456 | 38.132 | 38.414 | 38.368 |
19 | 524.288 | 310.205 | 155.096 | 155.109 | 77.849 | 77.251 | 77.771 | 77.334 |
20 | 1.048.576 | 625.982 | 312.636 | 313.346 | 157.079 | 155.781 | 157.200 | 155.922 |
21 | 2.097.152 | 1.262.615 | 631.182 | 631.433 | 316.659 | 314.076 | 317.493 | 314.387 |
22 | 4.194.304 | 2.544.102 | 1.271.405 | 1.272.697 | 638.587 | 633.564 | 638.367 | 633.584 |
23 | 8.388.608 | 5.120.974 | 2.560.147 | 2.560.827 | 1.283.810 | 1.276.128 | 1.285.621 | 1.275.415 |
24 | 16.777.216 | 10.303.998 | 5.149.919 | 5.154.079 | 2.582.864 | 2.567.448 | 2.586.999 | 2.566.687 |
25 | 33.554.432 | 20.721.290 | 10.357.647 | 10.363.643 | 5.195.206 | 5.162.315 | 5.201.250 | 5.162.519 |
26 | 67.108.864 | 41.653.940 | 20.820.232 | 20.833.708 | 10.446.048 | 10.378.233 | 10.451.295 | 10.378.364 |
27 | 134.217.728 | 83.689.491 | 41.835.419 | 41.854.072 | 20.991.260 | 20.854.053 | 20.991.579 | 20.852.599 |
28 | 268.435.456 | 168.086.044 | 84.036.420 | 84.049.624 | 42.152.786 | 41.890.932 | 42.155.353 | 41.886.973 |
29 | 536.870.912 | 337.474.945 | 168.725.814 | 168.749.131 | 84.626.737 | 84.114.748 | 84.632.299 | 84.101.161 |
30 | 1.073.741.824 | 677.375.666 | 338.667.954 | 338.707.712 | 169.850.830 | 168.846.210 | 169.849.042 | 168.829.584 |
31 | 2.147.483.648 | 1.359.265.980 | 679.591.989 | 679.673.991 | 340.817.253 | 338.824.132 | 340.814.533 | 338.810.062 |
32 | 4.294.967.296 | 2.726.988.186 | 1.363.413.009 | 1.363.575.177 | 683.725.854 | 679.784.388 | 683.686.531 | 679.791.413 |
33 | 8.589.934.592 | 5.469.817.140 | 2.734.739.492 | 2.735.077.648 | 1.371.308.233 | 1.363.633.477 | 1.371.247.204 | 1.363.628.226 |
34 | 17.179.869.184 | 10.969.359.523 | 5.484.336.147 | 5.485.023.376 | 2.749.963.283 | 2.734.731.253 | 2.749.860.268 | 2.734.804.719 |