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-138x+131
f(0)=131
f(1)=3
f(2)=47
f(3)=137
f(4)=5
f(5)=89
f(6)=661
f(7)=1
f(8)=101
f(9)=103
f(10)=383
f(11)=211
f(12)=1381
f(13)=83
f(14)=107
f(15)=857
f(16)=607
f(17)=1
f(18)=2029
f(19)=71
f(20)=743
f(21)=1163
f(22)=269
f(23)=419
f(24)=521
f(25)=449
f(26)=1
f(27)=1433
f(28)=983
f(29)=1
f(30)=3109
f(31)=59
f(32)=1087
f(33)=1667
f(34)=227
f(35)=193
f(36)=3541
f(37)=601
f(38)=1223
f(39)=373
f(40)=421
f(41)=641
f(42)=1
f(43)=659
f(44)=1
f(45)=2027
f(46)=1367
f(47)=691
f(48)=1
f(49)=1
f(50)=1423
f(51)=2153
f(52)=1447
f(53)=1
f(54)=881
f(55)=739
f(56)=1487
f(57)=2243
f(58)=167
f(59)=151
f(60)=4549
f(61)=761
f(62)=509
f(63)=2297
f(64)=307
f(65)=769
f(66)=4621
f(67)=257
f(68)=1543
f(69)=463
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-138x+131 could be written as f(y)= y^2-4630 with x=y+69
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-69
f'(x)>2x-139 with x > 68
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 60 | 9 | 51 | 0.600000 | 0.090000 | 0.600000 | 6.000000 | 3.000000 | 7.285714 |
3 | 1.000 | 693 | 80 | 613 | 0.693000 | 0.080000 | 0.693000 | 11.550000 | 8.888889 | 12.019608 |
4 | 10.000 | 7.388 | 587 | 6.801 | 0.738800 | 0.058700 | 0.738800 | 10.660894 | 7.337500 | 11.094617 |
5 | 100.000 | 73.786 | 4.528 | 69.258 | 0.737860 | 0.045280 | 0.737860 | 9.987277 | 7.713799 | 10.183502 |
6 | 1.000.000 | 729.536 | 37.005 | 692.531 | 0.729536 | 0.037005 | 0.729536 | 9.887187 | 8.172482 | 9.999292 |
7 | 10.000.000 | 7.238.230 | 312.924 | 6.925.306 | 0.723823 | 0.031292 | 0.723823 | 9.921690 | 8.456263 | 9.999994 |
8 | 100.000.000 | 71.947.758 | 2.716.654 | 69.231.104 | 0.719478 | 0.027167 | 0.719478 | 9.939966 | 8.681514 | 9.996830 |
9 | 1.000.000.000 | 716.266.805 | 23.977.501 | 692.289.304 | 0.716267 | 0.023977 | 0.716267 | 9.955374 | 8.826115 | 9.999685 |
10 | 10.000.000.000 | 7.137.478.145 | 214.571.791 | 6.922.906.354 | 0.713748 | 0.021457 | 0.713748 | 9.964831 | 8.948881 | 10.000019 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 16 | 4 | 12 | 1.000000 | 0.250000 | 0.750000 | 2.000000 | 1.333333 | 2.400000 |
5 | 32 | 28 | 6 | 22 | 0.875000 | 0.187500 | 0.687500 | 1.750000 | 1.500000 | 1.833333 |
6 | 64 | 55 | 8 | 47 | 0.859375 | 0.125000 | 0.734375 | 1.964286 | 1.333333 | 2.136364 |
7 | 128 | 60 | 9 | 51 | 0.468750 | 0.070312 | 0.398438 | 1.090909 | 1.125000 | 1.085106 |
8 | 256 | 143 | 21 | 122 | 0.558594 | 0.082031 | 0.476562 | 2.383333 | 2.333333 | 2.392157 |
9 | 512 | 338 | 46 | 292 | 0.660156 | 0.089844 | 0.570312 | 2.363636 | 2.190476 | 2.393443 |
10 | 1.024 | 711 | 82 | 629 | 0.694336 | 0.080078 | 0.614258 | 2.103550 | 1.782609 | 2.154109 |
11 | 2.048 | 1.484 | 145 | 1.339 | 0.724609 | 0.070801 | 0.653809 | 2.087201 | 1.768293 | 2.128776 |
12 | 4.096 | 3.000 | 264 | 2.736 | 0.732422 | 0.064453 | 0.667969 | 2.021563 | 1.820690 | 2.043316 |
13 | 8.192 | 6.074 | 487 | 5.587 | 0.741455 | 0.059448 | 0.682007 | 2.024667 | 1.844697 | 2.042032 |
14 | 16.384 | 12.171 | 911 | 11.260 | 0.742859 | 0.055603 | 0.687256 | 2.003787 | 1.870637 | 2.015393 |
15 | 32.768 | 24.254 | 1.673 | 22.581 | 0.740173 | 0.051056 | 0.689117 | 1.992770 | 1.836443 | 2.005417 |
16 | 65.536 | 48.406 | 3.091 | 45.315 | 0.738617 | 0.047165 | 0.691452 | 1.995795 | 1.847579 | 2.006776 |
17 | 131.072 | 96.549 | 5.756 | 90.793 | 0.736610 | 0.043915 | 0.692696 | 1.994567 | 1.862180 | 2.003597 |
18 | 262.144 | 192.476 | 10.806 | 181.670 | 0.734238 | 0.041222 | 0.693016 | 1.993558 | 1.877345 | 2.000925 |
19 | 524.288 | 383.581 | 20.391 | 363.190 | 0.731623 | 0.038893 | 0.692730 | 1.992877 | 1.887007 | 1.999174 |
20 | 1.048.576 | 764.870 | 38.659 | 726.211 | 0.729437 | 0.036868 | 0.692569 | 1.994025 | 1.895885 | 1.999535 |
21 | 2.097.152 | 1.525.777 | 73.328 | 1.452.449 | 0.727547 | 0.034966 | 0.692582 | 1.994819 | 1.896790 | 2.000037 |
22 | 4.194.304 | 3.044.330 | 139.349 | 2.904.981 | 0.725825 | 0.033223 | 0.692601 | 1.995265 | 1.900352 | 2.000057 |
23 | 8.388.608 | 6.074.498 | 265.716 | 5.808.782 | 0.724137 | 0.031676 | 0.692461 | 1.995348 | 1.906838 | 1.999594 |
24 | 16.777.216 | 12.124.070 | 507.619 | 11.616.451 | 0.722651 | 0.030256 | 0.692394 | 1.995897 | 1.910382 | 1.999808 |
25 | 33.554.432 | 24.204.513 | 971.974 | 23.232.539 | 0.721351 | 0.028967 | 0.692384 | 1.996402 | 1.914771 | 1.999969 |
26 | 67.108.864 | 48.326.154 | 1.866.031 | 46.460.123 | 0.720116 | 0.027806 | 0.692310 | 1.996576 | 1.919836 | 1.999787 |
27 | 134.217.728 | 96.507.991 | 3.584.495 | 92.923.496 | 0.719041 | 0.026707 | 0.692334 | 1.997014 | 1.920919 | 2.000070 |
28 | 268.435.456 | 192.737.668 | 6.898.101 | 185.839.567 | 0.718004 | 0.025697 | 0.692306 | 1.997116 | 1.924428 | 1.999920 |
29 | 536.870.912 | 384.965.042 | 13.295.549 | 371.669.493 | 0.717053 | 0.024765 | 0.692288 | 1.997352 | 1.927422 | 1.999948 |
30 | 1.073.741.824 | 768.996.498 | 25.653.635 | 743.342.863 | 0.716184 | 0.023892 | 0.692292 | 1.997575 | 1.929491 | 2.000010 |
31 | 2.147.483.648 | 1.536.231.841 | 49.559.584 | 1.486.672.257 | 0.715364 | 0.023078 | 0.692286 | 1.997710 | 1.931874 | 1.999982 |
32 | 4.294.967.296 | 3.069.218.151 | 95.854.267 | 2.973.363.884 | 0.714608 | 0.022318 | 0.692290 | 1.997887 | 1.934122 | 2.000013 |
33 | 8.589.934.592 | 6.132.351.288 | 185.606.915 | 5.946.744.373 | 0.713900 | 0.021607 | 0.692292 | 1.998018 | 1.936345 | 2.000005 |
34 | 17.179.869.184 | 12.253.276.002 | 359.761.610 | 11.893.514.392 | 0.713235 | 0.020941 | 0.692294 | 1.998137 | 1.938298 | 2.000004 |
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 | 0 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 1 | 2 | 0 |
4 | 16 | 4 | 2 | 1 | 0 | 1 | 3 | 0 |
5 | 32 | 6 | 4 | 1 | 0 | 1 | 5 | 0 |
6 | 64 | 8 | 6 | 1 | 0 | 1 | 7 | 0 |
7 | 128 | 9 | 7 | 1 | 0 | 1 | 8 | 0 |
8 | 256 | 21 | 7 | 13 | 0 | 13 | 8 | 0 |
9 | 512 | 46 | 7 | 38 | 0 | 38 | 8 | 0 |
10 | 1.024 | 82 | 7 | 74 | 0 | 74 | 8 | 0 |
11 | 2.048 | 145 | 7 | 137 | 0 | 137 | 8 | 0 |
12 | 4.096 | 264 | 7 | 256 | 0 | 256 | 8 | 0 |
13 | 8.192 | 487 | 7 | 479 | 0 | 479 | 8 | 0 |
14 | 16.384 | 911 | 7 | 903 | 0 | 903 | 8 | 0 |
15 | 32.768 | 1.673 | 7 | 1.665 | 0 | 1.665 | 8 | 0 |
16 | 65.536 | 3.091 | 7 | 3.083 | 0 | 3.083 | 8 | 0 |
17 | 131.072 | 5.756 | 7 | 5.748 | 0 | 5.748 | 8 | 0 |
18 | 262.144 | 10.806 | 7 | 10.798 | 0 | 10.798 | 8 | 0 |
19 | 524.288 | 20.391 | 7 | 20.383 | 0 | 20.383 | 8 | 0 |
20 | 1.048.576 | 38.659 | 7 | 38.651 | 0 | 38.651 | 8 | 0 |
21 | 2.097.152 | 73.328 | 7 | 73.320 | 0 | 73.320 | 8 | 0 |
22 | 4.194.304 | 139.349 | 7 | 139.341 | 0 | 139.341 | 8 | 0 |
23 | 8.388.608 | 265.716 | 7 | 265.708 | 0 | 265.708 | 8 | 0 |
24 | 16.777.216 | 507.619 | 7 | 507.611 | 0 | 507.611 | 8 | 0 |
25 | 33.554.432 | 971.974 | 7 | 971.966 | 0 | 971.966 | 8 | 0 |
26 | 67.108.864 | 1.866.031 | 7 | 1.866.023 | 0 | 1.866.023 | 8 | 0 |
27 | 134.217.728 | 3.584.495 | 7 | 3.584.487 | 0 | 3.584.487 | 8 | 0 |
28 | 268.435.456 | 6.898.101 | 7 | 6.898.093 | 0 | 6.898.093 | 8 | 0 |
29 | 536.870.912 | 13.295.549 | 7 | 13.295.541 | 0 | 13.295.541 | 8 | 0 |
30 | 1.073.741.824 | 25.653.635 | 7 | 25.653.627 | 0 | 25.653.627 | 8 | 0 |
31 | 2.147.483.648 | 49.559.584 | 7 | 49.559.576 | 0 | 49.559.576 | 8 | 0 |
32 | 4.294.967.296 | 95.854.267 | 7 | 95.854.259 | 0 | 95.854.259 | 8 | 0 |
33 | 8.589.934.592 | 185.606.915 | 7 | 185.606.907 | 0 | 185.606.907 | 8 | 0 |
34 | 17.179.869.184 | 359.761.610 | 7 | 359.761.602 | 0 | 359.761.602 | 8 | 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 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
3 | 8 | 5 | 0 | 4 | 2 | 1 | 1 | 1 |
4 | 16 | 12 | 3 | 8 | 3 | 4 | 1 | 4 |
5 | 32 | 22 | 4 | 17 | 6 | 6 | 2 | 8 |
6 | 64 | 47 | 14 | 32 | 13 | 14 | 5 | 15 |
7 | 128 | 51 | 17 | 33 | 15 | 14 | 5 | 17 |
8 | 256 | 122 | 57 | 64 | 36 | 22 | 26 | 38 |
9 | 512 | 292 | 153 | 138 | 85 | 50 | 75 | 82 |
10 | 1.024 | 629 | 336 | 292 | 177 | 99 | 178 | 175 |
11 | 2.048 | 1.339 | 717 | 621 | 372 | 223 | 373 | 371 |
12 | 4.096 | 2.736 | 1.481 | 1.254 | 758 | 476 | 743 | 759 |
13 | 8.192 | 5.587 | 2.993 | 2.593 | 1.531 | 1.012 | 1.534 | 1.510 |
14 | 16.384 | 11.260 | 6.025 | 5.234 | 3.042 | 2.064 | 3.097 | 3.057 |
15 | 32.768 | 22.581 | 11.987 | 10.593 | 6.156 | 4.273 | 6.153 | 5.999 |
16 | 65.536 | 45.315 | 24.078 | 21.236 | 12.137 | 8.903 | 12.160 | 12.115 |
17 | 131.072 | 90.793 | 48.270 | 42.522 | 24.135 | 18.183 | 24.281 | 24.194 |
18 | 262.144 | 181.670 | 96.271 | 85.398 | 48.132 | 36.922 | 48.391 | 48.225 |
19 | 524.288 | 363.190 | 192.014 | 171.175 | 95.782 | 74.675 | 96.383 | 96.350 |
20 | 1.048.576 | 726.211 | 382.473 | 343.737 | 191.080 | 151.394 | 192.311 | 191.426 |
21 | 2.097.152 | 1.452.449 | 763.693 | 688.755 | 381.007 | 305.732 | 383.100 | 382.610 |
22 | 4.194.304 | 2.904.981 | 1.522.865 | 1.382.115 | 760.672 | 617.160 | 763.814 | 763.335 |
23 | 8.388.608 | 5.808.782 | 3.038.182 | 2.770.599 | 1.518.666 | 1.244.957 | 1.522.631 | 1.522.528 |
24 | 16.777.216 | 11.616.451 | 6.064.115 | 5.552.335 | 3.031.092 | 2.508.976 | 3.038.831 | 3.037.552 |
25 | 33.554.432 | 23.232.539 | 12.107.641 | 11.124.897 | 6.050.860 | 5.054.123 | 6.065.708 | 6.061.848 |
26 | 67.108.864 | 46.460.123 | 24.171.651 | 22.288.471 | 12.079.926 | 10.170.301 | 12.106.086 | 12.103.810 |
27 | 134.217.728 | 92.923.496 | 48.271.439 | 44.652.056 | 24.120.249 | 20.463.465 | 24.173.188 | 24.166.594 |
28 | 268.435.456 | 185.839.567 | 96.396.263 | 89.443.303 | 48.170.352 | 41.140.239 | 48.274.580 | 48.254.396 |
29 | 536.870.912 | 371.669.493 | 192.541.613 | 179.127.879 | 96.226.822 | 82.680.492 | 96.394.203 | 96.367.976 |
30 | 1.073.741.824 | 743.342.863 | 384.618.935 | 358.723.927 | 192.220.961 | 166.092.592 | 192.551.777 | 192.477.533 |
31 | 2.147.483.648 | 1.486.672.257 | 768.342.818 | 718.329.438 | 384.040.915 | 333.544.187 | 384.624.602 | 384.462.553 |
32 | 4.294.967.296 | 2.973.363.884 | 1.535.036.251 | 1.438.327.632 | 767.255.567 | 669.678.953 | 768.370.210 | 768.059.154 |
33 | 8.589.934.592 | 5.946.744.373 | 3.067.013.443 | 2.879.730.929 | 1.532.988.150 | 1.344.149.638 | 1.535.114.031 | 1.534.492.554 |
34 | 17.179.869.184 | 11.893.514.392 | 6.128.181.387 | 5.765.333.004 | 3.063.167.947 | 2.697.270.032 | 3.067.141.408 | 3.065.935.005 |