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+56x-37
f(0)=37
f(1)=5
f(2)=79
f(3)=7
f(4)=29
f(5)=67
f(6)=1
f(7)=101
f(8)=19
f(9)=137
f(10)=89
f(11)=1
f(12)=41
f(13)=43
f(14)=23
f(15)=257
f(16)=223
f(17)=1
f(18)=1
f(19)=347
f(20)=1483
f(21)=1
f(22)=73
f(23)=1
f(24)=269
f(25)=71
f(26)=419
f(27)=1
f(28)=463
f(29)=607
f(30)=2543
f(31)=1
f(32)=397
f(33)=1
f(34)=3023
f(35)=787
f(36)=131
f(37)=1
f(38)=1
f(39)=1
f(40)=3803
f(41)=197
f(42)=4079
f(43)=211
f(44)=4363
f(45)=1
f(46)=1
f(47)=1201
f(48)=991
f(49)=1277
f(50)=277
f(51)=271
f(52)=797
f(53)=1
f(54)=5903
f(55)=1
f(56)=1
f(57)=1601
f(58)=263
f(59)=241
f(60)=1
f(61)=1
f(62)=251
f(63)=373
f(64)=7643
f(65)=103
f(66)=229
f(67)=293
f(68)=1
f(69)=113
f(70)=8783
f(71)=449
f(72)=1
f(73)=1
f(74)=1
f(75)=2447
f(76)=1999
f(77)=2551
f(78)=2083
f(79)=2657
f(80)=1549
f(81)=1
f(82)=11279
f(83)=1
f(84)=617
f(85)=1
f(86)=487
f(87)=443
f(88)=1
f(89)=3217
f(90)=13103
f(91)=1
f(92)=367
f(93)=691
f(94)=1
f(95)=1
f(96)=1
f(97)=3701
f(98)=3011
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+56x-37 could be written as f(y)= y^2-821 with x=y-28
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+28
f'(x)>2x+55
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 | 6 | 4 | 1.000000 | 0.600000 | 0.400000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 65 | 29 | 36 | 0.650000 | 0.290000 | 0.360000 | 6.500000 | 4.833333 | 9.000000 |
3 | 1.000 | 632 | 180 | 452 | 0.632000 | 0.180000 | 0.452000 | 9.723077 | 6.206897 | 12.555555 |
4 | 10.000 | 6.494 | 1.346 | 5.148 | 0.649400 | 0.134600 | 0.514800 | 10.275316 | 7.477778 | 11.389380 |
5 | 100.000 | 66.083 | 10.208 | 55.875 | 0.660830 | 0.102080 | 0.558750 | 10.176008 | 7.583952 | 10.853729 |
6 | 1.000.000 | 666.186 | 82.516 | 583.670 | 0.666186 | 0.082516 | 0.583670 | 10.081050 | 8.083464 | 10.445995 |
7 | 10.000.000 | 6.700.300 | 695.021 | 6.005.279 | 0.670030 | 0.069502 | 0.600528 | 10.057702 | 8.422863 | 10.288826 |
8 | 100.000.000 | 67.287.006 | 6.010.606 | 61.276.400 | 0.672870 | 0.060106 | 0.612764 | 10.042387 | 8.648092 | 10.203755 |
9 | 1.000.000.000 | 675.088.385 | 52.893.969 | 622.194.416 | 0.675088 | 0.052894 | 0.622194 | 10.032968 | 8.800106 | 10.153900 |
10 | 10.000.000.000 | 6.768.797.007 | 472.462.702 | 6.296.334.305 | 0.676880 | 0.047246 | 0.629633 | 10.026535 | 8.932261 | 10.119561 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.000000 | inf |
3 | 8 | 8 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 1.600000 | 1.666667 | 1.500000 |
4 | 16 | 14 | 7 | 7 | 0.875000 | 0.437500 | 0.437500 | 1.750000 | 1.400000 | 2.333333 |
5 | 32 | 24 | 11 | 13 | 0.750000 | 0.343750 | 0.406250 | 1.714286 | 1.571429 | 1.857143 |
6 | 64 | 45 | 21 | 24 | 0.703125 | 0.328125 | 0.375000 | 1.875000 | 1.909091 | 1.846154 |
7 | 128 | 82 | 37 | 45 | 0.640625 | 0.289062 | 0.351562 | 1.822222 | 1.761905 | 1.875000 |
8 | 256 | 158 | 64 | 94 | 0.617188 | 0.250000 | 0.367188 | 1.926829 | 1.729730 | 2.088889 |
9 | 512 | 317 | 100 | 217 | 0.619141 | 0.195312 | 0.423828 | 2.006329 | 1.562500 | 2.308511 |
10 | 1.024 | 647 | 185 | 462 | 0.631836 | 0.180664 | 0.451172 | 2.041009 | 1.850000 | 2.129032 |
11 | 2.048 | 1.310 | 337 | 973 | 0.639648 | 0.164551 | 0.475098 | 2.024729 | 1.821622 | 2.106061 |
12 | 4.096 | 2.634 | 624 | 2.010 | 0.643066 | 0.152344 | 0.490723 | 2.010687 | 1.851632 | 2.065776 |
13 | 8.192 | 5.294 | 1.130 | 4.164 | 0.646240 | 0.137939 | 0.508301 | 2.009871 | 1.810897 | 2.071642 |
14 | 16.384 | 10.698 | 2.037 | 8.661 | 0.652954 | 0.124329 | 0.528625 | 2.020778 | 1.802655 | 2.079971 |
15 | 32.768 | 21.525 | 3.789 | 17.736 | 0.656891 | 0.115631 | 0.541260 | 2.012058 | 1.860088 | 2.047801 |
16 | 65.536 | 43.240 | 6.991 | 36.249 | 0.659790 | 0.106674 | 0.553116 | 2.008827 | 1.845078 | 2.043809 |
17 | 131.072 | 86.736 | 13.008 | 73.728 | 0.661743 | 0.099243 | 0.562500 | 2.005920 | 1.860678 | 2.033932 |
18 | 262.144 | 173.866 | 24.273 | 149.593 | 0.663246 | 0.092594 | 0.570652 | 2.004543 | 1.866006 | 2.028985 |
19 | 524.288 | 348.596 | 45.576 | 303.020 | 0.664894 | 0.086929 | 0.577965 | 2.004969 | 1.877642 | 2.025630 |
20 | 1.048.576 | 698.603 | 86.210 | 612.393 | 0.666240 | 0.082216 | 0.584023 | 2.004048 | 1.891566 | 2.020966 |
21 | 2.097.152 | 1.399.907 | 163.252 | 1.236.655 | 0.667528 | 0.077845 | 0.589683 | 2.003866 | 1.893655 | 2.019381 |
22 | 4.194.304 | 2.804.256 | 310.228 | 2.494.028 | 0.668587 | 0.073964 | 0.594623 | 2.003173 | 1.900301 | 2.016753 |
23 | 8.388.608 | 5.618.315 | 590.003 | 5.028.312 | 0.669755 | 0.070334 | 0.599422 | 2.003496 | 1.901837 | 2.016141 |
24 | 16.777.216 | 11.252.289 | 1.126.813 | 10.125.476 | 0.670689 | 0.067163 | 0.603525 | 2.002787 | 1.909843 | 2.013693 |
25 | 33.554.432 | 22.535.978 | 2.155.450 | 20.380.528 | 0.671624 | 0.064237 | 0.607387 | 2.002790 | 1.912873 | 2.012797 |
26 | 67.108.864 | 45.125.376 | 4.131.023 | 40.994.353 | 0.672421 | 0.061557 | 0.610863 | 2.002370 | 1.916548 | 2.011447 |
27 | 134.217.728 | 90.354.479 | 7.927.920 | 82.426.559 | 0.673193 | 0.059068 | 0.614126 | 2.002299 | 1.919118 | 2.010681 |
28 | 268.435.456 | 180.894.336 | 15.241.389 | 165.652.947 | 0.673884 | 0.056779 | 0.617105 | 2.002052 | 1.922495 | 2.009703 |
29 | 536.870.912 | 362.139.835 | 29.347.764 | 332.792.071 | 0.674538 | 0.054664 | 0.619874 | 2.001941 | 1.925531 | 2.008972 |
30 | 1.073.741.824 | 724.931.852 | 56.586.330 | 668.345.522 | 0.675145 | 0.052700 | 0.622445 | 2.001801 | 1.928131 | 2.008298 |
31 | 2.147.483.648 | 1.451.101.770 | 109.256.087 | 1.341.845.683 | 0.675722 | 0.050876 | 0.624846 | 2.001708 | 1.930786 | 2.007712 |
32 | 4.294.967.296 | 2.904.520.400 | 211.205.777 | 2.693.314.623 | 0.676261 | 0.049175 | 0.627086 | 2.001597 | 1.933126 | 2.007172 |
33 | 8.589.934.592 | 5.813.422.235 | 408.722.246 | 5.404.699.989 | 0.676771 | 0.047582 | 0.629190 | 2.001508 | 1.935185 | 2.006710 |
34 | 17.179.869.184 | 11.635.075.755 | 791.791.533 | 10.843.284.222 | 0.677251 | 0.046088 | 0.631162 | 2.001416 | 1.937236 | 2.006269 |
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 | 0 | 0 | 2 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 0 | 2 | 1 |
3 | 8 | 5 | 3 | 2 | 0 | 1 | 3 | 1 |
4 | 16 | 7 | 3 | 4 | 2 | 1 | 3 | 1 |
5 | 32 | 11 | 5 | 6 | 2 | 3 | 3 | 3 |
6 | 64 | 21 | 8 | 13 | 4 | 7 | 4 | 6 |
7 | 128 | 37 | 14 | 23 | 8 | 10 | 6 | 13 |
8 | 256 | 64 | 22 | 42 | 10 | 19 | 10 | 25 |
9 | 512 | 100 | 33 | 67 | 16 | 32 | 14 | 38 |
10 | 1.024 | 185 | 62 | 123 | 29 | 65 | 29 | 62 |
11 | 2.048 | 337 | 114 | 223 | 44 | 131 | 43 | 119 |
12 | 4.096 | 624 | 194 | 430 | 82 | 228 | 86 | 228 |
13 | 8.192 | 1.130 | 373 | 757 | 152 | 395 | 149 | 434 |
14 | 16.384 | 2.037 | 671 | 1.366 | 272 | 725 | 283 | 757 |
15 | 32.768 | 3.789 | 1.260 | 2.529 | 496 | 1.358 | 515 | 1.420 |
16 | 65.536 | 6.991 | 2.304 | 4.687 | 891 | 2.585 | 922 | 2.593 |
17 | 131.072 | 13.008 | 4.339 | 8.669 | 1.687 | 4.835 | 1.705 | 4.781 |
18 | 262.144 | 24.273 | 8.106 | 16.167 | 3.151 | 9.040 | 3.127 | 8.955 |
19 | 524.288 | 45.576 | 15.253 | 30.323 | 5.855 | 16.982 | 5.839 | 16.900 |
20 | 1.048.576 | 86.210 | 28.877 | 57.333 | 11.038 | 32.091 | 11.112 | 31.969 |
21 | 2.097.152 | 163.252 | 54.682 | 108.570 | 20.917 | 60.671 | 21.023 | 60.641 |
22 | 4.194.304 | 310.228 | 103.786 | 206.442 | 39.792 | 115.270 | 39.772 | 115.394 |
23 | 8.388.608 | 590.003 | 197.162 | 392.841 | 75.370 | 219.236 | 75.622 | 219.775 |
24 | 16.777.216 | 1.126.813 | 375.919 | 750.894 | 143.888 | 418.917 | 144.332 | 419.676 |
25 | 33.554.432 | 2.155.450 | 718.315 | 1.437.135 | 275.436 | 802.007 | 275.307 | 802.700 |
26 | 67.108.864 | 4.131.023 | 1.375.934 | 2.755.089 | 527.073 | 1.539.486 | 527.130 | 1.537.334 |
27 | 134.217.728 | 7.927.920 | 2.641.570 | 5.286.350 | 1.010.655 | 2.953.970 | 1.010.739 | 2.952.556 |
28 | 268.435.456 | 15.241.389 | 5.080.346 | 10.161.043 | 1.940.952 | 5.680.658 | 1.943.276 | 5.676.503 |
29 | 536.870.912 | 29.347.764 | 9.782.183 | 19.565.581 | 3.735.992 | 10.936.846 | 3.738.279 | 10.936.647 |
30 | 1.073.741.824 | 56.586.330 | 18.861.566 | 37.724.764 | 7.199.043 | 21.092.607 | 7.203.016 | 21.091.664 |
31 | 2.147.483.648 | 109.256.087 | 36.418.592 | 72.837.495 | 13.895.288 | 40.730.867 | 13.896.730 | 40.733.202 |
32 | 4.294.967.296 | 211.205.777 | 70.399.644 | 140.806.133 | 26.843.977 | 78.761.812 | 26.839.829 | 78.760.159 |
33 | 8.589.934.592 | 408.722.246 | 136.236.597 | 272.485.649 | 51.915.869 | 152.442.885 | 51.909.066 | 152.454.426 |
34 | 17.179.869.184 | 791.791.533 | 263.929.911 | 527.861.622 | 100.536.177 | 295.369.023 | 100.522.806 | 295.363.527 |
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 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 7 | 4 | 3 | 2 | 2 | 1 | 2 |
5 | 32 | 13 | 7 | 6 | 3 | 3 | 3 | 4 |
6 | 64 | 24 | 13 | 11 | 4 | 6 | 7 | 7 |
7 | 128 | 45 | 23 | 22 | 10 | 11 | 12 | 12 |
8 | 256 | 94 | 47 | 47 | 21 | 24 | 26 | 23 |
9 | 512 | 217 | 111 | 106 | 52 | 59 | 52 | 54 |
10 | 1.024 | 462 | 227 | 235 | 101 | 122 | 120 | 119 |
11 | 2.048 | 973 | 501 | 472 | 223 | 257 | 254 | 239 |
12 | 4.096 | 2.010 | 1.022 | 988 | 477 | 538 | 500 | 495 |
13 | 8.192 | 4.164 | 2.100 | 2.064 | 1.036 | 1.078 | 1.024 | 1.026 |
14 | 16.384 | 8.661 | 4.385 | 4.276 | 2.115 | 2.228 | 2.148 | 2.170 |
15 | 32.768 | 17.736 | 8.993 | 8.743 | 4.380 | 4.501 | 4.373 | 4.482 |
16 | 65.536 | 36.249 | 18.342 | 17.907 | 8.970 | 9.140 | 8.958 | 9.181 |
17 | 131.072 | 73.728 | 37.350 | 36.378 | 18.290 | 18.493 | 18.368 | 18.577 |
18 | 262.144 | 149.593 | 75.649 | 73.944 | 37.332 | 37.459 | 37.285 | 37.517 |
19 | 524.288 | 303.020 | 153.237 | 149.783 | 75.475 | 75.628 | 75.673 | 76.244 |
20 | 1.048.576 | 612.393 | 309.697 | 302.696 | 152.454 | 153.192 | 152.667 | 154.080 |
21 | 2.097.152 | 1.236.655 | 625.123 | 611.532 | 307.563 | 309.929 | 308.609 | 310.554 |
22 | 4.194.304 | 2.494.028 | 1.259.783 | 1.234.245 | 619.931 | 626.163 | 621.480 | 626.454 |
23 | 8.388.608 | 5.028.312 | 2.537.244 | 2.491.068 | 1.251.212 | 1.261.728 | 1.252.592 | 1.262.780 |
24 | 16.777.216 | 10.125.476 | 5.107.307 | 5.018.169 | 2.519.703 | 2.541.435 | 2.523.207 | 2.541.131 |
25 | 33.554.432 | 20.380.528 | 10.275.041 | 10.105.487 | 5.074.062 | 5.114.825 | 5.076.949 | 5.114.692 |
26 | 67.108.864 | 40.994.353 | 20.657.508 | 20.336.845 | 10.207.855 | 10.286.905 | 10.215.528 | 10.284.065 |
27 | 134.217.728 | 82.426.559 | 41.525.094 | 40.901.465 | 20.528.989 | 20.678.167 | 20.538.165 | 20.681.238 |
28 | 268.435.456 | 165.652.947 | 83.413.636 | 82.239.311 | 41.273.367 | 41.550.736 | 41.277.125 | 41.551.719 |
29 | 536.870.912 | 332.792.071 | 167.539.315 | 165.252.756 | 82.935.537 | 83.464.844 | 82.933.978 | 83.457.712 |
30 | 1.073.741.824 | 668.345.522 | 336.369.403 | 331.976.119 | 166.586.089 | 167.590.496 | 166.573.331 | 167.595.606 |
31 | 2.147.483.648 | 1.341.845.683 | 675.147.736 | 666.697.947 | 334.483.739 | 336.435.465 | 334.490.151 | 336.436.328 |
32 | 4.294.967.296 | 2.693.314.623 | 1.354.796.166 | 1.338.518.457 | 671.422.793 | 675.222.661 | 671.445.591 | 675.223.578 |
33 | 8.589.934.592 | 5.404.699.989 | 2.718.069.607 | 2.686.630.382 | 1.347.475.188 | 1.354.860.816 | 1.347.475.346 | 1.354.888.639 |
34 | 17.179.869.184 | 10.843.284.222 | 5.452.061.486 | 5.391.222.736 | 2.703.638.196 | 2.717.966.986 | 2.703.654.940 | 2.718.024.100 |