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+114x-11
f(0)=11
f(1)=13
f(2)=17
f(3)=5
f(4)=461
f(5)=73
f(6)=709
f(7)=19
f(8)=193
f(9)=137
f(10)=1229
f(11)=31
f(12)=79
f(13)=41
f(14)=1
f(15)=37
f(16)=2069
f(17)=277
f(18)=43
f(19)=1
f(20)=157
f(21)=353
f(22)=271
f(23)=1
f(24)=3301
f(25)=433
f(26)=191
f(27)=1
f(28)=61
f(29)=47
f(30)=139
f(31)=59
f(32)=1
f(33)=1
f(34)=5021
f(35)=1301
f(36)=317
f(37)=1
f(38)=1153
f(39)=1489
f(40)=1
f(41)=1
f(42)=211
f(43)=337
f(44)=631
f(45)=1
f(46)=7349
f(47)=1889
f(48)=1553
f(49)=997
f(50)=431
f(51)=1
f(52)=233
f(53)=1
f(54)=1
f(55)=1
f(56)=257
f(57)=1217
f(58)=1993
f(59)=2549
f(60)=10429
f(61)=1
f(62)=991
f(63)=557
f(64)=599
f(65)=1453
f(66)=83
f(67)=1
f(68)=2473
f(69)=1
f(70)=757
f(71)=1
f(72)=13381
f(73)=1
f(74)=13901
f(75)=3541
f(76)=307
f(77)=167
f(78)=1
f(79)=293
f(80)=1193
f(81)=1973
f(82)=16061
f(83)=1
f(84)=1511
f(85)=2113
f(86)=17189
f(87)=1
f(88)=1
f(89)=1
f(90)=311
f(91)=1
f(92)=1
f(93)=1
f(94)=19541
f(95)=1
f(96)=20149
f(97)=2557
f(98)=4153
f(99)=479
b) Substitution of the polynom
The polynom f(x)=x^2+114x-11 could be written as f(y)= y^2-3260 with x=y-57
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+57
f'(x)>2x+113
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 | 11 | 4 | 7 | 1.100000 | 0.400000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 69 | 15 | 54 | 0.690000 | 0.150000 | 0.690000 | 6.272727 | 3.750000 | 7.714286 |
3 | 1.000 | 629 | 110 | 519 | 0.629000 | 0.110000 | 0.629000 | 9.115942 | 7.333333 | 9.611111 |
4 | 10.000 | 6.470 | 786 | 5.684 | 0.647000 | 0.078600 | 0.647000 | 10.286168 | 7.145454 | 10.951831 |
5 | 100.000 | 65.783 | 6.083 | 59.700 | 0.657830 | 0.060830 | 0.657830 | 10.167388 | 7.739186 | 10.503167 |
6 | 1.000.000 | 663.536 | 49.905 | 613.631 | 0.663536 | 0.049905 | 0.663536 | 10.086740 | 8.204011 | 10.278576 |
7 | 10.000.000 | 6.678.430 | 420.482 | 6.257.948 | 0.667843 | 0.042048 | 0.667843 | 10.064910 | 8.425649 | 10.198227 |
8 | 100.000.000 | 67.111.478 | 3.644.080 | 63.467.398 | 0.671115 | 0.036441 | 0.671115 | 10.048990 | 8.666435 | 10.141887 |
9 | 1.000.000.000 | 673.578.020 | 32.157.157 | 641.420.863 | 0.673578 | 0.032157 | 0.673578 | 10.036704 | 8.824492 | 10.106304 |
10 | 10.000.000.000 | 6.755.475.008 | 287.698.902 | 6.467.776.106 | 0.675547 | 0.028770 | 0.675547 | 10.029239 | 8.946652 | 10.083513 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.500000 | 2.000000 |
4 | 16 | 16 | 5 | 11 | 1.000000 | 0.312500 | 0.687500 | 1.777778 | 1.666667 | 1.833333 |
5 | 32 | 26 | 6 | 20 | 0.812500 | 0.187500 | 0.625000 | 1.625000 | 1.200000 | 1.818182 |
6 | 64 | 48 | 9 | 39 | 0.750000 | 0.140625 | 0.609375 | 1.846154 | 1.500000 | 1.950000 |
7 | 128 | 87 | 21 | 66 | 0.679688 | 0.164062 | 0.515625 | 1.812500 | 2.333333 | 1.692308 |
8 | 256 | 167 | 32 | 135 | 0.652344 | 0.125000 | 0.527344 | 1.919540 | 1.523810 | 2.045455 |
9 | 512 | 326 | 58 | 268 | 0.636719 | 0.113281 | 0.523438 | 1.952096 | 1.812500 | 1.985185 |
10 | 1.024 | 645 | 112 | 533 | 0.629883 | 0.109375 | 0.520508 | 1.978528 | 1.931034 | 1.988806 |
11 | 2.048 | 1.301 | 193 | 1.108 | 0.635254 | 0.094238 | 0.541016 | 2.017054 | 1.723214 | 2.078799 |
12 | 4.096 | 2.616 | 356 | 2.260 | 0.638672 | 0.086914 | 0.551758 | 2.010761 | 1.844560 | 2.039711 |
13 | 8.192 | 5.282 | 649 | 4.633 | 0.644775 | 0.079224 | 0.565552 | 2.019113 | 1.823034 | 2.050000 |
14 | 16.384 | 10.644 | 1.211 | 9.433 | 0.649658 | 0.073914 | 0.575745 | 2.015146 | 1.865948 | 2.036046 |
15 | 32.768 | 21.422 | 2.241 | 19.181 | 0.653748 | 0.068390 | 0.585358 | 2.012589 | 1.850537 | 2.033393 |
16 | 65.536 | 42.974 | 4.179 | 38.795 | 0.655731 | 0.063766 | 0.591965 | 2.006068 | 1.864792 | 2.022574 |
17 | 131.072 | 86.311 | 7.838 | 78.473 | 0.658501 | 0.059799 | 0.598701 | 2.008447 | 1.875568 | 2.022761 |
18 | 262.144 | 173.078 | 14.623 | 158.455 | 0.660240 | 0.055782 | 0.604458 | 2.005283 | 1.865654 | 2.019230 |
19 | 524.288 | 347.098 | 27.595 | 319.503 | 0.662037 | 0.052633 | 0.609404 | 2.005443 | 1.887096 | 2.016364 |
20 | 1.048.576 | 695.882 | 52.183 | 643.699 | 0.663645 | 0.049766 | 0.613879 | 2.004857 | 1.891031 | 2.014688 |
21 | 2.097.152 | 1.395.013 | 98.510 | 1.296.503 | 0.665194 | 0.046973 | 0.618221 | 2.004669 | 1.887780 | 2.014145 |
22 | 4.194.304 | 2.795.330 | 187.499 | 2.607.831 | 0.666459 | 0.044703 | 0.621755 | 2.003802 | 1.903350 | 2.011435 |
23 | 8.388.608 | 5.600.280 | 357.019 | 5.243.261 | 0.667605 | 0.042560 | 0.625045 | 2.003442 | 1.904112 | 2.010583 |
24 | 16.777.216 | 11.218.788 | 682.142 | 10.536.646 | 0.668692 | 0.040659 | 0.628033 | 2.003255 | 1.910660 | 2.009560 |
25 | 33.554.432 | 22.470.614 | 1.304.835 | 21.165.779 | 0.669676 | 0.038887 | 0.630789 | 2.002945 | 1.912850 | 2.008778 |
26 | 67.108.864 | 45.003.971 | 2.503.976 | 42.499.995 | 0.670611 | 0.037312 | 0.633299 | 2.002792 | 1.918998 | 2.007958 |
27 | 134.217.728 | 90.123.280 | 4.807.781 | 85.315.499 | 0.671471 | 0.035821 | 0.635650 | 2.002563 | 1.920059 | 2.007424 |
28 | 268.435.456 | 180.454.732 | 9.252.891 | 171.201.841 | 0.672246 | 0.034470 | 0.637777 | 2.002310 | 1.924566 | 2.006691 |
29 | 536.870.912 | 361.296.202 | 17.828.568 | 343.467.634 | 0.672967 | 0.033208 | 0.639758 | 2.002143 | 1.926811 | 2.006215 |
30 | 1.073.741.824 | 723.321.334 | 34.404.300 | 688.917.034 | 0.673645 | 0.032042 | 0.641604 | 2.002018 | 1.929729 | 2.005770 |
31 | 2.147.483.648 | 1.448.004.029 | 66.456.652 | 1.381.547.377 | 0.674279 | 0.030946 | 0.643333 | 2.001882 | 1.931638 | 2.005390 |
32 | 4.294.967.296 | 2.898.560.563 | 128.526.685 | 2.770.033.878 | 0.674874 | 0.029925 | 0.644949 | 2.001763 | 1.933993 | 2.005023 |
33 | 8.589.934.592 | 5.801.907.643 | 248.864.995 | 5.553.042.648 | 0.675431 | 0.028972 | 0.646459 | 2.001651 | 1.936290 | 2.004684 |
34 | 17.179.869.184 | 11.612.819.687 | 482.376.324 | 11.130.443.363 | 0.675955 | 0.028078 | 0.647877 | 2.001552 | 1.938305 | 2.004387 |
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 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 2 | 0 | 1 | 2 | 0 |
4 | 16 | 5 | 1 | 4 | 0 | 1 | 4 | 0 |
5 | 32 | 6 | 2 | 4 | 0 | 1 | 5 | 0 |
6 | 64 | 9 | 3 | 6 | 0 | 1 | 8 | 0 |
7 | 128 | 21 | 7 | 14 | 0 | 1 | 20 | 0 |
8 | 256 | 32 | 12 | 20 | 0 | 1 | 31 | 0 |
9 | 512 | 58 | 19 | 39 | 0 | 1 | 57 | 0 |
10 | 1.024 | 112 | 37 | 75 | 0 | 1 | 111 | 0 |
11 | 2.048 | 193 | 62 | 131 | 0 | 1 | 192 | 0 |
12 | 4.096 | 356 | 114 | 242 | 0 | 1 | 355 | 0 |
13 | 8.192 | 649 | 207 | 442 | 0 | 1 | 648 | 0 |
14 | 16.384 | 1.211 | 397 | 814 | 0 | 1 | 1.210 | 0 |
15 | 32.768 | 2.241 | 746 | 1.495 | 0 | 1 | 2.240 | 0 |
16 | 65.536 | 4.179 | 1.402 | 2.777 | 0 | 1 | 4.178 | 0 |
17 | 131.072 | 7.838 | 2.608 | 5.230 | 0 | 1 | 7.837 | 0 |
18 | 262.144 | 14.623 | 4.875 | 9.748 | 0 | 1 | 14.622 | 0 |
19 | 524.288 | 27.595 | 9.220 | 18.375 | 0 | 1 | 27.594 | 0 |
20 | 1.048.576 | 52.183 | 17.358 | 34.825 | 0 | 1 | 52.182 | 0 |
21 | 2.097.152 | 98.510 | 32.793 | 65.717 | 0 | 1 | 98.509 | 0 |
22 | 4.194.304 | 187.499 | 62.551 | 124.948 | 0 | 1 | 187.498 | 0 |
23 | 8.388.608 | 357.019 | 119.037 | 237.982 | 0 | 1 | 357.018 | 0 |
24 | 16.777.216 | 682.142 | 227.351 | 454.791 | 0 | 1 | 682.141 | 0 |
25 | 33.554.432 | 1.304.835 | 434.786 | 870.049 | 0 | 1 | 1.304.834 | 0 |
26 | 67.108.864 | 2.503.976 | 834.461 | 1.669.515 | 0 | 1 | 2.503.975 | 0 |
27 | 134.217.728 | 4.807.781 | 1.601.877 | 3.205.904 | 0 | 1 | 4.807.780 | 0 |
28 | 268.435.456 | 9.252.891 | 3.082.911 | 6.169.980 | 0 | 1 | 9.252.890 | 0 |
29 | 536.870.912 | 17.828.568 | 5.942.753 | 11.885.815 | 0 | 1 | 17.828.567 | 0 |
30 | 1.073.741.824 | 34.404.300 | 11.466.157 | 22.938.143 | 0 | 1 | 34.404.299 | 0 |
31 | 2.147.483.648 | 66.456.652 | 22.150.602 | 44.306.050 | 0 | 1 | 66.456.651 | 0 |
32 | 4.294.967.296 | 128.526.685 | 42.845.430 | 85.681.255 | 0 | 1 | 128.526.684 | 0 |
33 | 8.589.934.592 | 248.864.995 | 82.950.435 | 165.914.560 | 0 | 1 | 248.864.994 | 0 |
34 | 17.179.869.184 | 482.376.324 | 160.785.495 | 321.590.829 | 0 | 1 | 482.376.323 | 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 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
3 | 8 | 6 | 5 | 1 | 3 | 1 | 2 | 0 |
4 | 16 | 11 | 8 | 3 | 5 | 1 | 3 | 2 |
5 | 32 | 20 | 15 | 5 | 7 | 3 | 6 | 4 |
6 | 64 | 39 | 23 | 16 | 16 | 4 | 11 | 8 |
7 | 128 | 66 | 38 | 28 | 24 | 6 | 23 | 13 |
8 | 256 | 135 | 73 | 62 | 52 | 14 | 41 | 28 |
9 | 512 | 268 | 138 | 130 | 106 | 32 | 78 | 52 |
10 | 1.024 | 533 | 278 | 255 | 190 | 75 | 156 | 112 |
11 | 2.048 | 1.108 | 574 | 534 | 366 | 182 | 332 | 228 |
12 | 4.096 | 2.260 | 1.157 | 1.103 | 729 | 416 | 643 | 472 |
13 | 8.192 | 4.633 | 2.318 | 2.315 | 1.448 | 872 | 1.289 | 1.024 |
14 | 16.384 | 9.433 | 4.721 | 4.712 | 2.905 | 1.841 | 2.560 | 2.127 |
15 | 32.768 | 19.181 | 9.639 | 9.542 | 5.757 | 3.900 | 5.225 | 4.299 |
16 | 65.536 | 38.795 | 19.451 | 19.344 | 11.535 | 8.040 | 10.396 | 8.824 |
17 | 131.072 | 78.473 | 39.288 | 39.185 | 23.078 | 16.467 | 20.926 | 18.002 |
18 | 262.144 | 158.455 | 79.513 | 78.942 | 46.207 | 33.831 | 41.835 | 36.582 |
19 | 524.288 | 319.503 | 160.681 | 158.822 | 92.333 | 68.657 | 84.074 | 74.439 |
20 | 1.048.576 | 643.699 | 323.481 | 320.218 | 183.779 | 139.971 | 169.332 | 150.617 |
21 | 2.097.152 | 1.296.503 | 651.724 | 644.779 | 367.373 | 284.453 | 340.088 | 304.589 |
22 | 4.194.304 | 2.607.831 | 1.311.143 | 1.296.688 | 733.850 | 576.497 | 682.574 | 614.910 |
23 | 8.388.608 | 5.243.261 | 2.634.863 | 2.608.398 | 1.466.615 | 1.166.756 | 1.369.512 | 1.240.378 |
24 | 16.777.216 | 10.536.646 | 5.295.376 | 5.241.270 | 2.933.683 | 2.358.526 | 2.744.611 | 2.499.826 |
25 | 33.554.432 | 21.165.779 | 10.635.165 | 10.530.614 | 5.860.845 | 4.764.997 | 5.506.073 | 5.033.864 |
26 | 67.108.864 | 42.499.995 | 21.347.964 | 21.152.031 | 11.716.692 | 9.617.871 | 11.035.745 | 10.129.687 |
27 | 134.217.728 | 85.315.499 | 42.847.326 | 42.468.173 | 23.422.578 | 19.398.419 | 22.115.913 | 20.378.589 |
28 | 268.435.456 | 171.201.841 | 85.959.253 | 85.242.588 | 46.820.438 | 39.097.563 | 44.312.769 | 40.971.071 |
29 | 536.870.912 | 343.467.634 | 172.420.382 | 171.047.252 | 93.607.939 | 78.738.856 | 88.781.411 | 82.339.428 |
30 | 1.073.741.824 | 688.917.034 | 345.797.444 | 343.119.590 | 187.151.924 | 158.477.615 | 177.866.547 | 165.420.948 |
31 | 2.147.483.648 | 1.381.547.377 | 693.354.794 | 688.192.583 | 374.191.787 | 318.824.491 | 356.266.783 | 332.264.316 |
32 | 4.294.967.296 | 2.770.033.878 | 1.389.993.532 | 1.380.040.346 | 748.190.112 | 641.206.425 | 713.541.387 | 667.095.954 |
33 | 8.589.934.592 | 5.553.042.648 | 2.786.074.141 | 2.766.968.507 | 1.496.016.622 | 1.289.003.024 | 1.428.920.846 | 1.339.102.156 |
34 | 17.179.869.184 | 11.130.443.363 | 5.583.771.250 | 5.546.672.113 | 2.991.309.811 | 2.590.308.331 | 2.861.475.395 | 2.687.349.826 |