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+48x-73
f(0)=73
f(1)=3
f(2)=1
f(3)=5
f(4)=1
f(5)=1
f(6)=251
f(7)=13
f(8)=1
f(9)=11
f(10)=1
f(11)=1
f(12)=647
f(13)=1
f(14)=53
f(15)=109
f(16)=317
f(17)=43
f(18)=223
f(19)=1
f(20)=1
f(21)=1
f(22)=163
f(23)=1
f(24)=331
f(25)=1
f(26)=617
f(27)=61
f(28)=137
f(29)=1
f(30)=2267
f(31)=1
f(32)=829
f(33)=1
f(34)=181
f(35)=59
f(36)=227
f(37)=1
f(38)=71
f(39)=83
f(40)=383
f(41)=149
f(42)=337
f(43)=1
f(44)=1
f(45)=257
f(46)=1
f(47)=1
f(48)=907
f(49)=1
f(50)=1609
f(51)=311
f(52)=1709
f(53)=1
f(54)=1087
f(55)=233
f(56)=1
f(57)=739
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=173
f(63)=1
f(64)=1
f(65)=101
f(66)=7451
f(67)=1
f(68)=521
f(69)=1
f(70)=2729
f(71)=349
f(72)=659
f(73)=1
f(74)=199
f(75)=1
f(76)=1039
f(77)=1
f(78)=1951
f(79)=1
f(80)=3389
f(81)=1297
f(82)=3529
f(83)=1
f(84)=2203
f(85)=1
f(86)=347
f(87)=1459
f(88)=1
f(89)=1
f(90)=12347
f(91)=131
f(92)=1423
f(93)=1
f(94)=1
f(95)=563
f(96)=13751
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+48x-73 could be written as f(y)= y^2-649 with x=y-24
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
f'(x)>2x+47
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 | 4 | 2 | 2 | 0.400000 | 0.200000 | 0.400000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 52 | 7 | 45 | 0.520000 | 0.070000 | 0.520000 | 13.000000 | 3.500000 | 22.500000 |
3 | 1.000 | 569 | 47 | 522 | 0.569000 | 0.047000 | 0.569000 | 10.942307 | 6.714286 | 11.600000 |
4 | 10.000 | 6.094 | 325 | 5.769 | 0.609400 | 0.032500 | 0.609400 | 10.710017 | 6.914894 | 11.051724 |
5 | 100.000 | 62.786 | 2.512 | 60.274 | 0.627860 | 0.025120 | 0.627860 | 10.302921 | 7.729231 | 10.447911 |
6 | 1.000.000 | 639.166 | 20.395 | 618.771 | 0.639166 | 0.020395 | 0.639166 | 10.180072 | 8.119029 | 10.265968 |
7 | 10.000.000 | 6.472.453 | 172.669 | 6.299.784 | 0.647245 | 0.017267 | 0.647245 | 10.126404 | 8.466242 | 10.181124 |
8 | 100.000.000 | 65.308.554 | 1.497.486 | 63.811.068 | 0.653086 | 0.014975 | 0.653086 | 10.090232 | 8.672582 | 10.129088 |
9 | 1.000.000.000 | 657.621.379 | 13.208.431 | 644.412.948 | 0.657621 | 0.013208 | 0.657621 | 10.069452 | 8.820404 | 10.098764 |
10 | 10.000.000.000 | 6.612.325.516 | 118.183.448 | 6.494.142.068 | 0.661233 | 0.011818 | 0.661233 | 10.054913 | 8.947577 | 10.077610 |
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 | 2 | 1 | 1 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 2 | 1 | 1 | 0.500000 | 0.250000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 3 | 2 | 1 | 0.375000 | 0.250000 | 0.125000 | 1.500000 | 2.000000 | 1.000000 |
4 | 16 | 8 | 3 | 5 | 0.500000 | 0.187500 | 0.312500 | 2.666667 | 1.500000 | 5.000000 |
5 | 32 | 17 | 4 | 13 | 0.531250 | 0.125000 | 0.406250 | 2.125000 | 1.333333 | 2.600000 |
6 | 64 | 33 | 4 | 29 | 0.515625 | 0.062500 | 0.453125 | 1.941176 | 1.000000 | 2.230769 |
7 | 128 | 67 | 9 | 58 | 0.523438 | 0.070312 | 0.453125 | 2.030303 | 2.250000 | 2.000000 |
8 | 256 | 138 | 15 | 123 | 0.539062 | 0.058594 | 0.480469 | 2.059701 | 1.666667 | 2.120690 |
9 | 512 | 282 | 28 | 254 | 0.550781 | 0.054688 | 0.496094 | 2.043478 | 1.866667 | 2.065041 |
10 | 1.024 | 584 | 48 | 536 | 0.570312 | 0.046875 | 0.523438 | 2.070922 | 1.714286 | 2.110236 |
11 | 2.048 | 1.212 | 79 | 1.133 | 0.591797 | 0.038574 | 0.553223 | 2.075342 | 1.645833 | 2.113806 |
12 | 4.096 | 2.452 | 148 | 2.304 | 0.598633 | 0.036133 | 0.562500 | 2.023102 | 1.873418 | 2.033539 |
13 | 8.192 | 4.983 | 263 | 4.720 | 0.608276 | 0.032104 | 0.576172 | 2.032219 | 1.777027 | 2.048611 |
14 | 16.384 | 10.029 | 491 | 9.538 | 0.612122 | 0.029968 | 0.582153 | 2.012643 | 1.866920 | 2.020763 |
15 | 32.768 | 20.287 | 920 | 19.367 | 0.619110 | 0.028076 | 0.591034 | 2.022834 | 1.873727 | 2.030509 |
16 | 65.536 | 40.953 | 1.724 | 39.229 | 0.624893 | 0.026306 | 0.598587 | 2.018682 | 1.873913 | 2.025559 |
17 | 131.072 | 82.478 | 3.211 | 79.267 | 0.629257 | 0.024498 | 0.604759 | 2.013967 | 1.862529 | 2.020622 |
18 | 262.144 | 166.054 | 5.961 | 160.093 | 0.633446 | 0.022739 | 0.610706 | 2.013313 | 1.856431 | 2.019668 |
19 | 524.288 | 333.697 | 11.276 | 322.421 | 0.636477 | 0.021507 | 0.614969 | 2.009569 | 1.891629 | 2.013961 |
20 | 1.048.576 | 670.377 | 21.295 | 649.082 | 0.639321 | 0.020308 | 0.619013 | 2.008939 | 1.888524 | 2.013150 |
21 | 2.097.152 | 1.346.284 | 40.329 | 1.305.955 | 0.641958 | 0.019230 | 0.622728 | 2.008249 | 1.893825 | 2.012003 |
22 | 4.194.304 | 2.702.993 | 76.725 | 2.626.268 | 0.644444 | 0.018293 | 0.626151 | 2.007744 | 1.902477 | 2.010994 |
23 | 8.388.608 | 5.425.313 | 146.550 | 5.278.763 | 0.646748 | 0.017470 | 0.629278 | 2.007150 | 1.910068 | 2.009986 |
24 | 16.777.216 | 10.883.110 | 280.385 | 10.602.725 | 0.648684 | 0.016712 | 0.631972 | 2.005987 | 1.913238 | 2.008562 |
25 | 33.554.432 | 21.827.336 | 535.718 | 21.291.618 | 0.650505 | 0.015966 | 0.634540 | 2.005616 | 1.910651 | 2.008127 |
26 | 67.108.864 | 43.766.613 | 1.028.419 | 42.738.194 | 0.652173 | 0.015325 | 0.636849 | 2.005128 | 1.919702 | 2.007278 |
27 | 134.217.728 | 87.742.850 | 1.976.701 | 85.766.149 | 0.653735 | 0.014728 | 0.639008 | 2.004790 | 1.922078 | 2.006780 |
28 | 268.435.456 | 175.869.936 | 3.800.413 | 172.069.523 | 0.655167 | 0.014158 | 0.641009 | 2.004379 | 1.922604 | 2.006264 |
29 | 536.870.912 | 352.455.480 | 7.325.456 | 345.130.024 | 0.656500 | 0.013645 | 0.642855 | 2.004069 | 1.927542 | 2.005759 |
30 | 1.073.741.824 | 706.249.149 | 14.131.989 | 692.117.160 | 0.657746 | 0.013161 | 0.644584 | 2.003797 | 1.929162 | 2.005381 |
31 | 2.147.483.648 | 1.414.998.842 | 27.297.371 | 1.387.701.471 | 0.658910 | 0.012711 | 0.646199 | 2.003541 | 1.931602 | 2.005009 |
32 | 4.294.967.296 | 2.834.668.958 | 52.791.469 | 2.781.877.489 | 0.659998 | 0.012291 | 0.647706 | 2.003301 | 1.933940 | 2.004666 |
33 | 8.589.934.592 | 5.678.082.992 | 102.228.377 | 5.575.854.615 | 0.661016 | 0.011901 | 0.649115 | 2.003085 | 1.936456 | 2.004349 |
34 | 17.179.869.184 | 11.372.688.030 | 198.143.934 | 11.174.544.096 | 0.661978 | 0.011533 | 0.650444 | 2.002910 | 1.938248 | 2.004095 |
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 | 1 | 0 | 1 | 0 | 0 | 0 |
2 | 4 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
3 | 8 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
5 | 32 | 4 | 1 | 3 | 1 | 2 | 0 | 1 |
6 | 64 | 4 | 1 | 3 | 1 | 2 | 0 | 1 |
7 | 128 | 9 | 1 | 8 | 1 | 6 | 0 | 2 |
8 | 256 | 15 | 1 | 14 | 1 | 8 | 0 | 6 |
9 | 512 | 28 | 1 | 27 | 1 | 13 | 0 | 14 |
10 | 1.024 | 48 | 1 | 47 | 1 | 24 | 0 | 23 |
11 | 2.048 | 79 | 1 | 78 | 1 | 38 | 0 | 40 |
12 | 4.096 | 148 | 1 | 147 | 1 | 69 | 0 | 78 |
13 | 8.192 | 263 | 1 | 262 | 1 | 124 | 0 | 138 |
14 | 16.384 | 491 | 1 | 490 | 1 | 236 | 0 | 254 |
15 | 32.768 | 920 | 1 | 919 | 1 | 453 | 0 | 466 |
16 | 65.536 | 1.724 | 1 | 1.723 | 1 | 852 | 0 | 871 |
17 | 131.072 | 3.211 | 1 | 3.210 | 1 | 1.632 | 0 | 1.578 |
18 | 262.144 | 5.961 | 1 | 5.960 | 1 | 2.989 | 0 | 2.971 |
19 | 524.288 | 11.276 | 1 | 11.275 | 1 | 5.637 | 0 | 5.638 |
20 | 1.048.576 | 21.295 | 1 | 21.294 | 1 | 10.632 | 0 | 10.662 |
21 | 2.097.152 | 40.329 | 1 | 40.328 | 1 | 20.155 | 0 | 20.173 |
22 | 4.194.304 | 76.725 | 1 | 76.724 | 1 | 38.424 | 0 | 38.300 |
23 | 8.388.608 | 146.550 | 1 | 146.549 | 1 | 73.488 | 0 | 73.061 |
24 | 16.777.216 | 280.385 | 1 | 280.384 | 1 | 140.396 | 0 | 139.988 |
25 | 33.554.432 | 535.718 | 1 | 535.717 | 1 | 268.136 | 0 | 267.581 |
26 | 67.108.864 | 1.028.419 | 1 | 1.028.418 | 1 | 514.124 | 0 | 514.294 |
27 | 134.217.728 | 1.976.701 | 1 | 1.976.700 | 1 | 988.827 | 0 | 987.873 |
28 | 268.435.456 | 3.800.413 | 1 | 3.800.412 | 1 | 1.900.689 | 0 | 1.899.723 |
29 | 536.870.912 | 7.325.456 | 1 | 7.325.455 | 1 | 3.662.435 | 0 | 3.663.020 |
30 | 1.073.741.824 | 14.131.989 | 1 | 14.131.988 | 1 | 7.064.147 | 0 | 7.067.841 |
31 | 2.147.483.648 | 27.297.371 | 1 | 27.297.370 | 1 | 13.645.861 | 0 | 13.651.509 |
32 | 4.294.967.296 | 52.791.469 | 1 | 52.791.468 | 1 | 26.395.005 | 0 | 26.396.463 |
33 | 8.589.934.592 | 102.228.377 | 1 | 102.228.376 | 1 | 51.109.064 | 0 | 51.119.312 |
34 | 17.179.869.184 | 198.143.934 | 1 | 198.143.933 | 1 | 99.064.920 | 0 | 99.079.013 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 5 | 2 | 2 | 0 | 1 | 3 | 1 |
5 | 32 | 13 | 8 | 4 | 2 | 4 | 5 | 2 |
6 | 64 | 29 | 14 | 13 | 7 | 8 | 9 | 5 |
7 | 128 | 58 | 30 | 26 | 16 | 16 | 16 | 10 |
8 | 256 | 123 | 68 | 53 | 36 | 27 | 32 | 28 |
9 | 512 | 254 | 132 | 120 | 73 | 56 | 71 | 54 |
10 | 1.024 | 536 | 277 | 257 | 138 | 128 | 147 | 123 |
11 | 2.048 | 1.133 | 586 | 545 | 293 | 273 | 298 | 269 |
12 | 4.096 | 2.304 | 1.202 | 1.100 | 596 | 567 | 605 | 536 |
13 | 8.192 | 4.720 | 2.433 | 2.285 | 1.261 | 1.139 | 1.222 | 1.098 |
14 | 16.384 | 9.538 | 4.912 | 4.624 | 2.538 | 2.247 | 2.496 | 2.257 |
15 | 32.768 | 19.367 | 9.909 | 9.456 | 5.145 | 4.563 | 5.026 | 4.633 |
16 | 65.536 | 39.229 | 20.118 | 19.109 | 10.279 | 9.354 | 10.234 | 9.362 |
17 | 131.072 | 79.267 | 40.580 | 38.685 | 20.658 | 18.916 | 20.641 | 19.052 |
18 | 262.144 | 160.093 | 82.074 | 78.017 | 41.655 | 38.542 | 41.517 | 38.379 |
19 | 524.288 | 322.421 | 164.681 | 157.738 | 83.636 | 77.717 | 83.488 | 77.580 |
20 | 1.048.576 | 649.082 | 331.356 | 317.724 | 167.737 | 156.713 | 168.300 | 156.332 |
21 | 2.097.152 | 1.305.955 | 665.600 | 640.353 | 337.627 | 315.520 | 337.278 | 315.530 |
22 | 4.194.304 | 2.626.268 | 1.336.907 | 1.289.359 | 677.273 | 635.655 | 677.250 | 636.090 |
23 | 8.388.608 | 5.278.763 | 2.685.641 | 2.593.120 | 1.357.276 | 1.280.490 | 1.359.143 | 1.281.854 |
24 | 16.777.216 | 10.602.725 | 5.389.824 | 5.212.899 | 2.722.981 | 2.576.606 | 2.724.028 | 2.579.110 |
25 | 33.554.432 | 21.291.618 | 10.811.831 | 10.479.785 | 5.462.339 | 5.183.302 | 5.462.711 | 5.183.266 |
26 | 67.108.864 | 42.738.194 | 21.691.731 | 21.046.461 | 10.954.122 | 10.414.592 | 10.953.584 | 10.415.896 |
27 | 134.217.728 | 85.766.149 | 43.503.442 | 42.262.705 | 21.959.212 | 20.923.746 | 21.958.888 | 20.924.303 |
28 | 268.435.456 | 172.069.523 | 87.225.243 | 84.844.278 | 44.001.863 | 42.028.776 | 44.018.244 | 42.020.640 |
29 | 536.870.912 | 345.130.024 | 174.860.054 | 170.269.968 | 88.185.602 | 84.386.255 | 88.188.076 | 84.370.091 |
30 | 1.073.741.824 | 692.117.160 | 350.477.766 | 341.639.392 | 176.686.699 | 169.372.587 | 176.702.349 | 169.355.525 |
31 | 2.147.483.648 | 1.387.701.471 | 702.377.240 | 685.324.229 | 353.992.344 | 339.860.875 | 354.008.719 | 339.839.533 |
32 | 4.294.967.296 | 2.781.877.489 | 1.407.416.124 | 1.374.461.363 | 709.134.120 | 681.816.287 | 709.134.028 | 681.793.054 |
33 | 8.589.934.592 | 5.575.854.615 | 2.819.812.657 | 2.756.041.956 | 1.420.371.373 | 1.367.543.815 | 1.420.412.224 | 1.367.527.203 |
34 | 17.179.869.184 | 11.174.544.096 | 5.648.970.531 | 5.525.573.563 | 2.844.786.193 | 2.742.461.619 | 2.844.849.475 | 2.742.446.809 |