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+58x-3
f(0)=3
f(1)=7
f(2)=13
f(3)=5
f(4)=1
f(5)=1
f(6)=127
f(7)=113
f(8)=1
f(9)=1
f(10)=677
f(11)=1
f(12)=31
f(13)=23
f(14)=67
f(15)=1
f(16)=1181
f(17)=53
f(18)=1
f(19)=73
f(20)=173
f(21)=1
f(22)=251
f(23)=1
f(24)=131
f(25)=37
f(26)=727
f(27)=191
f(28)=1
f(29)=1
f(30)=293
f(31)=1
f(32)=137
f(33)=1
f(34)=1
f(35)=271
f(36)=1
f(37)=439
f(38)=1
f(39)=1
f(40)=3917
f(41)=1
f(42)=1399
f(43)=1
f(44)=1
f(45)=193
f(46)=683
f(47)=1
f(48)=1
f(49)=1
f(50)=257
f(51)=463
f(52)=5717
f(53)=1
f(54)=1
f(55)=1553
f(56)=709
f(57)=1
f(58)=269
f(59)=1
f(60)=337
f(61)=907
f(62)=1
f(63)=1
f(64)=223
f(65)=1
f(66)=101
f(67)=1
f(68)=571
f(69)=1
f(70)=1
f(71)=109
f(72)=3119
f(73)=239
f(74)=1
f(75)=277
f(76)=10181
f(77)=433
f(78)=1
f(79)=541
f(80)=283
f(81)=1
f(82)=499
f(83)=1
f(84)=1
f(85)=1
f(86)=4127
f(87)=1051
f(88)=367
f(89)=1
f(90)=1
f(91)=3389
f(92)=1
f(93)=1
f(94)=2857
f(95)=1
f(96)=379
f(97)=1879
f(98)=1019
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+58x-3 could be written as f(y)= y^2-844 with x=y-29
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+29
f'(x)>2x+57
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 | 6 | 4 | 2 | 0.600000 | 0.400000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 51 | 14 | 37 | 0.510000 | 0.140000 | 0.370000 | 8.500000 | 3.500000 | 18.500000 |
3 | 1.000 | 563 | 68 | 495 | 0.563000 | 0.068000 | 0.495000 | 11.039216 | 4.857143 | 13.378378 |
4 | 10.000 | 5.998 | 514 | 5.484 | 0.599800 | 0.051400 | 0.548400 | 10.653641 | 7.558824 | 11.078788 |
5 | 100.000 | 61.953 | 3.760 | 58.193 | 0.619530 | 0.037600 | 0.581930 | 10.328943 | 7.315175 | 10.611415 |
6 | 1.000.000 | 632.713 | 30.261 | 602.452 | 0.632713 | 0.030261 | 0.602452 | 10.212790 | 8.048139 | 10.352654 |
7 | 10.000.000 | 6.416.386 | 253.378 | 6.163.008 | 0.641639 | 0.025338 | 0.616301 | 10.141068 | 8.373088 | 10.229874 |
8 | 100.000.000 | 64.827.654 | 2.186.864 | 62.640.790 | 0.648277 | 0.021869 | 0.626408 | 10.103454 | 8.630836 | 10.163997 |
9 | 1.000.000.000 | 653.377.663 | 19.230.168 | 634.147.495 | 0.653378 | 0.019230 | 0.634148 | 10.078687 | 8.793490 | 10.123555 |
10 | 10.000.000.000 | 6.574.266.035 | 171.699.011 | 6.402.567.024 | 0.657427 | 0.017170 | 0.640257 | 10.061969 | 8.928628 | 10.096337 |
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 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 5 | 3 | 2 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.500000 | 2.000000 |
4 | 16 | 9 | 5 | 4 | 0.562500 | 0.312500 | 0.250000 | 1.800000 | 1.666667 | 2.000000 |
5 | 32 | 18 | 5 | 13 | 0.562500 | 0.156250 | 0.406250 | 2.000000 | 1.000000 | 3.250000 |
6 | 64 | 33 | 10 | 23 | 0.515625 | 0.156250 | 0.359375 | 1.833333 | 2.000000 | 1.769231 |
7 | 128 | 67 | 17 | 50 | 0.523438 | 0.132812 | 0.390625 | 2.030303 | 1.700000 | 2.173913 |
8 | 256 | 136 | 25 | 111 | 0.531250 | 0.097656 | 0.433594 | 2.029851 | 1.470588 | 2.220000 |
9 | 512 | 283 | 41 | 242 | 0.552734 | 0.080078 | 0.472656 | 2.080882 | 1.640000 | 2.180180 |
10 | 1.024 | 580 | 69 | 511 | 0.566406 | 0.067383 | 0.499023 | 2.049470 | 1.682927 | 2.111570 |
11 | 2.048 | 1.174 | 129 | 1.045 | 0.573242 | 0.062988 | 0.510254 | 2.024138 | 1.869565 | 2.045010 |
12 | 4.096 | 2.387 | 234 | 2.153 | 0.582764 | 0.057129 | 0.525635 | 2.033220 | 1.813954 | 2.060287 |
13 | 8.192 | 4.893 | 427 | 4.466 | 0.597290 | 0.052124 | 0.545166 | 2.049853 | 1.824786 | 2.074315 |
14 | 16.384 | 9.932 | 768 | 9.164 | 0.606201 | 0.046875 | 0.559326 | 2.029839 | 1.798595 | 2.051948 |
15 | 32.768 | 20.060 | 1.388 | 18.672 | 0.612183 | 0.042358 | 0.569824 | 2.019734 | 1.807292 | 2.037538 |
16 | 65.536 | 40.436 | 2.580 | 37.856 | 0.617004 | 0.039368 | 0.577637 | 2.015753 | 1.858790 | 2.027421 |
17 | 131.072 | 81.417 | 4.786 | 76.631 | 0.621162 | 0.036514 | 0.584648 | 2.013478 | 1.855039 | 2.024276 |
18 | 262.144 | 164.045 | 8.972 | 155.073 | 0.625782 | 0.034225 | 0.591557 | 2.014874 | 1.874634 | 2.023633 |
19 | 524.288 | 330.102 | 16.687 | 313.415 | 0.629620 | 0.031828 | 0.597792 | 2.012265 | 1.859897 | 2.021080 |
20 | 1.048.576 | 663.647 | 31.585 | 632.062 | 0.632903 | 0.030122 | 0.602781 | 2.010430 | 1.892791 | 2.016694 |
21 | 2.097.152 | 1.333.729 | 59.734 | 1.273.995 | 0.635972 | 0.028483 | 0.607488 | 2.009696 | 1.891214 | 2.015617 |
22 | 4.194.304 | 2.678.716 | 113.225 | 2.565.491 | 0.638656 | 0.026995 | 0.611661 | 2.008441 | 1.895487 | 2.013737 |
23 | 8.388.608 | 5.377.413 | 215.279 | 5.162.134 | 0.641038 | 0.025663 | 0.615374 | 2.007459 | 1.901338 | 2.012143 |
24 | 16.777.216 | 10.793.755 | 410.265 | 10.383.490 | 0.643358 | 0.024454 | 0.618904 | 2.007239 | 1.905736 | 2.011472 |
25 | 33.554.432 | 21.655.208 | 784.562 | 20.870.646 | 0.645375 | 0.023382 | 0.621994 | 2.006272 | 1.912330 | 2.009984 |
26 | 67.108.864 | 43.436.743 | 1.502.978 | 41.933.765 | 0.647258 | 0.022396 | 0.624862 | 2.005834 | 1.915691 | 2.009222 |
27 | 134.217.728 | 87.108.227 | 2.884.921 | 84.223.306 | 0.649007 | 0.021494 | 0.627513 | 2.005404 | 1.919470 | 2.008484 |
28 | 268.435.456 | 174.652.833 | 5.542.525 | 169.110.308 | 0.650633 | 0.020648 | 0.629985 | 2.005010 | 1.921205 | 2.007880 |
29 | 536.870.912 | 350.109.124 | 10.671.743 | 339.437.381 | 0.652129 | 0.019878 | 0.632251 | 2.004600 | 1.925430 | 2.007195 |
30 | 1.073.741.824 | 701.708.310 | 20.570.819 | 681.137.491 | 0.653517 | 0.019158 | 0.634359 | 2.004256 | 1.927597 | 2.006666 |
31 | 2.147.483.648 | 1.406.216.449 | 39.710.441 | 1.366.506.008 | 0.654821 | 0.018492 | 0.636329 | 2.003990 | 1.930426 | 2.006212 |
32 | 4.294.967.296 | 2.817.674.755 | 76.767.098 | 2.740.907.657 | 0.656041 | 0.017874 | 0.638167 | 2.003728 | 1.933172 | 2.005778 |
33 | 8.589.934.592 | 5.645.182.951 | 148.546.874 | 5.496.636.077 | 0.657186 | 0.017293 | 0.639893 | 2.003490 | 1.935033 | 2.005407 |
34 | 17.179.869.184 | 11.308.859.185 | 287.706.422 | 11.021.152.763 | 0.658262 | 0.016747 | 0.641515 | 2.003276 | 1.936806 | 2.005072 |
35 | 34.359.738.368 | 22.652.576.173 | 557.847.065 | 22.094.729.108 | 0.659277 | 0.016235 | 0.643041 | 2.003082 | 1.938945 | 2.004757 |
36 | 68.719.476.736 | 45.370.928.422 | 1.082.644.782 | 44.288.283.640 | 0.660234 | 0.015755 | 0.644479 | 2.002904 | 1.940755 | 2.004473 |
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 | 1 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 1 | 1 | 1 | 1 | 0 | 1 |
4 | 16 | 5 | 1 | 3 | 1 | 1 | 2 | 1 |
5 | 32 | 5 | 1 | 3 | 1 | 1 | 2 | 1 |
6 | 64 | 10 | 3 | 6 | 2 | 2 | 4 | 2 |
7 | 128 | 17 | 5 | 11 | 2 | 3 | 9 | 3 |
8 | 256 | 25 | 9 | 15 | 3 | 5 | 12 | 5 |
9 | 512 | 41 | 11 | 29 | 6 | 5 | 23 | 7 |
10 | 1.024 | 69 | 23 | 45 | 9 | 11 | 36 | 13 |
11 | 2.048 | 129 | 38 | 90 | 19 | 18 | 71 | 21 |
12 | 4.096 | 234 | 61 | 172 | 36 | 27 | 136 | 35 |
13 | 8.192 | 427 | 112 | 314 | 61 | 56 | 253 | 57 |
14 | 16.384 | 768 | 201 | 566 | 104 | 107 | 462 | 95 |
15 | 32.768 | 1.388 | 398 | 989 | 177 | 198 | 812 | 201 |
16 | 65.536 | 2.580 | 723 | 1.856 | 330 | 363 | 1.526 | 361 |
17 | 131.072 | 4.786 | 1.303 | 3.482 | 613 | 650 | 2.869 | 654 |
18 | 262.144 | 8.972 | 2.367 | 6.604 | 1.143 | 1.184 | 5.461 | 1.184 |
19 | 524.288 | 16.687 | 4.474 | 12.212 | 2.133 | 2.256 | 10.079 | 2.219 |
20 | 1.048.576 | 31.585 | 8.333 | 23.251 | 4.032 | 4.210 | 19.219 | 4.124 |
21 | 2.097.152 | 59.734 | 15.705 | 44.028 | 7.559 | 7.896 | 36.469 | 7.810 |
22 | 4.194.304 | 113.225 | 29.617 | 83.607 | 14.396 | 14.797 | 69.211 | 14.821 |
23 | 8.388.608 | 215.279 | 56.148 | 159.130 | 27.278 | 28.035 | 131.852 | 28.114 |
24 | 16.777.216 | 410.265 | 106.722 | 303.542 | 52.071 | 53.285 | 251.471 | 53.438 |
25 | 33.554.432 | 784.562 | 203.556 | 581.005 | 99.785 | 101.600 | 481.220 | 101.957 |
26 | 67.108.864 | 1.502.978 | 389.646 | 1.113.331 | 190.948 | 194.910 | 922.383 | 194.737 |
27 | 134.217.728 | 2.884.921 | 746.817 | 2.138.103 | 365.897 | 373.397 | 1.772.206 | 373.421 |
28 | 268.435.456 | 5.542.525 | 1.433.635 | 4.108.889 | 702.283 | 717.123 | 3.406.606 | 716.513 |
29 | 536.870.912 | 10.671.743 | 2.756.570 | 7.915.172 | 1.351.728 | 1.378.763 | 6.563.444 | 1.377.808 |
30 | 1.073.741.824 | 20.570.819 | 5.306.840 | 15.263.978 | 2.604.312 | 2.653.617 | 12.659.666 | 2.653.224 |
31 | 2.147.483.648 | 39.710.441 | 10.232.703 | 29.477.737 | 5.026.017 | 5.118.356 | 24.451.720 | 5.114.348 |
32 | 4.294.967.296 | 76.767.098 | 19.765.120 | 57.001.977 | 9.712.735 | 9.884.202 | 47.289.242 | 9.880.919 |
33 | 8.589.934.592 | 148.546.874 | 38.209.132 | 110.337.741 | 18.782.894 | 19.105.798 | 91.554.847 | 19.103.335 |
34 | 17.179.869.184 | 287.706.422 | 73.928.993 | 213.777.428 | 36.365.538 | 36.962.894 | 177.411.890 | 36.966.100 |
35 | 34.359.738.368 | 557.847.065 | 143.222.749 | 414.624.315 | 70.505.361 | 71.612.821 | 344.118.954 | 71.609.929 |
36 | 68.719.476.736 | 1.082.644.782 | 277.738.073 | 804.906.708 | 136.798.220 | 138.874.857 | 668.108.488 | 138.863.217 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 2 | 0 | 0 | 0 | 1 | 1 |
4 | 16 | 4 | 4 | 0 | 0 | 1 | 1 | 2 |
5 | 32 | 13 | 6 | 7 | 2 | 3 | 4 | 4 |
6 | 64 | 23 | 13 | 10 | 5 | 4 | 6 | 8 |
7 | 128 | 50 | 30 | 20 | 11 | 13 | 11 | 15 |
8 | 256 | 111 | 55 | 56 | 26 | 32 | 20 | 33 |
9 | 512 | 242 | 121 | 121 | 53 | 66 | 55 | 68 |
10 | 1.024 | 511 | 248 | 263 | 124 | 136 | 112 | 139 |
11 | 2.048 | 1.045 | 518 | 527 | 263 | 260 | 230 | 292 |
12 | 4.096 | 2.153 | 1.054 | 1.099 | 539 | 564 | 463 | 587 |
13 | 8.192 | 4.466 | 2.244 | 2.222 | 1.128 | 1.127 | 1.034 | 1.177 |
14 | 16.384 | 9.164 | 4.594 | 4.570 | 2.312 | 2.354 | 2.126 | 2.372 |
15 | 32.768 | 18.672 | 9.344 | 9.328 | 4.718 | 4.792 | 4.250 | 4.912 |
16 | 65.536 | 37.856 | 18.929 | 18.927 | 9.547 | 9.642 | 8.733 | 9.934 |
17 | 131.072 | 76.631 | 38.367 | 38.264 | 19.344 | 19.367 | 17.745 | 20.175 |
18 | 262.144 | 155.073 | 77.812 | 77.261 | 39.004 | 39.292 | 36.205 | 40.572 |
19 | 524.288 | 313.415 | 157.015 | 156.400 | 78.797 | 79.119 | 73.501 | 81.998 |
20 | 1.048.576 | 632.062 | 316.856 | 315.206 | 158.575 | 159.401 | 149.333 | 164.753 |
21 | 2.097.152 | 1.273.995 | 637.994 | 636.001 | 320.108 | 321.064 | 301.937 | 330.886 |
22 | 4.194.304 | 2.565.491 | 1.284.474 | 1.281.017 | 644.224 | 646.265 | 609.895 | 665.107 |
23 | 8.388.608 | 5.162.134 | 2.584.189 | 2.577.945 | 1.295.637 | 1.298.938 | 1.230.514 | 1.337.045 |
24 | 16.777.216 | 10.383.490 | 5.198.514 | 5.184.976 | 2.605.785 | 2.610.930 | 2.482.711 | 2.684.064 |
25 | 33.554.432 | 20.870.646 | 10.450.715 | 10.419.931 | 5.240.680 | 5.242.869 | 4.999.765 | 5.387.332 |
26 | 67.108.864 | 41.933.765 | 20.999.601 | 20.934.164 | 10.528.373 | 10.529.386 | 10.065.574 | 10.810.432 |
27 | 134.217.728 | 84.223.306 | 42.167.031 | 42.056.275 | 21.142.513 | 21.147.508 | 20.252.656 | 21.680.629 |
28 | 268.435.456 | 169.110.308 | 84.664.717 | 84.445.591 | 42.446.941 | 42.453.117 | 40.730.327 | 43.479.923 |
29 | 536.870.912 | 339.437.381 | 169.945.661 | 169.491.720 | 85.187.856 | 85.189.424 | 81.880.494 | 87.179.607 |
30 | 1.073.741.824 | 681.137.491 | 341.020.042 | 340.117.449 | 170.914.051 | 170.913.908 | 164.527.394 | 174.782.138 |
31 | 2.147.483.648 | 1.366.506.008 | 684.111.001 | 682.395.007 | 342.835.908 | 342.868.114 | 330.524.990 | 350.276.996 |
32 | 4.294.967.296 | 2.740.907.657 | 1.372.097.844 | 1.368.809.813 | 687.539.417 | 687.620.166 | 663.809.569 | 701.938.505 |
33 | 8.589.934.592 | 5.496.636.077 | 2.751.449.309 | 2.745.186.768 | 1.378.646.340 | 1.378.769.981 | 1.332.737.343 | 1.406.482.413 |
34 | 17.179.869.184 | 11.021.152.763 | 5.516.675.149 | 5.504.477.614 | 2.763.951.313 | 2.764.177.482 | 2.674.998.917 | 2.818.025.051 |
35 | 34.359.738.368 | 22.094.729.108 | 11.059.265.972 | 11.035.463.136 | 5.540.433.104 | 5.540.916.192 | 5.368.032.706 | 5.645.347.106 |
36 | 68.719.476.736 | 44.288.283.640 | 22.167.135.983 | 22.121.147.657 | 11.104.644.592 | 11.105.385.955 | 10.769.966.679 | 11.308.286.414 |