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-108x+19
f(0)=19
f(1)=11
f(2)=193
f(3)=37
f(4)=397
f(5)=31
f(6)=593
f(7)=43
f(8)=71
f(9)=109
f(10)=1
f(11)=131
f(12)=103
f(13)=1
f(14)=1297
f(15)=1
f(16)=1453
f(17)=191
f(18)=1601
f(19)=1
f(20)=1741
f(21)=113
f(22)=1873
f(23)=1
f(24)=1997
f(25)=257
f(26)=2113
f(27)=271
f(28)=2221
f(29)=1
f(30)=211
f(31)=1
f(32)=127
f(33)=307
f(34)=227
f(35)=317
f(36)=83
f(37)=163
f(38)=139
f(39)=167
f(40)=73
f(41)=1
f(42)=2753
f(43)=347
f(44)=2797
f(45)=1
f(46)=2833
f(47)=89
f(48)=2861
f(49)=359
f(50)=67
f(51)=1
f(52)=263
f(53)=181
f(54)=2897
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-108x+19 could be written as f(y)= y^2-2897 with x=y+54
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-54
f'(x)>2x-109 with x > 54
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 | 9 | 1 | 1.000000 | 0.900000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 42 | 34 | 8 | 0.420000 | 0.340000 | 0.080000 | 4.200000 | 3.777778 | 8.000000 |
3 | 1.000 | 609 | 383 | 226 | 0.609000 | 0.383000 | 0.226000 | 14.500000 | 11.264706 | 28.250000 |
4 | 10.000 | 6.670 | 2.884 | 3.786 | 0.667000 | 0.288400 | 0.378600 | 10.952381 | 7.530026 | 16.752213 |
5 | 100.000 | 67.993 | 22.182 | 45.811 | 0.679930 | 0.221820 | 0.458110 | 10.193853 | 7.691401 | 12.100105 |
6 | 1.000.000 | 683.051 | 178.047 | 505.004 | 0.683051 | 0.178047 | 0.505004 | 10.045902 | 8.026643 | 11.023641 |
7 | 10.000.000 | 6.843.579 | 1.493.359 | 5.350.220 | 0.684358 | 0.149336 | 0.535022 | 10.019134 | 8.387443 | 10.594411 |
8 | 100.000.000 | 68.539.607 | 12.846.721 | 55.692.886 | 0.685396 | 0.128467 | 0.556929 | 10.015170 | 8.602567 | 10.409457 |
9 | 1.000.000.000 | 686.234.167 | 112.735.244 | 573.498.923 | 0.686234 | 0.112735 | 0.573499 | 10.012228 | 8.775411 | 10.297525 |
10 | 10.000.000.000 | 6.869.063.714 | 1.004.511.489 | 5.864.552.225 | 0.686906 | 0.100451 | 0.586455 | 10.009795 | 8.910358 | 10.225917 |
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 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 14 | 12 | 2 | 0.875000 | 0.750000 | 0.125000 | 1.555556 | 1.500000 | 2.000000 |
5 | 32 | 26 | 22 | 4 | 0.812500 | 0.687500 | 0.125000 | 1.857143 | 1.833333 | 2.000000 |
6 | 64 | 42 | 34 | 8 | 0.656250 | 0.531250 | 0.125000 | 1.615385 | 1.545455 | 2.000000 |
7 | 128 | 49 | 41 | 8 | 0.382812 | 0.320312 | 0.062500 | 1.166667 | 1.205882 | 1.000000 |
8 | 256 | 121 | 100 | 21 | 0.472656 | 0.390625 | 0.082031 | 2.469388 | 2.439024 | 2.625000 |
9 | 512 | 287 | 210 | 77 | 0.560547 | 0.410156 | 0.150391 | 2.371901 | 2.100000 | 3.666667 |
10 | 1.024 | 624 | 392 | 232 | 0.609375 | 0.382812 | 0.226562 | 2.174216 | 1.866667 | 3.012987 |
11 | 2.048 | 1.310 | 722 | 588 | 0.639648 | 0.352539 | 0.287109 | 2.099359 | 1.841837 | 2.534483 |
12 | 4.096 | 2.679 | 1.317 | 1.362 | 0.654053 | 0.321533 | 0.332520 | 2.045038 | 1.824100 | 2.316327 |
13 | 8.192 | 5.433 | 2.400 | 3.033 | 0.663208 | 0.292969 | 0.370239 | 2.027996 | 1.822323 | 2.226872 |
14 | 16.384 | 10.989 | 4.451 | 6.538 | 0.670715 | 0.271667 | 0.399048 | 2.022640 | 1.854583 | 2.155622 |
15 | 32.768 | 22.142 | 8.205 | 13.937 | 0.675720 | 0.250397 | 0.425323 | 2.014924 | 1.843406 | 2.131692 |
16 | 65.536 | 44.485 | 15.168 | 29.317 | 0.678787 | 0.231445 | 0.447342 | 2.009078 | 1.848629 | 2.103537 |
17 | 131.072 | 89.170 | 28.256 | 60.914 | 0.680313 | 0.215576 | 0.464737 | 2.004496 | 1.862869 | 2.077770 |
18 | 262.144 | 178.572 | 52.709 | 125.863 | 0.681198 | 0.201069 | 0.480129 | 2.002602 | 1.865409 | 2.066241 |
19 | 524.288 | 357.760 | 98.741 | 259.019 | 0.682373 | 0.188334 | 0.494040 | 2.003450 | 1.873323 | 2.057944 |
20 | 1.048.576 | 716.291 | 185.915 | 530.376 | 0.683108 | 0.177302 | 0.505806 | 2.002155 | 1.882855 | 2.047634 |
21 | 2.097.152 | 1.433.444 | 351.741 | 1.081.703 | 0.683519 | 0.167723 | 0.515796 | 2.001204 | 1.891945 | 2.039502 |
22 | 4.194.304 | 2.868.680 | 667.292 | 2.201.388 | 0.683947 | 0.159095 | 0.524852 | 2.001250 | 1.897112 | 2.035113 |
23 | 8.388.608 | 5.740.036 | 1.268.034 | 4.472.002 | 0.684266 | 0.151161 | 0.533104 | 2.000933 | 1.900269 | 2.031446 |
24 | 16.777.216 | 11.485.761 | 2.416.735 | 9.069.026 | 0.684605 | 0.144049 | 0.540556 | 2.000991 | 1.905891 | 2.027957 |
25 | 33.554.432 | 22.983.363 | 4.614.793 | 18.368.570 | 0.684958 | 0.137532 | 0.547426 | 2.001031 | 1.909516 | 2.025418 |
26 | 67.108.864 | 45.985.301 | 8.834.619 | 37.150.682 | 0.685234 | 0.131646 | 0.553588 | 2.000808 | 1.914413 | 2.022513 |
27 | 134.217.728 | 92.007.554 | 16.941.471 | 75.066.083 | 0.685510 | 0.126224 | 0.559286 | 2.000803 | 1.917623 | 2.020584 |
28 | 268.435.456 | 184.086.579 | 32.538.800 | 151.547.779 | 0.685776 | 0.121216 | 0.564559 | 2.000777 | 1.920660 | 2.018858 |
29 | 536.870.912 | 368.305.489 | 62.595.875 | 305.709.614 | 0.686022 | 0.116594 | 0.569429 | 2.000719 | 1.923730 | 2.017249 |
30 | 1.073.741.824 | 736.862.105 | 120.593.705 | 616.268.400 | 0.686256 | 0.112312 | 0.573945 | 2.000682 | 1.926544 | 2.015862 |
31 | 2.147.483.648 | 1.474.190.158 | 232.648.762 | 1.241.541.396 | 0.686473 | 0.108336 | 0.578138 | 2.000633 | 1.929195 | 2.014611 |
32 | 4.294.967.296 | 2.949.246.940 | 449.406.122 | 2.499.840.818 | 0.686675 | 0.104636 | 0.582040 | 2.000588 | 1.931694 | 2.013498 |
33 | 8.589.934.592 | 5.900.133.670 | 869.120.377 | 5.031.013.293 | 0.686866 | 0.101179 | 0.585687 | 2.000556 | 1.933931 | 2.012533 |
34 | 17.179.869.184 | 11.803.316.036 | 1.682.750.920 | 10.120.565.116 | 0.687043 | 0.097949 | 0.589094 | 2.000517 | 1.936154 | 2.011636 |
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 | 2 | 1 | 1 | 2 | 0 | 0 |
2 | 4 | 5 | 4 | 1 | 1 | 2 | 2 | 0 |
3 | 8 | 8 | 6 | 2 | 2 | 3 | 2 | 1 |
4 | 16 | 12 | 9 | 3 | 3 | 4 | 4 | 1 |
5 | 32 | 22 | 14 | 8 | 8 | 4 | 7 | 3 |
6 | 64 | 34 | 19 | 15 | 11 | 7 | 11 | 5 |
7 | 128 | 41 | 21 | 20 | 11 | 12 | 11 | 7 |
8 | 256 | 100 | 48 | 52 | 17 | 38 | 16 | 29 |
9 | 512 | 210 | 97 | 113 | 33 | 74 | 31 | 72 |
10 | 1.024 | 392 | 179 | 213 | 55 | 145 | 56 | 136 |
11 | 2.048 | 722 | 333 | 389 | 107 | 263 | 104 | 248 |
12 | 4.096 | 1.317 | 597 | 720 | 187 | 474 | 194 | 462 |
13 | 8.192 | 2.400 | 1.081 | 1.319 | 336 | 856 | 351 | 857 |
14 | 16.384 | 4.451 | 2.047 | 2.404 | 616 | 1.586 | 637 | 1.612 |
15 | 32.768 | 8.205 | 3.752 | 4.453 | 1.109 | 2.957 | 1.156 | 2.983 |
16 | 65.536 | 15.168 | 6.850 | 8.318 | 2.037 | 5.495 | 2.070 | 5.566 |
17 | 131.072 | 28.256 | 12.764 | 15.492 | 3.795 | 10.315 | 3.808 | 10.338 |
18 | 262.144 | 52.709 | 23.762 | 28.947 | 7.017 | 19.313 | 7.066 | 19.313 |
19 | 524.288 | 98.741 | 44.392 | 54.349 | 13.044 | 36.250 | 13.154 | 36.293 |
20 | 1.048.576 | 185.915 | 83.597 | 102.318 | 24.489 | 68.186 | 24.697 | 68.543 |
21 | 2.097.152 | 351.741 | 157.857 | 193.884 | 46.345 | 129.562 | 46.364 | 129.470 |
22 | 4.194.304 | 667.292 | 299.586 | 367.706 | 87.825 | 245.499 | 87.735 | 246.233 |
23 | 8.388.608 | 1.268.034 | 569.168 | 698.866 | 166.336 | 466.953 | 166.256 | 468.489 |
24 | 16.777.216 | 2.416.735 | 1.083.807 | 1.332.928 | 316.211 | 891.201 | 316.145 | 893.178 |
25 | 33.554.432 | 4.614.793 | 2.069.548 | 2.545.245 | 603.058 | 1.703.437 | 601.963 | 1.706.335 |
26 | 67.108.864 | 8.834.619 | 3.961.604 | 4.873.015 | 1.151.200 | 3.265.175 | 1.152.010 | 3.266.234 |
27 | 134.217.728 | 16.941.471 | 7.593.510 | 9.347.961 | 2.203.063 | 6.264.821 | 2.206.405 | 6.267.182 |
28 | 268.435.456 | 32.538.800 | 14.580.691 | 17.958.109 | 4.226.762 | 12.037.462 | 4.228.751 | 12.045.825 |
29 | 536.870.912 | 62.595.875 | 28.042.338 | 34.553.537 | 8.121.776 | 23.171.974 | 8.123.826 | 23.178.299 |
30 | 1.073.741.824 | 120.593.705 | 54.003.995 | 66.589.710 | 15.624.981 | 44.668.814 | 15.630.824 | 44.669.086 |
31 | 2.147.483.648 | 232.648.762 | 104.158.980 | 128.489.782 | 30.110.506 | 86.215.848 | 30.114.165 | 86.208.243 |
32 | 4.294.967.296 | 449.406.122 | 201.156.075 | 248.250.047 | 58.098.936 | 166.609.614 | 58.102.842 | 166.594.730 |
33 | 8.589.934.592 | 869.120.377 | 388.918.493 | 480.201.884 | 112.242.521 | 322.319.173 | 112.243.557 | 322.315.126 |
34 | 17.179.869.184 | 1.682.750.920 | 752.847.976 | 929.902.944 | 217.104.692 | 624.268.864 | 217.096.849 | 624.280.515 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
4 | 16 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
5 | 32 | 4 | 3 | 1 | 0 | 1 | 0 | 3 |
6 | 64 | 8 | 4 | 4 | 0 | 4 | 0 | 4 |
7 | 128 | 8 | 4 | 4 | 0 | 4 | 0 | 4 |
8 | 256 | 21 | 10 | 11 | 3 | 4 | 9 | 5 |
9 | 512 | 77 | 32 | 45 | 19 | 12 | 30 | 16 |
10 | 1.024 | 232 | 105 | 127 | 66 | 38 | 82 | 46 |
11 | 2.048 | 588 | 285 | 303 | 178 | 105 | 185 | 120 |
12 | 4.096 | 1.362 | 667 | 695 | 402 | 267 | 413 | 280 |
13 | 8.192 | 3.033 | 1.497 | 1.536 | 885 | 639 | 889 | 620 |
14 | 16.384 | 6.538 | 3.263 | 3.275 | 1.846 | 1.412 | 1.869 | 1.411 |
15 | 32.768 | 13.937 | 6.887 | 7.050 | 3.907 | 3.072 | 3.909 | 3.049 |
16 | 65.536 | 29.317 | 14.582 | 14.735 | 8.020 | 6.739 | 8.031 | 6.527 |
17 | 131.072 | 60.914 | 30.388 | 30.526 | 16.509 | 13.992 | 16.597 | 13.816 |
18 | 262.144 | 125.863 | 62.882 | 62.981 | 33.923 | 29.121 | 33.911 | 28.908 |
19 | 524.288 | 259.019 | 129.206 | 129.813 | 69.170 | 60.281 | 69.243 | 60.325 |
20 | 1.048.576 | 530.376 | 264.604 | 265.772 | 140.911 | 124.155 | 141.116 | 124.194 |
21 | 2.097.152 | 1.081.703 | 539.289 | 542.414 | 286.694 | 254.593 | 286.150 | 254.266 |
22 | 4.194.304 | 2.201.388 | 1.097.617 | 1.103.771 | 580.727 | 520.582 | 580.577 | 519.502 |
23 | 8.388.608 | 4.472.002 | 2.230.760 | 2.241.242 | 1.174.995 | 1.061.383 | 1.175.006 | 1.060.618 |
24 | 16.777.216 | 9.069.026 | 4.525.022 | 4.544.004 | 2.375.521 | 2.159.304 | 2.377.384 | 2.156.817 |
25 | 33.554.432 | 18.368.570 | 9.166.047 | 9.202.523 | 4.797.016 | 4.384.822 | 4.803.139 | 4.383.593 |
26 | 67.108.864 | 37.150.682 | 18.540.671 | 18.610.011 | 9.683.455 | 8.890.246 | 9.688.350 | 8.888.631 |
27 | 134.217.728 | 75.066.083 | 37.457.911 | 37.608.172 | 19.531.030 | 18.002.708 | 19.533.931 | 17.998.414 |
28 | 268.435.456 | 151.547.779 | 75.630.640 | 75.917.139 | 39.350.669 | 36.423.702 | 39.359.426 | 36.413.982 |
29 | 536.870.912 | 305.709.614 | 152.580.032 | 153.129.582 | 79.240.668 | 73.608.641 | 79.254.322 | 73.605.983 |
30 | 1.073.741.824 | 616.268.400 | 307.608.614 | 308.659.786 | 159.480.008 | 148.647.309 | 159.501.573 | 148.639.510 |
31 | 2.147.483.648 | 1.241.541.396 | 619.770.431 | 621.770.965 | 320.825.191 | 299.933.616 | 320.862.134 | 299.920.455 |
32 | 4.294.967.296 | 2.499.840.818 | 1.247.982.203 | 1.251.858.615 | 645.149.205 | 604.771.956 | 645.156.529 | 604.763.128 |
33 | 8.589.934.592 | 5.031.013.293 | 2.511.747.568 | 2.519.265.725 | 1.296.805.749 | 1.218.697.044 | 1.296.773.688 | 1.218.736.812 |
34 | 17.179.869.184 | 10.120.565.116 | 5.052.998.144 | 5.067.566.972 | 2.605.710.601 | 2.454.587.333 | 2.605.680.022 | 2.454.587.160 |