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+66x-73
f(0)=73
f(1)=3
f(2)=7
f(3)=67
f(4)=23
f(5)=47
f(6)=359
f(7)=1
f(8)=173
f(9)=43
f(10)=229
f(11)=1
f(12)=863
f(13)=53
f(14)=349
f(15)=571
f(16)=59
f(17)=223
f(18)=1439
f(19)=257
f(20)=61
f(21)=877
f(22)=1
f(23)=1
f(24)=2087
f(25)=367
f(26)=773
f(27)=1
f(28)=853
f(29)=149
f(30)=401
f(31)=163
f(32)=1021
f(33)=1597
f(34)=1109
f(35)=577
f(36)=1
f(37)=89
f(38)=431
f(39)=2011
f(40)=463
f(41)=719
f(42)=4463
f(43)=769
f(44)=227
f(45)=107
f(46)=1693
f(47)=97
f(48)=5399
f(49)=103
f(50)=83
f(51)=421
f(52)=1
f(53)=1039
f(54)=1
f(55)=1097
f(56)=751
f(57)=3469
f(58)=113
f(59)=1217
f(60)=7487
f(61)=1279
f(62)=2621
f(63)=4027
f(64)=2749
f(65)=1
f(66)=1
f(67)=491
f(68)=131
f(69)=4621
f(70)=1
f(71)=1609
f(72)=1409
f(73)=1
f(74)=127
f(75)=1
f(76)=397
f(77)=1823
f(78)=11159
f(79)=271
f(80)=1
f(81)=1
f(82)=4021
f(83)=683
f(84)=12527
f(85)=709
f(86)=619
f(87)=6619
f(88)=4493
f(89)=2287
f(90)=13967
f(91)=1
f(92)=1607
f(93)=1051
f(94)=1663
f(95)=1
f(96)=673
f(97)=1
f(98)=5333
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+66x-73 could be written as f(y)= y^2-1162 with x=y-33
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+33
f'(x)>2x+65
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 79 | 13 | 66 | 0.790000 | 0.130000 | 0.790000 | 7.900000 | 4.333333 | 9.428572 |
3 | 1.000 | 697 | 68 | 629 | 0.697000 | 0.068000 | 0.697000 | 8.822784 | 5.230769 | 9.530303 |
4 | 10.000 | 6.888 | 485 | 6.403 | 0.688800 | 0.048500 | 0.688800 | 9.882353 | 7.132353 | 10.179650 |
5 | 100.000 | 68.919 | 3.743 | 65.176 | 0.689190 | 0.037430 | 0.689190 | 10.005662 | 7.717526 | 10.178979 |
6 | 1.000.000 | 690.524 | 30.437 | 660.087 | 0.690524 | 0.030437 | 0.690524 | 10.019356 | 8.131713 | 10.127762 |
7 | 10.000.000 | 6.907.692 | 256.186 | 6.651.506 | 0.690769 | 0.025619 | 0.690769 | 10.003551 | 8.416926 | 10.076711 |
8 | 100.000.000 | 69.092.364 | 2.218.163 | 66.874.201 | 0.690924 | 0.022182 | 0.690924 | 10.002236 | 8.658408 | 10.053994 |
9 | 1.000.000.000 | 691.045.007 | 19.582.683 | 671.462.324 | 0.691045 | 0.019583 | 0.691045 | 10.001756 | 8.828334 | 10.040678 |
10 | 10.000.000.000 | 6.911.852.843 | 175.259.188 | 6.736.593.655 | 0.691185 | 0.017526 | 0.691185 | 10.002030 | 8.949702 | 10.032720 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 15 | 4 | 11 | 0.937500 | 0.250000 | 0.687500 | 1.875000 | 1.333333 | 2.200000 |
5 | 32 | 28 | 6 | 22 | 0.875000 | 0.187500 | 0.687500 | 1.866667 | 1.500000 | 2.000000 |
6 | 64 | 56 | 10 | 46 | 0.875000 | 0.156250 | 0.718750 | 2.000000 | 1.666667 | 2.090909 |
7 | 128 | 99 | 15 | 84 | 0.773438 | 0.117188 | 0.656250 | 1.767857 | 1.500000 | 1.826087 |
8 | 256 | 188 | 23 | 165 | 0.734375 | 0.089844 | 0.644531 | 1.898990 | 1.533333 | 1.964286 |
9 | 512 | 360 | 42 | 318 | 0.703125 | 0.082031 | 0.621094 | 1.914894 | 1.826087 | 1.927273 |
10 | 1.024 | 712 | 70 | 642 | 0.695312 | 0.068359 | 0.626953 | 1.977778 | 1.666667 | 2.018868 |
11 | 2.048 | 1.421 | 121 | 1.300 | 0.693848 | 0.059082 | 0.634766 | 1.995787 | 1.728571 | 2.024922 |
12 | 4.096 | 2.821 | 231 | 2.590 | 0.688721 | 0.056396 | 0.632324 | 1.985222 | 1.909091 | 1.992308 |
13 | 8.192 | 5.628 | 405 | 5.223 | 0.687012 | 0.049438 | 0.637573 | 1.995037 | 1.753247 | 2.016602 |
14 | 16.384 | 11.263 | 760 | 10.503 | 0.687439 | 0.046387 | 0.641052 | 2.001244 | 1.876543 | 2.010913 |
15 | 32.768 | 22.565 | 1.397 | 21.168 | 0.688629 | 0.042633 | 0.645996 | 2.003463 | 1.838158 | 2.015424 |
16 | 65.536 | 45.139 | 2.544 | 42.595 | 0.688766 | 0.038818 | 0.649948 | 2.000399 | 1.821045 | 2.012235 |
17 | 131.072 | 90.377 | 4.739 | 85.638 | 0.689522 | 0.036156 | 0.653366 | 2.002193 | 1.862814 | 2.010518 |
18 | 262.144 | 180.852 | 8.980 | 171.872 | 0.689896 | 0.034256 | 0.655640 | 2.001084 | 1.894915 | 2.006959 |
19 | 524.288 | 362.075 | 16.848 | 345.227 | 0.690603 | 0.032135 | 0.658468 | 2.002051 | 1.876169 | 2.008629 |
20 | 1.048.576 | 724.097 | 31.773 | 692.324 | 0.690553 | 0.030301 | 0.660252 | 1.999854 | 1.885862 | 2.005417 |
21 | 2.097.152 | 1.448.407 | 60.180 | 1.388.227 | 0.690654 | 0.028696 | 0.661958 | 2.000294 | 1.894061 | 2.005170 |
22 | 4.194.304 | 2.896.859 | 114.048 | 2.782.811 | 0.690665 | 0.027191 | 0.663474 | 2.000031 | 1.895115 | 2.004579 |
23 | 8.388.608 | 5.794.430 | 217.495 | 5.576.935 | 0.690750 | 0.025927 | 0.664822 | 2.000246 | 1.907048 | 2.004065 |
24 | 16.777.216 | 11.590.192 | 415.442 | 11.174.750 | 0.690829 | 0.024762 | 0.666067 | 2.000230 | 1.910122 | 2.003744 |
25 | 33.554.432 | 23.181.602 | 794.956 | 22.386.646 | 0.690866 | 0.023692 | 0.667174 | 2.000105 | 1.913519 | 2.003324 |
26 | 67.108.864 | 46.364.568 | 1.524.431 | 44.840.137 | 0.690886 | 0.022716 | 0.668170 | 2.000059 | 1.917629 | 2.002986 |
27 | 134.217.728 | 92.736.847 | 2.927.744 | 89.809.103 | 0.690943 | 0.021813 | 0.669130 | 2.000166 | 1.920549 | 2.002873 |
28 | 268.435.456 | 185.484.322 | 5.633.491 | 179.850.831 | 0.690983 | 0.020986 | 0.669997 | 2.000115 | 1.924175 | 2.002590 |
29 | 536.870.912 | 370.987.790 | 10.855.980 | 360.131.810 | 0.691019 | 0.020221 | 0.670798 | 2.000103 | 1.927043 | 2.002392 |
30 | 1.073.741.824 | 742.007.276 | 20.950.870 | 721.056.406 | 0.691048 | 0.019512 | 0.671536 | 2.000086 | 1.929892 | 2.002201 |
31 | 2.147.483.648 | 1.484.120.041 | 40.474.631 | 1.443.645.410 | 0.691097 | 0.018847 | 0.672250 | 2.000142 | 1.931883 | 2.002126 |
32 | 4.294.967.296 | 2.968.390.522 | 78.290.558 | 2.890.099.964 | 0.691132 | 0.018228 | 0.672904 | 2.000101 | 1.934312 | 2.001946 |
33 | 8.589.934.592 | 5.937.156.424 | 151.596.215 | 5.785.560.209 | 0.691176 | 0.017648 | 0.673528 | 2.000127 | 1.936328 | 2.001855 |
34 | 17.179.869.184 | 11.875.004.651 | 293.828.361 | 11.581.176.290 | 0.691216 | 0.017103 | 0.674113 | 2.000116 | 1.938230 | 2.001738 |
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 | 1 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 0 | 1 | 0 | 0 | 1 |
3 | 8 | 3 | 1 | 1 | 1 | 0 | 0 | 2 |
4 | 16 | 4 | 1 | 2 | 1 | 0 | 0 | 3 |
5 | 32 | 6 | 1 | 4 | 1 | 0 | 0 | 5 |
6 | 64 | 10 | 1 | 7 | 1 | 0 | 0 | 9 |
7 | 128 | 15 | 1 | 12 | 1 | 0 | 0 | 14 |
8 | 256 | 23 | 1 | 20 | 1 | 0 | 0 | 22 |
9 | 512 | 42 | 1 | 39 | 1 | 0 | 0 | 41 |
10 | 1.024 | 70 | 1 | 67 | 1 | 0 | 0 | 69 |
11 | 2.048 | 121 | 1 | 118 | 1 | 0 | 0 | 120 |
12 | 4.096 | 231 | 1 | 228 | 1 | 0 | 0 | 230 |
13 | 8.192 | 405 | 1 | 402 | 1 | 0 | 0 | 404 |
14 | 16.384 | 760 | 1 | 757 | 1 | 0 | 0 | 759 |
15 | 32.768 | 1.397 | 1 | 1.394 | 1 | 0 | 0 | 1.396 |
16 | 65.536 | 2.544 | 1 | 2.541 | 1 | 0 | 0 | 2.543 |
17 | 131.072 | 4.739 | 1 | 4.736 | 1 | 0 | 0 | 4.738 |
18 | 262.144 | 8.980 | 1 | 8.977 | 1 | 0 | 0 | 8.979 |
19 | 524.288 | 16.848 | 1 | 16.845 | 1 | 0 | 0 | 16.847 |
20 | 1.048.576 | 31.773 | 1 | 31.770 | 1 | 0 | 0 | 31.772 |
21 | 2.097.152 | 60.180 | 1 | 60.177 | 1 | 0 | 0 | 60.179 |
22 | 4.194.304 | 114.048 | 1 | 114.045 | 1 | 0 | 0 | 114.047 |
23 | 8.388.608 | 217.495 | 1 | 217.492 | 1 | 0 | 0 | 217.494 |
24 | 16.777.216 | 415.442 | 1 | 415.439 | 1 | 0 | 0 | 415.441 |
25 | 33.554.432 | 794.956 | 1 | 794.953 | 1 | 0 | 0 | 794.955 |
26 | 67.108.864 | 1.524.431 | 1 | 1.524.428 | 1 | 0 | 0 | 1.524.430 |
27 | 134.217.728 | 2.927.744 | 1 | 2.927.741 | 1 | 0 | 0 | 2.927.743 |
28 | 268.435.456 | 5.633.491 | 1 | 5.633.488 | 1 | 0 | 0 | 5.633.490 |
29 | 536.870.912 | 10.855.980 | 1 | 10.855.977 | 1 | 0 | 0 | 10.855.979 |
30 | 1.073.741.824 | 20.950.870 | 1 | 20.950.867 | 1 | 0 | 0 | 20.950.869 |
31 | 2.147.483.648 | 40.474.631 | 1 | 40.474.628 | 1 | 0 | 0 | 40.474.630 |
32 | 4.294.967.296 | 78.290.558 | 1 | 78.290.555 | 1 | 0 | 0 | 78.290.557 |
33 | 8.589.934.592 | 151.596.215 | 1 | 151.596.212 | 1 | 0 | 0 | 151.596.214 |
34 | 17.179.869.184 | 293.828.361 | 1 | 293.828.358 | 1 | 0 | 0 | 293.828.360 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 5 | 1 | 3 | 0 | 2 | 1 | 2 |
4 | 16 | 11 | 5 | 5 | 0 | 5 | 4 | 2 |
5 | 32 | 22 | 12 | 9 | 2 | 6 | 10 | 4 |
6 | 64 | 46 | 27 | 18 | 8 | 10 | 17 | 11 |
7 | 128 | 84 | 50 | 33 | 13 | 18 | 30 | 23 |
8 | 256 | 165 | 100 | 64 | 30 | 35 | 59 | 41 |
9 | 512 | 318 | 173 | 144 | 61 | 68 | 115 | 74 |
10 | 1.024 | 642 | 360 | 281 | 130 | 145 | 222 | 145 |
11 | 2.048 | 1.300 | 701 | 598 | 275 | 295 | 434 | 296 |
12 | 4.096 | 2.590 | 1.375 | 1.214 | 577 | 565 | 833 | 615 |
13 | 8.192 | 5.223 | 2.791 | 2.431 | 1.138 | 1.173 | 1.671 | 1.241 |
14 | 16.384 | 10.503 | 5.622 | 4.880 | 2.345 | 2.335 | 3.293 | 2.530 |
15 | 32.768 | 21.168 | 11.219 | 9.948 | 4.786 | 4.777 | 6.545 | 5.060 |
16 | 65.536 | 42.595 | 22.534 | 20.060 | 9.795 | 9.655 | 12.893 | 10.252 |
17 | 131.072 | 85.638 | 45.157 | 40.480 | 19.790 | 19.538 | 25.577 | 20.733 |
18 | 262.144 | 171.872 | 90.380 | 81.491 | 39.857 | 39.752 | 50.720 | 41.543 |
19 | 524.288 | 345.227 | 181.004 | 164.222 | 80.430 | 80.122 | 100.842 | 83.833 |
20 | 1.048.576 | 692.324 | 362.080 | 330.243 | 161.830 | 161.166 | 200.835 | 168.493 |
21 | 2.097.152 | 1.388.227 | 724.624 | 663.602 | 325.740 | 324.748 | 399.124 | 338.615 |
22 | 4.194.304 | 2.782.811 | 1.449.725 | 1.333.085 | 655.032 | 653.904 | 793.902 | 679.973 |
23 | 8.388.608 | 5.576.935 | 2.899.974 | 2.676.960 | 1.317.355 | 1.315.020 | 1.581.594 | 1.362.966 |
24 | 16.777.216 | 11.174.750 | 5.802.113 | 5.372.636 | 2.646.383 | 2.644.722 | 3.151.075 | 2.732.570 |
25 | 33.554.432 | 22.386.646 | 11.603.305 | 10.783.340 | 5.316.181 | 5.310.453 | 6.280.212 | 5.479.800 |
26 | 67.108.864 | 44.840.137 | 23.204.489 | 21.635.647 | 10.672.251 | 10.661.808 | 12.518.921 | 10.987.157 |
27 | 134.217.728 | 89.809.103 | 46.404.684 | 43.404.418 | 21.420.540 | 21.399.820 | 24.969.176 | 22.019.567 |
28 | 268.435.456 | 179.850.831 | 92.803.199 | 87.047.631 | 42.976.331 | 42.939.191 | 49.804.708 | 44.130.601 |
29 | 536.870.912 | 360.131.810 | 185.600.746 | 174.531.063 | 86.215.131 | 86.141.243 | 99.350.534 | 88.424.902 |
30 | 1.073.741.824 | 721.056.406 | 371.189.164 | 349.867.241 | 172.905.328 | 172.761.715 | 198.234.212 | 177.155.151 |
31 | 2.147.483.648 | 1.443.645.410 | 742.437.957 | 701.207.452 | 346.702.145 | 346.438.528 | 395.629.488 | 354.875.249 |
32 | 4.294.967.296 | 2.890.099.964 | 1.484.873.393 | 1.405.226.570 | 695.063.076 | 694.544.807 | 789.636.446 | 710.855.635 |
33 | 8.589.934.592 | 5.785.560.209 | 2.969.885.559 | 2.815.674.649 | 1.393.246.650 | 1.392.202.110 | 1.576.299.018 | 1.423.812.431 |
34 | 17.179.869.184 | 11.581.176.290 | 5.939.980.931 | 5.641.195.358 | 2.792.269.972 | 2.790.432.359 | 3.146.959.336 | 2.851.514.623 |