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-24x+17
f(0)=17
f(1)=3
f(2)=1
f(3)=23
f(4)=7
f(5)=13
f(6)=1
f(7)=1
f(8)=37
f(9)=59
f(10)=41
f(11)=1
f(12)=127
f(13)=1
f(14)=1
f(15)=1
f(16)=1
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)=43
f(29)=1
f(30)=197
f(31)=1
f(32)=1
f(33)=157
f(34)=1
f(35)=67
f(36)=449
f(37)=83
f(38)=61
f(39)=1
f(40)=73
f(41)=1
f(42)=773
f(43)=139
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=167
f(49)=1
f(50)=439
f(51)=1
f(52)=491
f(53)=1
f(54)=1637
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=347
f(60)=311
f(61)=379
f(62)=113
f(63)=1237
f(64)=859
f(65)=149
f(66)=2789
f(67)=1
f(68)=1
f(69)=223
f(70)=1
f(71)=1
f(72)=151
f(73)=599
f(74)=1
f(75)=1
f(76)=1
f(77)=683
f(78)=4229
f(79)=727
f(80)=1499
f(81)=331
f(82)=1
f(83)=1
f(84)=389
f(85)=1
f(86)=1783
f(87)=2749
f(88)=269
f(89)=967
f(90)=1
f(91)=1019
f(92)=1
f(93)=3217
f(94)=733
f(95)=1
f(96)=1
f(97)=1
f(98)=2423
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-24x+17 could be written as f(y)= y^2-127 with x=y+12
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-12
f'(x)>2x-25 with x > 11
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 | 7 | 4 | 3 | 0.700000 | 0.400000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 43 | 15 | 28 | 0.430000 | 0.150000 | 0.280000 | 6.142857 | 3.750000 | 9.333333 |
3 | 1.000 | 625 | 94 | 531 | 0.625000 | 0.094000 | 0.531000 | 14.534883 | 6.266667 | 18.964285 |
4 | 10.000 | 6.536 | 638 | 5.898 | 0.653600 | 0.063800 | 0.589800 | 10.457600 | 6.787234 | 11.107345 |
5 | 100.000 | 66.343 | 5.157 | 61.186 | 0.663430 | 0.051570 | 0.611860 | 10.150398 | 8.083072 | 10.374025 |
6 | 1.000.000 | 668.576 | 42.341 | 626.235 | 0.668576 | 0.042341 | 0.626235 | 10.077566 | 8.210394 | 10.234940 |
7 | 10.000.000 | 6.719.234 | 358.284 | 6.360.950 | 0.671923 | 0.035828 | 0.636095 | 10.050068 | 8.461869 | 10.157449 |
8 | 100.000.000 | 67.450.202 | 3.099.775 | 64.350.427 | 0.674502 | 0.030998 | 0.643504 | 10.038377 | 8.651726 | 10.116481 |
9 | 1.000.000.000 | 676.512.499 | 27.317.668 | 649.194.831 | 0.676513 | 0.027318 | 0.649195 | 10.029807 | 8.812791 | 10.088430 |
10 | 10.000.000.000 | 6.781.258.482 | 244.227.753 | 6.537.030.729 | 0.678126 | 0.024423 | 0.653703 | 10.023848 | 8.940286 | 10.069444 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 5 | 3 | 2 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.000000 | inf |
4 | 16 | 8 | 5 | 3 | 0.500000 | 0.312500 | 0.187500 | 1.600000 | 1.666667 | 1.500000 |
5 | 32 | 9 | 6 | 3 | 0.281250 | 0.187500 | 0.093750 | 1.125000 | 1.200000 | 1.000000 |
6 | 64 | 23 | 11 | 12 | 0.359375 | 0.171875 | 0.187500 | 2.555556 | 1.833333 | 4.000000 |
7 | 128 | 59 | 17 | 42 | 0.460938 | 0.132812 | 0.328125 | 2.565217 | 1.545455 | 3.500000 |
8 | 256 | 141 | 31 | 110 | 0.550781 | 0.121094 | 0.429688 | 2.389831 | 1.823529 | 2.619048 |
9 | 512 | 304 | 56 | 248 | 0.593750 | 0.109375 | 0.484375 | 2.156028 | 1.806452 | 2.254545 |
10 | 1.024 | 642 | 96 | 546 | 0.626953 | 0.093750 | 0.533203 | 2.111842 | 1.714286 | 2.201613 |
11 | 2.048 | 1.304 | 172 | 1.132 | 0.636719 | 0.083984 | 0.552734 | 2.031153 | 1.791667 | 2.073260 |
12 | 4.096 | 2.643 | 303 | 2.340 | 0.645264 | 0.073975 | 0.571289 | 2.026840 | 1.761628 | 2.067138 |
13 | 8.192 | 5.356 | 538 | 4.818 | 0.653809 | 0.065674 | 0.588135 | 2.026485 | 1.775578 | 2.058974 |
14 | 16.384 | 10.755 | 1.006 | 9.749 | 0.656433 | 0.061401 | 0.595032 | 2.008028 | 1.869888 | 2.023454 |
15 | 32.768 | 21.635 | 1.862 | 19.773 | 0.660248 | 0.056824 | 0.603424 | 2.011622 | 1.850895 | 2.028208 |
16 | 65.536 | 43.353 | 3.518 | 39.835 | 0.661514 | 0.053680 | 0.607834 | 2.003836 | 1.889366 | 2.014616 |
17 | 131.072 | 87.054 | 6.599 | 80.455 | 0.664169 | 0.050346 | 0.613823 | 2.008027 | 1.875782 | 2.019706 |
18 | 262.144 | 174.508 | 12.439 | 162.069 | 0.665695 | 0.047451 | 0.618244 | 2.004595 | 1.884983 | 2.014405 |
19 | 524.288 | 349.844 | 23.420 | 326.424 | 0.667274 | 0.044670 | 0.622604 | 2.004745 | 1.882788 | 2.014105 |
20 | 1.048.576 | 701.103 | 44.231 | 656.872 | 0.668624 | 0.042182 | 0.626442 | 2.004045 | 1.888600 | 2.012327 |
21 | 2.097.152 | 1.404.596 | 83.872 | 1.320.724 | 0.669764 | 0.039993 | 0.629770 | 2.003409 | 1.896227 | 2.010626 |
22 | 4.194.304 | 2.813.351 | 159.502 | 2.653.849 | 0.670755 | 0.038028 | 0.632727 | 2.002961 | 1.901731 | 2.009390 |
23 | 8.388.608 | 5.634.750 | 303.993 | 5.330.757 | 0.671715 | 0.036239 | 0.635476 | 2.002861 | 1.905888 | 2.008689 |
24 | 16.777.216 | 11.284.052 | 580.785 | 10.703.267 | 0.672582 | 0.034617 | 0.637964 | 2.002583 | 1.910521 | 2.007833 |
25 | 33.554.432 | 22.596.039 | 1.110.904 | 21.485.135 | 0.673414 | 0.033108 | 0.640307 | 2.002476 | 1.912763 | 2.007344 |
26 | 67.108.864 | 45.238.984 | 2.129.205 | 43.109.779 | 0.674113 | 0.031728 | 0.642386 | 2.002076 | 1.916642 | 2.006493 |
27 | 134.217.728 | 90.567.409 | 4.091.195 | 86.476.214 | 0.674780 | 0.030482 | 0.644298 | 2.001977 | 1.921466 | 2.005954 |
28 | 268.435.456 | 181.306.495 | 7.866.719 | 173.439.776 | 0.675419 | 0.029306 | 0.646114 | 2.001896 | 1.922841 | 2.005635 |
29 | 536.870.912 | 362.931.328 | 15.151.428 | 347.779.900 | 0.676012 | 0.028222 | 0.647791 | 2.001756 | 1.926016 | 2.005191 |
30 | 1.073.741.824 | 726.461.522 | 29.224.536 | 697.236.986 | 0.676570 | 0.027217 | 0.649353 | 2.001650 | 1.928831 | 2.004822 |
31 | 2.147.483.648 | 1.454.026.645 | 56.443.414 | 1.397.583.231 | 0.677084 | 0.026284 | 0.650800 | 2.001519 | 1.931371 | 2.004459 |
32 | 4.294.967.296 | 2.910.140.387 | 109.138.407 | 2.801.001.980 | 0.677570 | 0.025411 | 0.652159 | 2.001436 | 1.933590 | 2.004175 |
33 | 8.589.934.592 | 5.824.241.731 | 211.265.735 | 5.612.975.996 | 0.678031 | 0.024595 | 0.653436 | 2.001361 | 1.935760 | 2.003917 |
34 | 17.179.869.184 | 11.655.862.869 | 409.381.874 | 11.246.480.995 | 0.678461 | 0.023829 | 0.654631 | 2.001267 | 1.937758 | 2.003657 |
35 | 34.359.738.368 | 23.325.783.802 | 794.075.620 | 22.531.708.182 | 0.678870 | 0.023111 | 0.655759 | 2.001206 | 1.939694 | 2.003445 |
36 | 68.719.476.736 | 46.678.085.538 | 1.541.677.280 | 45.136.408.258 | 0.679256 | 0.022434 | 0.656821 | 2.001137 | 1.941474 | 2.003239 |
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 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
3 | 8 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
4 | 16 | 5 | 1 | 3 | 1 | 2 | 0 | 2 |
5 | 32 | 6 | 1 | 4 | 1 | 2 | 1 | 2 |
6 | 64 | 11 | 3 | 7 | 2 | 2 | 5 | 2 |
7 | 128 | 17 | 7 | 9 | 4 | 2 | 9 | 2 |
8 | 256 | 31 | 14 | 16 | 8 | 2 | 19 | 2 |
9 | 512 | 56 | 30 | 25 | 22 | 2 | 30 | 2 |
10 | 1.024 | 96 | 51 | 44 | 39 | 2 | 53 | 2 |
11 | 2.048 | 172 | 92 | 79 | 78 | 2 | 90 | 2 |
12 | 4.096 | 303 | 156 | 146 | 150 | 2 | 149 | 2 |
13 | 8.192 | 538 | 279 | 258 | 262 | 2 | 272 | 2 |
14 | 16.384 | 1.006 | 510 | 495 | 501 | 2 | 501 | 2 |
15 | 32.768 | 1.862 | 956 | 905 | 921 | 2 | 937 | 2 |
16 | 65.536 | 3.518 | 1.813 | 1.704 | 1.744 | 2 | 1.770 | 2 |
17 | 131.072 | 6.599 | 3.388 | 3.210 | 3.265 | 2 | 3.330 | 2 |
18 | 262.144 | 12.439 | 6.332 | 6.106 | 6.193 | 2 | 6.242 | 2 |
19 | 524.288 | 23.420 | 11.859 | 11.560 | 11.662 | 2 | 11.754 | 2 |
20 | 1.048.576 | 44.231 | 22.376 | 21.854 | 22.098 | 2 | 22.129 | 2 |
21 | 2.097.152 | 83.872 | 42.415 | 41.456 | 42.019 | 2 | 41.849 | 2 |
22 | 4.194.304 | 159.502 | 80.549 | 78.952 | 79.693 | 2 | 79.805 | 2 |
23 | 8.388.608 | 303.993 | 153.693 | 150.299 | 151.767 | 2 | 152.222 | 2 |
24 | 16.777.216 | 580.785 | 293.726 | 287.058 | 290.234 | 2 | 290.547 | 2 |
25 | 33.554.432 | 1.110.904 | 561.486 | 549.417 | 555.618 | 2 | 555.282 | 2 |
26 | 67.108.864 | 2.129.205 | 1.075.043 | 1.054.161 | 1.065.346 | 2 | 1.063.855 | 2 |
27 | 134.217.728 | 4.091.195 | 2.065.175 | 2.026.019 | 2.046.672 | 2 | 2.044.519 | 2 |
28 | 268.435.456 | 7.866.719 | 3.969.897 | 3.896.821 | 3.933.069 | 2 | 3.933.646 | 2 |
29 | 536.870.912 | 15.151.428 | 7.643.672 | 7.507.755 | 7.575.624 | 2 | 7.575.800 | 2 |
30 | 1.073.741.824 | 29.224.536 | 14.740.519 | 14.484.016 | 14.613.045 | 2 | 14.611.487 | 2 |
31 | 2.147.483.648 | 56.443.414 | 28.460.843 | 27.982.570 | 28.224.863 | 2 | 28.218.547 | 2 |
32 | 4.294.967.296 | 109.138.407 | 55.019.565 | 54.118.841 | 54.571.847 | 2 | 54.566.556 | 2 |
33 | 8.589.934.592 | 211.265.735 | 106.475.177 | 104.790.557 | 105.641.874 | 2 | 105.623.857 | 2 |
34 | 17.179.869.184 | 409.381.874 | 206.273.098 | 203.108.775 | 204.694.599 | 2 | 204.687.271 | 2 |
35 | 34.359.738.368 | 794.075.620 | 400.022.281 | 394.053.338 | 397.035.543 | 2 | 397.040.073 | 2 |
36 | 68.719.476.736 | 1.541.677.280 | 776.478.550 | 765.198.729 | 770.843.022 | 2 | 770.834.254 | 2 |
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 | 2 | 2 | 0 | 0 | 0 | 2 | 0 |
4 | 16 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
5 | 32 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
6 | 64 | 12 | 6 | 6 | 1 | 6 | 2 | 3 |
7 | 128 | 42 | 21 | 21 | 4 | 16 | 10 | 12 |
8 | 256 | 110 | 51 | 59 | 16 | 39 | 23 | 32 |
9 | 512 | 248 | 117 | 131 | 50 | 73 | 50 | 75 |
10 | 1.024 | 546 | 267 | 279 | 115 | 154 | 112 | 165 |
11 | 2.048 | 1.132 | 570 | 562 | 230 | 321 | 246 | 335 |
12 | 4.096 | 2.340 | 1.173 | 1.167 | 478 | 654 | 516 | 692 |
13 | 8.192 | 4.818 | 2.413 | 2.405 | 1.021 | 1.314 | 1.103 | 1.380 |
14 | 16.384 | 9.749 | 4.866 | 4.883 | 2.127 | 2.679 | 2.215 | 2.728 |
15 | 32.768 | 19.773 | 9.832 | 9.941 | 4.368 | 5.459 | 4.480 | 5.466 |
16 | 65.536 | 39.835 | 19.887 | 19.948 | 9.017 | 10.874 | 9.043 | 10.901 |
17 | 131.072 | 80.455 | 40.165 | 40.290 | 18.325 | 21.960 | 18.347 | 21.823 |
18 | 262.144 | 162.069 | 80.818 | 81.251 | 37.341 | 43.626 | 37.267 | 43.835 |
19 | 524.288 | 326.424 | 163.105 | 163.319 | 75.803 | 87.542 | 75.515 | 87.564 |
20 | 1.048.576 | 656.872 | 328.289 | 328.583 | 152.919 | 175.420 | 152.957 | 175.576 |
21 | 2.097.152 | 1.320.724 | 659.698 | 661.026 | 308.518 | 351.729 | 308.392 | 352.085 |
22 | 4.194.304 | 2.653.849 | 1.327.229 | 1.326.620 | 621.877 | 704.340 | 622.222 | 705.410 |
23 | 8.388.608 | 5.330.757 | 2.666.281 | 2.664.476 | 1.255.422 | 1.409.949 | 1.255.214 | 1.410.172 |
24 | 16.777.216 | 10.703.267 | 5.352.515 | 5.350.752 | 2.527.868 | 2.823.655 | 2.527.105 | 2.824.639 |
25 | 33.554.432 | 21.485.135 | 10.744.046 | 10.741.089 | 5.086.651 | 5.656.341 | 5.086.952 | 5.655.191 |
26 | 67.108.864 | 43.109.779 | 21.561.380 | 21.548.399 | 10.232.552 | 11.323.265 | 10.233.449 | 11.320.513 |
27 | 134.217.728 | 86.476.214 | 43.245.996 | 43.230.218 | 20.572.756 | 22.664.179 | 20.573.508 | 22.665.771 |
28 | 268.435.456 | 173.439.776 | 86.736.492 | 86.703.284 | 41.354.829 | 45.365.186 | 41.351.153 | 45.368.608 |
29 | 536.870.912 | 347.779.900 | 173.908.912 | 173.870.988 | 83.087.447 | 90.806.442 | 83.088.496 | 90.797.515 |
30 | 1.073.741.824 | 697.236.986 | 348.674.312 | 348.562.674 | 166.873.097 | 181.754.247 | 166.873.851 | 181.735.791 |
31 | 2.147.483.648 | 1.397.583.231 | 698.875.757 | 698.707.474 | 335.021.768 | 363.756.770 | 335.057.582 | 363.747.111 |
32 | 4.294.967.296 | 2.801.001.980 | 1.400.678.266 | 1.400.323.714 | 672.496.996 | 728.009.079 | 672.528.911 | 727.966.994 |
33 | 8.589.934.592 | 5.612.975.996 | 2.806.828.219 | 2.806.147.777 | 1.349.561.765 | 1.456.910.951 | 1.349.604.494 | 1.456.898.786 |
34 | 17.179.869.184 | 11.246.480.995 | 5.623.910.791 | 5.622.570.204 | 2.707.711.966 | 2.915.579.843 | 2.707.681.570 | 2.915.507.616 |
35 | 34.359.738.368 | 22.531.708.182 | 11.267.124.446 | 11.264.583.736 | 5.431.436.203 | 5.834.498.403 | 5.431.389.569 | 5.834.384.007 |
36 | 68.719.476.736 | 45.136.408.258 | 22.570.637.130 | 22.565.771.128 | 10.893.134.567 | 11.675.144.578 | 10.893.070.291 | 11.675.058.822 |