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-112x+23
f(0)=23
f(1)=11
f(2)=197
f(3)=19
f(4)=409
f(5)=1
f(6)=613
f(7)=89
f(8)=809
f(9)=113
f(10)=997
f(11)=17
f(12)=107
f(13)=79
f(14)=71
f(15)=179
f(16)=1
f(17)=199
f(18)=1669
f(19)=109
f(20)=1
f(21)=59
f(22)=103
f(23)=1
f(24)=2089
f(25)=269
f(26)=2213
f(27)=1
f(28)=137
f(29)=149
f(30)=2437
f(31)=311
f(32)=43
f(33)=1
f(34)=239
f(35)=167
f(36)=2713
f(37)=1
f(38)=2789
f(39)=353
f(40)=2857
f(41)=1
f(42)=2917
f(43)=1
f(44)=2969
f(45)=1
f(46)=131
f(47)=379
f(48)=3049
f(49)=383
f(50)=181
f(51)=193
f(52)=163
f(53)=97
f(54)=3109
f(55)=389
f(56)=283
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-112x+23 could be written as f(y)= y^2-3113 with x=y+56
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-56
f'(x)>2x-113 with x > 56
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 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 44 | 17 | 27 | 0.440000 | 0.170000 | 0.440000 | 4.400000 | 2.833333 | 6.750000 |
3 | 1.000 | 606 | 173 | 433 | 0.606000 | 0.173000 | 0.606000 | 13.772727 | 10.176471 | 16.037037 |
4 | 10.000 | 6.634 | 1.350 | 5.284 | 0.663400 | 0.135000 | 0.663400 | 10.947195 | 7.803468 | 12.203234 |
5 | 100.000 | 67.844 | 10.227 | 57.617 | 0.678440 | 0.102270 | 0.678440 | 10.226711 | 7.575555 | 10.904050 |
6 | 1.000.000 | 681.996 | 83.315 | 598.681 | 0.681996 | 0.083315 | 0.681996 | 10.052414 | 8.146573 | 10.390700 |
7 | 10.000.000 | 6.834.994 | 704.975 | 6.130.019 | 0.683499 | 0.070497 | 0.683499 | 10.022044 | 8.461561 | 10.239207 |
8 | 100.000.000 | 68.462.047 | 6.110.491 | 62.351.556 | 0.684620 | 0.061105 | 0.684620 | 10.016402 | 8.667670 | 10.171511 |
9 | 1.000.000.000 | 685.547.172 | 53.931.389 | 631.615.783 | 0.685547 | 0.053931 | 0.685547 | 10.013536 | 8.826032 | 10.129912 |
10 | 10.000.000.000 | 6.862.901.912 | 482.701.408 | 6.380.200.504 | 0.686290 | 0.048270 | 0.686290 | 10.010838 | 8.950287 | 10.101395 |
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 | 2 | 1 | 1.500000 | 1.000000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 1.600000 | 1.666667 | 1.500000 |
4 | 16 | 14 | 6 | 8 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.200000 | 2.666667 |
5 | 32 | 26 | 10 | 16 | 0.812500 | 0.312500 | 0.500000 | 1.857143 | 1.666667 | 2.000000 |
6 | 64 | 44 | 17 | 27 | 0.687500 | 0.265625 | 0.421875 | 1.692308 | 1.700000 | 1.687500 |
7 | 128 | 49 | 22 | 27 | 0.382812 | 0.171875 | 0.210938 | 1.113636 | 1.294118 | 1.000000 |
8 | 256 | 125 | 53 | 72 | 0.488281 | 0.207031 | 0.281250 | 2.551020 | 2.409091 | 2.666667 |
9 | 512 | 278 | 101 | 177 | 0.542969 | 0.197266 | 0.345703 | 2.224000 | 1.905660 | 2.458333 |
10 | 1.024 | 620 | 178 | 442 | 0.605469 | 0.173828 | 0.431641 | 2.230216 | 1.762376 | 2.497175 |
11 | 2.048 | 1.305 | 332 | 973 | 0.637207 | 0.162109 | 0.475098 | 2.104839 | 1.865169 | 2.201357 |
12 | 4.096 | 2.661 | 604 | 2.057 | 0.649658 | 0.147461 | 0.502197 | 2.039080 | 1.819277 | 2.114080 |
13 | 8.192 | 5.400 | 1.130 | 4.270 | 0.659180 | 0.137939 | 0.521240 | 2.029312 | 1.870861 | 2.075839 |
14 | 16.384 | 10.938 | 2.059 | 8.879 | 0.667603 | 0.125671 | 0.541931 | 2.025556 | 1.822124 | 2.079391 |
15 | 32.768 | 22.053 | 3.808 | 18.245 | 0.673004 | 0.116211 | 0.556793 | 2.016182 | 1.849442 | 2.054848 |
16 | 65.536 | 44.337 | 7.029 | 37.308 | 0.676529 | 0.107254 | 0.569275 | 2.010475 | 1.845851 | 2.044834 |
17 | 131.072 | 88.986 | 13.044 | 75.942 | 0.678909 | 0.099518 | 0.579391 | 2.007037 | 1.855741 | 2.035542 |
18 | 262.144 | 178.297 | 24.517 | 153.780 | 0.680149 | 0.093525 | 0.586624 | 2.003652 | 1.879562 | 2.024966 |
19 | 524.288 | 357.179 | 45.953 | 311.226 | 0.681265 | 0.087648 | 0.593616 | 2.003281 | 1.874332 | 2.023839 |
20 | 1.048.576 | 715.026 | 86.953 | 628.073 | 0.681902 | 0.082925 | 0.598977 | 2.001870 | 1.892216 | 2.018061 |
21 | 2.097.152 | 1.431.189 | 164.948 | 1.266.241 | 0.682444 | 0.078653 | 0.603791 | 2.001590 | 1.896979 | 2.016073 |
22 | 4.194.304 | 2.864.446 | 314.037 | 2.550.409 | 0.682937 | 0.074872 | 0.608065 | 2.001445 | 1.903854 | 2.014158 |
23 | 8.388.608 | 5.732.455 | 598.482 | 5.133.973 | 0.683362 | 0.071345 | 0.612017 | 2.001244 | 1.905769 | 2.013000 |
24 | 16.777.216 | 11.470.824 | 1.143.406 | 10.327.418 | 0.683714 | 0.068152 | 0.615562 | 2.001032 | 1.910510 | 2.011584 |
25 | 33.554.432 | 22.954.485 | 2.188.577 | 20.765.908 | 0.684097 | 0.065225 | 0.618872 | 2.001119 | 1.914086 | 2.010755 |
26 | 67.108.864 | 45.932.019 | 4.197.770 | 41.734.249 | 0.684440 | 0.062552 | 0.621889 | 2.001004 | 1.918036 | 2.009748 |
27 | 134.217.728 | 91.905.364 | 8.065.246 | 83.840.118 | 0.684748 | 0.060091 | 0.624658 | 2.000900 | 1.921317 | 2.008904 |
28 | 268.435.456 | 183.887.593 | 15.520.579 | 168.367.014 | 0.685035 | 0.057819 | 0.627216 | 2.000837 | 1.924378 | 2.008191 |
29 | 536.870.912 | 367.927.832 | 29.906.120 | 338.021.712 | 0.685319 | 0.055704 | 0.629614 | 2.000830 | 1.926869 | 2.007648 |
30 | 1.073.741.824 | 736.127.876 | 57.700.298 | 678.427.578 | 0.685573 | 0.053738 | 0.631835 | 2.000740 | 1.929381 | 2.007053 |
31 | 2.147.483.648 | 1.472.770.960 | 111.474.837 | 1.361.296.123 | 0.685812 | 0.051910 | 0.633903 | 2.000700 | 1.931963 | 2.006546 |
32 | 4.294.967.296 | 2.946.510.725 | 215.620.202 | 2.730.890.523 | 0.686038 | 0.050203 | 0.635835 | 2.000658 | 1.934250 | 2.006096 |
33 | 8.589.934.592 | 5.894.805.731 | 417.529.361 | 5.477.276.370 | 0.686246 | 0.048607 | 0.637639 | 2.000605 | 1.936411 | 2.005674 |
34 | 17.179.869.184 | 11.792.981.275 | 809.289.717 | 10.983.691.558 | 0.686442 | 0.047107 | 0.639335 | 2.000572 | 1.938282 | 2.005320 |
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 | 2 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 2 | 1 | 0 | 1 | 1 |
3 | 8 | 5 | 2 | 3 | 2 | 0 | 2 | 1 |
4 | 16 | 6 | 3 | 3 | 2 | 0 | 3 | 1 |
5 | 32 | 10 | 6 | 4 | 3 | 0 | 6 | 1 |
6 | 64 | 17 | 11 | 6 | 7 | 0 | 9 | 1 |
7 | 128 | 22 | 12 | 10 | 7 | 2 | 9 | 4 |
8 | 256 | 53 | 24 | 29 | 7 | 17 | 9 | 20 |
9 | 512 | 101 | 38 | 63 | 7 | 41 | 9 | 44 |
10 | 1.024 | 178 | 65 | 113 | 7 | 81 | 9 | 81 |
11 | 2.048 | 332 | 119 | 213 | 7 | 162 | 9 | 154 |
12 | 4.096 | 604 | 213 | 391 | 7 | 293 | 9 | 295 |
13 | 8.192 | 1.130 | 382 | 748 | 7 | 559 | 9 | 555 |
14 | 16.384 | 2.059 | 686 | 1.373 | 7 | 1.026 | 9 | 1.017 |
15 | 32.768 | 3.808 | 1.254 | 2.554 | 7 | 1.902 | 9 | 1.890 |
16 | 65.536 | 7.029 | 2.306 | 4.723 | 7 | 3.529 | 9 | 3.484 |
17 | 131.072 | 13.044 | 4.352 | 8.692 | 7 | 6.543 | 9 | 6.485 |
18 | 262.144 | 24.517 | 8.173 | 16.344 | 7 | 12.281 | 9 | 12.220 |
19 | 524.288 | 45.953 | 15.279 | 30.674 | 7 | 22.977 | 9 | 22.960 |
20 | 1.048.576 | 86.953 | 28.903 | 58.050 | 7 | 43.461 | 9 | 43.476 |
21 | 2.097.152 | 164.948 | 54.988 | 109.960 | 7 | 82.445 | 9 | 82.487 |
22 | 4.194.304 | 314.037 | 104.734 | 209.303 | 7 | 157.077 | 9 | 156.944 |
23 | 8.388.608 | 598.482 | 199.757 | 398.725 | 7 | 299.558 | 9 | 298.908 |
24 | 16.777.216 | 1.143.406 | 381.471 | 761.935 | 7 | 572.131 | 9 | 571.259 |
25 | 33.554.432 | 2.188.577 | 729.695 | 1.458.882 | 7 | 1.094.716 | 9 | 1.093.845 |
26 | 67.108.864 | 4.197.770 | 1.399.772 | 2.797.998 | 7 | 2.099.419 | 9 | 2.098.335 |
27 | 134.217.728 | 8.065.246 | 2.689.497 | 5.375.749 | 7 | 4.033.366 | 9 | 4.031.864 |
28 | 268.435.456 | 15.520.579 | 5.175.927 | 10.344.652 | 7 | 7.762.176 | 9 | 7.758.387 |
29 | 536.870.912 | 29.906.120 | 9.971.125 | 19.934.995 | 7 | 14.956.415 | 9 | 14.949.689 |
30 | 1.073.741.824 | 57.700.298 | 19.232.678 | 38.467.620 | 7 | 28.853.183 | 9 | 28.847.099 |
31 | 2.147.483.648 | 111.474.837 | 37.154.496 | 74.320.341 | 7 | 55.736.988 | 9 | 55.737.833 |
32 | 4.294.967.296 | 215.620.202 | 71.866.766 | 143.753.436 | 7 | 107.813.703 | 9 | 107.806.483 |
33 | 8.589.934.592 | 417.529.361 | 139.170.297 | 278.359.064 | 7 | 208.761.631 | 9 | 208.767.714 |
34 | 17.179.869.184 | 809.289.717 | 269.763.123 | 539.526.594 | 7 | 404.634.055 | 9 | 404.655.646 |
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 | 1 | 1 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 1 | 2 | 1 | 2 | 0 | 0 |
4 | 16 | 8 | 2 | 6 | 2 | 4 | 0 | 2 |
5 | 32 | 16 | 5 | 11 | 3 | 5 | 3 | 5 |
6 | 64 | 27 | 10 | 17 | 5 | 9 | 5 | 8 |
7 | 128 | 27 | 10 | 17 | 5 | 9 | 5 | 8 |
8 | 256 | 72 | 34 | 38 | 17 | 18 | 19 | 18 |
9 | 512 | 177 | 90 | 87 | 39 | 45 | 52 | 41 |
10 | 1.024 | 442 | 224 | 218 | 108 | 100 | 134 | 100 |
11 | 2.048 | 973 | 509 | 464 | 261 | 213 | 273 | 226 |
12 | 4.096 | 2.057 | 1.067 | 990 | 545 | 466 | 562 | 484 |
13 | 8.192 | 4.270 | 2.211 | 2.059 | 1.109 | 1.000 | 1.167 | 994 |
14 | 16.384 | 8.879 | 4.608 | 4.271 | 2.344 | 2.066 | 2.370 | 2.099 |
15 | 32.768 | 18.245 | 9.503 | 8.742 | 4.766 | 4.280 | 4.849 | 4.350 |
16 | 65.536 | 37.308 | 19.220 | 18.088 | 9.553 | 8.878 | 9.971 | 8.906 |
17 | 131.072 | 75.942 | 39.117 | 36.825 | 19.494 | 18.270 | 19.951 | 18.227 |
18 | 262.144 | 153.780 | 79.093 | 74.687 | 39.926 | 36.881 | 40.016 | 36.957 |
19 | 524.288 | 311.226 | 159.452 | 151.774 | 80.464 | 74.895 | 81.059 | 74.808 |
20 | 1.048.576 | 628.073 | 321.263 | 306.810 | 162.287 | 151.405 | 162.754 | 151.627 |
21 | 2.097.152 | 1.266.241 | 646.765 | 619.476 | 326.378 | 306.068 | 327.126 | 306.669 |
22 | 4.194.304 | 2.550.409 | 1.301.391 | 1.249.018 | 656.517 | 617.534 | 657.580 | 618.778 |
23 | 8.388.608 | 5.133.973 | 2.616.201 | 2.517.772 | 1.319.440 | 1.246.200 | 1.321.153 | 1.247.180 |
24 | 16.777.216 | 10.327.418 | 5.258.012 | 5.069.406 | 2.650.831 | 2.512.488 | 2.652.241 | 2.511.858 |
25 | 33.554.432 | 20.765.908 | 10.560.988 | 10.204.920 | 5.322.986 | 5.059.174 | 5.325.242 | 5.058.506 |
26 | 67.108.864 | 41.734.249 | 21.212.488 | 20.521.761 | 10.685.312 | 10.180.066 | 10.687.713 | 10.181.158 |
27 | 134.217.728 | 83.840.118 | 42.580.944 | 41.259.174 | 21.445.263 | 20.474.046 | 21.445.672 | 20.475.137 |
28 | 268.435.456 | 168.367.014 | 85.446.583 | 82.920.431 | 43.025.531 | 41.158.771 | 43.025.337 | 41.157.375 |
29 | 536.870.912 | 338.021.712 | 171.447.745 | 166.573.967 | 86.294.259 | 82.720.845 | 86.297.488 | 82.709.120 |
30 | 1.073.741.824 | 678.427.578 | 343.932.017 | 334.495.561 | 173.061.125 | 166.157.717 | 173.052.299 | 166.156.437 |
31 | 2.147.483.648 | 1.361.296.123 | 689.767.997 | 671.528.126 | 346.971.365 | 333.672.544 | 346.963.745 | 333.688.469 |
32 | 4.294.967.296 | 2.730.890.523 | 1.383.085.300 | 1.347.805.223 | 695.544.877 | 669.890.441 | 695.552.697 | 669.902.508 |
33 | 8.589.934.592 | 5.477.276.370 | 2.772.822.712 | 2.704.453.658 | 1.394.155.694 | 1.344.484.106 | 1.394.114.641 | 1.344.521.929 |
34 | 17.179.869.184 | 10.983.691.558 | 5.558.051.596 | 5.425.639.962 | 2.793.935.390 | 2.697.922.362 | 2.793.889.029 | 2.697.944.777 |