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-64x+101
f(0)=101
f(1)=19
f(2)=23
f(3)=41
f(4)=139
f(5)=97
f(6)=13
f(7)=149
f(8)=347
f(9)=197
f(10)=439
f(11)=241
f(12)=523
f(13)=281
f(14)=599
f(15)=317
f(16)=29
f(17)=349
f(18)=727
f(19)=1
f(20)=1
f(21)=401
f(22)=823
f(23)=421
f(24)=859
f(25)=1
f(26)=887
f(27)=449
f(28)=907
f(29)=457
f(30)=919
f(31)=461
f(32)=71
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)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
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)=83
f(66)=233
f(67)=151
f(68)=373
f(69)=223
f(70)=521
f(71)=1
f(72)=677
f(73)=379
f(74)=1
f(75)=463
f(76)=1013
f(77)=1
f(78)=1193
f(79)=643
f(80)=1381
f(81)=739
f(82)=1
f(83)=839
f(84)=137
f(85)=1
f(86)=1993
f(87)=1051
f(88)=2213
f(89)=1163
f(90)=2441
f(91)=1279
f(92)=2677
f(93)=1399
f(94)=127
f(95)=1523
f(96)=167
f(97)=1
f(98)=3433
f(99)=1783
b) Substitution of the polynom
The polynom f(x)=x^2-64x+101 could be written as f(y)= y^2-923 with x=y+32
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-32
f'(x)>2x-65 with x > 30
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 | 11 | 6 | 5 | 1.100000 | 0.600000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 55 | 27 | 28 | 0.550000 | 0.270000 | 0.550000 | 5.000000 | 4.500000 | 5.600000 |
3 | 1.000 | 758 | 225 | 533 | 0.758000 | 0.225000 | 0.758000 | 13.781818 | 8.333333 | 19.035715 |
4 | 10.000 | 7.689 | 1.611 | 6.078 | 0.768900 | 0.161100 | 0.768900 | 10.143800 | 7.160000 | 11.403378 |
5 | 100.000 | 75.472 | 12.381 | 63.091 | 0.754720 | 0.123810 | 0.754720 | 9.815580 | 7.685288 | 10.380224 |
6 | 1.000.000 | 743.930 | 100.821 | 643.109 | 0.743930 | 0.100821 | 0.743930 | 9.857033 | 8.143204 | 10.193356 |
7 | 10.000.000 | 7.362.693 | 853.719 | 6.508.974 | 0.736269 | 0.085372 | 0.736269 | 9.897024 | 8.467670 | 10.121105 |
8 | 100.000.000 | 73.071.516 | 7.388.012 | 65.683.504 | 0.730715 | 0.073880 | 0.730715 | 9.924564 | 8.653915 | 10.091223 |
9 | 1.000.000.000 | 726.351.243 | 65.180.024 | 661.171.219 | 0.726351 | 0.065180 | 0.726351 | 9.940278 | 8.822404 | 10.066016 |
10 | 10.000.000.000 | 7.228.882.913 | 583.332.297 | 6.645.550.616 | 0.722888 | 0.058333 | 0.722888 | 9.952324 | 8.949556 | 10.051180 |
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 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 16 | 8 | 8 | 1.000000 | 0.500000 | 0.500000 | 1.777778 | 1.600000 | 2.000000 |
5 | 32 | 29 | 14 | 15 | 0.906250 | 0.437500 | 0.468750 | 1.812500 | 1.750000 | 1.875000 |
6 | 64 | 29 | 14 | 15 | 0.453125 | 0.218750 | 0.234375 | 1.000000 | 1.000000 | 1.000000 |
7 | 128 | 75 | 35 | 40 | 0.585938 | 0.273438 | 0.312500 | 2.586207 | 2.500000 | 2.666667 |
8 | 256 | 178 | 66 | 112 | 0.695312 | 0.257812 | 0.437500 | 2.373333 | 1.885714 | 2.800000 |
9 | 512 | 377 | 130 | 247 | 0.736328 | 0.253906 | 0.482422 | 2.117978 | 1.969697 | 2.205357 |
10 | 1.024 | 777 | 231 | 546 | 0.758789 | 0.225586 | 0.533203 | 2.061008 | 1.776923 | 2.210526 |
11 | 2.048 | 1.559 | 413 | 1.146 | 0.761230 | 0.201660 | 0.559570 | 2.006435 | 1.787879 | 2.098901 |
12 | 4.096 | 3.159 | 741 | 2.418 | 0.771240 | 0.180908 | 0.590332 | 2.026299 | 1.794189 | 2.109948 |
13 | 8.192 | 6.304 | 1.352 | 4.952 | 0.769531 | 0.165039 | 0.604492 | 1.995568 | 1.824561 | 2.047974 |
14 | 16.384 | 12.543 | 2.463 | 10.080 | 0.765564 | 0.150330 | 0.615234 | 1.989689 | 1.821746 | 2.035541 |
15 | 32.768 | 24.938 | 4.524 | 20.414 | 0.761047 | 0.138062 | 0.622986 | 1.988201 | 1.836784 | 2.025198 |
16 | 65.536 | 49.629 | 8.446 | 41.183 | 0.757278 | 0.128876 | 0.628403 | 1.990095 | 1.866932 | 2.017390 |
17 | 131.072 | 98.764 | 15.757 | 83.007 | 0.753510 | 0.120216 | 0.633293 | 1.990046 | 1.865617 | 2.015565 |
18 | 262.144 | 196.591 | 29.548 | 167.043 | 0.749935 | 0.112717 | 0.637218 | 1.990513 | 1.875230 | 2.012397 |
19 | 524.288 | 391.400 | 55.605 | 335.795 | 0.746536 | 0.106058 | 0.640478 | 1.990935 | 1.881853 | 2.010231 |
20 | 1.048.576 | 779.871 | 105.421 | 674.450 | 0.743743 | 0.100537 | 0.643206 | 1.992517 | 1.895891 | 2.008517 |
21 | 2.097.152 | 1.554.486 | 200.126 | 1.354.360 | 0.741237 | 0.095428 | 0.645809 | 1.993260 | 1.898350 | 2.008096 |
22 | 4.194.304 | 3.099.006 | 380.344 | 2.718.662 | 0.738861 | 0.090681 | 0.648180 | 1.993589 | 1.900523 | 2.007341 |
23 | 8.388.608 | 6.180.451 | 724.783 | 5.455.668 | 0.736767 | 0.086401 | 0.650366 | 1.994333 | 1.905599 | 2.006747 |
24 | 16.777.216 | 12.329.062 | 1.383.752 | 10.945.310 | 0.734869 | 0.082478 | 0.652391 | 1.994848 | 1.909195 | 2.006227 |
25 | 33.554.432 | 24.601.338 | 2.647.161 | 21.954.177 | 0.733177 | 0.078892 | 0.654285 | 1.995394 | 1.913031 | 2.005807 |
26 | 67.108.864 | 49.095.512 | 5.075.677 | 44.019.835 | 0.731580 | 0.075633 | 0.655947 | 1.995644 | 1.917404 | 2.005078 |
27 | 134.217.728 | 97.991.144 | 9.748.940 | 88.242.204 | 0.730091 | 0.072635 | 0.657456 | 1.995929 | 1.920717 | 2.004601 |
28 | 268.435.456 | 195.611.999 | 18.758.982 | 176.853.017 | 0.728711 | 0.069883 | 0.658829 | 1.996221 | 1.924207 | 2.004177 |
29 | 536.870.912 | 390.536.215 | 36.141.715 | 354.394.500 | 0.727430 | 0.067319 | 0.660111 | 1.996484 | 1.926635 | 2.003893 |
30 | 1.073.741.824 | 779.791.288 | 69.732.561 | 710.058.727 | 0.726237 | 0.064944 | 0.661294 | 1.996719 | 1.929420 | 2.003583 |
31 | 2.147.483.648 | 1.557.180.985 | 134.724.373 | 1.422.456.612 | 0.725119 | 0.062736 | 0.662383 | 1.996920 | 1.932015 | 2.003294 |
32 | 4.294.967.296 | 3.109.876.409 | 260.583.635 | 2.849.292.774 | 0.724075 | 0.060672 | 0.663403 | 1.997120 | 1.934198 | 2.003079 |
33 | 8.589.934.592 | 6.211.342.690 | 504.587.336 | 5.706.755.354 | 0.723095 | 0.058742 | 0.664354 | 1.997296 | 1.936374 | 2.002867 |
34 | 17.179.869.184 | 12.406.909.155 | 977.992.345 | 11.428.916.810 | 0.722177 | 0.056927 | 0.665251 | 1.997460 | 1.938202 | 2.002700 |
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 | 2 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 0 | 2 | 1 | 2 |
4 | 16 | 8 | 4 | 4 | 0 | 3 | 1 | 4 |
5 | 32 | 14 | 9 | 5 | 0 | 5 | 1 | 8 |
6 | 64 | 14 | 9 | 5 | 0 | 5 | 1 | 8 |
7 | 128 | 35 | 18 | 17 | 9 | 5 | 13 | 8 |
8 | 256 | 66 | 28 | 38 | 25 | 5 | 28 | 8 |
9 | 512 | 130 | 48 | 82 | 56 | 5 | 61 | 8 |
10 | 1.024 | 231 | 83 | 148 | 109 | 5 | 109 | 8 |
11 | 2.048 | 413 | 146 | 267 | 202 | 5 | 198 | 8 |
12 | 4.096 | 741 | 255 | 486 | 368 | 5 | 360 | 8 |
13 | 8.192 | 1.352 | 458 | 894 | 673 | 5 | 666 | 8 |
14 | 16.384 | 2.463 | 821 | 1.642 | 1.246 | 5 | 1.204 | 8 |
15 | 32.768 | 4.524 | 1.493 | 3.031 | 2.277 | 5 | 2.234 | 8 |
16 | 65.536 | 8.446 | 2.781 | 5.665 | 4.214 | 5 | 4.219 | 8 |
17 | 131.072 | 15.757 | 5.187 | 10.570 | 7.861 | 5 | 7.883 | 8 |
18 | 262.144 | 29.548 | 9.789 | 19.759 | 14.794 | 5 | 14.741 | 8 |
19 | 524.288 | 55.605 | 18.446 | 37.159 | 27.820 | 5 | 27.772 | 8 |
20 | 1.048.576 | 105.421 | 35.050 | 70.371 | 52.803 | 5 | 52.605 | 8 |
21 | 2.097.152 | 200.126 | 66.717 | 133.409 | 100.122 | 5 | 99.991 | 8 |
22 | 4.194.304 | 380.344 | 126.742 | 253.602 | 190.176 | 5 | 190.155 | 8 |
23 | 8.388.608 | 724.783 | 241.663 | 483.120 | 362.218 | 5 | 362.552 | 8 |
24 | 16.777.216 | 1.383.752 | 461.442 | 922.310 | 691.897 | 5 | 691.842 | 8 |
25 | 33.554.432 | 2.647.161 | 882.448 | 1.764.713 | 1.324.049 | 5 | 1.323.099 | 8 |
26 | 67.108.864 | 5.075.677 | 1.692.444 | 3.383.233 | 2.538.196 | 5 | 2.537.468 | 8 |
27 | 134.217.728 | 9.748.940 | 3.249.908 | 6.499.032 | 4.873.983 | 5 | 4.874.944 | 8 |
28 | 268.435.456 | 18.758.982 | 6.255.082 | 12.503.900 | 9.377.958 | 5 | 9.381.011 | 8 |
29 | 536.870.912 | 36.141.715 | 12.046.957 | 24.094.758 | 18.069.368 | 5 | 18.072.334 | 8 |
30 | 1.073.741.824 | 69.732.561 | 23.242.376 | 46.490.185 | 34.864.229 | 5 | 34.868.319 | 8 |
31 | 2.147.483.648 | 134.724.373 | 44.906.862 | 89.817.511 | 67.362.555 | 5 | 67.361.805 | 8 |
32 | 4.294.967.296 | 260.583.635 | 86.857.679 | 173.725.956 | 130.294.201 | 5 | 130.289.421 | 8 |
33 | 8.589.934.592 | 504.587.336 | 168.186.879 | 336.400.457 | 252.297.983 | 5 | 252.289.340 | 8 |
34 | 17.179.869.184 | 977.992.345 | 325.990.209 | 652.002.136 | 489.002.719 | 5 | 488.989.613 | 8 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 4 | 2 | 2 | 2 | 1 | 1 | 0 |
4 | 16 | 8 | 3 | 5 | 4 | 1 | 3 | 0 |
5 | 32 | 15 | 6 | 9 | 7 | 1 | 6 | 1 |
6 | 64 | 15 | 6 | 9 | 7 | 1 | 6 | 1 |
7 | 128 | 40 | 23 | 17 | 7 | 14 | 7 | 12 |
8 | 256 | 112 | 65 | 47 | 15 | 40 | 17 | 40 |
9 | 512 | 247 | 140 | 107 | 40 | 93 | 32 | 82 |
10 | 1.024 | 546 | 311 | 235 | 87 | 194 | 88 | 177 |
11 | 2.048 | 1.146 | 642 | 504 | 183 | 384 | 197 | 382 |
12 | 4.096 | 2.418 | 1.324 | 1.094 | 423 | 793 | 410 | 792 |
13 | 8.192 | 4.952 | 2.695 | 2.257 | 888 | 1.570 | 880 | 1.614 |
14 | 16.384 | 10.080 | 5.437 | 4.643 | 1.861 | 3.150 | 1.891 | 3.178 |
15 | 32.768 | 20.414 | 10.992 | 9.422 | 3.878 | 6.299 | 3.898 | 6.339 |
16 | 65.536 | 41.183 | 21.994 | 19.189 | 7.999 | 12.435 | 8.157 | 12.592 |
17 | 131.072 | 83.007 | 44.079 | 38.928 | 16.572 | 24.771 | 16.694 | 24.970 |
18 | 262.144 | 167.043 | 88.470 | 78.573 | 34.090 | 49.567 | 34.147 | 49.239 |
19 | 524.288 | 335.795 | 177.364 | 158.431 | 69.555 | 98.516 | 69.557 | 98.167 |
20 | 1.048.576 | 674.450 | 355.183 | 319.267 | 140.842 | 195.950 | 142.011 | 195.647 |
21 | 2.097.152 | 1.354.360 | 710.830 | 643.530 | 286.802 | 390.116 | 288.007 | 389.435 |
22 | 4.194.304 | 2.718.662 | 1.423.054 | 1.295.608 | 581.689 | 777.138 | 582.981 | 776.854 |
23 | 8.388.608 | 5.455.668 | 2.850.508 | 2.605.160 | 1.177.707 | 1.549.850 | 1.178.451 | 1.549.660 |
24 | 16.777.216 | 10.945.310 | 5.705.442 | 5.239.868 | 2.382.310 | 3.090.305 | 2.382.635 | 3.090.060 |
25 | 33.554.432 | 21.954.177 | 11.424.366 | 10.529.811 | 4.813.327 | 6.162.441 | 4.812.440 | 6.165.969 |
26 | 67.108.864 | 44.019.835 | 22.871.695 | 21.148.140 | 9.710.699 | 12.297.932 | 9.710.968 | 12.300.236 |
27 | 134.217.728 | 88.242.204 | 45.773.767 | 42.468.437 | 19.574.657 | 24.543.550 | 19.577.899 | 24.546.098 |
28 | 268.435.456 | 176.853.017 | 91.617.371 | 85.235.646 | 39.432.860 | 48.989.720 | 39.438.953 | 48.991.484 |
29 | 536.870.912 | 354.394.500 | 183.342.847 | 171.051.653 | 79.396.486 | 97.798.978 | 79.401.894 | 97.797.142 |
30 | 1.073.741.824 | 710.058.727 | 366.866.079 | 343.192.648 | 159.773.627 | 195.258.511 | 159.783.036 | 195.243.553 |
31 | 2.147.483.648 | 1.422.456.612 | 734.076.304 | 688.380.308 | 321.365.128 | 389.844.554 | 321.386.250 | 389.860.680 |
32 | 4.294.967.296 | 2.849.292.774 | 1.468.836.625 | 1.380.456.149 | 646.122.059 | 778.510.542 | 646.134.333 | 778.525.840 |
33 | 8.589.934.592 | 5.706.755.354 | 2.938.797.749 | 2.767.957.605 | 1.298.547.678 | 1.554.802.065 | 1.298.580.943 | 1.554.824.668 |
34 | 17.179.869.184 | 11.428.916.810 | 5.879.960.358 | 5.548.956.452 | 2.608.989.624 | 3.105.454.668 | 2.609.039.774 | 3.105.432.744 |