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+12x-59
f(0)=59
f(1)=23
f(2)=31
f(3)=7
f(4)=5
f(5)=13
f(6)=1
f(7)=37
f(8)=101
f(9)=1
f(10)=1
f(11)=97
f(12)=229
f(13)=19
f(14)=61
f(15)=173
f(16)=389
f(17)=1
f(18)=1
f(19)=53
f(20)=83
f(21)=317
f(22)=1
f(23)=373
f(24)=1
f(25)=433
f(26)=929
f(27)=71
f(28)=1061
f(29)=113
f(30)=1201
f(31)=1
f(32)=1
f(33)=1
f(34)=43
f(35)=1
f(36)=1669
f(37)=877
f(38)=263
f(39)=193
f(40)=47
f(41)=151
f(42)=1
f(43)=1153
f(44)=1
f(45)=179
f(46)=2609
f(47)=1
f(48)=1
f(49)=293
f(50)=3041
f(51)=1
f(52)=467
f(53)=1693
f(54)=701
f(55)=1
f(56)=163
f(57)=149
f(58)=4001
f(59)=1
f(60)=4261
f(61)=1
f(62)=647
f(63)=2333
f(64)=1
f(65)=2473
f(66)=727
f(67)=2617
f(68)=5381
f(69)=79
f(70)=1
f(71)=2917
f(72)=1
f(73)=439
f(74)=1
f(75)=1
f(76)=947
f(77)=1
f(78)=6961
f(79)=1
f(80)=1
f(81)=1
f(82)=7649
f(83)=1
f(84)=1601
f(85)=4093
f(86)=8369
f(87)=1
f(88)=8741
f(89)=1
f(90)=1303
f(91)=4657
f(92)=257
f(93)=211
f(94)=283
f(95)=1
f(96)=1
f(97)=751
f(98)=1
f(99)=1093
b) Substitution of the polynom
The polynom f(x)=x^2+12x-59 could be written as f(y)= y^2-95 with x=y-6
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+6
f'(x)>2x+11
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 | 8 | 4 | 4 | 0.800000 | 0.400000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 19 | 45 | 0.640000 | 0.190000 | 0.640000 | 8.000000 | 4.750000 | 11.250000 |
3 | 1.000 | 680 | 110 | 570 | 0.680000 | 0.110000 | 0.680000 | 10.625000 | 5.789474 | 12.666667 |
4 | 10.000 | 6.887 | 781 | 6.106 | 0.688700 | 0.078100 | 0.688700 | 10.127941 | 7.100000 | 10.712280 |
5 | 100.000 | 68.859 | 5.868 | 62.991 | 0.688590 | 0.058680 | 0.688590 | 9.998403 | 7.513444 | 10.316246 |
6 | 1.000.000 | 689.956 | 48.090 | 641.866 | 0.689956 | 0.048090 | 0.689956 | 10.019837 | 8.195296 | 10.189805 |
7 | 10.000.000 | 6.899.878 | 406.696 | 6.493.182 | 0.689988 | 0.040670 | 0.689988 | 10.000461 | 8.456977 | 10.116102 |
8 | 100.000.000 | 69.025.642 | 3.528.010 | 65.497.632 | 0.690256 | 0.035280 | 0.690256 | 10.003893 | 8.674809 | 10.087139 |
9 | 1.000.000.000 | 690.465.669 | 31.140.414 | 659.325.255 | 0.690466 | 0.031140 | 0.690466 | 10.003032 | 8.826623 | 10.066399 |
10 | 10.000.000.000 | 6.906.551.223 | 278.630.768 | 6.627.920.455 | 0.690655 | 0.027863 | 0.690655 | 10.002744 | 8.947562 | 10.052581 |
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 | 14 | 6 | 8 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
5 | 32 | 24 | 9 | 15 | 0.750000 | 0.281250 | 0.468750 | 1.714286 | 1.500000 | 1.875000 |
6 | 64 | 43 | 14 | 29 | 0.671875 | 0.218750 | 0.453125 | 1.791667 | 1.555556 | 1.933333 |
7 | 128 | 83 | 20 | 63 | 0.648438 | 0.156250 | 0.492188 | 1.930233 | 1.428571 | 2.172414 |
8 | 256 | 167 | 34 | 133 | 0.652344 | 0.132812 | 0.519531 | 2.012048 | 1.700000 | 2.111111 |
9 | 512 | 350 | 57 | 293 | 0.683594 | 0.111328 | 0.572266 | 2.095808 | 1.676471 | 2.203007 |
10 | 1.024 | 698 | 112 | 586 | 0.681641 | 0.109375 | 0.572266 | 1.994286 | 1.964912 | 2.000000 |
11 | 2.048 | 1.403 | 198 | 1.205 | 0.685059 | 0.096680 | 0.588379 | 2.010029 | 1.767857 | 2.056314 |
12 | 4.096 | 2.806 | 364 | 2.442 | 0.685059 | 0.088867 | 0.596191 | 2.000000 | 1.838384 | 2.026556 |
13 | 8.192 | 5.652 | 649 | 5.003 | 0.689941 | 0.079224 | 0.610718 | 2.014255 | 1.782967 | 2.048731 |
14 | 16.384 | 11.263 | 1.199 | 10.064 | 0.687439 | 0.073181 | 0.614258 | 1.992746 | 1.847458 | 2.011593 |
15 | 32.768 | 22.581 | 2.174 | 20.407 | 0.689117 | 0.066345 | 0.622772 | 2.004883 | 1.813178 | 2.027723 |
16 | 65.536 | 45.115 | 4.065 | 41.050 | 0.688400 | 0.062027 | 0.626373 | 1.997919 | 1.869825 | 2.011565 |
17 | 131.072 | 90.288 | 7.527 | 82.761 | 0.688843 | 0.057426 | 0.631416 | 2.001286 | 1.851660 | 2.016102 |
18 | 262.144 | 180.625 | 14.058 | 166.567 | 0.689030 | 0.053627 | 0.635403 | 2.000543 | 1.867676 | 2.012627 |
19 | 524.288 | 361.565 | 26.523 | 335.042 | 0.689631 | 0.050589 | 0.639042 | 2.001744 | 1.886684 | 2.011455 |
20 | 1.048.576 | 723.439 | 50.232 | 673.207 | 0.689925 | 0.047905 | 0.642020 | 2.000855 | 1.893903 | 2.009321 |
21 | 2.097.152 | 1.446.856 | 95.520 | 1.351.336 | 0.689915 | 0.045547 | 0.644367 | 1.999970 | 1.901577 | 2.007311 |
22 | 4.194.304 | 2.893.888 | 181.609 | 2.712.279 | 0.689957 | 0.043299 | 0.646658 | 2.000122 | 1.901267 | 2.007109 |
23 | 8.388.608 | 5.787.835 | 345.374 | 5.442.461 | 0.689964 | 0.041172 | 0.648792 | 2.000021 | 1.901745 | 2.006601 |
24 | 16.777.216 | 11.577.607 | 659.758 | 10.917.849 | 0.690079 | 0.039325 | 0.650755 | 2.000335 | 1.910271 | 2.006050 |
25 | 33.554.432 | 23.157.420 | 1.263.409 | 21.894.011 | 0.690145 | 0.037653 | 0.652492 | 2.000190 | 1.914958 | 2.005341 |
26 | 67.108.864 | 46.319.069 | 2.423.980 | 43.895.089 | 0.690208 | 0.036120 | 0.654088 | 2.000183 | 1.918603 | 2.004890 |
27 | 134.217.728 | 92.647.612 | 4.656.431 | 87.991.181 | 0.690279 | 0.034693 | 0.655585 | 2.000205 | 1.920986 | 2.004579 |
28 | 268.435.456 | 185.312.925 | 8.960.633 | 176.352.292 | 0.690344 | 0.033381 | 0.656963 | 2.000191 | 1.924356 | 2.004204 |
29 | 536.870.912 | 370.661.321 | 17.264.409 | 353.396.912 | 0.690410 | 0.032157 | 0.658253 | 2.000191 | 1.926695 | 2.003926 |
30 | 1.073.741.824 | 741.388.982 | 33.316.884 | 708.072.098 | 0.690472 | 0.031029 | 0.659444 | 2.000179 | 1.929802 | 2.003617 |
31 | 2.147.483.648 | 1.482.905.888 | 64.357.122 | 1.418.548.766 | 0.690532 | 0.029969 | 0.660563 | 2.000172 | 1.931667 | 2.003396 |
32 | 4.294.967.296 | 2.966.062.224 | 124.471.778 | 2.841.590.446 | 0.690590 | 0.028981 | 0.661609 | 2.000169 | 1.934079 | 2.003167 |
33 | 8.589.934.592 | 5.932.580.981 | 241.016.883 | 5.691.564.098 | 0.690643 | 0.028058 | 0.662585 | 2.000154 | 1.936318 | 2.002950 |
34 | 17.179.869.184 | 11.866.084.823 | 467.149.895 | 11.398.934.928 | 0.690697 | 0.027192 | 0.663505 | 2.000155 | 1.938246 | 2.002777 |
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 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 2 | 0 | 1 | 1 | 1 |
3 | 8 | 4 | 1 | 3 | 0 | 1 | 2 | 1 |
4 | 16 | 6 | 2 | 4 | 0 | 1 | 4 | 1 |
5 | 32 | 9 | 3 | 6 | 2 | 1 | 5 | 1 |
6 | 64 | 14 | 5 | 9 | 5 | 1 | 7 | 1 |
7 | 128 | 20 | 6 | 14 | 8 | 1 | 10 | 1 |
8 | 256 | 34 | 11 | 23 | 17 | 1 | 15 | 1 |
9 | 512 | 57 | 18 | 39 | 28 | 1 | 27 | 1 |
10 | 1.024 | 112 | 36 | 76 | 51 | 1 | 59 | 1 |
11 | 2.048 | 198 | 66 | 132 | 98 | 1 | 98 | 1 |
12 | 4.096 | 364 | 116 | 248 | 183 | 1 | 179 | 1 |
13 | 8.192 | 649 | 211 | 438 | 317 | 1 | 330 | 1 |
14 | 16.384 | 1.199 | 399 | 800 | 586 | 1 | 611 | 1 |
15 | 32.768 | 2.174 | 709 | 1.465 | 1.081 | 1 | 1.091 | 1 |
16 | 65.536 | 4.065 | 1.348 | 2.717 | 2.018 | 1 | 2.045 | 1 |
17 | 131.072 | 7.527 | 2.474 | 5.053 | 3.744 | 1 | 3.781 | 1 |
18 | 262.144 | 14.058 | 4.702 | 9.356 | 7.079 | 1 | 6.977 | 1 |
19 | 524.288 | 26.523 | 8.849 | 17.674 | 13.333 | 1 | 13.188 | 1 |
20 | 1.048.576 | 50.232 | 16.683 | 33.549 | 25.186 | 1 | 25.044 | 1 |
21 | 2.097.152 | 95.520 | 31.743 | 63.777 | 47.869 | 1 | 47.649 | 1 |
22 | 4.194.304 | 181.609 | 60.472 | 121.137 | 90.909 | 1 | 90.698 | 1 |
23 | 8.388.608 | 345.374 | 114.885 | 230.489 | 172.858 | 1 | 172.514 | 1 |
24 | 16.777.216 | 659.758 | 219.687 | 440.071 | 330.206 | 1 | 329.550 | 1 |
25 | 33.554.432 | 1.263.409 | 420.836 | 842.573 | 632.811 | 1 | 630.596 | 1 |
26 | 67.108.864 | 2.423.980 | 808.341 | 1.615.639 | 1.212.704 | 1 | 1.211.274 | 1 |
27 | 134.217.728 | 4.656.431 | 1.552.087 | 3.104.344 | 2.328.979 | 1 | 2.327.450 | 1 |
28 | 268.435.456 | 8.960.633 | 2.986.242 | 5.974.391 | 4.481.230 | 1 | 4.479.401 | 1 |
29 | 536.870.912 | 17.264.409 | 5.753.087 | 11.511.322 | 8.632.870 | 1 | 8.631.537 | 1 |
30 | 1.073.741.824 | 33.316.884 | 11.106.442 | 22.210.442 | 16.660.521 | 1 | 16.656.361 | 1 |
31 | 2.147.483.648 | 64.357.122 | 21.454.895 | 42.902.227 | 32.177.824 | 1 | 32.179.296 | 1 |
32 | 4.294.967.296 | 124.471.778 | 41.497.276 | 82.974.502 | 62.235.077 | 1 | 62.236.699 | 1 |
33 | 8.589.934.592 | 241.016.883 | 80.345.875 | 160.671.008 | 120.507.029 | 1 | 120.509.852 | 1 |
34 | 17.179.869.184 | 467.149.895 | 155.718.746 | 311.431.149 | 233.569.583 | 1 | 233.580.310 | 1 |
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 | 0 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
3 | 8 | 4 | 3 | 1 | 0 | 0 | 2 | 2 |
4 | 16 | 8 | 6 | 2 | 1 | 0 | 5 | 2 |
5 | 32 | 15 | 8 | 7 | 3 | 1 | 8 | 3 |
6 | 64 | 29 | 14 | 15 | 5 | 4 | 14 | 6 |
7 | 128 | 63 | 36 | 27 | 18 | 10 | 20 | 15 |
8 | 256 | 133 | 73 | 60 | 39 | 29 | 41 | 24 |
9 | 512 | 293 | 147 | 146 | 78 | 63 | 87 | 65 |
10 | 1.024 | 586 | 298 | 288 | 147 | 137 | 165 | 137 |
11 | 2.048 | 1.205 | 628 | 577 | 312 | 265 | 345 | 283 |
12 | 4.096 | 2.442 | 1.262 | 1.180 | 636 | 572 | 687 | 547 |
13 | 8.192 | 5.003 | 2.611 | 2.392 | 1.297 | 1.188 | 1.376 | 1.142 |
14 | 16.384 | 10.064 | 5.236 | 4.828 | 2.633 | 2.363 | 2.710 | 2.358 |
15 | 32.768 | 20.407 | 10.627 | 9.780 | 5.345 | 4.849 | 5.416 | 4.797 |
16 | 65.536 | 41.050 | 21.381 | 19.669 | 10.690 | 9.777 | 10.872 | 9.711 |
17 | 131.072 | 82.761 | 42.790 | 39.971 | 21.610 | 19.673 | 21.775 | 19.703 |
18 | 262.144 | 166.567 | 85.623 | 80.944 | 43.381 | 39.934 | 43.460 | 39.792 |
19 | 524.288 | 335.042 | 171.968 | 163.074 | 87.082 | 80.471 | 87.220 | 80.269 |
20 | 1.048.576 | 673.207 | 344.965 | 328.242 | 175.008 | 161.471 | 175.279 | 161.449 |
21 | 2.097.152 | 1.351.336 | 691.928 | 659.408 | 350.830 | 325.104 | 351.318 | 324.084 |
22 | 4.194.304 | 2.712.279 | 1.386.868 | 1.325.411 | 703.433 | 652.845 | 703.593 | 652.408 |
23 | 8.388.608 | 5.442.461 | 2.781.006 | 2.661.455 | 1.409.089 | 1.311.924 | 1.410.125 | 1.311.323 |
24 | 16.777.216 | 10.917.849 | 5.572.868 | 5.344.981 | 2.822.018 | 2.636.365 | 2.821.577 | 2.637.889 |
25 | 33.554.432 | 21.894.011 | 11.162.136 | 10.731.875 | 5.651.854 | 5.294.339 | 5.651.293 | 5.296.525 |
26 | 67.108.864 | 43.895.089 | 22.363.280 | 21.531.809 | 11.324.016 | 10.627.477 | 11.314.955 | 10.628.641 |
27 | 134.217.728 | 87.991.181 | 44.790.089 | 43.201.092 | 22.665.641 | 21.332.935 | 22.660.396 | 21.332.209 |
28 | 268.435.456 | 176.352.292 | 89.701.455 | 86.650.837 | 45.377.967 | 42.805.205 | 45.367.616 | 42.801.504 |
29 | 536.870.912 | 353.396.912 | 179.637.920 | 173.758.992 | 90.832.262 | 85.865.690 | 90.825.056 | 85.873.904 |
30 | 1.073.741.824 | 708.072.098 | 359.706.342 | 348.365.756 | 181.817.773 | 172.210.754 | 181.801.695 | 172.241.876 |
31 | 2.147.483.648 | 1.418.548.766 | 720.224.003 | 698.324.763 | 363.894.345 | 345.357.763 | 363.895.852 | 345.400.806 |
32 | 4.294.967.296 | 2.841.590.446 | 1.441.977.680 | 1.399.612.766 | 728.315.900 | 692.465.064 | 728.316.938 | 692.492.544 |
33 | 8.589.934.592 | 5.691.564.098 | 2.886.779.241 | 2.804.784.857 | 1.457.667.459 | 1.388.154.819 | 1.457.607.428 | 1.388.134.392 |
34 | 17.179.869.184 | 11.398.934.928 | 5.778.855.641 | 5.620.079.287 | 2.917.223.665 | 2.782.298.894 | 2.917.134.452 | 2.782.277.917 |