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+124x-3
f(0)=3
f(1)=61
f(2)=83
f(3)=7
f(4)=509
f(5)=107
f(6)=37
f(7)=457
f(8)=13
f(9)=199
f(10)=191
f(11)=19
f(12)=181
f(13)=127
f(14)=643
f(15)=347
f(16)=2237
f(17)=1
f(18)=23
f(19)=59
f(20)=137
f(21)=1
f(22)=3209
f(23)=563
f(24)=1
f(25)=1861
f(26)=433
f(27)=97
f(28)=4253
f(29)=739
f(30)=1
f(31)=1
f(32)=1663
f(33)=863
f(34)=1
f(35)=103
f(36)=101
f(37)=229
f(38)=293
f(39)=353
f(40)=79
f(41)=1
f(42)=1
f(43)=1
f(44)=821
f(45)=1
f(46)=7817
f(47)=1
f(48)=131
f(49)=223
f(50)=1
f(51)=1487
f(52)=1307
f(53)=521
f(54)=3203
f(55)=1
f(56)=3359
f(57)=1
f(58)=173
f(59)=257
f(60)=283
f(61)=5641
f(62)=1
f(63)=151
f(64)=523
f(65)=89
f(66)=1
f(67)=6397
f(68)=1
f(69)=317
f(70)=13577
f(71)=769
f(72)=4703
f(73)=1
f(74)=1
f(75)=829
f(76)=167
f(77)=2579
f(78)=1
f(79)=8017
f(80)=1
f(81)=2767
f(82)=16889
f(83)=409
f(84)=647
f(85)=1
f(86)=463
f(87)=1
f(88)=811
f(89)=1
f(90)=1
f(91)=9781
f(92)=179
f(93)=1
f(94)=2927
f(95)=3467
f(96)=7039
f(97)=1531
f(98)=2417
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+124x-3 could be written as f(y)= y^2-3847 with x=y-62
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+62
f'(x)>2x+123
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 | 4 | 6 | 1.000000 | 0.400000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 68 | 16 | 52 | 0.680000 | 0.160000 | 0.520000 | 6.800000 | 4.000000 | 8.666667 |
3 | 1.000 | 625 | 104 | 521 | 0.625000 | 0.104000 | 0.521000 | 9.191176 | 6.500000 | 10.019231 |
4 | 10.000 | 6.411 | 679 | 5.732 | 0.641100 | 0.067900 | 0.573200 | 10.257600 | 6.528846 | 11.001920 |
5 | 100.000 | 65.438 | 5.211 | 60.227 | 0.654380 | 0.052110 | 0.602270 | 10.207144 | 7.674521 | 10.507153 |
6 | 1.000.000 | 661.488 | 42.102 | 619.386 | 0.661488 | 0.042102 | 0.619386 | 10.108622 | 8.079448 | 10.284191 |
7 | 10.000.000 | 6.659.267 | 356.322 | 6.302.945 | 0.665927 | 0.035632 | 0.630295 | 10.067101 | 8.463304 | 10.176118 |
8 | 100.000.000 | 66.934.467 | 3.083.330 | 63.851.137 | 0.669345 | 0.030833 | 0.638511 | 10.051327 | 8.653213 | 10.130365 |
9 | 1.000.000.000 | 672.012.069 | 27.183.579 | 644.828.490 | 0.672012 | 0.027184 | 0.644828 | 10.039851 | 8.816306 | 10.098935 |
10 | 10.000.000.000 | 6.741.257.469 | 243.057.634 | 6.498.199.835 | 0.674126 | 0.024306 | 0.649820 | 10.031452 | 8.941340 | 10.077409 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 15 | 5 | 10 | 0.937500 | 0.312500 | 0.625000 | 1.875000 | 1.250000 | 2.500000 |
5 | 32 | 25 | 8 | 17 | 0.781250 | 0.250000 | 0.531250 | 1.666667 | 1.600000 | 1.700000 |
6 | 64 | 46 | 10 | 36 | 0.718750 | 0.156250 | 0.562500 | 1.840000 | 1.250000 | 2.117647 |
7 | 128 | 87 | 20 | 67 | 0.679688 | 0.156250 | 0.523438 | 1.891304 | 2.000000 | 1.861111 |
8 | 256 | 166 | 30 | 136 | 0.648438 | 0.117188 | 0.531250 | 1.908046 | 1.500000 | 2.029851 |
9 | 512 | 322 | 54 | 268 | 0.628906 | 0.105469 | 0.523438 | 1.939759 | 1.800000 | 1.970588 |
10 | 1.024 | 637 | 106 | 531 | 0.622070 | 0.103516 | 0.518555 | 1.978261 | 1.962963 | 1.981343 |
11 | 2.048 | 1.284 | 181 | 1.103 | 0.626953 | 0.088379 | 0.538574 | 2.015699 | 1.707547 | 2.077213 |
12 | 4.096 | 2.591 | 316 | 2.275 | 0.632568 | 0.077148 | 0.555420 | 2.017913 | 1.745856 | 2.062557 |
13 | 8.192 | 5.233 | 556 | 4.677 | 0.638794 | 0.067871 | 0.570923 | 2.019684 | 1.759494 | 2.055824 |
14 | 16.384 | 10.542 | 1.051 | 9.491 | 0.643433 | 0.064148 | 0.579285 | 2.014523 | 1.890288 | 2.029292 |
15 | 32.768 | 21.266 | 1.898 | 19.368 | 0.648987 | 0.057922 | 0.591064 | 2.017264 | 1.805899 | 2.040670 |
16 | 65.536 | 42.756 | 3.543 | 39.213 | 0.652405 | 0.054062 | 0.598343 | 2.010533 | 1.866702 | 2.024628 |
17 | 131.072 | 86.005 | 6.615 | 79.390 | 0.656166 | 0.050468 | 0.605698 | 2.011531 | 1.867062 | 2.024584 |
18 | 262.144 | 172.518 | 12.368 | 160.150 | 0.658104 | 0.047180 | 0.610924 | 2.005907 | 1.869690 | 2.017256 |
19 | 524.288 | 345.922 | 23.273 | 322.649 | 0.659794 | 0.044390 | 0.615404 | 2.005136 | 1.881711 | 2.014668 |
20 | 1.048.576 | 693.775 | 44.010 | 649.765 | 0.661635 | 0.041971 | 0.619664 | 2.005582 | 1.891033 | 2.013845 |
21 | 2.097.152 | 1.390.365 | 83.371 | 1.306.994 | 0.662978 | 0.039754 | 0.623223 | 2.004057 | 1.894365 | 2.011487 |
22 | 4.194.304 | 2.786.284 | 158.824 | 2.627.460 | 0.664302 | 0.037867 | 0.626435 | 2.003995 | 1.905027 | 2.010308 |
23 | 8.388.608 | 5.583.378 | 302.608 | 5.280.770 | 0.665591 | 0.036074 | 0.629517 | 2.003880 | 1.905304 | 2.009838 |
24 | 16.777.216 | 11.186.912 | 577.286 | 10.609.626 | 0.666792 | 0.034409 | 0.632383 | 2.003610 | 1.907702 | 2.009106 |
25 | 33.554.432 | 22.408.730 | 1.105.402 | 21.303.328 | 0.667832 | 0.032944 | 0.634889 | 2.003120 | 1.914826 | 2.007925 |
26 | 67.108.864 | 44.884.821 | 2.118.824 | 42.765.997 | 0.668836 | 0.031573 | 0.637263 | 2.003006 | 1.916790 | 2.007480 |
27 | 134.217.728 | 89.889.525 | 4.068.932 | 85.820.593 | 0.669729 | 0.030316 | 0.639413 | 2.002671 | 1.920373 | 2.006748 |
28 | 268.435.456 | 180.004.135 | 7.826.739 | 172.177.396 | 0.670568 | 0.029157 | 0.641411 | 2.002504 | 1.923536 | 2.006248 |
29 | 536.870.912 | 360.428.534 | 15.077.992 | 345.350.542 | 0.671350 | 0.028085 | 0.643265 | 2.002335 | 1.926472 | 2.005783 |
30 | 1.073.741.824 | 721.645.773 | 29.081.919 | 692.563.854 | 0.672085 | 0.027085 | 0.645000 | 2.002188 | 1.928766 | 2.005394 |
31 | 2.147.483.648 | 1.444.749.712 | 56.170.978 | 1.388.578.734 | 0.672764 | 0.026157 | 0.646607 | 2.002021 | 1.931474 | 2.004983 |
32 | 4.294.967.296 | 2.892.235.308 | 108.610.997 | 2.783.624.311 | 0.673401 | 0.025288 | 0.648113 | 2.001894 | 1.933579 | 2.004657 |
33 | 8.589.934.592 | 5.789.624.468 | 210.252.667 | 5.579.371.801 | 0.674001 | 0.024477 | 0.649524 | 2.001782 | 1.935832 | 2.004355 |
34 | 17.179.869.184 | 11.588.938.064 | 407.425.728 | 11.181.512.336 | 0.674565 | 0.023715 | 0.650850 | 2.001673 | 1.937791 | 2.004081 |
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 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 1 | 2 | 0 |
3 | 8 | 4 | 2 | 1 | 1 | 1 | 2 | 0 |
4 | 16 | 5 | 2 | 2 | 1 | 1 | 3 | 0 |
5 | 32 | 8 | 3 | 4 | 2 | 1 | 5 | 0 |
6 | 64 | 10 | 4 | 5 | 4 | 1 | 5 | 0 |
7 | 128 | 20 | 11 | 8 | 10 | 1 | 9 | 0 |
8 | 256 | 30 | 18 | 11 | 14 | 1 | 15 | 0 |
9 | 512 | 54 | 28 | 25 | 23 | 1 | 30 | 0 |
10 | 1.024 | 106 | 56 | 49 | 47 | 1 | 58 | 0 |
11 | 2.048 | 181 | 95 | 85 | 91 | 1 | 89 | 0 |
12 | 4.096 | 316 | 153 | 162 | 159 | 1 | 156 | 0 |
13 | 8.192 | 556 | 272 | 283 | 272 | 1 | 283 | 0 |
14 | 16.384 | 1.051 | 502 | 548 | 525 | 1 | 525 | 0 |
15 | 32.768 | 1.898 | 905 | 992 | 957 | 1 | 940 | 0 |
16 | 65.536 | 3.543 | 1.745 | 1.797 | 1.778 | 1 | 1.764 | 0 |
17 | 131.072 | 6.615 | 3.318 | 3.296 | 3.340 | 1 | 3.274 | 0 |
18 | 262.144 | 12.368 | 6.288 | 6.079 | 6.248 | 1 | 6.119 | 0 |
19 | 524.288 | 23.273 | 11.827 | 11.445 | 11.764 | 1 | 11.508 | 0 |
20 | 1.048.576 | 44.010 | 22.399 | 21.610 | 22.183 | 1 | 21.826 | 0 |
21 | 2.097.152 | 83.371 | 42.236 | 41.134 | 41.909 | 1 | 41.461 | 0 |
22 | 4.194.304 | 158.824 | 80.524 | 78.299 | 79.653 | 1 | 79.170 | 0 |
23 | 8.388.608 | 302.608 | 153.229 | 149.378 | 151.525 | 1 | 151.082 | 0 |
24 | 16.777.216 | 577.286 | 291.902 | 285.383 | 288.503 | 1 | 288.782 | 0 |
25 | 33.554.432 | 1.105.402 | 558.795 | 546.606 | 552.341 | 1 | 553.060 | 0 |
26 | 67.108.864 | 2.118.824 | 1.071.169 | 1.047.654 | 1.058.752 | 1 | 1.060.071 | 0 |
27 | 134.217.728 | 4.068.932 | 2.054.891 | 2.014.040 | 2.034.253 | 1 | 2.034.678 | 0 |
28 | 268.435.456 | 7.826.739 | 3.952.727 | 3.874.011 | 3.913.314 | 1 | 3.913.424 | 0 |
29 | 536.870.912 | 15.077.992 | 7.608.824 | 7.469.167 | 7.538.096 | 1 | 7.539.895 | 0 |
30 | 1.073.741.824 | 29.081.919 | 14.671.772 | 14.410.146 | 14.539.389 | 1 | 14.542.529 | 0 |
31 | 2.147.483.648 | 56.170.978 | 28.331.774 | 27.839.203 | 28.084.850 | 1 | 28.086.127 | 0 |
32 | 4.294.967.296 | 108.610.997 | 54.759.623 | 53.851.373 | 54.309.016 | 1 | 54.301.980 | 0 |
33 | 8.589.934.592 | 210.252.667 | 105.974.314 | 104.278.352 | 105.126.557 | 1 | 105.126.109 | 0 |
34 | 17.179.869.184 | 407.425.728 | 205.302.497 | 202.123.230 | 203.711.569 | 1 | 203.714.158 | 0 |
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 | 1 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 0 | 2 | 1 | 1 |
4 | 16 | 10 | 6 | 4 | 0 | 4 | 2 | 4 |
5 | 32 | 17 | 10 | 7 | 3 | 7 | 2 | 5 |
6 | 64 | 36 | 16 | 20 | 6 | 12 | 7 | 11 |
7 | 128 | 67 | 30 | 37 | 11 | 20 | 14 | 22 |
8 | 256 | 136 | 66 | 70 | 29 | 39 | 28 | 40 |
9 | 512 | 268 | 131 | 137 | 58 | 79 | 51 | 80 |
10 | 1.024 | 531 | 258 | 273 | 100 | 168 | 108 | 155 |
11 | 2.048 | 1.103 | 547 | 556 | 230 | 324 | 227 | 322 |
12 | 4.096 | 2.275 | 1.134 | 1.141 | 481 | 664 | 486 | 644 |
13 | 8.192 | 4.677 | 2.352 | 2.325 | 1.025 | 1.322 | 1.034 | 1.296 |
14 | 16.384 | 9.491 | 4.759 | 4.732 | 2.122 | 2.638 | 2.117 | 2.614 |
15 | 32.768 | 19.368 | 9.741 | 9.627 | 4.344 | 5.393 | 4.384 | 5.247 |
16 | 65.536 | 39.213 | 19.609 | 19.604 | 8.935 | 10.732 | 8.922 | 10.624 |
17 | 131.072 | 79.390 | 39.943 | 39.447 | 18.043 | 21.741 | 18.279 | 21.327 |
18 | 262.144 | 160.150 | 80.289 | 79.861 | 36.744 | 43.334 | 37.052 | 43.020 |
19 | 524.288 | 322.649 | 161.671 | 160.978 | 74.301 | 86.819 | 74.782 | 86.747 |
20 | 1.048.576 | 649.765 | 325.055 | 324.710 | 150.626 | 173.635 | 151.303 | 174.201 |
21 | 2.097.152 | 1.306.994 | 653.611 | 653.383 | 305.115 | 347.943 | 305.588 | 348.348 |
22 | 4.194.304 | 2.627.460 | 1.313.664 | 1.313.796 | 616.953 | 697.237 | 615.576 | 697.694 |
23 | 8.388.608 | 5.280.770 | 2.641.477 | 2.639.293 | 1.244.210 | 1.396.670 | 1.242.317 | 1.397.573 |
24 | 16.777.216 | 10.609.626 | 5.306.197 | 5.303.429 | 2.505.948 | 2.799.113 | 2.505.876 | 2.798.689 |
25 | 33.554.432 | 21.303.328 | 10.656.006 | 10.647.322 | 5.047.278 | 5.605.770 | 5.045.966 | 5.604.314 |
26 | 67.108.864 | 42.765.997 | 21.390.440 | 21.375.557 | 10.155.112 | 11.226.120 | 10.156.613 | 11.228.152 |
27 | 134.217.728 | 85.820.593 | 42.923.906 | 42.896.687 | 20.424.572 | 22.483.877 | 20.427.423 | 22.484.721 |
28 | 268.435.456 | 172.177.396 | 86.118.873 | 86.058.523 | 41.062.515 | 45.021.008 | 41.067.665 | 45.026.208 |
29 | 536.870.912 | 345.350.542 | 172.722.267 | 172.628.275 | 82.511.319 | 90.152.750 | 82.530.437 | 90.156.036 |
30 | 1.073.741.824 | 692.563.854 | 346.374.163 | 346.189.691 | 165.752.312 | 180.512.899 | 165.786.816 | 180.511.827 |
31 | 2.147.483.648 | 1.388.578.734 | 694.477.162 | 694.101.572 | 332.900.554 | 361.393.451 | 332.905.442 | 361.379.287 |
32 | 4.294.967.296 | 2.783.624.311 | 1.392.133.657 | 1.391.490.654 | 668.376.414 | 723.438.992 | 668.391.994 | 723.416.911 |
33 | 8.589.934.592 | 5.579.371.801 | 2.790.333.998 | 2.789.037.803 | 1.341.597.327 | 1.448.100.659 | 1.341.580.272 | 1.448.093.543 |
34 | 17.179.869.184 | 11.181.512.336 | 5.591.984.155 | 5.589.528.181 | 2.692.250.218 | 2.898.510.040 | 2.692.211.272 | 2.898.540.806 |