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+78x-137
f(0)=137
f(1)=29
f(2)=23
f(3)=53
f(4)=191
f(5)=139
f(6)=367
f(7)=229
f(8)=19
f(9)=17
f(10)=743
f(11)=421
f(12)=41
f(13)=523
f(14)=1151
f(15)=37
f(16)=1367
f(17)=739
f(18)=43
f(19)=853
f(20)=1823
f(21)=971
f(22)=2063
f(23)=1093
f(24)=2311
f(25)=1
f(26)=151
f(27)=71
f(28)=149
f(29)=1483
f(30)=107
f(31)=1621
f(32)=199
f(33)=1
f(34)=3671
f(35)=83
f(36)=3967
f(37)=1
f(38)=4271
f(39)=2213
f(40)=4583
f(41)=2371
f(42)=4903
f(43)=1
f(44)=5231
f(45)=2699
f(46)=293
f(47)=1
f(48)=257
f(49)=179
f(50)=6263
f(51)=3221
f(52)=1
f(53)=1
f(54)=6991
f(55)=97
f(56)=1
f(57)=3779
f(58)=337
f(59)=1
f(60)=479
f(61)=1
f(62)=8543
f(63)=4373
f(64)=8951
f(65)=241
f(66)=1
f(67)=4789
f(68)=9791
f(69)=5003
f(70)=10223
f(71)=227
f(72)=10663
f(73)=5443
f(74)=271
f(75)=5669
f(76)=269
f(77)=347
f(78)=1
f(79)=6133
f(80)=12503
f(81)=277
f(82)=12983
f(83)=389
f(84)=709
f(85)=1
f(86)=13967
f(87)=7109
f(88)=499
f(89)=1
f(90)=14983
f(91)=7621
f(92)=419
f(93)=7883
f(94)=1
f(95)=281
f(96)=16567
f(97)=8419
f(98)=1
f(99)=8693
b) Substitution of the polynom
The polynom f(x)=x^2+78x-137 could be written as f(y)= y^2-1658 with x=y-39
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+39
f'(x)>2x+77
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 | 9 | 1 | 1.000000 | 0.900000 | 1.000000 | |||
2 | 100 | 83 | 56 | 27 | 0.830000 | 0.560000 | 0.830000 | 8.300000 | 6.222222 | 27.000000 |
3 | 1.000 | 766 | 368 | 398 | 0.766000 | 0.368000 | 0.766000 | 9.228915 | 6.571429 | 14.740741 |
4 | 10.000 | 7.340 | 2.705 | 4.635 | 0.734000 | 0.270500 | 0.734000 | 9.582246 | 7.350543 | 11.645729 |
5 | 100.000 | 72.594 | 21.028 | 51.566 | 0.725940 | 0.210280 | 0.725940 | 9.890191 | 7.773752 | 11.125351 |
6 | 1.000.000 | 720.505 | 171.386 | 549.119 | 0.720505 | 0.171386 | 0.720505 | 9.925132 | 8.150371 | 10.648858 |
7 | 10.000.000 | 7.164.005 | 1.446.943 | 5.717.062 | 0.716401 | 0.144694 | 0.716401 | 9.943033 | 8.442597 | 10.411335 |
8 | 100.000.000 | 71.334.141 | 12.511.840 | 58.822.301 | 0.713341 | 0.125118 | 0.713341 | 9.957299 | 8.647085 | 10.288903 |
9 | 1.000.000.000 | 710.951.527 | 110.279.008 | 600.672.519 | 0.710952 | 0.110279 | 0.710952 | 9.966497 | 8.813972 | 10.211646 |
10 | 10.000.000.000 | 7.090.681.365 | 985.894.269 | 6.104.787.096 | 0.709068 | 0.098589 | 0.709068 | 9.973509 | 8.940000 | 10.163254 |
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 | |||
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 16 | 13 | 3 | 1.000000 | 0.812500 | 0.187500 | 1.777778 | 1.625000 | 3.000000 |
5 | 32 | 31 | 22 | 9 | 0.968750 | 0.687500 | 0.281250 | 1.937500 | 1.692308 | 3.000000 |
6 | 64 | 53 | 38 | 15 | 0.828125 | 0.593750 | 0.234375 | 1.709677 | 1.727273 | 1.666667 |
7 | 128 | 103 | 68 | 35 | 0.804688 | 0.531250 | 0.273438 | 1.943396 | 1.789474 | 2.333333 |
8 | 256 | 202 | 120 | 82 | 0.789062 | 0.468750 | 0.320312 | 1.961165 | 1.764706 | 2.342857 |
9 | 512 | 397 | 215 | 182 | 0.775391 | 0.419922 | 0.355469 | 1.965347 | 1.791667 | 2.219512 |
10 | 1.024 | 784 | 376 | 408 | 0.765625 | 0.367188 | 0.398438 | 1.974811 | 1.748837 | 2.241758 |
11 | 2.048 | 1.545 | 676 | 869 | 0.754395 | 0.330078 | 0.424316 | 1.970663 | 1.797872 | 2.129902 |
12 | 4.096 | 3.034 | 1.237 | 1.797 | 0.740723 | 0.302002 | 0.438721 | 1.963754 | 1.829882 | 2.067894 |
13 | 8.192 | 6.037 | 2.297 | 3.740 | 0.736938 | 0.280396 | 0.456543 | 1.989782 | 1.856912 | 2.081247 |
14 | 16.384 | 11.994 | 4.198 | 7.796 | 0.732056 | 0.256226 | 0.475830 | 1.986748 | 1.827601 | 2.084492 |
15 | 32.768 | 23.894 | 7.745 | 16.149 | 0.729187 | 0.236359 | 0.492828 | 1.992163 | 1.844926 | 2.071447 |
16 | 65.536 | 47.595 | 14.420 | 33.175 | 0.726242 | 0.220032 | 0.506210 | 1.991923 | 1.861846 | 2.054307 |
17 | 131.072 | 95.097 | 26.767 | 68.330 | 0.725533 | 0.204216 | 0.521317 | 1.998046 | 1.856241 | 2.059684 |
18 | 262.144 | 189.724 | 50.188 | 139.536 | 0.723740 | 0.191452 | 0.532288 | 1.995058 | 1.874995 | 2.042090 |
19 | 524.288 | 378.398 | 94.805 | 283.593 | 0.721737 | 0.180826 | 0.540911 | 1.994466 | 1.888997 | 2.032400 |
20 | 1.048.576 | 755.433 | 178.965 | 576.468 | 0.720437 | 0.170674 | 0.549763 | 1.996398 | 1.887717 | 2.032730 |
21 | 2.097.152 | 1.507.836 | 339.340 | 1.168.496 | 0.718992 | 0.161810 | 0.557182 | 1.995989 | 1.896125 | 2.026992 |
22 | 4.194.304 | 3.010.353 | 645.071 | 2.365.282 | 0.717724 | 0.153797 | 0.563927 | 1.996472 | 1.900958 | 2.024211 |
23 | 8.388.608 | 6.012.156 | 1.228.135 | 4.784.021 | 0.716705 | 0.146405 | 0.570300 | 1.997160 | 1.903876 | 2.022601 |
24 | 16.777.216 | 12.006.933 | 2.344.385 | 9.662.548 | 0.715669 | 0.139736 | 0.575933 | 1.997109 | 1.908898 | 2.019754 |
25 | 33.554.432 | 23.980.770 | 4.485.648 | 19.495.122 | 0.714683 | 0.133683 | 0.581000 | 1.997244 | 1.913358 | 2.017596 |
26 | 67.108.864 | 47.903.211 | 8.597.438 | 39.305.773 | 0.713813 | 0.128112 | 0.585702 | 1.997568 | 1.916655 | 2.016185 |
27 | 134.217.728 | 95.695.437 | 16.509.869 | 79.185.568 | 0.712987 | 0.123008 | 0.589978 | 1.997683 | 1.920324 | 2.014604 |
28 | 268.435.456 | 191.190.346 | 31.752.632 | 159.437.714 | 0.712240 | 0.118288 | 0.593952 | 1.997905 | 1.923252 | 2.013469 |
29 | 536.870.912 | 382.002.209 | 61.169.781 | 320.832.428 | 0.711535 | 0.113938 | 0.597597 | 1.998020 | 1.926448 | 2.012274 |
30 | 1.073.741.824 | 763.306.288 | 117.980.853 | 645.325.435 | 0.710884 | 0.109878 | 0.601006 | 1.998173 | 1.928744 | 2.011410 |
31 | 2.147.483.648 | 1.525.313.918 | 227.854.890 | 1.297.459.028 | 0.710280 | 0.106103 | 0.604176 | 1.998299 | 1.931287 | 2.010550 |
32 | 4.294.967.296 | 3.048.186.811 | 440.566.199 | 2.607.620.612 | 0.709711 | 0.102577 | 0.607134 | 1.998400 | 1.933538 | 2.009790 |
33 | 8.589.934.592 | 6.091.822.557 | 852.832.976 | 5.238.989.581 | 0.709181 | 0.099283 | 0.609899 | 1.998507 | 1.935766 | 2.009107 |
34 | 17.179.869.184 | 12.175.056.437 | 1.652.606.943 | 10.522.449.494 | 0.708682 | 0.096194 | 0.612487 | 1.998590 | 1.937785 | 2.008488 |
35 | 34.359.738.368 | 24.333.987.065 | 3.205.557.879 | 21.128.429.186 | 0.708212 | 0.093294 | 0.614918 | 1.998675 | 1.939698 | 2.007938 |
36 | 68.719.476.736 | 48.637.720.403 | 6.223.448.404 | 42.414.271.999 | 0.707772 | 0.090563 | 0.617209 | 1.998757 | 1.941456 | 2.007450 |
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 | 0 | 3 | 1 | 0 | 1 | 1 |
2 | 4 | 5 | 0 | 5 | 1 | 0 | 2 | 2 |
3 | 8 | 8 | 3 | 5 | 1 | 1 | 3 | 3 |
4 | 16 | 13 | 5 | 8 | 1 | 2 | 4 | 6 |
5 | 32 | 22 | 11 | 11 | 1 | 5 | 7 | 9 |
6 | 64 | 38 | 15 | 23 | 1 | 8 | 10 | 19 |
7 | 128 | 68 | 31 | 37 | 1 | 17 | 17 | 33 |
8 | 256 | 120 | 59 | 61 | 1 | 29 | 33 | 57 |
9 | 512 | 215 | 109 | 106 | 1 | 58 | 58 | 98 |
10 | 1.024 | 376 | 192 | 184 | 1 | 94 | 105 | 176 |
11 | 2.048 | 676 | 348 | 328 | 1 | 173 | 177 | 325 |
12 | 4.096 | 1.237 | 630 | 607 | 1 | 303 | 335 | 598 |
13 | 8.192 | 2.297 | 1.171 | 1.126 | 1 | 588 | 608 | 1.100 |
14 | 16.384 | 4.198 | 2.109 | 2.089 | 1 | 1.067 | 1.090 | 2.040 |
15 | 32.768 | 7.745 | 3.895 | 3.850 | 1 | 1.964 | 2.002 | 3.778 |
16 | 65.536 | 14.420 | 7.211 | 7.209 | 1 | 3.663 | 3.651 | 7.105 |
17 | 131.072 | 26.767 | 13.393 | 13.374 | 1 | 6.837 | 6.742 | 13.187 |
18 | 262.144 | 50.188 | 25.241 | 24.947 | 1 | 12.772 | 12.724 | 24.691 |
19 | 524.288 | 94.805 | 47.668 | 47.137 | 1 | 24.096 | 23.961 | 46.747 |
20 | 1.048.576 | 178.965 | 89.745 | 89.220 | 1 | 45.347 | 45.307 | 88.310 |
21 | 2.097.152 | 339.340 | 170.429 | 168.911 | 1 | 85.890 | 85.816 | 167.633 |
22 | 4.194.304 | 645.071 | 323.672 | 321.399 | 1 | 163.208 | 162.873 | 318.989 |
23 | 8.388.608 | 1.228.135 | 616.521 | 611.614 | 1 | 310.496 | 310.117 | 607.521 |
24 | 16.777.216 | 2.344.385 | 1.176.917 | 1.167.468 | 1 | 592.572 | 592.656 | 1.159.156 |
25 | 33.554.432 | 4.485.648 | 2.251.152 | 2.234.496 | 1 | 1.133.951 | 1.133.592 | 2.218.104 |
26 | 67.108.864 | 8.597.438 | 4.314.261 | 4.283.177 | 1 | 2.173.273 | 2.170.656 | 4.253.508 |
27 | 134.217.728 | 16.509.869 | 8.281.730 | 8.228.139 | 1 | 4.168.618 | 4.168.230 | 8.173.020 |
28 | 268.435.456 | 31.752.632 | 15.925.897 | 15.826.735 | 1 | 8.012.442 | 8.015.160 | 15.725.029 |
29 | 536.870.912 | 61.169.781 | 30.678.030 | 30.491.751 | 1 | 15.431.678 | 15.434.883 | 30.303.219 |
30 | 1.073.741.824 | 117.980.853 | 59.166.377 | 58.814.476 | 1 | 29.753.701 | 29.760.738 | 58.466.413 |
31 | 2.147.483.648 | 227.854.890 | 114.251.471 | 113.603.419 | 1 | 57.453.108 | 57.450.198 | 112.951.583 |
32 | 4.294.967.296 | 440.566.199 | 220.900.142 | 219.666.057 | 1 | 111.056.804 | 111.053.674 | 218.455.720 |
33 | 8.589.934.592 | 852.832.976 | 427.556.328 | 425.276.648 | 1 | 214.907.934 | 214.933.065 | 422.991.976 |
34 | 17.179.869.184 | 1.652.606.943 | 828.448.138 | 824.158.805 | 1 | 416.336.489 | 416.378.989 | 819.891.464 |
35 | 34.359.738.368 | 3.205.557.879 | 1.606.804.373 | 1.598.753.506 | 1 | 807.391.830 | 807.446.864 | 1.590.719.184 |
36 | 68.719.476.736 | 6.223.448.404 | 3.119.283.187 | 3.104.165.217 | 1 | 1.567.223.888 | 1.567.245.471 | 3.088.979.044 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 2 | 1 | 1 | 1 | 1 | 0 |
5 | 32 | 9 | 5 | 4 | 1 | 3 | 2 | 3 |
6 | 64 | 15 | 6 | 9 | 3 | 5 | 3 | 4 |
7 | 128 | 35 | 17 | 18 | 5 | 12 | 9 | 9 |
8 | 256 | 82 | 37 | 45 | 18 | 22 | 22 | 20 |
9 | 512 | 182 | 92 | 90 | 38 | 47 | 49 | 48 |
10 | 1.024 | 408 | 201 | 207 | 92 | 98 | 105 | 113 |
11 | 2.048 | 869 | 432 | 437 | 186 | 220 | 224 | 239 |
12 | 4.096 | 1.797 | 899 | 898 | 401 | 436 | 470 | 490 |
13 | 8.192 | 3.740 | 1.858 | 1.882 | 874 | 906 | 980 | 980 |
14 | 16.384 | 7.796 | 3.839 | 3.957 | 1.832 | 1.910 | 2.002 | 2.052 |
15 | 32.768 | 16.149 | 8.096 | 8.053 | 3.849 | 3.980 | 4.135 | 4.185 |
16 | 65.536 | 33.175 | 16.711 | 16.464 | 8.079 | 8.186 | 8.438 | 8.472 |
17 | 131.072 | 68.330 | 34.282 | 34.048 | 16.640 | 16.870 | 17.212 | 17.608 |
18 | 262.144 | 139.536 | 69.755 | 69.781 | 34.045 | 34.605 | 35.133 | 35.753 |
19 | 524.288 | 283.593 | 141.671 | 141.922 | 69.351 | 70.202 | 71.589 | 72.451 |
20 | 1.048.576 | 576.468 | 287.912 | 288.556 | 141.444 | 142.744 | 145.310 | 146.970 |
21 | 2.097.152 | 1.168.496 | 583.592 | 584.904 | 287.062 | 289.485 | 294.608 | 297.341 |
22 | 4.194.304 | 2.365.282 | 1.181.188 | 1.184.094 | 581.738 | 585.958 | 595.812 | 601.774 |
23 | 8.388.608 | 4.784.021 | 2.391.019 | 2.393.002 | 1.177.431 | 1.186.393 | 1.205.002 | 1.215.195 |
24 | 16.777.216 | 9.662.548 | 4.830.502 | 4.832.046 | 2.380.725 | 2.397.288 | 2.431.154 | 2.453.381 |
25 | 33.554.432 | 19.495.122 | 9.745.837 | 9.749.285 | 4.806.252 | 4.839.948 | 4.904.025 | 4.944.897 |
26 | 67.108.864 | 39.305.773 | 19.644.450 | 19.661.323 | 9.698.906 | 9.761.850 | 9.885.455 | 9.959.562 |
27 | 134.217.728 | 79.185.568 | 39.584.177 | 39.601.391 | 19.549.157 | 19.675.490 | 19.907.073 | 20.053.848 |
28 | 268.435.456 | 159.437.714 | 79.704.616 | 79.733.098 | 39.377.296 | 39.626.249 | 40.077.509 | 40.356.660 |
29 | 536.870.912 | 320.832.428 | 160.387.563 | 160.444.865 | 79.285.079 | 79.755.177 | 80.626.447 | 81.165.725 |
30 | 1.073.741.824 | 645.325.435 | 322.610.072 | 322.715.363 | 159.562.365 | 160.449.343 | 162.149.932 | 163.163.795 |
31 | 2.147.483.648 | 1.297.459.028 | 648.626.857 | 648.832.171 | 320.936.678 | 322.653.588 | 325.966.393 | 327.902.369 |
32 | 4.294.967.296 | 2.607.620.612 | 1.303.621.706 | 1.303.998.906 | 645.263.283 | 648.629.190 | 654.992.381 | 658.735.758 |
33 | 8.589.934.592 | 5.238.989.581 | 2.619.198.554 | 2.619.791.027 | 1.296.871.046 | 1.303.428.012 | 1.315.722.502 | 1.322.968.021 |
34 | 17.179.869.184 | 10.522.449.494 | 5.260.744.612 | 5.261.704.882 | 2.605.687.773 | 2.618.361.286 | 2.642.171.793 | 2.656.228.642 |
35 | 34.359.738.368 | 21.128.429.186 | 10.563.358.509 | 10.565.070.677 | 5.233.801.581 | 5.258.341.853 | 5.304.494.688 | 5.331.791.064 |
36 | 68.719.476.736 | 42.414.271.999 | 21.205.544.424 | 21.208.727.575 | 10.509.820.468 | 10.557.521.519 | 10.646.984.393 | 10.699.945.619 |