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+49x-97
f(0)=97
f(1)=47
f(2)=5
f(3)=59
f(4)=23
f(5)=173
f(6)=233
f(7)=1
f(8)=359
f(9)=17
f(10)=29
f(11)=563
f(12)=127
f(13)=709
f(14)=157
f(15)=863
f(16)=41
f(17)=1
f(18)=1109
f(19)=239
f(20)=1283
f(21)=1373
f(22)=293
f(23)=1559
f(24)=331
f(25)=1753
f(26)=109
f(27)=1
f(28)=71
f(29)=433
f(30)=2273
f(31)=2383
f(32)=499
f(33)=2609
f(34)=1
f(35)=2843
f(36)=2963
f(37)=617
f(38)=3209
f(39)=1
f(40)=3463
f(41)=3593
f(42)=149
f(43)=227
f(44)=1
f(45)=4133
f(46)=4273
f(47)=883
f(48)=1
f(49)=941
f(50)=211
f(51)=5003
f(52)=1031
f(53)=5309
f(54)=1093
f(55)=5623
f(56)=5783
f(57)=1
f(58)=1
f(59)=251
f(60)=379
f(61)=389
f(62)=1
f(63)=6959
f(64)=1427
f(65)=103
f(66)=1
f(67)=307
f(68)=271
f(69)=1609
f(70)=8233
f(71)=8423
f(72)=1723
f(73)=383
f(74)=1801
f(75)=9203
f(76)=9403
f(77)=113
f(78)=577
f(79)=2003
f(80)=10223
f(81)=10433
f(82)=2129
f(83)=10859
f(84)=443
f(85)=491
f(86)=397
f(87)=2347
f(88)=11959
f(89)=2437
f(90)=12413
f(91)=269
f(92)=1
f(93)=13109
f(94)=1
f(95)=1
f(96)=601
f(97)=1
f(98)=349
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+49x-97 could be written as f(y)= y^2-697.25 with x=y-24.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+24.5
f'(x)>2x+48
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 | 9 | 7 | 2 | 0.900000 | 0.700000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 40 | 41 | 0.810000 | 0.400000 | 0.410000 | 9.000000 | 5.714286 | 20.500000 |
3 | 1.000 | 744 | 258 | 486 | 0.744000 | 0.258000 | 0.486000 | 9.185185 | 6.450000 | 11.853659 |
4 | 10.000 | 7.279 | 1.838 | 5.441 | 0.727900 | 0.183800 | 0.544100 | 9.783602 | 7.124031 | 11.195474 |
5 | 100.000 | 72.164 | 14.212 | 57.952 | 0.721640 | 0.142120 | 0.579520 | 9.914000 | 7.732318 | 10.650983 |
6 | 1.000.000 | 716.992 | 115.966 | 601.026 | 0.716992 | 0.115966 | 0.601026 | 9.935591 | 8.159724 | 10.371100 |
7 | 10.000.000 | 7.136.311 | 981.192 | 6.155.119 | 0.713631 | 0.098119 | 0.615512 | 9.953125 | 8.461032 | 10.241019 |
8 | 100.000.000 | 71.082.514 | 8.505.590 | 62.576.924 | 0.710825 | 0.085056 | 0.625769 | 9.960680 | 8.668630 | 10.166647 |
9 | 1.000.000.000 | 708.726.253 | 75.058.549 | 633.667.704 | 0.708726 | 0.075059 | 0.633668 | 9.970473 | 8.824615 | 10.126220 |
10 | 10.000.000.000 | 7.070.698.522 | 671.730.243 | 6.398.968.279 | 0.707070 | 0.067173 | 0.639897 | 9.976628 | 8.949416 | 10.098303 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 15 | 10 | 5 | 0.937500 | 0.625000 | 0.312500 | 1.875000 | 1.428571 | 5.000000 |
5 | 32 | 29 | 17 | 12 | 0.906250 | 0.531250 | 0.375000 | 1.933333 | 1.700000 | 2.400000 |
6 | 64 | 54 | 30 | 24 | 0.843750 | 0.468750 | 0.375000 | 1.862069 | 1.764706 | 2.000000 |
7 | 128 | 104 | 48 | 56 | 0.812500 | 0.375000 | 0.437500 | 1.925926 | 1.600000 | 2.333333 |
8 | 256 | 198 | 85 | 113 | 0.773438 | 0.332031 | 0.441406 | 1.903846 | 1.770833 | 2.017857 |
9 | 512 | 390 | 146 | 244 | 0.761719 | 0.285156 | 0.476562 | 1.969697 | 1.717647 | 2.159292 |
10 | 1.024 | 762 | 261 | 501 | 0.744141 | 0.254883 | 0.489258 | 1.953846 | 1.787671 | 2.053279 |
11 | 2.048 | 1.509 | 476 | 1.033 | 0.736816 | 0.232422 | 0.504395 | 1.980315 | 1.823755 | 2.061876 |
12 | 4.096 | 3.006 | 835 | 2.171 | 0.733887 | 0.203857 | 0.530029 | 1.992048 | 1.754202 | 2.101646 |
13 | 8.192 | 5.985 | 1.543 | 4.442 | 0.730591 | 0.188354 | 0.542236 | 1.991018 | 1.847904 | 2.046062 |
14 | 16.384 | 11.938 | 2.811 | 9.127 | 0.728638 | 0.171570 | 0.557068 | 1.994653 | 1.821776 | 2.054705 |
15 | 32.768 | 23.728 | 5.204 | 18.524 | 0.724121 | 0.158813 | 0.565308 | 1.987603 | 1.851298 | 2.029583 |
16 | 65.536 | 47.342 | 9.701 | 37.641 | 0.722382 | 0.148026 | 0.574356 | 1.995196 | 1.864143 | 2.032012 |
17 | 131.072 | 94.453 | 18.150 | 76.303 | 0.720619 | 0.138474 | 0.582146 | 1.995121 | 1.870941 | 2.027125 |
18 | 262.144 | 188.580 | 33.995 | 154.585 | 0.719376 | 0.129681 | 0.589695 | 1.996549 | 1.873003 | 2.025936 |
19 | 524.288 | 376.709 | 63.927 | 312.782 | 0.718515 | 0.121931 | 0.596584 | 1.997608 | 1.880482 | 2.023366 |
20 | 1.048.576 | 751.849 | 121.156 | 630.693 | 0.717019 | 0.115543 | 0.601476 | 1.995835 | 1.895224 | 2.016398 |
21 | 2.097.152 | 1.501.301 | 229.807 | 1.271.494 | 0.715876 | 0.109581 | 0.606296 | 1.996812 | 1.896786 | 2.016027 |
22 | 4.194.304 | 2.998.486 | 437.134 | 2.561.352 | 0.714895 | 0.104221 | 0.610674 | 1.997258 | 1.902179 | 2.014443 |
23 | 8.388.608 | 5.988.353 | 832.833 | 5.155.520 | 0.713867 | 0.099281 | 0.614586 | 1.997126 | 1.905212 | 2.012812 |
24 | 16.777.216 | 11.960.577 | 1.590.722 | 10.369.855 | 0.712906 | 0.094814 | 0.618092 | 1.997307 | 1.910013 | 2.011408 |
25 | 33.554.432 | 23.891.521 | 3.046.565 | 20.844.956 | 0.712023 | 0.090795 | 0.621228 | 1.997522 | 1.915209 | 2.010149 |
26 | 67.108.864 | 47.731.686 | 5.842.412 | 41.889.274 | 0.711258 | 0.087059 | 0.624199 | 1.997851 | 1.917705 | 2.009564 |
27 | 134.217.728 | 95.365.171 | 11.225.450 | 84.139.721 | 0.710526 | 0.083636 | 0.626890 | 1.997942 | 1.921373 | 2.008622 |
28 | 268.435.456 | 190.552.752 | 21.599.848 | 168.952.904 | 0.709864 | 0.080466 | 0.629399 | 1.998138 | 1.924186 | 2.008004 |
29 | 536.870.912 | 380.773.122 | 41.620.625 | 339.152.497 | 0.709245 | 0.077524 | 0.631721 | 1.998256 | 1.926894 | 2.007379 |
30 | 1.073.741.824 | 760.927.868 | 80.303.587 | 680.624.281 | 0.708669 | 0.074789 | 0.633881 | 1.998376 | 1.929418 | 2.006838 |
31 | 2.147.483.648 | 1.520.706.080 | 155.141.815 | 1.365.564.265 | 0.708134 | 0.072244 | 0.635890 | 1.998489 | 1.931941 | 2.006341 |
32 | 4.294.967.296 | 3.039.264.308 | 300.080.339 | 2.739.183.969 | 0.707634 | 0.069868 | 0.637766 | 1.998588 | 1.934233 | 2.005899 |
33 | 8.589.934.592 | 6.074.525.541 | 581.036.137 | 5.493.489.404 | 0.707168 | 0.067642 | 0.639526 | 1.998683 | 1.936269 | 2.005520 |
34 | 17.179.869.184 | 12.141.534.618 | 1.126.198.513 | 11.015.336.105 | 0.706730 | 0.065553 | 0.641177 | 1.998762 | 1.938259 | 2.005162 |
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 | 1 | 2 | 1 | 0 | 1 | 1 |
2 | 4 | 4 | 1 | 3 | 1 | 1 | 1 | 1 |
3 | 8 | 7 | 1 | 6 | 2 | 1 | 2 | 2 |
4 | 16 | 10 | 2 | 8 | 2 | 2 | 3 | 3 |
5 | 32 | 17 | 4 | 13 | 4 | 3 | 5 | 5 |
6 | 64 | 30 | 7 | 23 | 8 | 6 | 7 | 9 |
7 | 128 | 48 | 13 | 35 | 13 | 10 | 11 | 14 |
8 | 256 | 85 | 28 | 57 | 24 | 16 | 21 | 24 |
9 | 512 | 146 | 50 | 96 | 35 | 30 | 40 | 41 |
10 | 1.024 | 261 | 91 | 170 | 59 | 64 | 69 | 69 |
11 | 2.048 | 476 | 161 | 315 | 112 | 123 | 113 | 128 |
12 | 4.096 | 835 | 279 | 556 | 193 | 214 | 212 | 216 |
13 | 8.192 | 1.543 | 510 | 1.033 | 378 | 384 | 394 | 387 |
14 | 16.384 | 2.811 | 937 | 1.874 | 696 | 703 | 708 | 704 |
15 | 32.768 | 5.204 | 1.764 | 3.440 | 1.308 | 1.289 | 1.299 | 1.308 |
16 | 65.536 | 9.701 | 3.251 | 6.450 | 2.383 | 2.421 | 2.432 | 2.465 |
17 | 131.072 | 18.150 | 6.069 | 12.081 | 4.486 | 4.515 | 4.581 | 4.568 |
18 | 262.144 | 33.995 | 11.362 | 22.633 | 8.451 | 8.521 | 8.505 | 8.518 |
19 | 524.288 | 63.927 | 21.289 | 42.638 | 15.917 | 15.991 | 15.993 | 16.026 |
20 | 1.048.576 | 121.156 | 40.374 | 80.782 | 30.269 | 30.340 | 30.318 | 30.229 |
21 | 2.097.152 | 229.807 | 76.685 | 153.122 | 57.717 | 57.410 | 57.388 | 57.292 |
22 | 4.194.304 | 437.134 | 145.923 | 291.211 | 109.731 | 109.281 | 109.119 | 109.003 |
23 | 8.388.608 | 832.833 | 277.799 | 555.034 | 208.789 | 207.887 | 208.308 | 207.849 |
24 | 16.777.216 | 1.590.722 | 530.704 | 1.060.018 | 397.669 | 397.588 | 398.256 | 397.209 |
25 | 33.554.432 | 3.046.565 | 1.016.029 | 2.030.536 | 761.537 | 761.504 | 762.167 | 761.357 |
26 | 67.108.864 | 5.842.412 | 1.947.857 | 3.894.555 | 1.460.277 | 1.461.234 | 1.460.733 | 1.460.168 |
27 | 134.217.728 | 11.225.450 | 3.741.341 | 7.484.109 | 2.806.658 | 2.807.474 | 2.806.981 | 2.804.337 |
28 | 268.435.456 | 21.599.848 | 7.199.196 | 14.400.652 | 5.400.081 | 5.400.598 | 5.398.731 | 5.400.438 |
29 | 536.870.912 | 41.620.625 | 13.870.186 | 27.750.439 | 10.406.305 | 10.405.609 | 10.402.618 | 10.406.093 |
30 | 1.073.741.824 | 80.303.587 | 26.768.339 | 53.535.248 | 20.076.192 | 20.074.494 | 20.076.497 | 20.076.404 |
31 | 2.147.483.648 | 155.141.815 | 51.714.571 | 103.427.244 | 38.783.369 | 38.783.428 | 38.789.286 | 38.785.732 |
32 | 4.294.967.296 | 300.080.339 | 100.022.137 | 200.058.202 | 75.015.794 | 75.019.571 | 75.019.332 | 75.025.642 |
33 | 8.589.934.592 | 581.036.137 | 193.679.779 | 387.356.358 | 145.251.279 | 145.258.223 | 145.262.138 | 145.264.497 |
34 | 17.179.869.184 | 1.126.198.513 | 375.408.179 | 750.790.334 | 281.543.352 | 281.559.926 | 281.547.369 | 281.547.866 |
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 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
4 | 16 | 5 | 2 | 3 | 1 | 0 | 2 | 2 |
5 | 32 | 12 | 6 | 6 | 2 | 2 | 4 | 4 |
6 | 64 | 24 | 10 | 14 | 3 | 8 | 8 | 5 |
7 | 128 | 56 | 31 | 25 | 10 | 17 | 16 | 13 |
8 | 256 | 113 | 65 | 48 | 24 | 27 | 32 | 30 |
9 | 512 | 244 | 137 | 107 | 57 | 61 | 67 | 59 |
10 | 1.024 | 501 | 290 | 211 | 120 | 127 | 130 | 124 |
11 | 2.048 | 1.033 | 572 | 461 | 254 | 267 | 249 | 263 |
12 | 4.096 | 2.171 | 1.184 | 987 | 538 | 549 | 523 | 561 |
13 | 8.192 | 4.442 | 2.400 | 2.042 | 1.105 | 1.091 | 1.123 | 1.123 |
14 | 16.384 | 9.127 | 4.893 | 4.234 | 2.220 | 2.262 | 2.327 | 2.318 |
15 | 32.768 | 18.524 | 9.878 | 8.646 | 4.598 | 4.594 | 4.651 | 4.681 |
16 | 65.536 | 37.641 | 19.937 | 17.704 | 9.388 | 9.400 | 9.437 | 9.416 |
17 | 131.072 | 76.303 | 40.125 | 36.178 | 19.195 | 19.095 | 19.030 | 18.983 |
18 | 262.144 | 154.585 | 81.276 | 73.309 | 38.789 | 38.648 | 38.528 | 38.620 |
19 | 524.288 | 312.782 | 164.009 | 148.773 | 78.260 | 78.212 | 78.117 | 78.193 |
20 | 1.048.576 | 630.693 | 330.043 | 300.650 | 157.874 | 157.550 | 157.271 | 157.998 |
21 | 2.097.152 | 1.271.494 | 663.139 | 608.355 | 318.287 | 317.311 | 317.624 | 318.272 |
22 | 4.194.304 | 2.561.352 | 1.332.357 | 1.228.995 | 640.866 | 639.685 | 640.049 | 640.752 |
23 | 8.388.608 | 5.155.520 | 2.673.811 | 2.481.709 | 1.288.509 | 1.287.985 | 1.289.428 | 1.289.598 |
24 | 16.777.216 | 10.369.855 | 5.367.976 | 5.001.879 | 2.593.047 | 2.590.629 | 2.593.748 | 2.592.431 |
25 | 33.554.432 | 20.844.956 | 10.771.980 | 10.072.976 | 5.210.248 | 5.210.852 | 5.213.950 | 5.209.906 |
26 | 67.108.864 | 41.889.274 | 21.611.523 | 20.277.751 | 10.469.130 | 10.473.896 | 10.473.521 | 10.472.727 |
27 | 134.217.728 | 84.139.721 | 43.345.598 | 40.794.123 | 21.032.897 | 21.039.035 | 21.035.511 | 21.032.278 |
28 | 268.435.456 | 168.952.904 | 86.920.764 | 82.032.140 | 42.233.043 | 42.237.080 | 42.244.454 | 42.238.327 |
29 | 536.870.912 | 339.152.497 | 174.278.719 | 164.873.778 | 84.777.054 | 84.788.117 | 84.794.735 | 84.792.591 |
30 | 1.073.741.824 | 680.624.281 | 349.378.192 | 331.246.089 | 170.149.444 | 170.158.538 | 170.161.947 | 170.154.352 |
31 | 2.147.483.648 | 1.365.564.265 | 700.246.300 | 665.317.965 | 341.387.144 | 341.385.435 | 341.397.907 | 341.393.779 |
32 | 4.294.967.296 | 2.739.183.969 | 1.403.346.799 | 1.335.837.170 | 684.797.681 | 684.770.734 | 684.802.736 | 684.812.818 |
33 | 8.589.934.592 | 5.493.489.404 | 2.812.007.561 | 2.681.481.843 | 1.373.380.305 | 1.373.324.354 | 1.373.379.167 | 1.373.405.578 |
34 | 17.179.869.184 | 11.015.336.105 | 5.634.000.645 | 5.381.335.460 | 2.753.825.966 | 2.753.821.770 | 2.753.823.892 | 2.753.864.477 |