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+104x-1
f(0)=1
f(1)=13
f(2)=211
f(3)=5
f(4)=431
f(5)=17
f(6)=659
f(7)=97
f(8)=179
f(9)=127
f(10)=67
f(11)=79
f(12)=107
f(13)=19
f(14)=1
f(15)=223
f(16)=101
f(17)=257
f(18)=439
f(19)=73
f(20)=37
f(21)=41
f(22)=163
f(23)=1
f(24)=83
f(25)=31
f(26)=109
f(27)=1
f(28)=739
f(29)=241
f(30)=4019
f(31)=523
f(32)=229
f(33)=113
f(34)=4691
f(35)=1
f(36)=5039
f(37)=1
f(38)=1
f(39)=1
f(40)=443
f(41)=743
f(42)=6131
f(43)=1
f(44)=383
f(45)=419
f(46)=6899
f(47)=887
f(48)=1459
f(49)=937
f(50)=7699
f(51)=1
f(52)=8111
f(53)=1
f(54)=449
f(55)=1093
f(56)=1
f(57)=1
f(58)=1879
f(59)=601
f(60)=9839
f(61)=1
f(62)=251
f(63)=263
f(64)=827
f(65)=1373
f(66)=863
f(67)=1
f(68)=2339
f(69)=373
f(70)=641
f(71)=1553
f(72)=12671
f(73)=1
f(74)=13171
f(75)=839
f(76)=13679
f(77)=1
f(78)=167
f(79)=139
f(80)=359
f(81)=1873
f(82)=151
f(83)=1
f(84)=15791
f(85)=1
f(86)=16339
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1109
f(92)=1
f(93)=1
f(94)=503
f(95)=1
f(96)=1
f(97)=2437
f(98)=1
f(99)=157
b) Substitution of the polynom
The polynom f(x)=x^2+104x-1 could be written as f(y)= y^2-2705 with x=y-52
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+52
f'(x)>2x+103
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 66 | 17 | 49 | 0.660000 | 0.170000 | 0.660000 | 6.600000 | 5.666667 | 7.000000 |
3 | 1.000 | 621 | 140 | 481 | 0.621000 | 0.140000 | 0.621000 | 9.409091 | 8.235294 | 9.816326 |
4 | 10.000 | 6.509 | 974 | 5.535 | 0.650900 | 0.097400 | 0.650900 | 10.481482 | 6.957143 | 11.507277 |
5 | 100.000 | 65.976 | 7.638 | 58.338 | 0.659760 | 0.076380 | 0.659760 | 10.136119 | 7.841889 | 10.539838 |
6 | 1.000.000 | 665.307 | 62.887 | 602.420 | 0.665307 | 0.062887 | 0.665307 | 10.084076 | 8.233438 | 10.326374 |
7 | 10.000.000 | 6.693.943 | 532.042 | 6.161.901 | 0.669394 | 0.053204 | 0.669394 | 10.061435 | 8.460286 | 10.228580 |
8 | 100.000.000 | 67.245.032 | 4.611.872 | 62.633.160 | 0.672450 | 0.046119 | 0.672450 | 10.045653 | 8.668248 | 10.164584 |
9 | 1.000.000.000 | 674.771.118 | 40.704.448 | 634.066.670 | 0.674771 | 0.040704 | 0.674771 | 10.034513 | 8.826015 | 10.123498 |
10 | 10.000.000.000 | 6.766.194.116 | 364.251.957 | 6.401.942.159 | 0.676619 | 0.036425 | 0.676619 | 10.027391 | 8.948702 | 10.096639 |
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 | 2 | 1 | 1 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 2.000000 | 2.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.500000 | 2.500000 |
4 | 16 | 14 | 3 | 11 | 0.875000 | 0.187500 | 0.687500 | 1.750000 | 1.000000 | 2.200000 |
5 | 32 | 25 | 4 | 21 | 0.781250 | 0.125000 | 0.656250 | 1.785714 | 1.333333 | 1.909091 |
6 | 64 | 47 | 11 | 36 | 0.734375 | 0.171875 | 0.562500 | 1.880000 | 2.750000 | 1.714286 |
7 | 128 | 81 | 23 | 58 | 0.632812 | 0.179688 | 0.453125 | 1.723404 | 2.090909 | 1.611111 |
8 | 256 | 160 | 42 | 118 | 0.625000 | 0.164062 | 0.460938 | 1.975309 | 1.826087 | 2.034483 |
9 | 512 | 316 | 83 | 233 | 0.617188 | 0.162109 | 0.455078 | 1.975000 | 1.976190 | 1.974576 |
10 | 1.024 | 636 | 146 | 490 | 0.621094 | 0.142578 | 0.478516 | 2.012658 | 1.759036 | 2.103004 |
11 | 2.048 | 1.305 | 244 | 1.061 | 0.637207 | 0.119141 | 0.518066 | 2.051887 | 1.671233 | 2.165306 |
12 | 4.096 | 2.640 | 441 | 2.199 | 0.644531 | 0.107666 | 0.536865 | 2.022989 | 1.807377 | 2.072573 |
13 | 8.192 | 5.330 | 812 | 4.518 | 0.650635 | 0.099121 | 0.551514 | 2.018939 | 1.841270 | 2.054570 |
14 | 16.384 | 10.671 | 1.508 | 9.163 | 0.651306 | 0.092041 | 0.559265 | 2.002064 | 1.857143 | 2.028110 |
15 | 32.768 | 21.497 | 2.782 | 18.715 | 0.656036 | 0.084900 | 0.571136 | 2.014525 | 1.844828 | 2.042453 |
16 | 65.536 | 43.201 | 5.197 | 38.004 | 0.659195 | 0.079300 | 0.579895 | 2.009629 | 1.868080 | 2.030671 |
17 | 131.072 | 86.524 | 9.804 | 76.720 | 0.660126 | 0.074799 | 0.585327 | 2.002824 | 1.886473 | 2.018735 |
18 | 262.144 | 173.441 | 18.475 | 154.966 | 0.661625 | 0.070477 | 0.591148 | 2.004542 | 1.884435 | 2.019891 |
19 | 524.288 | 347.951 | 34.643 | 313.308 | 0.663664 | 0.066076 | 0.597588 | 2.006164 | 1.875129 | 2.021785 |
20 | 1.048.576 | 697.711 | 65.741 | 631.970 | 0.665389 | 0.062696 | 0.602694 | 2.005199 | 1.897671 | 2.017089 |
21 | 2.097.152 | 1.398.355 | 124.748 | 1.273.607 | 0.666788 | 0.059484 | 0.607303 | 2.004204 | 1.897568 | 2.015297 |
22 | 4.194.304 | 2.801.489 | 237.082 | 2.564.407 | 0.667927 | 0.056525 | 0.611402 | 2.003417 | 1.900487 | 2.013499 |
23 | 8.388.608 | 5.612.778 | 451.776 | 5.161.002 | 0.669095 | 0.053856 | 0.615239 | 2.003498 | 1.905568 | 2.012552 |
24 | 16.777.216 | 11.243.550 | 862.489 | 10.381.061 | 0.670168 | 0.051408 | 0.618759 | 2.003206 | 1.909108 | 2.011443 |
25 | 33.554.432 | 22.518.787 | 1.651.451 | 20.867.336 | 0.671112 | 0.049217 | 0.621895 | 2.002818 | 1.914750 | 2.010135 |
26 | 67.108.864 | 45.096.233 | 3.167.379 | 41.928.854 | 0.671986 | 0.047198 | 0.624789 | 2.002605 | 1.917937 | 2.009306 |
27 | 134.217.728 | 90.298.716 | 6.084.933 | 84.213.783 | 0.672778 | 0.045336 | 0.627442 | 2.002356 | 1.921126 | 2.008492 |
28 | 268.435.456 | 180.796.239 | 11.712.381 | 169.083.858 | 0.673518 | 0.043632 | 0.629886 | 2.002202 | 1.924817 | 2.007793 |
29 | 536.870.912 | 361.954.976 | 22.567.327 | 339.387.649 | 0.674194 | 0.042035 | 0.632159 | 2.002005 | 1.926793 | 2.007215 |
30 | 1.073.741.824 | 724.595.678 | 43.548.789 | 681.046.889 | 0.674832 | 0.040558 | 0.634274 | 2.001894 | 1.929727 | 2.006693 |
31 | 2.147.483.648 | 1.450.465.366 | 84.132.450 | 1.366.332.916 | 0.675426 | 0.039177 | 0.636248 | 2.001758 | 1.931913 | 2.006224 |
32 | 4.294.967.296 | 2.903.334.518 | 162.721.924 | 2.740.612.594 | 0.675985 | 0.037887 | 0.638099 | 2.001657 | 1.934116 | 2.005816 |
33 | 8.589.934.592 | 5.811.165.339 | 315.069.799 | 5.496.095.540 | 0.676509 | 0.036679 | 0.639830 | 2.001549 | 1.936247 | 2.005426 |
34 | 17.179.869.184 | 11.630.818.946 | 610.733.367 | 11.020.085.579 | 0.677003 | 0.035549 | 0.641453 | 2.001461 | 1.938407 | 2.005075 |
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 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 1 | 2 | 0 | 2 | 0 | 1 |
4 | 16 | 3 | 1 | 2 | 0 | 2 | 0 | 1 |
5 | 32 | 4 | 1 | 3 | 0 | 3 | 0 | 1 |
6 | 64 | 11 | 2 | 9 | 0 | 7 | 0 | 4 |
7 | 128 | 23 | 5 | 18 | 0 | 14 | 0 | 9 |
8 | 256 | 42 | 14 | 28 | 0 | 22 | 0 | 20 |
9 | 512 | 83 | 31 | 52 | 0 | 43 | 0 | 40 |
10 | 1.024 | 146 | 47 | 99 | 0 | 73 | 0 | 73 |
11 | 2.048 | 244 | 86 | 158 | 0 | 120 | 0 | 124 |
12 | 4.096 | 441 | 149 | 292 | 0 | 211 | 0 | 230 |
13 | 8.192 | 812 | 279 | 533 | 0 | 392 | 0 | 420 |
14 | 16.384 | 1.508 | 512 | 996 | 0 | 737 | 0 | 771 |
15 | 32.768 | 2.782 | 956 | 1.826 | 0 | 1.379 | 0 | 1.403 |
16 | 65.536 | 5.197 | 1.775 | 3.422 | 0 | 2.569 | 0 | 2.628 |
17 | 131.072 | 9.804 | 3.280 | 6.524 | 0 | 4.853 | 0 | 4.951 |
18 | 262.144 | 18.475 | 6.163 | 12.312 | 0 | 9.208 | 0 | 9.267 |
19 | 524.288 | 34.643 | 11.558 | 23.085 | 0 | 17.306 | 0 | 17.337 |
20 | 1.048.576 | 65.741 | 21.918 | 43.823 | 0 | 32.820 | 0 | 32.921 |
21 | 2.097.152 | 124.748 | 41.639 | 83.109 | 0 | 62.281 | 0 | 62.467 |
22 | 4.194.304 | 237.082 | 78.867 | 158.215 | 0 | 118.496 | 0 | 118.586 |
23 | 8.388.608 | 451.776 | 150.481 | 301.295 | 0 | 225.768 | 0 | 226.008 |
24 | 16.777.216 | 862.489 | 287.850 | 574.639 | 0 | 430.748 | 0 | 431.741 |
25 | 33.554.432 | 1.651.451 | 551.294 | 1.100.157 | 0 | 824.733 | 0 | 826.718 |
26 | 67.108.864 | 3.167.379 | 1.056.715 | 2.110.664 | 0 | 1.582.807 | 0 | 1.584.572 |
27 | 134.217.728 | 6.084.933 | 2.029.119 | 4.055.814 | 0 | 3.041.067 | 0 | 3.043.866 |
28 | 268.435.456 | 11.712.381 | 3.904.200 | 7.808.181 | 0 | 5.855.412 | 0 | 5.856.969 |
29 | 536.870.912 | 22.567.327 | 7.523.084 | 15.044.243 | 0 | 11.284.039 | 0 | 11.283.288 |
30 | 1.073.741.824 | 43.548.789 | 14.516.421 | 29.032.368 | 0 | 21.774.771 | 0 | 21.774.018 |
31 | 2.147.483.648 | 84.132.450 | 28.038.065 | 56.094.385 | 0 | 42.067.201 | 0 | 42.065.249 |
32 | 4.294.967.296 | 162.721.924 | 54.238.870 | 108.483.054 | 0 | 81.359.413 | 0 | 81.362.511 |
33 | 8.589.934.592 | 315.069.799 | 105.023.369 | 210.046.430 | 0 | 157.527.581 | 0 | 157.542.218 |
34 | 17.179.869.184 | 610.733.367 | 203.579.344 | 407.154.023 | 0 | 305.357.262 | 0 | 305.376.105 |
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 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 5 | 2 | 3 | 2 | 1 | 2 | 0 |
4 | 16 | 11 | 6 | 5 | 2 | 3 | 3 | 3 |
5 | 32 | 21 | 14 | 7 | 5 | 7 | 5 | 4 |
6 | 64 | 36 | 19 | 17 | 9 | 12 | 6 | 9 |
7 | 128 | 58 | 28 | 30 | 12 | 16 | 13 | 17 |
8 | 256 | 118 | 60 | 58 | 26 | 36 | 22 | 34 |
9 | 512 | 233 | 114 | 119 | 49 | 64 | 50 | 70 |
10 | 1.024 | 490 | 251 | 239 | 98 | 129 | 108 | 155 |
11 | 2.048 | 1.061 | 527 | 534 | 214 | 295 | 239 | 313 |
12 | 4.096 | 2.199 | 1.083 | 1.116 | 467 | 599 | 496 | 637 |
13 | 8.192 | 4.518 | 2.302 | 2.216 | 1.005 | 1.255 | 1.023 | 1.235 |
14 | 16.384 | 9.163 | 4.608 | 4.555 | 2.094 | 2.503 | 2.060 | 2.506 |
15 | 32.768 | 18.715 | 9.475 | 9.240 | 4.355 | 5.044 | 4.269 | 5.047 |
16 | 65.536 | 38.004 | 19.204 | 18.800 | 8.811 | 10.110 | 8.881 | 10.202 |
17 | 131.072 | 76.720 | 38.977 | 37.743 | 17.975 | 20.395 | 17.995 | 20.355 |
18 | 262.144 | 154.966 | 78.532 | 76.434 | 36.456 | 40.954 | 36.400 | 41.156 |
19 | 524.288 | 313.308 | 158.782 | 154.526 | 73.945 | 82.575 | 73.929 | 82.859 |
20 | 1.048.576 | 631.970 | 320.061 | 311.909 | 149.890 | 165.826 | 149.648 | 166.606 |
21 | 2.097.152 | 1.273.607 | 644.876 | 628.731 | 302.905 | 333.526 | 302.721 | 334.455 |
22 | 4.194.304 | 2.564.407 | 1.297.344 | 1.267.063 | 612.107 | 671.001 | 611.399 | 669.900 |
23 | 8.388.608 | 5.161.002 | 2.608.063 | 2.552.939 | 1.234.969 | 1.347.360 | 1.233.893 | 1.344.780 |
24 | 16.777.216 | 10.381.061 | 5.243.230 | 5.137.831 | 2.489.837 | 2.701.532 | 2.488.692 | 2.701.000 |
25 | 33.554.432 | 20.867.336 | 10.531.710 | 10.335.626 | 5.015.761 | 5.419.571 | 5.014.024 | 5.417.980 |
26 | 67.108.864 | 41.928.854 | 21.152.295 | 20.776.559 | 10.095.124 | 10.871.476 | 10.094.891 | 10.867.363 |
27 | 134.217.728 | 84.213.783 | 42.466.961 | 41.746.822 | 20.313.867 | 21.798.135 | 20.312.558 | 21.789.223 |
28 | 268.435.456 | 169.083.858 | 85.230.698 | 83.853.160 | 40.853.600 | 43.693.414 | 40.848.792 | 43.688.052 |
29 | 536.870.912 | 339.387.649 | 171.018.150 | 168.369.499 | 82.115.013 | 87.583.235 | 82.116.657 | 87.572.744 |
30 | 1.073.741.824 | 681.046.889 | 343.081.068 | 337.965.821 | 164.997.246 | 175.540.020 | 165.003.145 | 175.506.478 |
31 | 2.147.483.648 | 1.366.332.916 | 688.109.891 | 678.223.025 | 331.406.035 | 351.752.488 | 331.449.356 | 351.725.037 |
32 | 4.294.967.296 | 2.740.612.594 | 1.379.886.903 | 1.360.725.691 | 665.532.203 | 704.774.627 | 665.553.435 | 704.752.329 |
33 | 8.589.934.592 | 5.496.095.540 | 2.766.596.860 | 2.729.498.680 | 1.336.099.582 | 1.411.969.903 | 1.336.093.606 | 1.411.932.449 |
34 | 17.179.869.184 | 11.020.085.579 | 5.545.994.958 | 5.474.090.621 | 2.681.640.104 | 2.828.457.687 | 2.681.601.696 | 2.828.386.092 |