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-7
f(0)=7
f(1)=3
f(2)=1
f(3)=1
f(4)=1
f(5)=1
f(6)=29
f(7)=1
f(8)=19
f(9)=37
f(10)=31
f(11)=1
f(12)=137
f(13)=1
f(14)=1
f(15)=109
f(16)=83
f(17)=47
f(18)=317
f(19)=59
f(20)=131
f(21)=1
f(22)=53
f(23)=1
f(24)=569
f(25)=103
f(26)=223
f(27)=1
f(28)=1
f(29)=139
f(30)=1
f(31)=1
f(32)=113
f(33)=541
f(34)=383
f(35)=1
f(36)=1289
f(37)=227
f(38)=479
f(39)=757
f(40)=1
f(41)=1
f(42)=251
f(43)=307
f(44)=643
f(45)=1009
f(46)=1
f(47)=367
f(48)=2297
f(49)=1
f(50)=277
f(51)=1297
f(52)=1
f(53)=467
f(54)=2909
f(55)=503
f(56)=149
f(57)=1621
f(58)=373
f(59)=193
f(60)=3593
f(61)=619
f(62)=1279
f(63)=283
f(64)=1
f(65)=1
f(66)=4349
f(67)=1
f(68)=1
f(69)=2377
f(70)=233
f(71)=839
f(72)=167
f(73)=887
f(74)=1823
f(75)=1
f(76)=641
f(77)=1
f(78)=1
f(79)=1039
f(80)=2131
f(81)=1
f(82)=2239
f(83)=1
f(84)=1
f(85)=401
f(86)=821
f(87)=199
f(88)=2579
f(89)=1319
f(90)=8093
f(91)=197
f(92)=2819
f(93)=1
f(94)=1
f(95)=1
f(96)=9209
f(97)=1567
f(98)=457
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-7 could be written as f(y)= y^2-7 with x=y+0
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+0
f'(x)>2x-1 with x > 3
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.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 21 | 46 | 0.670000 | 0.210000 | 0.670000 | 11.166667 | 5.250000 | 23.000000 |
3 | 1.000 | 698 | 138 | 560 | 0.698000 | 0.138000 | 0.698000 | 10.417911 | 6.571429 | 12.173913 |
4 | 10.000 | 7.014 | 935 | 6.079 | 0.701400 | 0.093500 | 0.701400 | 10.048711 | 6.775362 | 10.855357 |
5 | 100.000 | 69.810 | 7.418 | 62.392 | 0.698100 | 0.074180 | 0.698100 | 9.952951 | 7.933690 | 10.263530 |
6 | 1.000.000 | 696.854 | 60.394 | 636.460 | 0.696854 | 0.060394 | 0.696854 | 9.982152 | 8.141547 | 10.200987 |
7 | 10.000.000 | 6.960.488 | 509.298 | 6.451.190 | 0.696049 | 0.050930 | 0.696049 | 9.988445 | 8.432924 | 10.136049 |
8 | 100.000.000 | 69.546.625 | 4.409.568 | 65.137.057 | 0.695466 | 0.044096 | 0.695466 | 9.991631 | 8.658130 | 10.096906 |
9 | 1.000.000.000 | 695.034.566 | 38.856.626 | 656.177.940 | 0.695035 | 0.038857 | 0.695035 | 9.993793 | 8.811889 | 10.073804 |
10 | 10.000.000.000 | 6.947.138.834 | 347.408.685 | 6.599.730.149 | 0.694714 | 0.034741 | 0.694714 | 9.995386 | 8.940784 | 10.057837 |
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 | 2 | 2 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 4 | 3 | 1 | 0.500000 | 0.375000 | 0.125000 | 2.000000 | 1.500000 | inf |
4 | 16 | 9 | 6 | 3 | 0.562500 | 0.375000 | 0.187500 | 2.250000 | 2.000000 | 3.000000 |
5 | 32 | 19 | 8 | 11 | 0.593750 | 0.250000 | 0.343750 | 2.111111 | 1.333333 | 3.666667 |
6 | 64 | 44 | 17 | 27 | 0.687500 | 0.265625 | 0.421875 | 2.315789 | 2.125000 | 2.454545 |
7 | 128 | 86 | 24 | 62 | 0.671875 | 0.187500 | 0.484375 | 1.954545 | 1.411765 | 2.296296 |
8 | 256 | 178 | 47 | 131 | 0.695312 | 0.183594 | 0.511719 | 2.069767 | 1.958333 | 2.112903 |
9 | 512 | 349 | 87 | 262 | 0.681641 | 0.169922 | 0.511719 | 1.960674 | 1.851064 | 2.000000 |
10 | 1.024 | 714 | 141 | 573 | 0.697266 | 0.137695 | 0.559570 | 2.045845 | 1.620690 | 2.187023 |
11 | 2.048 | 1.435 | 250 | 1.185 | 0.700684 | 0.122070 | 0.578613 | 2.009804 | 1.773050 | 2.068063 |
12 | 4.096 | 2.859 | 446 | 2.413 | 0.697998 | 0.108887 | 0.589111 | 1.992334 | 1.784000 | 2.036287 |
13 | 8.192 | 5.745 | 794 | 4.951 | 0.701294 | 0.096924 | 0.604370 | 2.009444 | 1.780269 | 2.051803 |
14 | 16.384 | 11.468 | 1.472 | 9.996 | 0.699951 | 0.089844 | 0.610107 | 1.996171 | 1.853904 | 2.018986 |
15 | 32.768 | 22.907 | 2.734 | 20.173 | 0.699066 | 0.083435 | 0.615631 | 1.997471 | 1.857337 | 2.018107 |
16 | 65.536 | 45.764 | 5.068 | 40.696 | 0.698303 | 0.077332 | 0.620972 | 1.997817 | 1.853694 | 2.017350 |
17 | 131.072 | 91.485 | 9.496 | 81.989 | 0.697975 | 0.072449 | 0.625526 | 1.999060 | 1.873717 | 2.014670 |
18 | 262.144 | 182.881 | 17.694 | 165.187 | 0.697636 | 0.067497 | 0.630138 | 1.999027 | 1.863311 | 2.014746 |
19 | 524.288 | 365.538 | 33.416 | 332.122 | 0.697208 | 0.063736 | 0.633472 | 1.998775 | 1.888550 | 2.010582 |
20 | 1.048.576 | 730.763 | 63.098 | 667.665 | 0.696910 | 0.060175 | 0.636735 | 1.999144 | 1.888257 | 2.010300 |
21 | 2.097.152 | 1.460.854 | 119.421 | 1.341.433 | 0.696589 | 0.056944 | 0.639645 | 1.999080 | 1.892627 | 2.009141 |
22 | 4.194.304 | 2.920.954 | 226.770 | 2.694.184 | 0.696410 | 0.054066 | 0.642344 | 1.999484 | 1.898912 | 2.008437 |
23 | 8.388.608 | 5.839.711 | 432.085 | 5.407.626 | 0.696148 | 0.051509 | 0.644639 | 1.999248 | 1.905389 | 2.007148 |
24 | 16.777.216 | 11.675.911 | 825.856 | 10.850.055 | 0.695939 | 0.049225 | 0.646714 | 1.999399 | 1.911328 | 2.006436 |
25 | 33.554.432 | 23.345.156 | 1.580.686 | 21.764.470 | 0.695740 | 0.047108 | 0.648632 | 1.999429 | 1.913997 | 2.005932 |
26 | 67.108.864 | 46.678.500 | 3.029.894 | 43.648.606 | 0.695564 | 0.045149 | 0.650415 | 1.999494 | 1.916822 | 2.005498 |
27 | 134.217.728 | 93.335.653 | 5.818.735 | 87.516.918 | 0.695405 | 0.043353 | 0.652052 | 1.999543 | 1.920442 | 2.005033 |
28 | 268.435.456 | 186.632.496 | 11.192.895 | 175.439.601 | 0.695260 | 0.041697 | 0.653563 | 1.999584 | 1.923596 | 2.004636 |
29 | 536.870.912 | 373.197.014 | 21.556.494 | 351.640.520 | 0.695134 | 0.040152 | 0.654981 | 1.999636 | 1.925909 | 2.004339 |
30 | 1.073.741.824 | 746.275.558 | 41.569.639 | 704.705.919 | 0.695023 | 0.038715 | 0.656309 | 1.999683 | 1.928404 | 2.004052 |
31 | 2.147.483.648 | 1.492.331.191 | 80.284.645 | 1.412.046.546 | 0.694921 | 0.037385 | 0.657535 | 1.999705 | 1.931329 | 2.003739 |
32 | 4.294.967.296 | 2.984.234.582 | 155.247.290 | 2.828.987.292 | 0.694821 | 0.036146 | 0.658675 | 1.999713 | 1.933711 | 2.003466 |
33 | 8.589.934.592 | 5.967.701.262 | 300.516.614 | 5.667.184.648 | 0.694732 | 0.034985 | 0.659747 | 1.999743 | 1.935728 | 2.003256 |
34 | 17.179.869.184 | 11.934.015.600 | 582.343.856 | 11.351.671.744 | 0.694651 | 0.033897 | 0.660754 | 1.999768 | 1.937809 | 2.003053 |
35 | 34.359.738.368 | 23.865.486.387 | 1.129.597.699 | 22.735.888.688 | 0.694577 | 0.032876 | 0.661701 | 1.999787 | 1.939743 | 2.002867 |
36 | 68.719.476.736 | 47.726.357.995 | 2.193.058.421 | 45.533.299.574 | 0.694510 | 0.031913 | 0.662597 | 1.999807 | 1.941451 | 2.002706 |
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 | 0 | 1 | 1 | 1 |
4 | 16 | 6 | 3 | 2 | 1 | 1 | 3 | 1 |
5 | 32 | 8 | 3 | 4 | 2 | 1 | 4 | 1 |
6 | 64 | 17 | 8 | 8 | 7 | 1 | 8 | 1 |
7 | 128 | 24 | 11 | 12 | 12 | 1 | 10 | 1 |
8 | 256 | 47 | 21 | 25 | 22 | 1 | 23 | 1 |
9 | 512 | 87 | 45 | 41 | 42 | 1 | 43 | 1 |
10 | 1.024 | 141 | 73 | 67 | 68 | 1 | 71 | 1 |
11 | 2.048 | 250 | 132 | 117 | 118 | 1 | 130 | 1 |
12 | 4.096 | 446 | 238 | 207 | 216 | 1 | 228 | 1 |
13 | 8.192 | 794 | 426 | 367 | 402 | 1 | 390 | 1 |
14 | 16.384 | 1.472 | 763 | 708 | 733 | 1 | 737 | 1 |
15 | 32.768 | 2.734 | 1.401 | 1.332 | 1.355 | 1 | 1.377 | 1 |
16 | 65.536 | 5.068 | 2.607 | 2.460 | 2.525 | 1 | 2.541 | 1 |
17 | 131.072 | 9.496 | 4.832 | 4.663 | 4.760 | 1 | 4.734 | 1 |
18 | 262.144 | 17.694 | 8.973 | 8.720 | 8.893 | 1 | 8.799 | 1 |
19 | 524.288 | 33.416 | 16.923 | 16.492 | 16.702 | 1 | 16.712 | 1 |
20 | 1.048.576 | 63.098 | 31.953 | 31.144 | 31.658 | 1 | 31.438 | 1 |
21 | 2.097.152 | 119.421 | 60.374 | 59.046 | 59.783 | 1 | 59.636 | 1 |
22 | 4.194.304 | 226.770 | 114.642 | 112.127 | 113.294 | 1 | 113.474 | 1 |
23 | 8.388.608 | 432.085 | 218.473 | 213.611 | 215.862 | 1 | 216.221 | 1 |
24 | 16.777.216 | 825.856 | 417.958 | 407.897 | 412.986 | 1 | 412.868 | 1 |
25 | 33.554.432 | 1.580.686 | 799.338 | 781.347 | 790.513 | 1 | 790.171 | 1 |
26 | 67.108.864 | 3.029.894 | 1.530.600 | 1.499.293 | 1.515.042 | 1 | 1.514.850 | 1 |
27 | 134.217.728 | 5.818.735 | 2.938.133 | 2.880.601 | 2.909.856 | 1 | 2.908.877 | 1 |
28 | 268.435.456 | 11.192.895 | 5.649.088 | 5.543.806 | 5.597.434 | 1 | 5.595.459 | 1 |
29 | 536.870.912 | 21.556.494 | 10.875.639 | 10.680.854 | 10.777.965 | 1 | 10.778.527 | 1 |
30 | 1.073.741.824 | 41.569.639 | 20.965.614 | 20.604.024 | 20.784.674 | 1 | 20.784.963 | 1 |
31 | 2.147.483.648 | 80.284.645 | 40.478.415 | 39.806.229 | 40.142.002 | 1 | 40.142.641 | 1 |
32 | 4.294.967.296 | 155.247.290 | 78.260.052 | 76.987.237 | 77.619.459 | 1 | 77.627.829 | 1 |
33 | 8.589.934.592 | 300.516.614 | 151.457.041 | 149.059.572 | 150.250.252 | 1 | 150.266.360 | 1 |
34 | 17.179.869.184 | 582.343.856 | 293.435.610 | 288.908.245 | 291.157.899 | 1 | 291.185.955 | 1 |
35 | 34.359.738.368 | 1.129.597.699 | 569.069.238 | 560.528.460 | 564.795.518 | 1 | 564.802.179 | 1 |
36 | 68.719.476.736 | 2.193.058.421 | 1.104.583.592 | 1.088.474.828 | 1.096.520.969 | 1 | 1.096.537.450 | 1 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 2 | 1 | 0 | 2 | 0 | 1 |
5 | 32 | 11 | 5 | 6 | 1 | 5 | 1 | 4 |
6 | 64 | 27 | 14 | 13 | 2 | 12 | 4 | 9 |
7 | 128 | 62 | 30 | 32 | 9 | 24 | 8 | 21 |
8 | 256 | 131 | 64 | 67 | 21 | 47 | 21 | 42 |
9 | 512 | 262 | 132 | 130 | 41 | 89 | 47 | 85 |
10 | 1.024 | 573 | 284 | 289 | 102 | 181 | 112 | 178 |
11 | 2.048 | 1.185 | 589 | 596 | 224 | 374 | 226 | 361 |
12 | 4.096 | 2.413 | 1.188 | 1.225 | 475 | 717 | 498 | 723 |
13 | 8.192 | 4.951 | 2.453 | 2.498 | 998 | 1.458 | 1.030 | 1.465 |
14 | 16.384 | 9.996 | 4.976 | 5.020 | 2.064 | 2.870 | 2.113 | 2.949 |
15 | 32.768 | 20.173 | 10.009 | 10.164 | 4.297 | 5.762 | 4.353 | 5.761 |
16 | 65.536 | 40.696 | 20.250 | 20.446 | 8.791 | 11.483 | 8.923 | 11.499 |
17 | 131.072 | 81.989 | 40.950 | 41.039 | 18.011 | 22.877 | 18.152 | 22.949 |
18 | 262.144 | 165.187 | 82.628 | 82.559 | 36.674 | 45.841 | 36.744 | 45.928 |
19 | 524.288 | 332.122 | 165.751 | 166.371 | 74.536 | 91.644 | 74.247 | 91.695 |
20 | 1.048.576 | 667.665 | 333.589 | 334.076 | 150.673 | 183.126 | 150.739 | 183.127 |
21 | 2.097.152 | 1.341.433 | 670.079 | 671.354 | 304.855 | 365.833 | 304.869 | 365.876 |
22 | 4.194.304 | 2.694.184 | 1.346.438 | 1.347.746 | 615.676 | 731.198 | 615.942 | 731.368 |
23 | 8.388.608 | 5.407.626 | 2.702.847 | 2.704.779 | 1.241.525 | 1.462.078 | 1.241.655 | 1.462.368 |
24 | 16.777.216 | 10.850.055 | 5.425.061 | 5.424.994 | 2.503.430 | 2.922.743 | 2.500.818 | 2.923.064 |
25 | 33.554.432 | 21.764.470 | 10.886.093 | 10.878.377 | 5.037.384 | 5.844.575 | 5.038.844 | 5.843.667 |
26 | 67.108.864 | 43.648.606 | 21.825.699 | 21.822.907 | 10.141.486 | 11.685.025 | 10.141.736 | 11.680.359 |
27 | 134.217.728 | 87.516.918 | 43.764.925 | 43.751.993 | 20.401.518 | 23.359.196 | 20.400.791 | 23.355.413 |
28 | 268.435.456 | 175.439.601 | 87.730.943 | 87.708.658 | 41.013.836 | 46.702.226 | 41.022.977 | 46.700.562 |
29 | 536.870.912 | 351.640.520 | 175.842.298 | 175.798.222 | 82.440.498 | 93.377.705 | 82.437.381 | 93.384.936 |
30 | 1.073.741.824 | 704.705.919 | 352.376.532 | 352.329.387 | 165.626.411 | 186.729.675 | 165.625.365 | 186.724.468 |
31 | 2.147.483.648 | 1.412.046.546 | 706.085.486 | 705.961.060 | 332.651.647 | 373.369.627 | 332.664.922 | 373.360.350 |
32 | 4.294.967.296 | 2.828.987.292 | 1.414.613.106 | 1.414.374.186 | 667.923.945 | 746.569.624 | 667.914.637 | 746.579.086 |
33 | 8.589.934.592 | 5.667.184.648 | 2.833.806.625 | 2.833.378.023 | 1.340.641.354 | 1.492.911.477 | 1.340.667.898 | 1.492.963.919 |
34 | 17.179.869.184 | 11.351.671.744 | 5.676.263.740 | 5.675.408.004 | 2.690.447.018 | 2.985.371.968 | 2.690.419.363 | 2.985.433.395 |
35 | 34.359.738.368 | 22.735.888.688 | 11.368.684.948 | 11.367.203.740 | 5.397.986.747 | 5.969.880.120 | 5.398.019.087 | 5.970.002.734 |
36 | 68.719.476.736 | 45.533.299.574 | 22.768.050.734 | 22.765.248.840 | 10.828.285.068 | 11.938.294.226 | 10.828.375.193 | 11.938.345.087 |