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+62x-181
f(0)=181
f(1)=59
f(2)=53
f(3)=7
f(4)=83
f(5)=11
f(6)=227
f(7)=151
f(8)=379
f(9)=229
f(10)=1
f(11)=311
f(12)=101
f(13)=397
f(14)=883
f(15)=487
f(16)=97
f(17)=1
f(18)=1259
f(19)=1
f(20)=1459
f(21)=71
f(22)=1667
f(23)=887
f(24)=269
f(25)=997
f(26)=43
f(27)=1
f(28)=2339
f(29)=1229
f(30)=2579
f(31)=193
f(32)=257
f(33)=211
f(34)=3083
f(35)=1607
f(36)=3347
f(37)=1741
f(38)=47
f(39)=1879
f(40)=557
f(41)=1
f(42)=79
f(43)=197
f(44)=4483
f(45)=331
f(46)=4787
f(47)=353
f(48)=5099
f(49)=239
f(50)=5419
f(51)=2791
f(52)=821
f(53)=2957
f(54)=1
f(55)=1
f(56)=6427
f(57)=3301
f(58)=6779
f(59)=1
f(60)=1
f(61)=523
f(62)=7507
f(63)=3847
f(64)=7883
f(65)=367
f(66)=1181
f(67)=4231
f(68)=1237
f(69)=103
f(70)=9059
f(71)=421
f(72)=9467
f(73)=691
f(74)=9883
f(75)=1
f(76)=937
f(77)=5261
f(78)=10739
f(79)=5479
f(80)=1597
f(81)=5701
f(82)=1
f(83)=5927
f(84)=281
f(85)=131
f(86)=12547
f(87)=1
f(88)=277
f(89)=947
f(90)=13499
f(91)=6871
f(92)=1
f(93)=647
f(94)=2069
f(95)=139
f(96)=2141
f(97)=7621
f(98)=1409
f(99)=7879
b) Substitution of the polynom
The polynom f(x)=x^2+62x-181 could be written as f(y)= y^2-1142 with x=y-31
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+31
f'(x)>2x+61
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 | 9 | 1 | 1.000000 | 0.900000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 52 | 29 | 0.810000 | 0.520000 | 0.810000 | 8.100000 | 5.777778 | 29.000000 |
3 | 1.000 | 747 | 326 | 421 | 0.747000 | 0.326000 | 0.747000 | 9.222222 | 6.269231 | 14.517241 |
4 | 10.000 | 7.298 | 2.315 | 4.983 | 0.729800 | 0.231500 | 0.729800 | 9.769746 | 7.101227 | 11.836104 |
5 | 100.000 | 72.242 | 17.669 | 54.573 | 0.722420 | 0.176690 | 0.722420 | 9.898876 | 7.632397 | 10.951837 |
6 | 1.000.000 | 716.928 | 144.509 | 572.419 | 0.716928 | 0.144509 | 0.716928 | 9.923978 | 8.178675 | 10.489052 |
7 | 10.000.000 | 7.134.202 | 1.221.551 | 5.912.651 | 0.713420 | 0.122155 | 0.713420 | 9.951072 | 8.453114 | 10.329236 |
8 | 100.000.000 | 71.069.623 | 10.578.680 | 60.490.943 | 0.710696 | 0.105787 | 0.710696 | 9.961819 | 8.660040 | 10.230765 |
9 | 1.000.000.000 | 708.575.905 | 93.223.070 | 615.352.835 | 0.708576 | 0.093223 | 0.708576 | 9.970166 | 8.812354 | 10.172644 |
10 | 10.000.000.000 | 7.069.246.089 | 833.420.540 | 6.235.825.549 | 0.706925 | 0.083342 | 0.706925 | 9.976695 | 8.940067 | 10.133740 |
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 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 16 | 13 | 3 | 1.000000 | 0.812500 | 0.187500 | 1.777778 | 1.625000 | 3.000000 |
5 | 32 | 28 | 21 | 7 | 0.875000 | 0.656250 | 0.218750 | 1.750000 | 1.615385 | 2.333333 |
6 | 64 | 53 | 38 | 15 | 0.828125 | 0.593750 | 0.234375 | 1.892857 | 1.809524 | 2.142857 |
7 | 128 | 100 | 60 | 40 | 0.781250 | 0.468750 | 0.312500 | 1.886792 | 1.578947 | 2.666667 |
8 | 256 | 198 | 104 | 94 | 0.773438 | 0.406250 | 0.367188 | 1.980000 | 1.733333 | 2.350000 |
9 | 512 | 386 | 185 | 201 | 0.753906 | 0.361328 | 0.392578 | 1.949495 | 1.778846 | 2.138298 |
10 | 1.024 | 762 | 332 | 430 | 0.744141 | 0.324219 | 0.419922 | 1.974093 | 1.794595 | 2.139303 |
11 | 2.048 | 1.506 | 602 | 904 | 0.735352 | 0.293945 | 0.441406 | 1.976378 | 1.813253 | 2.102326 |
12 | 4.096 | 3.020 | 1.063 | 1.957 | 0.737305 | 0.259521 | 0.477783 | 2.005312 | 1.765781 | 2.164823 |
13 | 8.192 | 6.002 | 1.948 | 4.054 | 0.732666 | 0.237793 | 0.494873 | 1.987417 | 1.832549 | 2.071538 |
14 | 16.384 | 11.921 | 3.545 | 8.376 | 0.727600 | 0.216370 | 0.511230 | 1.986171 | 1.819815 | 2.066108 |
15 | 32.768 | 23.800 | 6.526 | 17.274 | 0.726318 | 0.199158 | 0.527161 | 1.996477 | 1.840903 | 2.062321 |
16 | 65.536 | 47.432 | 12.053 | 35.379 | 0.723755 | 0.183914 | 0.539841 | 1.992941 | 1.846920 | 2.048107 |
17 | 131.072 | 94.560 | 22.632 | 71.928 | 0.721436 | 0.172668 | 0.548767 | 1.993591 | 1.877707 | 2.033071 |
18 | 262.144 | 188.651 | 42.466 | 146.185 | 0.719646 | 0.161995 | 0.557652 | 1.995040 | 1.876370 | 2.032380 |
19 | 524.288 | 376.528 | 79.919 | 296.609 | 0.718170 | 0.152433 | 0.565737 | 1.995897 | 1.881953 | 2.028997 |
20 | 1.048.576 | 751.659 | 150.963 | 600.696 | 0.716838 | 0.143970 | 0.572868 | 1.996290 | 1.888950 | 2.025212 |
21 | 2.097.152 | 1.501.141 | 286.369 | 1.214.772 | 0.715800 | 0.136551 | 0.579248 | 1.997104 | 1.896948 | 2.022274 |
22 | 4.194.304 | 2.997.558 | 544.287 | 2.453.271 | 0.714674 | 0.129768 | 0.584905 | 1.996853 | 1.900649 | 2.019532 |
23 | 8.388.608 | 5.986.462 | 1.037.024 | 4.949.438 | 0.713642 | 0.123623 | 0.590019 | 1.997113 | 1.905289 | 2.017485 |
24 | 16.777.216 | 11.958.204 | 1.981.269 | 9.976.935 | 0.712765 | 0.118093 | 0.594672 | 1.997541 | 1.910533 | 2.015771 |
25 | 33.554.432 | 23.886.564 | 3.793.143 | 20.093.421 | 0.711875 | 0.113044 | 0.598831 | 1.997504 | 1.914502 | 2.013987 |
26 | 67.108.864 | 47.722.123 | 7.267.707 | 40.454.416 | 0.711115 | 0.108297 | 0.602818 | 1.997865 | 1.916012 | 2.013317 |
27 | 134.217.728 | 95.345.857 | 13.957.464 | 81.388.393 | 0.710382 | 0.103991 | 0.606391 | 1.997938 | 1.920477 | 2.011854 |
28 | 268.435.456 | 190.512.276 | 26.844.024 | 163.668.252 | 0.709714 | 0.100002 | 0.609712 | 1.998118 | 1.923274 | 2.010953 |
29 | 536.870.912 | 380.697.668 | 51.703.235 | 328.994.433 | 0.709105 | 0.096305 | 0.612800 | 1.998284 | 1.926061 | 2.010130 |
30 | 1.073.741.824 | 760.768.672 | 99.731.741 | 661.036.931 | 0.708521 | 0.092882 | 0.615639 | 1.998354 | 1.928927 | 2.009265 |
31 | 2.147.483.648 | 1.520.396.586 | 192.605.936 | 1.327.790.650 | 0.707990 | 0.089689 | 0.618301 | 1.998501 | 1.931240 | 2.008648 |
32 | 4.294.967.296 | 3.038.645.795 | 372.419.218 | 2.666.226.577 | 0.707490 | 0.086711 | 0.620779 | 1.998588 | 1.933581 | 2.008018 |
33 | 8.589.934.592 | 6.073.287.343 | 720.934.797 | 5.352.352.546 | 0.707024 | 0.083928 | 0.623096 | 1.998682 | 1.935815 | 2.007463 |
34 | 17.179.869.184 | 12.139.058.051 | 1.397.039.336 | 10.742.018.715 | 0.706586 | 0.081318 | 0.625268 | 1.998762 | 1.937817 | 2.006971 |
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 | 0 | 1 | 2 | 0 |
2 | 4 | 5 | 2 | 3 | 0 | 2 | 2 | 1 |
3 | 8 | 8 | 4 | 4 | 0 | 4 | 2 | 2 |
4 | 16 | 13 | 8 | 5 | 0 | 5 | 4 | 4 |
5 | 32 | 21 | 10 | 11 | 0 | 10 | 6 | 5 |
6 | 64 | 38 | 19 | 19 | 0 | 20 | 9 | 9 |
7 | 128 | 60 | 30 | 30 | 0 | 29 | 14 | 17 |
8 | 256 | 104 | 54 | 50 | 0 | 47 | 27 | 30 |
9 | 512 | 185 | 99 | 86 | 0 | 88 | 47 | 50 |
10 | 1.024 | 332 | 168 | 164 | 0 | 161 | 83 | 88 |
11 | 2.048 | 602 | 295 | 307 | 0 | 303 | 142 | 157 |
12 | 4.096 | 1.063 | 529 | 534 | 0 | 519 | 265 | 279 |
13 | 8.192 | 1.948 | 981 | 967 | 0 | 955 | 486 | 507 |
14 | 16.384 | 3.545 | 1.787 | 1.758 | 0 | 1.731 | 914 | 900 |
15 | 32.768 | 6.526 | 3.288 | 3.238 | 0 | 3.183 | 1.720 | 1.623 |
16 | 65.536 | 12.053 | 6.056 | 5.997 | 0 | 5.901 | 3.126 | 3.026 |
17 | 131.072 | 22.632 | 11.403 | 11.229 | 0 | 11.143 | 5.798 | 5.691 |
18 | 262.144 | 42.466 | 21.396 | 21.070 | 0 | 20.840 | 10.852 | 10.774 |
19 | 524.288 | 79.919 | 40.027 | 39.892 | 0 | 39.456 | 20.258 | 20.205 |
20 | 1.048.576 | 150.963 | 75.832 | 75.131 | 0 | 74.548 | 38.260 | 38.155 |
21 | 2.097.152 | 286.369 | 143.687 | 142.682 | 0 | 141.355 | 72.527 | 72.487 |
22 | 4.194.304 | 544.287 | 273.272 | 271.015 | 0 | 268.789 | 137.952 | 137.546 |
23 | 8.388.608 | 1.037.024 | 520.468 | 516.556 | 0 | 512.008 | 262.780 | 262.236 |
24 | 16.777.216 | 1.981.269 | 994.548 | 986.721 | 0 | 979.314 | 501.431 | 500.524 |
25 | 33.554.432 | 3.793.143 | 1.903.825 | 1.889.318 | 0 | 1.875.634 | 959.452 | 958.057 |
26 | 67.108.864 | 7.267.707 | 3.648.260 | 3.619.447 | 0 | 3.596.413 | 1.836.562 | 1.834.732 |
27 | 134.217.728 | 13.957.464 | 7.004.031 | 6.953.433 | 0 | 6.909.041 | 3.524.231 | 3.524.192 |
28 | 268.435.456 | 26.844.024 | 13.467.165 | 13.376.859 | 0 | 13.293.651 | 6.774.734 | 6.775.639 |
29 | 536.870.912 | 51.703.235 | 25.931.118 | 25.772.117 | 0 | 25.610.452 | 13.046.307 | 13.046.476 |
30 | 1.073.741.824 | 99.731.741 | 50.014.837 | 49.716.904 | 0 | 49.422.980 | 25.156.422 | 25.152.339 |
31 | 2.147.483.648 | 192.605.936 | 96.583.298 | 96.022.638 | 0 | 95.473.016 | 48.565.816 | 48.567.104 |
32 | 4.294.967.296 | 372.419.218 | 186.732.376 | 185.686.842 | 0 | 184.655.211 | 93.881.914 | 93.882.093 |
33 | 8.589.934.592 | 720.934.797 | 361.437.796 | 359.497.001 | 0 | 357.554.710 | 181.683.290 | 181.696.797 |
34 | 17.179.869.184 | 1.397.039.336 | 700.342.244 | 696.697.092 | 0 | 693.063.755 | 351.989.638 | 351.985.943 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
5 | 32 | 7 | 2 | 5 | 3 | 1 | 2 | 1 |
6 | 64 | 15 | 5 | 10 | 4 | 4 | 5 | 2 |
7 | 128 | 40 | 18 | 22 | 12 | 9 | 14 | 5 |
8 | 256 | 94 | 45 | 49 | 28 | 15 | 35 | 16 |
9 | 512 | 201 | 104 | 97 | 60 | 40 | 66 | 35 |
10 | 1.024 | 430 | 214 | 216 | 128 | 82 | 137 | 83 |
11 | 2.048 | 904 | 459 | 445 | 258 | 193 | 264 | 189 |
12 | 4.096 | 1.957 | 963 | 994 | 557 | 416 | 584 | 400 |
13 | 8.192 | 4.054 | 2.023 | 2.031 | 1.149 | 876 | 1.166 | 863 |
14 | 16.384 | 8.376 | 4.170 | 4.206 | 2.302 | 1.879 | 2.334 | 1.861 |
15 | 32.768 | 17.274 | 8.642 | 8.632 | 4.753 | 3.861 | 4.830 | 3.830 |
16 | 65.536 | 35.379 | 17.582 | 17.797 | 9.735 | 7.923 | 9.744 | 7.977 |
17 | 131.072 | 71.928 | 35.900 | 36.028 | 19.534 | 16.373 | 19.619 | 16.402 |
18 | 262.144 | 146.185 | 72.996 | 73.189 | 39.418 | 33.575 | 39.487 | 33.705 |
19 | 524.288 | 296.609 | 148.484 | 148.125 | 79.713 | 68.718 | 79.660 | 68.518 |
20 | 1.048.576 | 600.696 | 300.113 | 300.583 | 160.613 | 140.207 | 160.506 | 139.370 |
21 | 2.097.152 | 1.214.772 | 607.381 | 607.391 | 322.999 | 284.906 | 322.936 | 283.931 |
22 | 4.194.304 | 2.453.271 | 1.226.059 | 1.227.212 | 650.094 | 578.047 | 650.043 | 575.087 |
23 | 8.388.608 | 4.949.438 | 2.474.191 | 2.475.247 | 1.308.477 | 1.168.886 | 1.307.509 | 1.164.566 |
24 | 16.777.216 | 9.976.935 | 4.987.937 | 4.988.998 | 2.628.224 | 2.363.891 | 2.628.733 | 2.356.087 |
25 | 33.554.432 | 20.093.421 | 10.047.700 | 10.045.721 | 5.279.187 | 4.775.668 | 5.278.296 | 4.760.270 |
26 | 67.108.864 | 40.454.416 | 20.225.520 | 20.228.896 | 10.596.654 | 9.640.685 | 10.607.078 | 9.609.999 |
27 | 134.217.728 | 81.388.393 | 40.693.042 | 40.695.351 | 21.265.100 | 19.436.092 | 21.298.587 | 19.388.614 |
28 | 268.435.456 | 163.668.252 | 81.837.140 | 81.831.112 | 42.684.397 | 39.170.119 | 42.742.586 | 39.071.150 |
29 | 536.870.912 | 328.994.433 | 164.504.231 | 164.490.202 | 85.638.539 | 78.892.492 | 85.773.164 | 78.690.238 |
30 | 1.073.741.824 | 661.036.931 | 330.533.261 | 330.503.670 | 171.770.132 | 158.820.258 | 172.050.085 | 158.396.456 |
31 | 2.147.483.648 | 1.327.790.650 | 663.925.361 | 663.865.289 | 344.501.114 | 319.546.772 | 345.066.612 | 318.676.152 |
32 | 4.294.967.296 | 2.666.226.577 | 1.333.133.071 | 1.333.093.506 | 690.808.324 | 642.562.400 | 691.948.522 | 640.907.331 |
33 | 8.589.934.592 | 5.352.352.546 | 2.676.236.512 | 2.676.116.034 | 1.384.898.735 | 1.291.755.093 | 1.387.258.502 | 1.288.440.216 |
34 | 17.179.869.184 | 10.742.018.715 | 5.371.149.736 | 5.370.868.979 | 2.776.083.946 | 2.595.819.472 | 2.780.746.662 | 2.589.368.635 |