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+19
f(0)=19
f(1)=5
f(2)=23
f(3)=7
f(4)=1
f(5)=11
f(6)=1
f(7)=17
f(8)=83
f(9)=1
f(10)=1
f(11)=1
f(12)=163
f(13)=47
f(14)=43
f(15)=61
f(16)=1
f(17)=1
f(18)=1
f(19)=1
f(20)=419
f(21)=1
f(22)=503
f(23)=137
f(24)=1
f(25)=1
f(26)=139
f(27)=1
f(28)=73
f(29)=1
f(30)=919
f(31)=1
f(32)=149
f(33)=277
f(34)=1
f(35)=311
f(36)=263
f(37)=347
f(38)=1
f(39)=1
f(40)=1619
f(41)=1
f(42)=1783
f(43)=467
f(44)=1
f(45)=1
f(46)=1
f(47)=557
f(48)=101
f(49)=1
f(50)=229
f(51)=131
f(52)=389
f(53)=1
f(54)=587
f(55)=761
f(56)=631
f(57)=1
f(58)=199
f(59)=1
f(60)=1
f(61)=1
f(62)=3863
f(63)=997
f(64)=823
f(65)=1061
f(66)=1
f(67)=1
f(68)=4643
f(69)=239
f(70)=4919
f(71)=1
f(72)=1
f(73)=191
f(74)=157
f(75)=1
f(76)=1
f(77)=1487
f(78)=359
f(79)=313
f(80)=1
f(81)=1
f(82)=613
f(83)=1
f(84)=283
f(85)=1811
f(86)=1483
f(87)=271
f(88)=1109
f(89)=397
f(90)=353
f(91)=1
f(92)=499
f(93)=197
f(94)=1
f(95)=1
f(96)=1847
f(97)=2357
f(98)=9623
f(99)=491
b) Substitution of the polynom
The polynom f(x)=x^2+19 could be written as f(y)= y^2+19 with x=y+0
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+0
f'(x)>2x-1 with x > 4
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 | 7 | 7 | 0 | 0.700000 | 0.700000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 61 | 31 | 30 | 0.610000 | 0.310000 | 0.610000 | 8.714286 | 4.428571 | inf |
3 | 1.000 | 629 | 175 | 454 | 0.629000 | 0.175000 | 0.629000 | 10.311476 | 5.645161 | 15.133333 |
4 | 10.000 | 6.497 | 1.255 | 5.242 | 0.649700 | 0.125500 | 0.649700 | 10.329094 | 7.171429 | 11.546255 |
5 | 100.000 | 66.028 | 9.388 | 56.640 | 0.660280 | 0.093880 | 0.660280 | 10.162845 | 7.480478 | 10.805037 |
6 | 1.000.000 | 666.113 | 76.277 | 589.836 | 0.666113 | 0.076277 | 0.666113 | 10.088342 | 8.124947 | 10.413772 |
7 | 10.000.000 | 6.699.263 | 641.433 | 6.057.830 | 0.669926 | 0.064143 | 0.669926 | 10.057247 | 8.409258 | 10.270363 |
8 | 100.000.000 | 67.276.803 | 5.544.360 | 61.732.443 | 0.672768 | 0.055444 | 0.672768 | 10.042418 | 8.643708 | 10.190521 |
9 | 1.000.000.000 | 675.003.138 | 48.786.087 | 626.217.051 | 0.675003 | 0.048786 | 0.675003 | 10.033223 | 8.799228 | 10.144051 |
10 | 10.000.000.000 | 6.767.832.235 | 435.760.770 | 6.332.071.465 | 0.676783 | 0.043576 | 0.676783 | 10.026371 | 8.932071 | 10.111625 |
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 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.750000 | 1.750000 | -nan |
4 | 16 | 11 | 10 | 1 | 0.687500 | 0.625000 | 0.062500 | 1.571429 | 1.428571 | inf |
5 | 32 | 18 | 14 | 4 | 0.562500 | 0.437500 | 0.125000 | 1.636364 | 1.400000 | 4.000000 |
6 | 64 | 37 | 24 | 13 | 0.578125 | 0.375000 | 0.203125 | 2.055556 | 1.714286 | 3.250000 |
7 | 128 | 78 | 35 | 43 | 0.609375 | 0.273438 | 0.335938 | 2.108108 | 1.458333 | 3.307692 |
8 | 256 | 160 | 61 | 99 | 0.625000 | 0.238281 | 0.386719 | 2.051282 | 1.742857 | 2.302325 |
9 | 512 | 316 | 107 | 209 | 0.617188 | 0.208984 | 0.408203 | 1.975000 | 1.754098 | 2.111111 |
10 | 1.024 | 646 | 179 | 467 | 0.630859 | 0.174805 | 0.456055 | 2.044304 | 1.672897 | 2.234450 |
11 | 2.048 | 1.308 | 321 | 987 | 0.638672 | 0.156738 | 0.481934 | 2.024768 | 1.793296 | 2.113490 |
12 | 4.096 | 2.634 | 585 | 2.049 | 0.643066 | 0.142822 | 0.500244 | 2.013762 | 1.822430 | 2.075988 |
13 | 8.192 | 5.314 | 1.065 | 4.249 | 0.648682 | 0.130005 | 0.518677 | 2.017464 | 1.820513 | 2.073694 |
14 | 16.384 | 10.725 | 1.923 | 8.802 | 0.654602 | 0.117371 | 0.537231 | 2.018254 | 1.805634 | 2.071546 |
15 | 32.768 | 21.517 | 3.522 | 17.995 | 0.656647 | 0.107483 | 0.549164 | 2.006247 | 1.831513 | 2.044422 |
16 | 65.536 | 43.197 | 6.413 | 36.784 | 0.659134 | 0.097855 | 0.561279 | 2.007576 | 1.820840 | 2.044123 |
17 | 131.072 | 86.709 | 11.996 | 74.713 | 0.661537 | 0.091522 | 0.570015 | 2.007292 | 1.870575 | 2.031128 |
18 | 262.144 | 173.863 | 22.450 | 151.413 | 0.663235 | 0.085640 | 0.577595 | 2.005132 | 1.871457 | 2.026595 |
19 | 524.288 | 348.652 | 42.157 | 306.495 | 0.665001 | 0.080408 | 0.584593 | 2.005326 | 1.877817 | 2.024232 |
20 | 1.048.576 | 698.530 | 79.678 | 618.852 | 0.666170 | 0.075987 | 0.590183 | 2.003516 | 1.890030 | 2.019126 |
21 | 2.097.152 | 1.399.841 | 150.903 | 1.248.938 | 0.667496 | 0.071956 | 0.595540 | 2.003981 | 1.893911 | 2.018153 |
22 | 4.194.304 | 2.804.419 | 286.205 | 2.518.214 | 0.668626 | 0.068237 | 0.600389 | 2.003384 | 1.896616 | 2.016284 |
23 | 8.388.608 | 5.617.943 | 544.556 | 5.073.387 | 0.669711 | 0.064916 | 0.604795 | 2.003247 | 1.902678 | 2.014677 |
24 | 16.777.216 | 11.251.334 | 1.039.023 | 10.212.311 | 0.670632 | 0.061931 | 0.608701 | 2.002750 | 1.908019 | 2.012918 |
25 | 33.554.432 | 22.532.649 | 1.988.271 | 20.544.378 | 0.671525 | 0.059255 | 0.612270 | 2.002665 | 1.913597 | 2.011727 |
26 | 67.108.864 | 45.118.458 | 3.810.638 | 41.307.820 | 0.672317 | 0.056783 | 0.615534 | 2.002359 | 1.916559 | 2.010663 |
27 | 134.217.728 | 90.339.197 | 7.314.956 | 83.024.241 | 0.673079 | 0.054501 | 0.618579 | 2.002267 | 1.919615 | 2.009892 |
28 | 268.435.456 | 180.869.871 | 14.061.194 | 166.808.677 | 0.673793 | 0.052382 | 0.621411 | 2.002120 | 1.922253 | 2.009156 |
29 | 536.870.912 | 362.090.846 | 27.069.406 | 335.021.440 | 0.674447 | 0.050421 | 0.624026 | 2.001941 | 1.925114 | 2.008417 |
30 | 1.073.741.824 | 724.845.378 | 52.189.035 | 672.656.343 | 0.675065 | 0.048605 | 0.626460 | 2.001833 | 1.927971 | 2.007801 |
31 | 2.147.483.648 | 1.450.921.648 | 100.765.387 | 1.350.156.261 | 0.675638 | 0.046923 | 0.628716 | 2.001698 | 1.930777 | 2.007201 |
32 | 4.294.967.296 | 2.904.143.862 | 194.788.640 | 2.709.355.222 | 0.676174 | 0.045353 | 0.630821 | 2.001586 | 1.933091 | 2.006697 |
33 | 8.589.934.592 | 5.812.616.475 | 376.968.233 | 5.435.648.242 | 0.676678 | 0.043885 | 0.632793 | 2.001491 | 1.935268 | 2.006252 |
34 | 17.179.869.184 | 11.633.399.706 | 730.297.062 | 10.903.102.644 | 0.677153 | 0.042509 | 0.634644 | 2.001405 | 1.937291 | 2.005852 |
35 | 34.359.738.368 | 23.282.309.727 | 1.416.203.341 | 21.866.106.386 | 0.677604 | 0.041217 | 0.636387 | 2.001333 | 1.939215 | 2.005494 |
36 | 68.719.476.736 | 46.593.812.355 | 2.748.862.995 | 43.844.949.360 | 0.678029 | 0.040001 | 0.638028 | 2.001254 | 1.941009 | 2.005156 |
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 | 1 | 2 | 0 | 1 | 1 | 1 |
2 | 4 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
3 | 8 | 7 | 2 | 5 | 1 | 3 | 1 | 2 |
4 | 16 | 10 | 4 | 6 | 1 | 4 | 2 | 3 |
5 | 32 | 14 | 5 | 9 | 2 | 5 | 2 | 5 |
6 | 64 | 24 | 8 | 16 | 3 | 8 | 5 | 8 |
7 | 128 | 35 | 9 | 26 | 4 | 11 | 7 | 13 |
8 | 256 | 61 | 18 | 43 | 10 | 17 | 9 | 25 |
9 | 512 | 107 | 35 | 72 | 15 | 38 | 17 | 37 |
10 | 1.024 | 179 | 63 | 116 | 25 | 68 | 23 | 63 |
11 | 2.048 | 321 | 111 | 210 | 44 | 121 | 42 | 114 |
12 | 4.096 | 585 | 195 | 390 | 87 | 221 | 74 | 203 |
13 | 8.192 | 1.065 | 357 | 708 | 154 | 399 | 134 | 378 |
14 | 16.384 | 1.923 | 645 | 1.278 | 247 | 716 | 258 | 702 |
15 | 32.768 | 3.522 | 1.183 | 2.339 | 461 | 1.297 | 469 | 1.295 |
16 | 65.536 | 6.413 | 2.176 | 4.237 | 847 | 2.363 | 832 | 2.371 |
17 | 131.072 | 11.996 | 4.053 | 7.943 | 1.569 | 4.455 | 1.547 | 4.425 |
18 | 262.144 | 22.450 | 7.501 | 14.949 | 2.934 | 8.327 | 2.888 | 8.301 |
19 | 524.288 | 42.157 | 14.050 | 28.107 | 5.492 | 15.692 | 5.390 | 15.583 |
20 | 1.048.576 | 79.678 | 26.519 | 53.159 | 10.295 | 29.702 | 10.143 | 29.538 |
21 | 2.097.152 | 150.903 | 50.245 | 100.658 | 19.446 | 56.287 | 19.306 | 55.864 |
22 | 4.194.304 | 286.205 | 95.357 | 190.848 | 36.684 | 106.664 | 36.562 | 106.295 |
23 | 8.388.608 | 544.556 | 181.245 | 363.311 | 69.583 | 202.568 | 69.720 | 202.685 |
24 | 16.777.216 | 1.039.023 | 345.899 | 693.124 | 132.933 | 386.523 | 133.109 | 386.458 |
25 | 33.554.432 | 1.988.271 | 662.567 | 1.325.704 | 253.907 | 740.083 | 254.230 | 740.051 |
26 | 67.108.864 | 3.810.638 | 1.270.492 | 2.540.146 | 486.464 | 1.419.390 | 486.317 | 1.418.467 |
27 | 134.217.728 | 7.314.956 | 2.439.032 | 4.875.924 | 932.685 | 2.725.750 | 931.803 | 2.724.718 |
28 | 268.435.456 | 14.061.194 | 4.688.612 | 9.372.582 | 1.790.965 | 5.240.553 | 1.790.556 | 5.239.120 |
29 | 536.870.912 | 27.069.406 | 9.024.776 | 18.044.630 | 3.445.395 | 10.089.873 | 3.445.102 | 10.089.036 |
30 | 1.073.741.824 | 52.189.035 | 17.398.034 | 34.791.001 | 6.640.297 | 19.455.621 | 6.638.549 | 19.454.568 |
31 | 2.147.483.648 | 100.765.387 | 33.589.375 | 67.176.012 | 12.813.119 | 37.574.289 | 12.810.571 | 37.567.408 |
32 | 4.294.967.296 | 194.788.640 | 64.937.069 | 129.851.571 | 24.756.907 | 72.644.000 | 24.750.827 | 72.636.906 |
33 | 8.589.934.592 | 376.968.233 | 125.669.788 | 251.298.445 | 47.889.915 | 140.600.240 | 47.879.898 | 140.598.180 |
34 | 17.179.869.184 | 730.297.062 | 243.449.532 | 486.847.530 | 92.716.404 | 272.446.536 | 92.712.172 | 272.421.950 |
35 | 34.359.738.368 | 1.416.203.341 | 472.083.254 | 944.120.087 | 179.710.039 | 528.417.769 | 179.699.888 | 528.375.645 |
36 | 68.719.476.736 | 2.748.862.995 | 916.295.521 | 1.832.567.474 | 348.651.117 | 1.025.775.499 | 348.662.004 | 1.025.774.375 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 32 | 4 | 3 | 1 | 1 | 2 | 1 | 0 |
6 | 64 | 13 | 7 | 6 | 1 | 4 | 4 | 4 |
7 | 128 | 43 | 25 | 18 | 7 | 11 | 14 | 11 |
8 | 256 | 99 | 53 | 46 | 22 | 24 | 29 | 24 |
9 | 512 | 209 | 109 | 100 | 48 | 56 | 55 | 50 |
10 | 1.024 | 467 | 244 | 223 | 111 | 120 | 121 | 115 |
11 | 2.048 | 987 | 516 | 471 | 252 | 243 | 257 | 235 |
12 | 4.096 | 2.049 | 1.078 | 971 | 525 | 513 | 511 | 500 |
13 | 8.192 | 4.249 | 2.207 | 2.042 | 1.105 | 1.061 | 1.064 | 1.019 |
14 | 16.384 | 8.802 | 4.528 | 4.274 | 2.262 | 2.189 | 2.230 | 2.121 |
15 | 32.768 | 17.995 | 9.271 | 8.724 | 4.600 | 4.417 | 4.541 | 4.437 |
16 | 65.536 | 36.784 | 18.957 | 17.827 | 9.319 | 9.039 | 9.273 | 9.153 |
17 | 131.072 | 74.713 | 38.421 | 36.292 | 18.855 | 18.473 | 18.856 | 18.529 |
18 | 262.144 | 151.413 | 77.340 | 74.073 | 38.119 | 37.459 | 38.406 | 37.429 |
19 | 524.288 | 306.495 | 156.400 | 150.095 | 77.454 | 75.809 | 77.843 | 75.389 |
20 | 1.048.576 | 618.852 | 315.687 | 303.165 | 156.505 | 152.862 | 156.637 | 152.848 |
21 | 2.097.152 | 1.248.938 | 636.385 | 612.553 | 315.676 | 309.070 | 315.538 | 308.654 |
22 | 4.194.304 | 2.518.214 | 1.282.219 | 1.235.995 | 635.583 | 623.577 | 635.584 | 623.470 |
23 | 8.388.608 | 5.073.387 | 2.582.660 | 2.490.727 | 1.279.377 | 1.256.788 | 1.279.712 | 1.257.510 |
24 | 16.777.216 | 10.212.311 | 5.192.921 | 5.019.390 | 2.574.782 | 2.531.473 | 2.574.022 | 2.532.034 |
25 | 33.554.432 | 20.544.378 | 10.436.633 | 10.107.745 | 5.176.198 | 5.095.017 | 5.176.889 | 5.096.274 |
26 | 67.108.864 | 41.307.820 | 20.970.079 | 20.337.741 | 10.402.987 | 10.249.344 | 10.402.398 | 10.253.091 |
27 | 134.217.728 | 83.024.241 | 42.112.313 | 40.911.928 | 20.899.432 | 20.612.111 | 20.903.227 | 20.609.471 |
28 | 268.435.456 | 166.808.677 | 84.562.887 | 82.245.790 | 41.977.918 | 41.429.709 | 41.979.104 | 41.421.946 |
29 | 536.870.912 | 335.021.440 | 169.725.023 | 165.296.417 | 84.278.511 | 83.230.559 | 84.290.476 | 83.221.894 |
30 | 1.073.741.824 | 672.656.343 | 340.598.908 | 332.057.435 | 169.174.500 | 167.157.920 | 169.188.080 | 167.135.843 |
31 | 2.147.483.648 | 1.350.156.261 | 683.319.079 | 666.837.182 | 339.476.078 | 335.601.512 | 339.507.578 | 335.571.093 |
32 | 4.294.967.296 | 2.709.355.222 | 1.370.589.280 | 1.338.765.942 | 681.097.587 | 673.595.131 | 681.126.806 | 673.535.698 |
33 | 8.589.934.592 | 5.435.648.242 | 2.748.593.585 | 2.687.054.657 | 1.366.163.636 | 1.351.675.446 | 1.366.189.751 | 1.351.619.409 |
34 | 17.179.869.184 | 10.903.102.644 | 5.511.139.385 | 5.391.963.259 | 2.739.764.911 | 2.711.772.591 | 2.739.810.262 | 2.711.754.880 |
35 | 34.359.738.368 | 21.866.106.386 | 11.048.434.385 | 10.817.672.001 | 5.493.633.816 | 5.439.387.336 | 5.493.695.294 | 5.439.389.940 |
36 | 68.719.476.736 | 43.844.949.360 | 22.146.120.793 | 21.698.828.567 | 11.013.686.771 | 10.908.719.235 | 11.013.824.123 | 10.908.719.231 |