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-32x+17
f(0)=17
f(1)=7
f(2)=43
f(3)=5
f(4)=19
f(5)=59
f(6)=139
f(7)=79
f(8)=1
f(9)=1
f(10)=29
f(11)=107
f(12)=223
f(13)=23
f(14)=47
f(15)=1
f(16)=239
f(17)=1
f(18)=1
f(19)=1
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=61
f(36)=1
f(37)=101
f(38)=1
f(39)=1
f(40)=337
f(41)=193
f(42)=1
f(43)=1
f(44)=109
f(45)=1
f(46)=661
f(47)=1
f(48)=157
f(49)=1
f(50)=131
f(51)=1
f(52)=151
f(53)=113
f(54)=241
f(55)=641
f(56)=1361
f(57)=103
f(58)=1
f(59)=1
f(60)=1697
f(61)=1
f(62)=1877
f(63)=197
f(64)=1
f(65)=1
f(66)=1
f(67)=1181
f(68)=1
f(69)=257
f(70)=2677
f(71)=199
f(72)=2897
f(73)=1
f(74)=1
f(75)=1621
f(76)=3361
f(77)=1741
f(78)=1
f(79)=373
f(80)=1
f(81)=1993
f(82)=179
f(83)=1
f(84)=877
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=509
f(90)=5237
f(91)=2693
f(92)=1
f(93)=569
f(94)=167
f(95)=3001
f(96)=1
f(97)=1
f(98)=1297
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-32x+17 could be written as f(y)= y^2-239 with x=y+16
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-16
f'(x)>2x-33 with x > 15
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 | 8 | 6 | 2 | 0.800000 | 0.600000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 46 | 27 | 19 | 0.460000 | 0.270000 | 0.190000 | 5.750000 | 4.500000 | 9.500000 |
3 | 1.000 | 630 | 172 | 458 | 0.630000 | 0.172000 | 0.458000 | 13.695652 | 6.370370 | 24.105263 |
4 | 10.000 | 6.660 | 1.262 | 5.398 | 0.666000 | 0.126200 | 0.539800 | 10.571428 | 7.337209 | 11.786026 |
5 | 100.000 | 67.353 | 9.576 | 57.777 | 0.673530 | 0.095760 | 0.577770 | 10.113063 | 7.587955 | 10.703408 |
6 | 1.000.000 | 677.594 | 77.740 | 599.854 | 0.677594 | 0.077740 | 0.599854 | 10.060339 | 8.118212 | 10.382228 |
7 | 10.000.000 | 6.797.617 | 656.146 | 6.141.471 | 0.679762 | 0.065615 | 0.614147 | 10.031991 | 8.440263 | 10.238276 |
8 | 100.000.000 | 68.131.355 | 5.679.812 | 62.451.543 | 0.681314 | 0.056798 | 0.624515 | 10.022829 | 8.656323 | 10.168825 |
9 | 1.000.000.000 | 682.563.627 | 50.067.770 | 632.495.857 | 0.682564 | 0.050068 | 0.632496 | 10.018349 | 8.815040 | 10.127786 |
10 | 10.000.000.000 | 6.835.692.220 | 447.636.697 | 6.388.055.523 | 0.683569 | 0.044764 | 0.638806 | 10.014732 | 8.940617 | 10.099758 |
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 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.000000 | inf |
3 | 8 | 7 | 6 | 1 | 0.875000 | 0.750000 | 0.125000 | 1.750000 | 2.000000 | 1.000000 |
4 | 16 | 12 | 9 | 3 | 0.750000 | 0.562500 | 0.187500 | 1.714286 | 1.500000 | 3.000000 |
5 | 32 | 12 | 9 | 3 | 0.375000 | 0.281250 | 0.093750 | 1.000000 | 1.000000 | 1.000000 |
6 | 64 | 27 | 17 | 10 | 0.421875 | 0.265625 | 0.156250 | 2.250000 | 1.888889 | 3.333333 |
7 | 128 | 62 | 31 | 31 | 0.484375 | 0.242188 | 0.242188 | 2.296296 | 1.823529 | 3.100000 |
8 | 256 | 141 | 57 | 84 | 0.550781 | 0.222656 | 0.328125 | 2.274194 | 1.838710 | 2.709677 |
9 | 512 | 303 | 98 | 205 | 0.591797 | 0.191406 | 0.400391 | 2.148936 | 1.719298 | 2.440476 |
10 | 1.024 | 647 | 179 | 468 | 0.631836 | 0.174805 | 0.457031 | 2.135314 | 1.826531 | 2.282927 |
11 | 2.048 | 1.327 | 327 | 1.000 | 0.647949 | 0.159668 | 0.488281 | 2.051005 | 1.826816 | 2.136752 |
12 | 4.096 | 2.698 | 591 | 2.107 | 0.658691 | 0.144287 | 0.514404 | 2.033158 | 1.807339 | 2.107000 |
13 | 8.192 | 5.441 | 1.055 | 4.386 | 0.664185 | 0.128784 | 0.535400 | 2.016679 | 1.785110 | 2.081633 |
14 | 16.384 | 10.960 | 1.936 | 9.024 | 0.668945 | 0.118164 | 0.550781 | 2.014336 | 1.835071 | 2.057456 |
15 | 32.768 | 22.001 | 3.542 | 18.459 | 0.671417 | 0.108093 | 0.563324 | 2.007390 | 1.829545 | 2.045545 |
16 | 65.536 | 44.100 | 6.526 | 37.574 | 0.672913 | 0.099579 | 0.573334 | 2.004454 | 1.842462 | 2.035538 |
17 | 131.072 | 88.325 | 12.210 | 76.115 | 0.673866 | 0.093155 | 0.580711 | 2.002835 | 1.870978 | 2.025736 |
18 | 262.144 | 177.171 | 22.836 | 154.335 | 0.675854 | 0.087112 | 0.588741 | 2.005899 | 1.870270 | 2.027656 |
19 | 524.288 | 354.820 | 43.033 | 311.787 | 0.676765 | 0.082079 | 0.594687 | 2.002698 | 1.884437 | 2.020196 |
20 | 1.048.576 | 710.660 | 81.189 | 629.471 | 0.677738 | 0.077428 | 0.600310 | 2.002875 | 1.886668 | 2.018914 |
21 | 2.097.152 | 1.422.749 | 153.805 | 1.268.944 | 0.678420 | 0.073340 | 0.605080 | 2.002011 | 1.894407 | 2.015890 |
22 | 4.194.304 | 2.847.973 | 292.265 | 2.555.708 | 0.679010 | 0.069681 | 0.609328 | 2.001740 | 1.900231 | 2.014043 |
23 | 8.388.608 | 5.700.980 | 557.213 | 5.143.767 | 0.679610 | 0.066425 | 0.613185 | 2.001768 | 1.906533 | 2.012658 |
24 | 16.777.216 | 11.410.383 | 1.064.356 | 10.346.027 | 0.680112 | 0.063441 | 0.616671 | 2.001477 | 1.910142 | 2.011372 |
25 | 33.554.432 | 22.836.604 | 2.036.788 | 20.799.816 | 0.680584 | 0.060701 | 0.619883 | 2.001388 | 1.913634 | 2.010416 |
26 | 67.108.864 | 45.704.999 | 3.902.563 | 41.802.436 | 0.681058 | 0.058153 | 0.622905 | 2.001392 | 1.916038 | 2.009750 |
27 | 134.217.728 | 91.468.860 | 7.495.197 | 83.973.663 | 0.681496 | 0.055844 | 0.625653 | 2.001288 | 1.920583 | 2.008822 |
28 | 268.435.456 | 183.039.348 | 14.418.560 | 168.620.788 | 0.681875 | 0.053713 | 0.628161 | 2.001111 | 1.923707 | 2.008020 |
29 | 536.870.912 | 366.281.008 | 27.772.959 | 338.508.049 | 0.682252 | 0.051731 | 0.630520 | 2.001105 | 1.926195 | 2.007511 |
30 | 1.073.741.824 | 732.934.036 | 53.563.613 | 679.370.423 | 0.682598 | 0.049885 | 0.632713 | 2.001015 | 1.928625 | 2.006955 |
31 | 2.147.483.648 | 1.466.569.088 | 103.443.438 | 1.363.125.650 | 0.682924 | 0.048170 | 0.634755 | 2.000957 | 1.931226 | 2.006454 |
32 | 4.294.967.296 | 2.934.422.501 | 200.037.541 | 2.734.384.960 | 0.683223 | 0.046575 | 0.636649 | 2.000876 | 1.933787 | 2.005967 |
33 | 8.589.934.592 | 5.871.303.702 | 387.218.399 | 5.484.085.303 | 0.683510 | 0.045078 | 0.638432 | 2.000838 | 1.935729 | 2.005601 |
34 | 17.179.869.184 | 11.747.220.702 | 750.354.905 | 10.996.865.797 | 0.683778 | 0.043676 | 0.640102 | 2.000786 | 1.937808 | 2.005233 |
35 | 34.359.738.368 | 23.503.252.088 | 1.455.383.260 | 22.047.868.828 | 0.684035 | 0.042357 | 0.641677 | 2.000750 | 1.939593 | 2.004923 |
36 | 68.719.476.736 | 47.023.088.753 | 2.825.578.389 | 44.197.510.364 | 0.684276 | 0.041118 | 0.643158 | 2.000706 | 1.941467 | 2.004616 |
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 | 3 | 2 | 1 | 1 | 1 | 0 | 1 |
3 | 8 | 6 | 4 | 2 | 1 | 3 | 0 | 2 |
4 | 16 | 9 | 5 | 4 | 1 | 4 | 0 | 4 |
5 | 32 | 9 | 5 | 4 | 1 | 4 | 0 | 4 |
6 | 64 | 17 | 8 | 9 | 6 | 4 | 3 | 4 |
7 | 128 | 31 | 16 | 15 | 11 | 4 | 12 | 4 |
8 | 256 | 57 | 28 | 29 | 28 | 4 | 21 | 4 |
9 | 512 | 98 | 51 | 47 | 52 | 4 | 38 | 4 |
10 | 1.024 | 179 | 97 | 82 | 92 | 4 | 79 | 4 |
11 | 2.048 | 327 | 170 | 157 | 165 | 4 | 154 | 4 |
12 | 4.096 | 591 | 293 | 298 | 299 | 4 | 284 | 4 |
13 | 8.192 | 1.055 | 521 | 534 | 519 | 4 | 528 | 4 |
14 | 16.384 | 1.936 | 963 | 973 | 948 | 4 | 980 | 4 |
15 | 32.768 | 3.542 | 1.771 | 1.771 | 1.743 | 4 | 1.791 | 4 |
16 | 65.536 | 6.526 | 3.256 | 3.270 | 3.266 | 4 | 3.252 | 4 |
17 | 131.072 | 12.210 | 6.129 | 6.081 | 6.078 | 4 | 6.124 | 4 |
18 | 262.144 | 22.836 | 11.488 | 11.348 | 11.372 | 4 | 11.456 | 4 |
19 | 524.288 | 43.033 | 21.523 | 21.510 | 21.528 | 4 | 21.497 | 4 |
20 | 1.048.576 | 81.189 | 40.723 | 40.466 | 40.635 | 4 | 40.546 | 4 |
21 | 2.097.152 | 153.805 | 77.081 | 76.724 | 77.041 | 4 | 76.756 | 4 |
22 | 4.194.304 | 292.265 | 146.593 | 145.672 | 146.249 | 4 | 146.008 | 4 |
23 | 8.388.608 | 557.213 | 279.952 | 277.261 | 278.883 | 4 | 278.322 | 4 |
24 | 16.777.216 | 1.064.356 | 534.403 | 529.953 | 532.082 | 4 | 532.266 | 4 |
25 | 33.554.432 | 2.036.788 | 1.022.360 | 1.014.428 | 1.018.097 | 4 | 1.018.683 | 4 |
26 | 67.108.864 | 3.902.563 | 1.958.795 | 1.943.768 | 1.950.524 | 4 | 1.952.031 | 4 |
27 | 134.217.728 | 7.495.197 | 3.760.411 | 3.734.786 | 3.747.223 | 4 | 3.747.966 | 4 |
28 | 268.435.456 | 14.418.560 | 7.232.847 | 7.185.713 | 7.207.825 | 4 | 7.210.727 | 4 |
29 | 536.870.912 | 27.772.959 | 13.928.763 | 13.844.196 | 13.886.869 | 4 | 13.886.082 | 4 |
30 | 1.073.741.824 | 53.563.613 | 26.861.507 | 26.702.106 | 26.783.455 | 4 | 26.780.150 | 4 |
31 | 2.147.483.648 | 103.443.438 | 51.874.787 | 51.568.651 | 51.723.356 | 4 | 51.720.074 | 4 |
32 | 4.294.967.296 | 200.037.541 | 100.302.262 | 99.735.279 | 100.025.682 | 4 | 100.011.851 | 4 |
33 | 8.589.934.592 | 387.218.399 | 194.132.792 | 193.085.607 | 193.616.752 | 4 | 193.601.639 | 4 |
34 | 17.179.869.184 | 750.354.905 | 376.154.645 | 374.200.260 | 375.194.001 | 4 | 375.160.896 | 4 |
35 | 34.359.738.368 | 1.455.383.260 | 729.527.700 | 725.855.560 | 727.724.409 | 4 | 727.658.843 | 4 |
36 | 68.719.476.736 | 2.825.578.389 | 1.416.273.256 | 1.409.305.133 | 1.412.812.150 | 4 | 1.412.766.231 | 4 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
5 | 32 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
6 | 64 | 10 | 5 | 5 | 2 | 2 | 4 | 2 |
7 | 128 | 31 | 16 | 15 | 9 | 7 | 10 | 5 |
8 | 256 | 84 | 45 | 39 | 23 | 23 | 25 | 13 |
9 | 512 | 205 | 108 | 97 | 54 | 53 | 53 | 45 |
10 | 1.024 | 468 | 228 | 240 | 116 | 117 | 124 | 111 |
11 | 2.048 | 1.000 | 497 | 503 | 243 | 255 | 261 | 241 |
12 | 4.096 | 2.107 | 1.051 | 1.056 | 497 | 555 | 537 | 518 |
13 | 8.192 | 4.386 | 2.188 | 2.198 | 1.061 | 1.141 | 1.087 | 1.097 |
14 | 16.384 | 9.024 | 4.487 | 4.537 | 2.183 | 2.287 | 2.276 | 2.278 |
15 | 32.768 | 18.459 | 9.159 | 9.300 | 4.485 | 4.656 | 4.663 | 4.655 |
16 | 65.536 | 37.574 | 18.812 | 18.762 | 9.208 | 9.485 | 9.364 | 9.517 |
17 | 131.072 | 76.115 | 37.997 | 38.118 | 18.918 | 19.209 | 18.828 | 19.160 |
18 | 262.144 | 154.335 | 77.247 | 77.088 | 38.524 | 38.693 | 38.208 | 38.910 |
19 | 524.288 | 311.787 | 155.756 | 156.031 | 77.366 | 78.368 | 77.822 | 78.231 |
20 | 1.048.576 | 629.471 | 314.410 | 315.061 | 156.658 | 157.817 | 156.896 | 158.100 |
21 | 2.097.152 | 1.268.944 | 634.066 | 634.878 | 316.178 | 318.285 | 315.712 | 318.769 |
22 | 4.194.304 | 2.555.708 | 1.276.659 | 1.279.049 | 636.702 | 641.236 | 636.289 | 641.481 |
23 | 8.388.608 | 5.143.767 | 2.570.761 | 2.573.006 | 1.282.936 | 1.288.956 | 1.282.409 | 1.289.466 |
24 | 16.777.216 | 10.346.027 | 5.171.736 | 5.174.291 | 2.579.864 | 2.594.151 | 2.578.880 | 2.593.132 |
25 | 33.554.432 | 20.799.816 | 10.399.764 | 10.400.052 | 5.188.223 | 5.212.558 | 5.188.007 | 5.211.028 |
26 | 67.108.864 | 41.802.436 | 20.902.471 | 20.899.965 | 10.432.082 | 10.471.595 | 10.430.700 | 10.468.059 |
27 | 134.217.728 | 83.973.663 | 41.985.376 | 41.988.287 | 20.963.992 | 21.027.292 | 20.960.832 | 21.021.547 |
28 | 268.435.456 | 168.620.788 | 84.301.739 | 84.319.049 | 42.097.166 | 42.216.717 | 42.090.913 | 42.215.992 |
29 | 536.870.912 | 338.508.049 | 169.236.060 | 169.271.989 | 84.528.832 | 84.737.430 | 84.516.005 | 84.725.782 |
30 | 1.073.741.824 | 679.370.423 | 339.659.502 | 339.710.921 | 169.666.707 | 170.036.289 | 169.633.689 | 170.033.738 |
31 | 2.147.483.648 | 1.363.125.650 | 681.518.338 | 681.607.312 | 340.443.975 | 341.125.607 | 340.412.718 | 341.143.350 |
32 | 4.294.967.296 | 2.734.384.960 | 1.367.096.022 | 1.367.288.938 | 682.935.623 | 684.273.869 | 682.913.859 | 684.261.609 |
33 | 8.589.934.592 | 5.484.085.303 | 2.741.842.190 | 2.742.243.113 | 1.369.797.617 | 1.372.271.637 | 1.369.762.493 | 1.372.253.556 |
34 | 17.179.869.184 | 10.996.865.797 | 5.498.103.302 | 5.498.762.495 | 2.746.902.266 | 2.751.541.026 | 2.746.907.668 | 2.751.514.837 |
35 | 34.359.738.368 | 22.047.868.828 | 11.023.250.231 | 11.024.618.597 | 5.507.697.892 | 5.516.293.112 | 5.507.684.220 | 5.516.193.604 |
36 | 68.719.476.736 | 44.197.510.364 | 22.097.434.160 | 22.100.076.204 | 11.041.448.882 | 11.057.348.470 | 11.041.430.132 | 11.057.282.880 |