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-100x-37
f(0)=37
f(1)=17
f(2)=233
f(3)=41
f(4)=421
f(5)=1
f(6)=601
f(7)=43
f(8)=773
f(9)=107
f(10)=937
f(11)=127
f(12)=1093
f(13)=73
f(14)=1
f(15)=1
f(16)=1381
f(17)=181
f(18)=89
f(19)=197
f(20)=1637
f(21)=53
f(22)=1753
f(23)=113
f(24)=1861
f(25)=239
f(26)=1
f(27)=251
f(28)=2053
f(29)=131
f(30)=2137
f(31)=1
f(32)=2213
f(33)=281
f(34)=2281
f(35)=1
f(36)=2341
f(37)=1
f(38)=2393
f(39)=151
f(40)=2437
f(41)=307
f(42)=2473
f(43)=311
f(44)=61
f(45)=157
f(46)=2521
f(47)=79
f(48)=149
f(49)=317
f(50)=59
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)=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-100x-37 could be written as f(y)= y^2-2537 with x=y+50
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-50
f'(x)>2x-101 with x > 50
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 | 6 | 4 | 1.000000 | 0.600000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 42 | 20 | 22 | 0.420000 | 0.200000 | 0.420000 | 4.200000 | 3.333333 | 5.500000 |
3 | 1.000 | 654 | 215 | 439 | 0.654000 | 0.215000 | 0.654000 | 15.571428 | 10.750000 | 19.954546 |
4 | 10.000 | 6.945 | 1.591 | 5.354 | 0.694500 | 0.159100 | 0.694500 | 10.619267 | 7.400000 | 12.195900 |
5 | 100.000 | 69.965 | 12.552 | 57.413 | 0.699650 | 0.125520 | 0.699650 | 10.074154 | 7.889378 | 10.723385 |
6 | 1.000.000 | 699.930 | 102.189 | 597.741 | 0.699930 | 0.102189 | 0.699930 | 10.004002 | 8.141253 | 10.411248 |
7 | 10.000.000 | 6.988.149 | 864.829 | 6.123.320 | 0.698815 | 0.086483 | 0.698815 | 9.984069 | 8.463035 | 10.244102 |
8 | 100.000.000 | 69.805.158 | 7.493.488 | 62.311.670 | 0.698052 | 0.074935 | 0.698052 | 9.989078 | 8.664705 | 10.176126 |
9 | 1.000.000.000 | 697.396.568 | 66.123.347 | 631.273.221 | 0.697397 | 0.066123 | 0.697397 | 9.990616 | 8.824108 | 10.130898 |
10 | 10.000.000.000 | 6.969.030.347 | 591.781.555 | 6.377.248.792 | 0.696903 | 0.059178 | 0.696903 | 9.992923 | 8.949661 | 10.102201 |
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 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 1.600000 | 1.666667 | 1.500000 |
4 | 16 | 14 | 8 | 6 | 0.875000 | 0.500000 | 0.375000 | 1.750000 | 1.600000 | 2.000000 |
5 | 32 | 28 | 14 | 14 | 0.875000 | 0.437500 | 0.437500 | 2.000000 | 1.750000 | 2.333333 |
6 | 64 | 42 | 20 | 22 | 0.656250 | 0.312500 | 0.343750 | 1.500000 | 1.428571 | 1.571429 |
7 | 128 | 54 | 30 | 24 | 0.421875 | 0.234375 | 0.187500 | 1.285714 | 1.500000 | 1.090909 |
8 | 256 | 143 | 65 | 78 | 0.558594 | 0.253906 | 0.304688 | 2.648148 | 2.166667 | 3.250000 |
9 | 512 | 319 | 120 | 199 | 0.623047 | 0.234375 | 0.388672 | 2.230769 | 1.846154 | 2.551282 |
10 | 1.024 | 675 | 220 | 455 | 0.659180 | 0.214844 | 0.444336 | 2.115988 | 1.833333 | 2.286432 |
11 | 2.048 | 1.394 | 409 | 985 | 0.680664 | 0.199707 | 0.480957 | 2.065185 | 1.859091 | 2.164835 |
12 | 4.096 | 2.810 | 747 | 2.063 | 0.686035 | 0.182373 | 0.503662 | 2.015782 | 1.826406 | 2.094416 |
13 | 8.192 | 5.677 | 1.337 | 4.340 | 0.692993 | 0.163208 | 0.529785 | 2.020285 | 1.789826 | 2.103732 |
14 | 16.384 | 11.421 | 2.451 | 8.970 | 0.697083 | 0.149597 | 0.547485 | 2.011802 | 1.833209 | 2.066820 |
15 | 32.768 | 22.896 | 4.563 | 18.333 | 0.698730 | 0.139252 | 0.559479 | 2.004728 | 1.861689 | 2.043813 |
16 | 65.536 | 45.862 | 8.570 | 37.292 | 0.699799 | 0.130768 | 0.569031 | 2.003057 | 1.878150 | 2.034146 |
17 | 131.072 | 91.708 | 16.001 | 75.707 | 0.699677 | 0.122078 | 0.577599 | 1.999651 | 1.867095 | 2.030114 |
18 | 262.144 | 183.537 | 29.982 | 153.555 | 0.700138 | 0.114372 | 0.585766 | 2.001319 | 1.873758 | 2.028280 |
19 | 524.288 | 367.062 | 56.545 | 310.517 | 0.700115 | 0.107851 | 0.592264 | 1.999935 | 1.885965 | 2.022187 |
20 | 1.048.576 | 733.904 | 106.827 | 627.077 | 0.699905 | 0.101878 | 0.598027 | 1.999401 | 1.889239 | 2.019461 |
21 | 2.097.152 | 1.467.071 | 202.448 | 1.264.623 | 0.699554 | 0.096535 | 0.603019 | 1.998996 | 1.895101 | 2.016695 |
22 | 4.194.304 | 2.932.749 | 384.719 | 2.548.030 | 0.699222 | 0.091724 | 0.607498 | 1.999050 | 1.900335 | 2.014853 |
23 | 8.388.608 | 5.862.900 | 733.929 | 5.128.971 | 0.698912 | 0.087491 | 0.611421 | 1.999114 | 1.907701 | 2.012916 |
24 | 16.777.216 | 11.721.662 | 1.401.905 | 10.319.757 | 0.698665 | 0.083560 | 0.615105 | 1.999294 | 1.910137 | 2.012052 |
25 | 33.554.432 | 23.435.594 | 2.682.980 | 20.752.614 | 0.698435 | 0.079959 | 0.618476 | 1.999341 | 1.913810 | 2.010960 |
26 | 67.108.864 | 46.854.035 | 5.146.748 | 41.707.287 | 0.698180 | 0.076693 | 0.621487 | 1.999268 | 1.918295 | 2.009737 |
27 | 134.217.728 | 93.677.421 | 9.890.611 | 83.786.810 | 0.697951 | 0.073691 | 0.624260 | 1.999346 | 1.921721 | 2.008925 |
28 | 268.435.456 | 187.297.614 | 19.031.354 | 168.266.260 | 0.697738 | 0.070897 | 0.626841 | 1.999389 | 1.924184 | 2.008267 |
29 | 536.870.912 | 374.490.233 | 36.670.298 | 337.819.935 | 0.697542 | 0.068304 | 0.629239 | 1.999439 | 1.926836 | 2.007651 |
30 | 1.073.741.824 | 748.804.178 | 70.743.768 | 678.060.410 | 0.697378 | 0.065885 | 0.631493 | 1.999529 | 1.929185 | 2.007165 |
31 | 2.147.483.648 | 1.497.256.621 | 136.678.680 | 1.360.577.941 | 0.697214 | 0.063646 | 0.633568 | 1.999530 | 1.932024 | 2.006573 |
32 | 4.294.967.296 | 2.993.891.130 | 264.360.853 | 2.729.530.277 | 0.697070 | 0.061551 | 0.635518 | 1.999585 | 1.934178 | 2.006155 |
33 | 8.589.934.592 | 5.986.603.650 | 511.879.838 | 5.474.723.812 | 0.696932 | 0.059591 | 0.637342 | 1.999606 | 1.936292 | 2.005738 |
34 | 17.179.869.184 | 11.970.973.497 | 992.196.804 | 10.978.776.693 | 0.696802 | 0.057753 | 0.639049 | 1.999627 | 1.938339 | 2.005357 |
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 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
3 | 8 | 5 | 3 | 2 | 2 | 0 | 3 | 0 |
4 | 16 | 8 | 6 | 2 | 3 | 0 | 5 | 0 |
5 | 32 | 14 | 10 | 4 | 5 | 0 | 9 | 0 |
6 | 64 | 20 | 15 | 5 | 9 | 0 | 11 | 0 |
7 | 128 | 30 | 19 | 11 | 9 | 5 | 11 | 5 |
8 | 256 | 65 | 36 | 29 | 9 | 20 | 11 | 25 |
9 | 512 | 120 | 50 | 70 | 9 | 48 | 11 | 52 |
10 | 1.024 | 220 | 85 | 135 | 9 | 94 | 11 | 106 |
11 | 2.048 | 409 | 150 | 259 | 9 | 198 | 11 | 191 |
12 | 4.096 | 747 | 270 | 477 | 9 | 370 | 11 | 357 |
13 | 8.192 | 1.337 | 466 | 871 | 9 | 661 | 11 | 656 |
14 | 16.384 | 2.451 | 836 | 1.615 | 9 | 1.208 | 11 | 1.223 |
15 | 32.768 | 4.563 | 1.528 | 3.035 | 9 | 2.289 | 11 | 2.254 |
16 | 65.536 | 8.570 | 2.881 | 5.689 | 9 | 4.266 | 11 | 4.284 |
17 | 131.072 | 16.001 | 5.375 | 10.626 | 9 | 7.968 | 11 | 8.013 |
18 | 262.144 | 29.982 | 10.041 | 19.941 | 9 | 15.009 | 11 | 14.953 |
19 | 524.288 | 56.545 | 18.887 | 37.658 | 9 | 28.270 | 11 | 28.255 |
20 | 1.048.576 | 106.827 | 35.654 | 71.173 | 9 | 53.342 | 11 | 53.465 |
21 | 2.097.152 | 202.448 | 67.318 | 135.130 | 9 | 101.078 | 11 | 101.350 |
22 | 4.194.304 | 384.719 | 128.147 | 256.572 | 9 | 192.265 | 11 | 192.434 |
23 | 8.388.608 | 733.929 | 244.629 | 489.300 | 9 | 367.017 | 11 | 366.892 |
24 | 16.777.216 | 1.401.905 | 467.048 | 934.857 | 9 | 700.819 | 11 | 701.066 |
25 | 33.554.432 | 2.682.980 | 894.159 | 1.788.821 | 9 | 1.341.305 | 11 | 1.341.655 |
26 | 67.108.864 | 5.146.748 | 1.715.057 | 3.431.691 | 9 | 2.573.001 | 11 | 2.573.727 |
27 | 134.217.728 | 9.890.611 | 3.295.504 | 6.595.107 | 9 | 4.945.321 | 11 | 4.945.270 |
28 | 268.435.456 | 19.031.354 | 6.344.230 | 12.687.124 | 9 | 9.514.632 | 11 | 9.516.702 |
29 | 536.870.912 | 36.670.298 | 12.224.668 | 24.445.630 | 9 | 18.332.610 | 11 | 18.337.668 |
30 | 1.073.741.824 | 70.743.768 | 23.583.009 | 47.160.759 | 9 | 35.371.560 | 11 | 35.372.188 |
31 | 2.147.483.648 | 136.678.680 | 45.562.205 | 91.116.475 | 9 | 68.336.880 | 11 | 68.341.780 |
32 | 4.294.967.296 | 264.360.853 | 88.119.355 | 176.241.498 | 9 | 132.179.716 | 11 | 132.181.117 |
33 | 8.589.934.592 | 511.879.838 | 170.625.234 | 341.254.604 | 9 | 255.940.543 | 11 | 255.939.275 |
34 | 17.179.869.184 | 992.196.804 | 330.729.387 | 661.467.417 | 9 | 496.096.259 | 11 | 496.100.525 |
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 | 1 | 0 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 2 | 0 | 0 | 0 |
3 | 8 | 3 | 1 | 2 | 2 | 1 | 0 | 0 |
4 | 16 | 6 | 3 | 3 | 3 | 2 | 0 | 1 |
5 | 32 | 14 | 4 | 10 | 5 | 4 | 3 | 2 |
6 | 64 | 22 | 7 | 15 | 6 | 6 | 6 | 4 |
7 | 128 | 24 | 9 | 15 | 7 | 6 | 7 | 4 |
8 | 256 | 78 | 41 | 37 | 17 | 24 | 18 | 19 |
9 | 512 | 199 | 107 | 92 | 46 | 53 | 45 | 55 |
10 | 1.024 | 455 | 246 | 209 | 99 | 123 | 107 | 126 |
11 | 2.048 | 985 | 524 | 461 | 221 | 257 | 226 | 281 |
12 | 4.096 | 2.063 | 1.090 | 973 | 483 | 543 | 475 | 562 |
13 | 8.192 | 4.340 | 2.264 | 2.076 | 1.025 | 1.113 | 1.007 | 1.195 |
14 | 16.384 | 8.970 | 4.668 | 4.302 | 2.103 | 2.386 | 2.095 | 2.386 |
15 | 32.768 | 18.333 | 9.476 | 8.857 | 4.331 | 4.836 | 4.313 | 4.853 |
16 | 65.536 | 37.292 | 19.234 | 18.058 | 8.870 | 9.762 | 8.850 | 9.810 |
17 | 131.072 | 75.707 | 38.837 | 36.870 | 18.078 | 19.959 | 17.887 | 19.783 |
18 | 262.144 | 153.555 | 78.771 | 74.784 | 36.747 | 40.116 | 36.745 | 39.947 |
19 | 524.288 | 310.517 | 159.223 | 151.294 | 74.599 | 80.793 | 74.577 | 80.548 |
20 | 1.048.576 | 627.077 | 321.037 | 306.040 | 151.064 | 162.604 | 150.858 | 162.551 |
21 | 2.097.152 | 1.264.623 | 646.468 | 618.155 | 304.986 | 327.423 | 304.726 | 327.488 |
22 | 4.194.304 | 2.548.030 | 1.301.774 | 1.246.256 | 616.100 | 657.945 | 615.699 | 658.286 |
23 | 8.388.608 | 5.128.971 | 2.617.158 | 2.511.813 | 1.241.587 | 1.322.150 | 1.241.696 | 1.323.538 |
24 | 16.777.216 | 10.319.757 | 5.261.169 | 5.058.588 | 2.502.245 | 2.655.113 | 2.502.720 | 2.659.679 |
25 | 33.554.432 | 20.752.614 | 10.568.155 | 10.184.459 | 5.040.183 | 5.334.290 | 5.041.126 | 5.337.015 |
26 | 67.108.864 | 41.707.287 | 21.222.129 | 20.485.158 | 10.145.452 | 10.704.199 | 10.146.622 | 10.711.014 |
27 | 134.217.728 | 83.786.810 | 42.606.251 | 41.180.559 | 20.407.788 | 21.480.228 | 20.408.718 | 21.490.076 |
28 | 268.435.456 | 168.266.260 | 85.501.896 | 82.764.364 | 41.031.198 | 43.096.813 | 41.032.293 | 43.105.956 |
29 | 536.870.912 | 337.819.935 | 171.547.343 | 166.272.592 | 82.476.286 | 86.442.452 | 82.453.385 | 86.447.812 |
30 | 1.073.741.824 | 678.060.410 | 344.106.917 | 333.953.493 | 165.685.285 | 173.338.248 | 165.681.849 | 173.355.028 |
31 | 2.147.483.648 | 1.360.577.941 | 690.063.960 | 670.513.981 | 332.760.521 | 347.520.295 | 332.751.931 | 347.545.194 |
32 | 4.294.967.296 | 2.729.530.277 | 1.383.632.615 | 1.345.897.662 | 668.150.724 | 696.604.676 | 668.116.170 | 696.658.707 |
33 | 8.589.934.592 | 5.474.723.812 | 2.773.804.893 | 2.700.918.919 | 1.341.173.592 | 1.396.198.034 | 1.341.129.442 | 1.396.222.744 |
34 | 17.179.869.184 | 10.978.776.693 | 5.559.907.735 | 5.418.868.958 | 2.691.466.224 | 2.797.947.511 | 2.691.417.701 | 2.797.945.257 |