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+23x-97
f(0)=97
f(1)=73
f(2)=47
f(3)=19
f(4)=11
f(5)=43
f(6)=7
f(7)=113
f(8)=151
f(9)=191
f(10)=233
f(11)=277
f(12)=17
f(13)=53
f(14)=421
f(15)=1
f(16)=31
f(17)=1
f(18)=641
f(19)=701
f(20)=109
f(21)=827
f(22)=1
f(23)=1
f(24)=1031
f(25)=1103
f(26)=107
f(27)=179
f(28)=1
f(29)=83
f(30)=1493
f(31)=1
f(32)=1663
f(33)=103
f(34)=263
f(35)=1933
f(36)=2027
f(37)=193
f(38)=2221
f(39)=211
f(40)=2423
f(41)=1
f(42)=2633
f(43)=2741
f(44)=2851
f(45)=2963
f(46)=181
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=3677
f(52)=3803
f(53)=3931
f(54)=131
f(55)=599
f(56)=4327
f(57)=4463
f(58)=1
f(59)=431
f(60)=257
f(61)=457
f(62)=739
f(63)=313
f(64)=5471
f(65)=5623
f(66)=1
f(67)=349
f(68)=6091
f(69)=1
f(70)=1
f(71)=6577
f(72)=613
f(73)=6911
f(74)=1
f(75)=7253
f(76)=1061
f(77)=7603
f(78)=251
f(79)=419
f(80)=479
f(81)=757
f(82)=8513
f(83)=1
f(84)=523
f(85)=293
f(86)=9277
f(87)=9473
f(88)=509
f(89)=9871
f(90)=1439
f(91)=239
f(92)=953
f(93)=10691
f(94)=991
f(95)=11113
f(96)=241
f(97)=1
f(98)=619
f(99)=11981
b) Substitution of the polynom
The polynom f(x)=x^2+23x-97 could be written as f(y)= y^2-229.25 with x=y-11.5
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+11.5
f'(x)>2x+22
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 | 11 | 11 | 0 | 1.100000 | 1.100000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 49 | 32 | 0.810000 | 0.490000 | 0.810000 | 7.363636 | 4.454545 | inf |
3 | 1.000 | 730 | 291 | 439 | 0.730000 | 0.291000 | 0.730000 | 9.012345 | 5.938776 | 13.718750 |
4 | 10.000 | 7.229 | 2.094 | 5.135 | 0.722900 | 0.209400 | 0.722900 | 9.902740 | 7.195876 | 11.697039 |
5 | 100.000 | 71.927 | 16.014 | 55.913 | 0.719270 | 0.160140 | 0.719270 | 9.949785 | 7.647564 | 10.888608 |
6 | 1.000.000 | 715.595 | 129.990 | 585.605 | 0.715595 | 0.129990 | 0.715595 | 9.948907 | 8.117272 | 10.473503 |
7 | 10.000.000 | 7.120.283 | 1.101.409 | 6.018.874 | 0.712028 | 0.110141 | 0.712028 | 9.950157 | 8.473029 | 10.278044 |
8 | 100.000.000 | 70.942.998 | 9.550.369 | 61.392.629 | 0.709430 | 0.095504 | 0.709430 | 9.963509 | 8.671047 | 10.200019 |
9 | 1.000.000.000 | 707.495.961 | 84.277.172 | 623.218.789 | 0.707496 | 0.084277 | 0.707496 | 9.972737 | 8.824493 | 10.151362 |
10 | 10.000.000.000 | 7.059.733.183 | 754.204.367 | 6.305.528.816 | 0.705973 | 0.075420 | 0.705973 | 9.978478 | 8.949095 | 10.117681 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 13 | 1 | 0.875000 | 0.812500 | 0.062500 | 1.555556 | 1.444444 | inf |
5 | 32 | 25 | 20 | 5 | 0.781250 | 0.625000 | 0.156250 | 1.785714 | 1.538462 | 5.000000 |
6 | 64 | 51 | 35 | 16 | 0.796875 | 0.546875 | 0.250000 | 2.040000 | 1.750000 | 3.200000 |
7 | 128 | 101 | 58 | 43 | 0.789062 | 0.453125 | 0.335938 | 1.980392 | 1.657143 | 2.687500 |
8 | 256 | 193 | 94 | 99 | 0.753906 | 0.367188 | 0.386719 | 1.910891 | 1.620690 | 2.302325 |
9 | 512 | 378 | 164 | 214 | 0.738281 | 0.320312 | 0.417969 | 1.958549 | 1.744681 | 2.161616 |
10 | 1.024 | 748 | 296 | 452 | 0.730469 | 0.289062 | 0.441406 | 1.978836 | 1.804878 | 2.112149 |
11 | 2.048 | 1.492 | 542 | 950 | 0.728516 | 0.264648 | 0.463867 | 1.994652 | 1.831081 | 2.101770 |
12 | 4.096 | 2.975 | 950 | 2.025 | 0.726318 | 0.231934 | 0.494385 | 1.993968 | 1.752768 | 2.131579 |
13 | 8.192 | 5.944 | 1.752 | 4.192 | 0.725586 | 0.213867 | 0.511719 | 1.997983 | 1.844211 | 2.070123 |
14 | 16.384 | 11.820 | 3.183 | 8.637 | 0.721436 | 0.194275 | 0.527161 | 1.988560 | 1.816781 | 2.060353 |
15 | 32.768 | 23.641 | 5.950 | 17.691 | 0.721466 | 0.181580 | 0.539886 | 2.000085 | 1.869306 | 2.048281 |
16 | 65.536 | 47.216 | 10.948 | 36.268 | 0.720459 | 0.167053 | 0.553406 | 1.997208 | 1.840000 | 2.050082 |
17 | 131.072 | 94.311 | 20.452 | 73.859 | 0.719536 | 0.156036 | 0.563499 | 1.997437 | 1.868104 | 2.036479 |
18 | 262.144 | 188.287 | 38.191 | 150.096 | 0.718258 | 0.145687 | 0.572571 | 1.996448 | 1.867348 | 2.032197 |
19 | 524.288 | 375.833 | 71.834 | 303.999 | 0.716845 | 0.137012 | 0.579832 | 1.996065 | 1.880914 | 2.025364 |
20 | 1.048.576 | 750.298 | 135.839 | 614.459 | 0.715540 | 0.129546 | 0.585994 | 1.996360 | 1.891013 | 2.021253 |
21 | 2.097.152 | 1.497.833 | 257.770 | 1.240.063 | 0.714222 | 0.122914 | 0.591308 | 1.996318 | 1.897614 | 2.018138 |
22 | 4.194.304 | 2.991.473 | 490.510 | 2.500.963 | 0.713223 | 0.116947 | 0.596276 | 1.997201 | 1.902898 | 2.016803 |
23 | 8.388.608 | 5.974.612 | 934.521 | 5.040.091 | 0.712229 | 0.111404 | 0.600826 | 1.997214 | 1.905203 | 2.015260 |
24 | 16.777.216 | 11.933.975 | 1.786.493 | 10.147.482 | 0.711320 | 0.106483 | 0.604837 | 1.997448 | 1.911667 | 2.013353 |
25 | 33.554.432 | 23.840.979 | 3.421.744 | 20.419.235 | 0.710517 | 0.101976 | 0.608541 | 1.997740 | 1.915341 | 2.012247 |
26 | 67.108.864 | 47.634.739 | 6.561.303 | 41.073.436 | 0.709813 | 0.097771 | 0.612042 | 1.998019 | 1.917532 | 2.011507 |
27 | 134.217.728 | 95.181.568 | 12.603.558 | 82.578.010 | 0.709158 | 0.093904 | 0.615254 | 1.998154 | 1.920893 | 2.010497 |
28 | 268.435.456 | 190.198.859 | 24.247.829 | 165.951.030 | 0.708546 | 0.090330 | 0.618216 | 1.998274 | 1.923887 | 2.009627 |
29 | 536.870.912 | 380.086.885 | 46.728.186 | 333.358.699 | 0.707967 | 0.087038 | 0.620929 | 1.998366 | 1.927108 | 2.008778 |
30 | 1.073.741.824 | 759.611.658 | 90.166.006 | 669.445.652 | 0.707443 | 0.083974 | 0.623470 | 1.998521 | 1.929585 | 2.008184 |
31 | 2.147.483.648 | 1.518.169.166 | 174.193.517 | 1.343.975.649 | 0.706953 | 0.081115 | 0.625837 | 1.998612 | 1.931920 | 2.007595 |
32 | 4.294.967.296 | 3.034.370.244 | 336.921.213 | 2.697.449.031 | 0.706494 | 0.078446 | 0.628049 | 1.998704 | 1.934178 | 2.007067 |
33 | 8.589.934.592 | 6.065.023.030 | 652.389.650 | 5.412.633.380 | 0.706062 | 0.075948 | 0.630113 | 1.998775 | 1.936327 | 2.006575 |
34 | 17.179.869.184 | 12.123.158.478 | 1.264.518.855 | 10.858.639.623 | 0.705661 | 0.073605 | 0.632056 | 1.998864 | 1.938288 | 2.006166 |
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 | 3 | 2 | 1 | 2 | 0 | 0 | 1 |
2 | 4 | 5 | 3 | 2 | 2 | 2 | 0 | 1 |
3 | 8 | 9 | 5 | 4 | 3 | 3 | 1 | 2 |
4 | 16 | 13 | 7 | 6 | 4 | 3 | 3 | 3 |
5 | 32 | 20 | 8 | 12 | 5 | 4 | 5 | 6 |
6 | 64 | 35 | 13 | 22 | 6 | 9 | 10 | 10 |
7 | 128 | 58 | 23 | 35 | 11 | 15 | 16 | 16 |
8 | 256 | 94 | 30 | 64 | 20 | 25 | 23 | 26 |
9 | 512 | 164 | 56 | 108 | 38 | 43 | 42 | 41 |
10 | 1.024 | 296 | 101 | 195 | 70 | 74 | 80 | 72 |
11 | 2.048 | 542 | 180 | 362 | 134 | 133 | 146 | 129 |
12 | 4.096 | 950 | 318 | 632 | 241 | 237 | 246 | 226 |
13 | 8.192 | 1.752 | 594 | 1.158 | 438 | 437 | 453 | 424 |
14 | 16.384 | 3.183 | 1.065 | 2.118 | 797 | 781 | 816 | 789 |
15 | 32.768 | 5.950 | 1.983 | 3.967 | 1.483 | 1.482 | 1.483 | 1.502 |
16 | 65.536 | 10.948 | 3.662 | 7.286 | 2.754 | 2.724 | 2.728 | 2.742 |
17 | 131.072 | 20.452 | 6.853 | 13.599 | 5.088 | 5.145 | 5.120 | 5.099 |
18 | 262.144 | 38.191 | 12.653 | 25.538 | 9.567 | 9.560 | 9.530 | 9.534 |
19 | 524.288 | 71.834 | 23.902 | 47.932 | 17.882 | 17.847 | 18.134 | 17.971 |
20 | 1.048.576 | 135.839 | 45.269 | 90.570 | 33.920 | 33.819 | 34.145 | 33.955 |
21 | 2.097.152 | 257.770 | 85.720 | 172.050 | 64.365 | 64.402 | 64.537 | 64.466 |
22 | 4.194.304 | 490.510 | 163.259 | 327.251 | 122.693 | 122.674 | 122.437 | 122.706 |
23 | 8.388.608 | 934.521 | 311.454 | 623.067 | 233.899 | 233.915 | 233.570 | 233.137 |
24 | 16.777.216 | 1.786.493 | 595.318 | 1.191.175 | 446.879 | 447.063 | 446.008 | 446.543 |
25 | 33.554.432 | 3.421.744 | 1.140.410 | 2.281.334 | 855.570 | 856.419 | 854.591 | 855.164 |
26 | 67.108.864 | 6.561.303 | 2.186.407 | 4.374.896 | 1.640.713 | 1.641.602 | 1.639.307 | 1.639.681 |
27 | 134.217.728 | 12.603.558 | 4.200.658 | 8.402.900 | 3.152.148 | 3.153.196 | 3.148.605 | 3.149.609 |
28 | 268.435.456 | 24.247.829 | 8.083.143 | 16.164.686 | 6.061.824 | 6.064.272 | 6.060.680 | 6.061.053 |
29 | 536.870.912 | 46.728.186 | 15.575.493 | 31.152.693 | 11.682.816 | 11.683.235 | 11.679.485 | 11.682.650 |
30 | 1.073.741.824 | 90.166.006 | 30.053.302 | 60.112.704 | 22.540.747 | 22.544.414 | 22.537.977 | 22.542.868 |
31 | 2.147.483.648 | 174.193.517 | 58.060.051 | 116.133.466 | 43.548.268 | 43.550.847 | 43.547.488 | 43.546.914 |
32 | 4.294.967.296 | 336.921.213 | 112.308.149 | 224.613.064 | 84.226.903 | 84.236.991 | 84.229.761 | 84.227.558 |
33 | 8.589.934.592 | 652.389.650 | 217.466.955 | 434.922.695 | 163.104.956 | 163.103.395 | 163.091.418 | 163.089.881 |
34 | 17.179.869.184 | 1.264.518.855 | 421.510.260 | 843.008.595 | 316.133.552 | 316.136.665 | 316.115.749 | 316.132.889 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
5 | 32 | 5 | 1 | 4 | 0 | 3 | 2 | 0 |
6 | 64 | 16 | 8 | 8 | 4 | 5 | 3 | 4 |
7 | 128 | 43 | 21 | 22 | 9 | 11 | 12 | 11 |
8 | 256 | 99 | 51 | 48 | 22 | 24 | 26 | 27 |
9 | 512 | 214 | 104 | 110 | 58 | 53 | 57 | 46 |
10 | 1.024 | 452 | 216 | 236 | 116 | 121 | 114 | 101 |
11 | 2.048 | 950 | 456 | 494 | 232 | 241 | 253 | 224 |
12 | 4.096 | 2.025 | 979 | 1.046 | 495 | 493 | 525 | 512 |
13 | 8.192 | 4.192 | 2.088 | 2.104 | 1.030 | 1.044 | 1.058 | 1.060 |
14 | 16.384 | 8.637 | 4.282 | 4.355 | 2.165 | 2.171 | 2.174 | 2.127 |
15 | 32.768 | 17.691 | 8.863 | 8.828 | 4.368 | 4.485 | 4.440 | 4.398 |
16 | 65.536 | 36.268 | 18.114 | 18.154 | 9.023 | 9.073 | 9.075 | 9.097 |
17 | 131.072 | 73.859 | 37.049 | 36.810 | 18.403 | 18.493 | 18.571 | 18.392 |
18 | 262.144 | 150.096 | 75.046 | 75.050 | 37.475 | 37.648 | 37.409 | 37.564 |
19 | 524.288 | 303.999 | 152.179 | 151.820 | 75.792 | 76.160 | 75.999 | 76.048 |
20 | 1.048.576 | 614.459 | 307.534 | 306.925 | 153.381 | 153.566 | 153.623 | 153.889 |
21 | 2.097.152 | 1.240.063 | 620.725 | 619.338 | 309.522 | 309.678 | 309.990 | 310.873 |
22 | 4.194.304 | 2.500.963 | 1.251.286 | 1.249.677 | 624.272 | 624.641 | 626.204 | 625.846 |
23 | 8.388.608 | 5.040.091 | 2.520.902 | 2.519.189 | 1.259.083 | 1.258.988 | 1.261.788 | 1.260.232 |
24 | 16.777.216 | 10.147.482 | 5.077.091 | 5.070.391 | 2.536.670 | 2.535.290 | 2.538.261 | 2.537.261 |
25 | 33.554.432 | 20.419.235 | 10.219.395 | 10.199.840 | 5.104.463 | 5.103.069 | 5.106.004 | 5.105.699 |
26 | 67.108.864 | 41.073.436 | 20.552.956 | 20.520.480 | 10.268.286 | 10.266.474 | 10.271.122 | 10.267.554 |
27 | 134.217.728 | 82.578.010 | 41.317.425 | 41.260.585 | 20.647.210 | 20.640.947 | 20.647.339 | 20.642.514 |
28 | 268.435.456 | 165.951.030 | 83.036.877 | 82.914.153 | 41.493.832 | 41.488.751 | 41.484.784 | 41.483.663 |
29 | 536.870.912 | 333.358.699 | 166.802.276 | 166.556.423 | 83.342.027 | 83.349.289 | 83.337.659 | 83.329.724 |
30 | 1.073.741.824 | 669.445.652 | 334.967.148 | 334.478.504 | 167.369.888 | 167.367.899 | 167.350.346 | 167.357.519 |
31 | 2.147.483.648 | 1.343.975.649 | 672.454.410 | 671.521.239 | 335.995.244 | 335.994.688 | 335.996.287 | 335.989.430 |
32 | 4.294.967.296 | 2.697.449.031 | 1.349.621.097 | 1.347.827.934 | 674.362.088 | 674.349.319 | 674.366.923 | 674.370.701 |
33 | 8.589.934.592 | 5.412.633.380 | 2.708.014.432 | 2.704.618.948 | 1.353.179.987 | 1.353.129.942 | 1.353.171.800 | 1.353.151.651 |
34 | 17.179.869.184 | 10.858.639.623 | 5.432.595.342 | 5.426.044.281 | 2.714.663.383 | 2.714.672.455 | 2.714.702.651 | 2.714.601.134 |