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-46x+59
f(0)=59
f(1)=7
f(2)=29
f(3)=5
f(4)=109
f(5)=73
f(6)=181
f(7)=107
f(8)=1
f(9)=137
f(10)=43
f(11)=163
f(12)=349
f(13)=37
f(14)=389
f(15)=1
f(16)=421
f(17)=31
f(18)=89
f(19)=227
f(20)=461
f(21)=233
f(22)=67
f(23)=47
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)=53
f(48)=1
f(49)=103
f(50)=1
f(51)=157
f(52)=1
f(53)=1
f(54)=491
f(55)=277
f(56)=619
f(57)=1
f(58)=151
f(59)=1
f(60)=1
f(61)=487
f(62)=1051
f(63)=113
f(64)=173
f(65)=647
f(66)=197
f(67)=733
f(68)=311
f(69)=823
f(70)=1
f(71)=131
f(72)=1931
f(73)=1
f(74)=2131
f(75)=1117
f(76)=2339
f(77)=1223
f(78)=1
f(79)=1
f(80)=397
f(81)=1447
f(82)=3011
f(83)=313
f(84)=3251
f(85)=241
f(86)=3499
f(87)=1
f(88)=751
f(89)=1
f(90)=4019
f(91)=1
f(92)=613
f(93)=443
f(94)=653
f(95)=2357
f(96)=1
f(97)=2503
f(98)=1031
f(99)=379
b) Substitution of the polynom
The polynom f(x)=x^2-46x+59 could be written as f(y)= y^2-470 with x=y+23
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-23
f'(x)>2x-47 with x > 22
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 | 56 | 18 | 38 | 0.560000 | 0.180000 | 0.560000 | 5.600000 | 4.500000 | 6.333333 |
3 | 1.000 | 670 | 134 | 536 | 0.670000 | 0.134000 | 0.670000 | 11.964286 | 7.444445 | 14.105263 |
4 | 10.000 | 7.016 | 908 | 6.108 | 0.701600 | 0.090800 | 0.701600 | 10.471642 | 6.776119 | 11.395522 |
5 | 100.000 | 70.323 | 7.222 | 63.101 | 0.703230 | 0.072220 | 0.703230 | 10.023232 | 7.953744 | 10.330877 |
6 | 1.000.000 | 701.946 | 58.528 | 643.418 | 0.701946 | 0.058528 | 0.701946 | 9.981741 | 8.104126 | 10.196637 |
7 | 10.000.000 | 7.003.523 | 494.373 | 6.509.150 | 0.700352 | 0.049437 | 0.700352 | 9.977296 | 8.446777 | 10.116518 |
8 | 100.000.000 | 69.927.063 | 4.282.532 | 65.644.531 | 0.699271 | 0.042825 | 0.699271 | 9.984555 | 8.662553 | 10.084962 |
9 | 1.000.000.000 | 698.469.637 | 37.788.244 | 660.681.393 | 0.698470 | 0.037788 | 0.698470 | 9.988545 | 8.823809 | 10.064530 |
10 | 10.000.000.000 | 6.978.596.796 | 338.156.813 | 6.640.439.983 | 0.697860 | 0.033816 | 0.697860 | 9.991267 | 8.948730 | 10.050896 |
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 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 15 | 7 | 8 | 0.937500 | 0.437500 | 0.500000 | 1.875000 | 1.750000 | 2.000000 |
5 | 32 | 21 | 8 | 13 | 0.656250 | 0.250000 | 0.406250 | 1.400000 | 1.142857 | 1.625000 |
6 | 64 | 30 | 11 | 19 | 0.468750 | 0.171875 | 0.296875 | 1.428571 | 1.375000 | 1.461538 |
7 | 128 | 74 | 22 | 52 | 0.578125 | 0.171875 | 0.406250 | 2.466667 | 2.000000 | 2.736842 |
8 | 256 | 160 | 45 | 115 | 0.625000 | 0.175781 | 0.449219 | 2.162162 | 2.045455 | 2.211539 |
9 | 512 | 335 | 76 | 259 | 0.654297 | 0.148438 | 0.505859 | 2.093750 | 1.688889 | 2.252174 |
10 | 1.024 | 687 | 135 | 552 | 0.670898 | 0.131836 | 0.539062 | 2.050746 | 1.776316 | 2.131274 |
11 | 2.048 | 1.415 | 236 | 1.179 | 0.690918 | 0.115234 | 0.575684 | 2.059680 | 1.748148 | 2.135870 |
12 | 4.096 | 2.858 | 418 | 2.440 | 0.697754 | 0.102051 | 0.595703 | 2.019788 | 1.771186 | 2.069551 |
13 | 8.192 | 5.723 | 762 | 4.961 | 0.698608 | 0.093018 | 0.605591 | 2.002449 | 1.822966 | 2.033197 |
14 | 16.384 | 11.501 | 1.415 | 10.086 | 0.701965 | 0.086365 | 0.615601 | 2.009610 | 1.856955 | 2.033058 |
15 | 32.768 | 23.059 | 2.640 | 20.419 | 0.703705 | 0.080566 | 0.623138 | 2.004956 | 1.865724 | 2.024489 |
16 | 65.536 | 46.052 | 4.890 | 41.162 | 0.702698 | 0.074615 | 0.628082 | 1.997138 | 1.852273 | 2.015867 |
17 | 131.072 | 92.136 | 9.225 | 82.911 | 0.702942 | 0.070381 | 0.632561 | 2.000695 | 1.886503 | 2.014261 |
18 | 262.144 | 184.199 | 17.201 | 166.998 | 0.702663 | 0.065617 | 0.637047 | 1.999208 | 1.864607 | 2.014184 |
19 | 524.288 | 368.242 | 32.353 | 335.889 | 0.702366 | 0.061708 | 0.640657 | 1.999153 | 1.880879 | 2.011335 |
20 | 1.048.576 | 736.143 | 61.144 | 674.999 | 0.702041 | 0.058311 | 0.643729 | 1.999074 | 1.889902 | 2.009589 |
21 | 2.097.152 | 1.471.082 | 115.834 | 1.355.248 | 0.701467 | 0.055234 | 0.646233 | 1.998364 | 1.894446 | 2.007778 |
22 | 4.194.304 | 2.939.944 | 220.420 | 2.719.524 | 0.700937 | 0.052552 | 0.648385 | 1.998491 | 1.902896 | 2.006661 |
23 | 8.388.608 | 5.875.428 | 419.863 | 5.455.565 | 0.700406 | 0.050052 | 0.650354 | 1.998483 | 1.904832 | 2.006073 |
24 | 16.777.216 | 11.744.984 | 802.269 | 10.942.715 | 0.700056 | 0.047819 | 0.652237 | 1.999001 | 1.910788 | 2.005790 |
25 | 33.554.432 | 23.478.412 | 1.535.168 | 21.943.244 | 0.699711 | 0.045752 | 0.653960 | 1.999016 | 1.913533 | 2.005283 |
26 | 67.108.864 | 46.936.125 | 2.941.910 | 43.994.215 | 0.699403 | 0.043838 | 0.655565 | 1.999118 | 1.916344 | 2.004909 |
27 | 134.217.728 | 93.835.784 | 5.652.870 | 88.182.914 | 0.699131 | 0.042117 | 0.657014 | 1.999223 | 1.921497 | 2.004421 |
28 | 268.435.456 | 187.607.899 | 10.877.083 | 176.730.816 | 0.698894 | 0.040520 | 0.658374 | 1.999322 | 1.924170 | 2.004139 |
29 | 536.870.912 | 375.094.363 | 20.955.934 | 354.138.429 | 0.698668 | 0.039033 | 0.659634 | 1.999353 | 1.926613 | 2.003829 |
30 | 1.073.741.824 | 749.950.725 | 40.429.088 | 709.521.637 | 0.698446 | 0.037653 | 0.660794 | 1.999365 | 1.929243 | 2.003515 |
31 | 2.147.483.648 | 1.499.479.567 | 78.107.619 | 1.421.371.948 | 0.698250 | 0.036372 | 0.661878 | 1.999437 | 1.931966 | 2.003282 |
32 | 4.294.967.296 | 2.998.175.182 | 151.068.569 | 2.847.106.613 | 0.698067 | 0.035173 | 0.662894 | 1.999477 | 1.934108 | 2.003069 |
33 | 8.589.934.592 | 5.994.881.673 | 292.507.523 | 5.702.374.150 | 0.697896 | 0.034052 | 0.663844 | 1.999510 | 1.936257 | 2.002867 |
34 | 17.179.869.184 | 11.986.957.175 | 566.945.971 | 11.420.011.204 | 0.697733 | 0.033001 | 0.664732 | 1.999532 | 1.938227 | 2.002676 |
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 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 2 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 3 | 0 |
4 | 16 | 7 | 4 | 3 | 0 | 1 | 6 | 0 |
5 | 32 | 8 | 4 | 4 | 0 | 1 | 7 | 0 |
6 | 64 | 11 | 6 | 5 | 0 | 4 | 7 | 0 |
7 | 128 | 22 | 10 | 12 | 0 | 15 | 7 | 0 |
8 | 256 | 45 | 17 | 28 | 0 | 38 | 7 | 0 |
9 | 512 | 76 | 27 | 49 | 0 | 69 | 7 | 0 |
10 | 1.024 | 135 | 48 | 87 | 0 | 128 | 7 | 0 |
11 | 2.048 | 236 | 83 | 153 | 0 | 229 | 7 | 0 |
12 | 4.096 | 418 | 149 | 269 | 0 | 411 | 7 | 0 |
13 | 8.192 | 762 | 263 | 499 | 0 | 755 | 7 | 0 |
14 | 16.384 | 1.415 | 480 | 935 | 0 | 1.408 | 7 | 0 |
15 | 32.768 | 2.640 | 880 | 1.760 | 0 | 2.633 | 7 | 0 |
16 | 65.536 | 4.890 | 1.631 | 3.259 | 0 | 4.883 | 7 | 0 |
17 | 131.072 | 9.225 | 3.067 | 6.158 | 0 | 9.218 | 7 | 0 |
18 | 262.144 | 17.201 | 5.707 | 11.494 | 0 | 17.194 | 7 | 0 |
19 | 524.288 | 32.353 | 10.714 | 21.639 | 0 | 32.346 | 7 | 0 |
20 | 1.048.576 | 61.144 | 20.191 | 40.953 | 0 | 61.137 | 7 | 0 |
21 | 2.097.152 | 115.834 | 38.400 | 77.434 | 0 | 115.827 | 7 | 0 |
22 | 4.194.304 | 220.420 | 73.225 | 147.195 | 0 | 220.413 | 7 | 0 |
23 | 8.388.608 | 419.863 | 139.897 | 279.966 | 0 | 419.856 | 7 | 0 |
24 | 16.777.216 | 802.269 | 267.790 | 534.479 | 0 | 802.262 | 7 | 0 |
25 | 33.554.432 | 1.535.168 | 512.318 | 1.022.850 | 0 | 1.535.161 | 7 | 0 |
26 | 67.108.864 | 2.941.910 | 981.686 | 1.960.224 | 0 | 2.941.903 | 7 | 0 |
27 | 134.217.728 | 5.652.870 | 1.884.400 | 3.768.470 | 0 | 5.652.863 | 7 | 0 |
28 | 268.435.456 | 10.877.083 | 3.625.822 | 7.251.261 | 0 | 10.877.076 | 7 | 0 |
29 | 536.870.912 | 20.955.934 | 6.983.925 | 13.972.009 | 0 | 20.955.927 | 7 | 0 |
30 | 1.073.741.824 | 40.429.088 | 13.475.169 | 26.953.919 | 0 | 40.429.081 | 7 | 0 |
31 | 2.147.483.648 | 78.107.619 | 26.036.328 | 52.071.291 | 0 | 78.107.612 | 7 | 0 |
32 | 4.294.967.296 | 151.068.569 | 50.358.325 | 100.710.244 | 0 | 151.068.562 | 7 | 0 |
33 | 8.589.934.592 | 292.507.523 | 97.498.209 | 195.009.314 | 0 | 292.507.516 | 7 | 0 |
34 | 17.179.869.184 | 566.945.971 | 188.983.139 | 377.962.832 | 0 | 566.945.964 | 7 | 0 |
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 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 2 | 0 | 1 |
4 | 16 | 8 | 5 | 3 | 2 | 4 | 1 | 1 |
5 | 32 | 13 | 6 | 7 | 4 | 6 | 1 | 2 |
6 | 64 | 19 | 11 | 8 | 4 | 6 | 4 | 5 |
7 | 128 | 52 | 28 | 24 | 9 | 10 | 15 | 18 |
8 | 256 | 115 | 59 | 56 | 23 | 23 | 35 | 34 |
9 | 512 | 259 | 130 | 129 | 50 | 47 | 88 | 74 |
10 | 1.024 | 552 | 294 | 258 | 108 | 116 | 173 | 155 |
11 | 2.048 | 1.179 | 618 | 561 | 244 | 239 | 346 | 350 |
12 | 4.096 | 2.440 | 1.274 | 1.166 | 517 | 486 | 720 | 717 |
13 | 8.192 | 4.961 | 2.566 | 2.395 | 1.052 | 1.012 | 1.435 | 1.462 |
14 | 16.384 | 10.086 | 5.308 | 4.778 | 2.221 | 2.060 | 2.892 | 2.913 |
15 | 32.768 | 20.419 | 10.671 | 9.748 | 4.630 | 4.209 | 5.774 | 5.806 |
16 | 65.536 | 41.162 | 21.428 | 19.734 | 9.318 | 8.711 | 11.593 | 11.540 |
17 | 131.072 | 82.911 | 43.018 | 39.893 | 19.058 | 17.696 | 23.130 | 23.027 |
18 | 262.144 | 166.998 | 86.446 | 80.552 | 38.752 | 36.206 | 46.035 | 46.005 |
19 | 524.288 | 335.889 | 173.377 | 162.512 | 78.361 | 73.546 | 91.833 | 92.149 |
20 | 1.048.576 | 674.999 | 347.896 | 327.103 | 157.326 | 149.520 | 183.822 | 184.331 |
21 | 2.097.152 | 1.355.248 | 697.693 | 657.555 | 316.693 | 302.802 | 366.906 | 368.847 |
22 | 4.194.304 | 2.719.524 | 1.397.369 | 1.322.155 | 638.401 | 610.402 | 733.982 | 736.739 |
23 | 8.388.608 | 5.455.565 | 2.799.762 | 2.655.803 | 1.284.338 | 1.230.813 | 1.466.473 | 1.473.941 |
24 | 16.777.216 | 10.942.715 | 5.608.555 | 5.334.160 | 2.583.477 | 2.481.319 | 2.933.094 | 2.944.825 |
25 | 33.554.432 | 21.943.244 | 11.230.717 | 10.712.527 | 5.193.649 | 5.000.027 | 5.863.601 | 5.885.967 |
26 | 67.108.864 | 43.994.215 | 22.493.758 | 21.500.457 | 10.437.492 | 10.069.878 | 11.723.546 | 11.763.299 |
27 | 134.217.728 | 88.182.914 | 45.047.847 | 43.135.067 | 20.970.711 | 20.261.995 | 23.435.894 | 23.514.314 |
28 | 268.435.456 | 176.730.816 | 90.206.146 | 86.524.670 | 42.122.905 | 40.753.917 | 46.850.653 | 47.003.341 |
29 | 536.870.912 | 354.138.429 | 180.632.009 | 173.506.420 | 84.565.657 | 81.942.980 | 93.667.990 | 93.961.802 |
30 | 1.073.741.824 | 709.521.637 | 361.622.026 | 347.899.611 | 169.731.672 | 164.658.214 | 187.281.701 | 187.850.050 |
31 | 2.147.483.648 | 1.421.371.948 | 723.939.149 | 697.432.799 | 340.566.962 | 330.784.346 | 374.481.336 | 375.539.304 |
32 | 4.294.967.296 | 2.847.106.613 | 1.449.198.794 | 1.397.907.819 | 683.168.470 | 664.333.272 | 748.761.936 | 750.842.935 |
33 | 8.589.934.592 | 5.702.374.150 | 2.900.806.091 | 2.801.568.059 | 1.370.146.411 | 1.333.789.633 | 1.497.235.584 | 1.501.202.522 |
34 | 17.179.869.184 | 11.420.011.204 | 5.806.146.080 | 5.613.865.124 | 2.747.431.277 | 2.677.188.041 | 2.993.828.123 | 3.001.563.763 |