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+1x-73
f(0)=73
f(1)=71
f(2)=67
f(3)=61
f(4)=53
f(5)=43
f(6)=31
f(7)=17
f(8)=1
f(9)=1
f(10)=37
f(11)=59
f(12)=83
f(13)=109
f(14)=137
f(15)=167
f(16)=199
f(17)=233
f(18)=269
f(19)=307
f(20)=347
f(21)=389
f(22)=433
f(23)=479
f(24)=1
f(25)=577
f(26)=1
f(27)=683
f(28)=739
f(29)=797
f(30)=857
f(31)=919
f(32)=983
f(33)=1049
f(34)=1117
f(35)=1187
f(36)=1259
f(37)=1
f(38)=1409
f(39)=1487
f(40)=1567
f(41)=97
f(42)=1733
f(43)=107
f(44)=1907
f(45)=1997
f(46)=2089
f(47)=1
f(48)=1
f(49)=2377
f(50)=2477
f(51)=2579
f(52)=2683
f(53)=2789
f(54)=2897
f(55)=1
f(56)=3119
f(57)=1
f(58)=197
f(59)=3467
f(60)=211
f(61)=3709
f(62)=3833
f(63)=1
f(64)=1
f(65)=4217
f(66)=4349
f(67)=4483
f(68)=149
f(69)=1
f(70)=1
f(71)=5039
f(72)=1
f(73)=1
f(74)=5477
f(75)=331
f(76)=5779
f(77)=349
f(78)=6089
f(79)=6247
f(80)=1
f(81)=6569
f(82)=6733
f(83)=6899
f(84)=191
f(85)=7237
f(86)=239
f(87)=7583
f(88)=7759
f(89)=7937
f(90)=8117
f(91)=193
f(92)=499
f(93)=8669
f(94)=521
f(95)=1
f(96)=9239
f(97)=9433
f(98)=9629
f(99)=317
b) Substitution of the polynom
The polynom f(x)=x^2+1x-73 could be written as f(y)= y^2-73.25 with x=y-0.5
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.5
f'(x)>2x
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 | 9 | 9 | 0 | 0.900000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 84 | 70 | 14 | 0.840000 | 0.700000 | 0.140000 | 9.333333 | 7.777778 | inf |
3 | 1.000 | 795 | 431 | 364 | 0.795000 | 0.431000 | 0.364000 | 9.464286 | 6.157143 | 26.000000 |
4 | 10.000 | 7.675 | 3.067 | 4.608 | 0.767500 | 0.306700 | 0.460800 | 9.654088 | 7.116009 | 12.659341 |
5 | 100.000 | 75.327 | 23.566 | 51.761 | 0.753270 | 0.235660 | 0.517610 | 9.814592 | 7.683730 | 11.232856 |
6 | 1.000.000 | 743.399 | 191.991 | 551.408 | 0.743399 | 0.191991 | 0.551408 | 9.868958 | 8.146949 | 10.652963 |
7 | 10.000.000 | 7.361.268 | 1.622.041 | 5.739.227 | 0.736127 | 0.162204 | 0.573923 | 9.902176 | 8.448526 | 10.408313 |
8 | 100.000.000 | 73.051.008 | 14.054.363 | 58.996.645 | 0.730510 | 0.140544 | 0.589966 | 9.923699 | 8.664617 | 10.279546 |
9 | 1.000.000.000 | 726.216.157 | 124.006.146 | 602.210.011 | 0.726216 | 0.124006 | 0.602210 | 9.941220 | 8.823320 | 10.207529 |
10 | 10.000.000.000 | 7.228.014.301 | 1.109.752.736 | 6.118.261.565 | 0.722801 | 0.110975 | 0.611826 | 9.952979 | 8.949175 | 10.159681 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 8 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.600000 | 1.600000 | -nan |
4 | 16 | 15 | 15 | 0 | 0.937500 | 0.937500 | 0.000000 | 1.875000 | 1.875000 | -nan |
5 | 32 | 29 | 29 | 0 | 0.906250 | 0.906250 | 0.000000 | 1.933333 | 1.933333 | -nan |
6 | 64 | 54 | 50 | 4 | 0.843750 | 0.781250 | 0.062500 | 1.862069 | 1.724138 | inf |
7 | 128 | 108 | 85 | 23 | 0.843750 | 0.664062 | 0.179688 | 2.000000 | 1.700000 | 5.750000 |
8 | 256 | 215 | 144 | 71 | 0.839844 | 0.562500 | 0.277344 | 1.990741 | 1.694118 | 3.086957 |
9 | 512 | 414 | 254 | 160 | 0.808594 | 0.496094 | 0.312500 | 1.925581 | 1.763889 | 2.253521 |
10 | 1.024 | 814 | 437 | 377 | 0.794922 | 0.426758 | 0.368164 | 1.966184 | 1.720472 | 2.356250 |
11 | 2.048 | 1.611 | 785 | 826 | 0.786621 | 0.383301 | 0.403320 | 1.979115 | 1.796339 | 2.190981 |
12 | 4.096 | 3.181 | 1.422 | 1.759 | 0.776611 | 0.347168 | 0.429443 | 1.974550 | 1.811465 | 2.129540 |
13 | 8.192 | 6.310 | 2.575 | 3.735 | 0.770264 | 0.314331 | 0.455933 | 1.983653 | 1.810830 | 2.123366 |
14 | 16.384 | 12.500 | 4.683 | 7.817 | 0.762939 | 0.285828 | 0.477112 | 1.980983 | 1.818641 | 2.092905 |
15 | 32.768 | 24.878 | 8.689 | 16.189 | 0.759216 | 0.265167 | 0.494049 | 1.990240 | 1.855435 | 2.070999 |
16 | 65.536 | 49.470 | 16.072 | 33.398 | 0.754852 | 0.245239 | 0.509613 | 1.988504 | 1.849695 | 2.063006 |
17 | 131.072 | 98.564 | 30.064 | 68.500 | 0.751984 | 0.229370 | 0.522614 | 1.992399 | 1.870582 | 2.051021 |
18 | 262.144 | 196.307 | 56.214 | 140.093 | 0.748852 | 0.214439 | 0.534412 | 1.991670 | 1.869811 | 2.045153 |
19 | 524.288 | 391.145 | 106.082 | 285.063 | 0.746050 | 0.202335 | 0.543715 | 1.992517 | 1.887110 | 2.034813 |
20 | 1.048.576 | 779.326 | 200.565 | 578.761 | 0.743223 | 0.191274 | 0.551950 | 1.992422 | 1.890660 | 2.030292 |
21 | 2.097.152 | 1.553.891 | 379.828 | 1.174.063 | 0.740953 | 0.181116 | 0.559837 | 1.993891 | 1.893790 | 2.028580 |
22 | 4.194.304 | 3.098.123 | 722.682 | 2.375.441 | 0.738650 | 0.172301 | 0.566349 | 1.993784 | 1.902656 | 2.023265 |
23 | 8.388.608 | 6.179.558 | 1.376.808 | 4.802.750 | 0.736661 | 0.164128 | 0.572532 | 1.994614 | 1.905137 | 2.021835 |
24 | 16.777.216 | 12.327.008 | 2.629.868 | 9.697.140 | 0.734747 | 0.156752 | 0.577995 | 1.994804 | 1.910120 | 2.019081 |
25 | 33.554.432 | 24.595.042 | 5.035.309 | 19.559.733 | 0.732989 | 0.150064 | 0.582925 | 1.995216 | 1.914662 | 2.017062 |
26 | 67.108.864 | 49.082.584 | 9.655.612 | 39.426.972 | 0.731387 | 0.143880 | 0.587508 | 1.995629 | 1.917581 | 2.015722 |
27 | 134.217.728 | 97.967.046 | 18.547.613 | 79.419.433 | 0.729911 | 0.138190 | 0.591721 | 1.995964 | 1.920915 | 2.014343 |
28 | 268.435.456 | 195.566.606 | 35.688.181 | 159.878.425 | 0.728542 | 0.132949 | 0.595594 | 1.996249 | 1.924139 | 2.013090 |
29 | 536.870.912 | 390.453.951 | 68.760.384 | 321.693.567 | 0.727277 | 0.128076 | 0.599201 | 1.996527 | 1.926699 | 2.012114 |
30 | 1.073.741.824 | 779.643.574 | 132.669.794 | 646.973.780 | 0.726100 | 0.123558 | 0.602541 | 1.996762 | 1.929451 | 2.011149 |
31 | 2.147.483.648 | 1.556.916.837 | 256.322.049 | 1.300.594.788 | 0.724996 | 0.119359 | 0.605637 | 1.996960 | 1.932030 | 2.010274 |
32 | 4.294.967.296 | 3.109.422.351 | 495.762.946 | 2.613.659.405 | 0.723969 | 0.115429 | 0.608540 | 1.997167 | 1.934141 | 2.009588 |
33 | 8.589.934.592 | 6.210.568.787 | 959.930.153 | 5.250.638.634 | 0.723005 | 0.111751 | 0.611255 | 1.997338 | 1.936268 | 2.008922 |
34 | 17.179.869.184 | 12.405.573.120 | 1.860.587.196 | 10.544.985.924 | 0.722099 | 0.108300 | 0.613799 | 1.997494 | 1.938253 | 2.008324 |
35 | 34.359.738.368 | 24.781.839.303 | 3.609.812.787 | 21.172.026.516 | 0.721246 | 0.105059 | 0.616187 | 1.997637 | 1.940147 | 2.007782 |
36 | 68.719.476.736 | 49.508.414.275 | 7.009.798.265 | 42.498.616.010 | 0.720442 | 0.102006 | 0.618436 | 1.997770 | 1.941873 | 2.007300 |
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 | 2 | 1 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 3 | 2 | 1 | 1 | 2 | 1 |
3 | 8 | 8 | 5 | 3 | 2 | 2 | 2 | 2 |
4 | 16 | 15 | 8 | 7 | 3 | 4 | 4 | 4 |
5 | 32 | 29 | 13 | 16 | 7 | 8 | 7 | 7 |
6 | 64 | 50 | 19 | 31 | 13 | 14 | 13 | 10 |
7 | 128 | 85 | 31 | 54 | 21 | 22 | 21 | 21 |
8 | 256 | 144 | 52 | 92 | 33 | 37 | 38 | 36 |
9 | 512 | 254 | 87 | 167 | 59 | 62 | 71 | 62 |
10 | 1.024 | 437 | 146 | 291 | 107 | 109 | 117 | 104 |
11 | 2.048 | 785 | 265 | 520 | 193 | 187 | 210 | 195 |
12 | 4.096 | 1.422 | 479 | 943 | 361 | 356 | 362 | 343 |
13 | 8.192 | 2.575 | 873 | 1.702 | 646 | 650 | 651 | 628 |
14 | 16.384 | 4.683 | 1.569 | 3.114 | 1.161 | 1.181 | 1.185 | 1.156 |
15 | 32.768 | 8.689 | 2.899 | 5.790 | 2.138 | 2.195 | 2.197 | 2.159 |
16 | 65.536 | 16.072 | 5.350 | 10.722 | 3.987 | 4.047 | 4.031 | 4.007 |
17 | 131.072 | 30.064 | 9.995 | 20.069 | 7.514 | 7.531 | 7.511 | 7.508 |
18 | 262.144 | 56.214 | 18.841 | 37.373 | 14.086 | 14.033 | 14.067 | 14.028 |
19 | 524.288 | 106.082 | 35.472 | 70.610 | 26.644 | 26.469 | 26.461 | 26.508 |
20 | 1.048.576 | 200.565 | 66.966 | 133.599 | 50.353 | 50.119 | 50.054 | 50.039 |
21 | 2.097.152 | 379.828 | 126.842 | 252.986 | 95.167 | 94.924 | 94.966 | 94.771 |
22 | 4.194.304 | 722.682 | 241.200 | 481.482 | 180.957 | 180.577 | 180.842 | 180.306 |
23 | 8.388.608 | 1.376.808 | 458.985 | 917.823 | 344.671 | 344.572 | 344.005 | 343.560 |
24 | 16.777.216 | 2.629.868 | 876.580 | 1.753.288 | 657.849 | 657.903 | 657.341 | 656.775 |
25 | 33.554.432 | 5.035.309 | 1.677.753 | 3.357.556 | 1.259.072 | 1.258.953 | 1.258.574 | 1.258.710 |
26 | 67.108.864 | 9.655.612 | 3.217.829 | 6.437.783 | 2.413.114 | 2.414.552 | 2.414.107 | 2.413.839 |
27 | 134.217.728 | 18.547.613 | 6.183.437 | 12.364.176 | 4.636.435 | 4.636.815 | 4.639.178 | 4.635.185 |
28 | 268.435.456 | 35.688.181 | 11.896.542 | 23.791.639 | 8.921.316 | 8.921.666 | 8.923.745 | 8.921.454 |
29 | 536.870.912 | 68.760.384 | 22.922.732 | 45.837.652 | 17.189.234 | 17.186.738 | 17.193.802 | 17.190.610 |
30 | 1.073.741.824 | 132.669.794 | 44.227.268 | 88.442.526 | 33.164.688 | 33.167.440 | 33.168.267 | 33.169.399 |
31 | 2.147.483.648 | 256.322.049 | 85.441.697 | 170.880.352 | 64.080.715 | 64.078.107 | 64.081.551 | 64.081.676 |
32 | 4.294.967.296 | 495.762.946 | 165.246.152 | 330.516.794 | 123.951.309 | 123.932.988 | 123.937.863 | 123.940.786 |
33 | 8.589.934.592 | 959.930.153 | 319.973.223 | 639.956.930 | 239.991.216 | 239.977.609 | 239.981.673 | 239.979.655 |
34 | 17.179.869.184 | 1.860.587.196 | 620.189.112 | 1.240.398.084 | 465.148.648 | 465.147.846 | 465.151.519 | 465.139.183 |
35 | 34.359.738.368 | 3.609.812.787 | 1.203.269.341 | 2.406.543.446 | 902.442.466 | 902.457.086 | 902.474.146 | 902.439.089 |
36 | 68.719.476.736 | 7.009.798.265 | 2.336.558.474 | 4.673.239.791 | 1.752.436.198 | 1.752.467.075 | 1.752.493.057 | 1.752.401.935 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 64 | 4 | 2 | 2 | 1 | 2 | 1 | 0 |
7 | 128 | 23 | 12 | 11 | 6 | 5 | 7 | 5 |
8 | 256 | 71 | 34 | 37 | 17 | 22 | 18 | 14 |
9 | 512 | 160 | 82 | 78 | 34 | 44 | 40 | 42 |
10 | 1.024 | 377 | 197 | 180 | 86 | 96 | 95 | 100 |
11 | 2.048 | 826 | 408 | 418 | 200 | 210 | 202 | 214 |
12 | 4.096 | 1.759 | 867 | 892 | 430 | 437 | 445 | 447 |
13 | 8.192 | 3.735 | 1.890 | 1.845 | 930 | 909 | 955 | 941 |
14 | 16.384 | 7.817 | 3.975 | 3.842 | 1.941 | 1.918 | 2.003 | 1.955 |
15 | 32.768 | 16.189 | 8.201 | 7.988 | 4.019 | 4.025 | 4.097 | 4.048 |
16 | 65.536 | 33.398 | 16.850 | 16.548 | 8.333 | 8.339 | 8.395 | 8.331 |
17 | 131.072 | 68.500 | 34.580 | 33.920 | 17.103 | 17.100 | 17.221 | 17.076 |
18 | 262.144 | 140.093 | 70.566 | 69.527 | 34.972 | 35.145 | 35.116 | 34.860 |
19 | 524.288 | 285.063 | 143.325 | 141.738 | 71.189 | 71.167 | 71.457 | 71.250 |
20 | 1.048.576 | 578.761 | 290.524 | 288.237 | 144.808 | 144.765 | 144.730 | 144.458 |
21 | 2.097.152 | 1.174.063 | 589.690 | 584.373 | 293.384 | 293.545 | 293.875 | 293.259 |
22 | 4.194.304 | 2.375.441 | 1.193.154 | 1.182.287 | 594.255 | 593.534 | 594.063 | 593.589 |
23 | 8.388.608 | 4.802.750 | 2.412.861 | 2.389.889 | 1.200.622 | 1.200.018 | 1.201.609 | 1.200.501 |
24 | 16.777.216 | 9.697.140 | 4.870.363 | 4.826.777 | 2.422.856 | 2.423.594 | 2.425.235 | 2.425.455 |
25 | 33.554.432 | 19.559.733 | 9.820.105 | 9.739.628 | 4.886.446 | 4.889.524 | 4.891.379 | 4.892.384 |
26 | 67.108.864 | 39.426.972 | 19.788.608 | 19.638.364 | 9.851.231 | 9.856.726 | 9.858.590 | 9.860.425 |
27 | 134.217.728 | 79.419.433 | 39.855.193 | 39.564.240 | 19.848.989 | 19.853.926 | 19.857.169 | 19.859.349 |
28 | 268.435.456 | 159.878.425 | 80.215.413 | 79.663.012 | 39.965.447 | 39.967.255 | 39.965.220 | 39.980.503 |
29 | 536.870.912 | 321.693.567 | 161.379.024 | 160.314.543 | 80.419.624 | 80.424.859 | 80.419.047 | 80.430.037 |
30 | 1.073.741.824 | 646.973.780 | 324.495.870 | 322.477.910 | 161.727.150 | 161.750.130 | 161.734.101 | 161.762.399 |
31 | 2.147.483.648 | 1.300.594.788 | 652.240.017 | 648.354.771 | 325.143.250 | 325.151.512 | 325.136.294 | 325.163.732 |
32 | 4.294.967.296 | 2.613.659.405 | 1.310.603.003 | 1.303.056.402 | 653.403.392 | 653.390.353 | 653.412.176 | 653.453.484 |
33 | 8.589.934.592 | 5.250.638.634 | 2.632.595.839 | 2.618.042.795 | 1.312.656.535 | 1.312.628.384 | 1.312.642.934 | 1.312.710.781 |
34 | 17.179.869.184 | 10.544.985.924 | 5.286.520.242 | 5.258.465.682 | 2.636.207.905 | 2.636.244.975 | 2.636.233.183 | 2.636.299.861 |
35 | 34.359.738.368 | 21.172.026.516 | 10.613.165.186 | 10.558.861.330 | 5.292.977.717 | 5.293.045.102 | 5.292.936.003 | 5.293.067.694 |
36 | 68.719.476.736 | 42.498.616.010 | 21.301.937.851 | 21.196.678.159 | 10.624.610.521 | 10.624.654.072 | 10.624.609.028 | 10.624.742.389 |