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+32x-53
f(0)=53
f(1)=5
f(2)=3
f(3)=13
f(4)=7
f(5)=11
f(6)=1
f(7)=1
f(8)=89
f(9)=79
f(10)=367
f(11)=1
f(12)=19
f(13)=1
f(14)=197
f(15)=163
f(16)=1
f(17)=1
f(18)=1
f(19)=229
f(20)=47
f(21)=1
f(22)=227
f(23)=101
f(24)=1291
f(25)=1
f(26)=97
f(27)=1
f(28)=1627
f(29)=1
f(30)=139
f(31)=1
f(32)=1
f(33)=523
f(34)=313
f(35)=191
f(36)=479
f(37)=1
f(38)=1
f(39)=1
f(40)=257
f(41)=1
f(42)=1
f(43)=61
f(44)=1097
f(45)=853
f(46)=1
f(47)=1
f(48)=541
f(49)=1
f(50)=71
f(51)=1
f(52)=863
f(53)=1
f(54)=4591
f(55)=1
f(56)=1
f(57)=251
f(58)=5167
f(59)=443
f(60)=1
f(61)=281
f(62)=1
f(63)=1483
f(64)=6091
f(65)=521
f(66)=1283
f(67)=1
f(68)=173
f(69)=1
f(70)=373
f(71)=1
f(72)=1487
f(73)=1
f(74)=1
f(75)=1993
f(76)=233
f(77)=1
f(78)=8527
f(79)=2179
f(80)=2969
f(81)=1
f(82)=1
f(83)=113
f(84)=881
f(85)=2473
f(86)=673
f(87)=103
f(88)=1
f(89)=1
f(90)=223
f(91)=557
f(92)=757
f(93)=263
f(94)=907
f(95)=1
f(96)=2447
f(97)=1
f(98)=4229
f(99)=3229
b) Substitution of the polynom
The polynom f(x)=x^2+32x-53 could be written as f(y)= y^2-309 with x=y-16
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+16
f'(x)>2x+31
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 | 3 | 5 | 0.800000 | 0.300000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 10 | 47 | 0.570000 | 0.100000 | 0.570000 | 7.125000 | 3.333333 | 9.400000 |
3 | 1.000 | 612 | 50 | 562 | 0.612000 | 0.050000 | 0.612000 | 10.736842 | 5.000000 | 11.957447 |
4 | 10.000 | 6.311 | 380 | 5.931 | 0.631100 | 0.038000 | 0.631100 | 10.312092 | 7.600000 | 10.553381 |
5 | 100.000 | 64.474 | 2.975 | 61.499 | 0.644740 | 0.029750 | 0.644740 | 10.216130 | 7.828948 | 10.369078 |
6 | 1.000.000 | 652.755 | 24.308 | 628.447 | 0.652755 | 0.024308 | 0.652755 | 10.124313 | 8.170756 | 10.218817 |
7 | 10.000.000 | 6.586.887 | 205.779 | 6.381.108 | 0.658689 | 0.020578 | 0.658689 | 10.090902 | 8.465485 | 10.153772 |
8 | 100.000.000 | 66.298.732 | 1.785.655 | 64.513.077 | 0.662987 | 0.017857 | 0.662987 | 10.065260 | 8.677538 | 10.110012 |
9 | 1.000.000.000 | 666.358.539 | 15.742.161 | 650.616.378 | 0.666359 | 0.015742 | 0.666359 | 10.050849 | 8.815903 | 10.085032 |
10 | 10.000.000.000 | 6.690.338.555 | 140.922.828 | 6.549.415.727 | 0.669034 | 0.014092 | 0.669034 | 10.040148 | 8.951937 | 10.066479 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 1.000000 | 2.000000 |
4 | 16 | 10 | 3 | 7 | 0.625000 | 0.187500 | 0.437500 | 1.666667 | 1.500000 | 1.750000 |
5 | 32 | 18 | 5 | 13 | 0.562500 | 0.156250 | 0.406250 | 1.800000 | 1.666667 | 1.857143 |
6 | 64 | 34 | 8 | 26 | 0.531250 | 0.125000 | 0.406250 | 1.888889 | 1.600000 | 2.000000 |
7 | 128 | 71 | 10 | 61 | 0.554688 | 0.078125 | 0.476562 | 2.088235 | 1.250000 | 2.346154 |
8 | 256 | 149 | 15 | 134 | 0.582031 | 0.058594 | 0.523438 | 2.098592 | 1.500000 | 2.196721 |
9 | 512 | 303 | 26 | 277 | 0.591797 | 0.050781 | 0.541016 | 2.033557 | 1.733333 | 2.067164 |
10 | 1.024 | 626 | 51 | 575 | 0.611328 | 0.049805 | 0.561523 | 2.066007 | 1.961538 | 2.075812 |
11 | 2.048 | 1.262 | 91 | 1.171 | 0.616211 | 0.044434 | 0.571777 | 2.015975 | 1.784314 | 2.036522 |
12 | 4.096 | 2.557 | 172 | 2.385 | 0.624268 | 0.041992 | 0.582275 | 2.026149 | 1.890110 | 2.036721 |
13 | 8.192 | 5.151 | 320 | 4.831 | 0.628784 | 0.039062 | 0.589722 | 2.014470 | 1.860465 | 2.025577 |
14 | 16.384 | 10.385 | 587 | 9.798 | 0.633850 | 0.035828 | 0.598022 | 2.016113 | 1.834375 | 2.028152 |
15 | 32.768 | 20.922 | 1.086 | 19.836 | 0.638489 | 0.033142 | 0.605347 | 2.014637 | 1.850085 | 2.024495 |
16 | 65.536 | 42.093 | 2.014 | 40.079 | 0.642288 | 0.030731 | 0.611557 | 2.011901 | 1.854512 | 2.020518 |
17 | 131.072 | 84.645 | 3.771 | 80.874 | 0.645790 | 0.028770 | 0.617020 | 2.010904 | 1.872393 | 2.017865 |
18 | 262.144 | 170.011 | 7.063 | 162.948 | 0.648540 | 0.026943 | 0.621597 | 2.008518 | 1.872978 | 2.014838 |
19 | 524.288 | 341.144 | 13.437 | 327.707 | 0.650681 | 0.025629 | 0.625051 | 2.006600 | 1.902449 | 2.011114 |
20 | 1.048.576 | 684.610 | 25.399 | 659.211 | 0.652895 | 0.024222 | 0.628673 | 2.006807 | 1.890229 | 2.011587 |
21 | 2.097.152 | 1.373.331 | 48.110 | 1.325.221 | 0.654855 | 0.022941 | 0.631915 | 2.006005 | 1.894169 | 2.010314 |
22 | 4.194.304 | 2.754.030 | 91.770 | 2.662.260 | 0.656612 | 0.021880 | 0.634732 | 2.005365 | 1.907504 | 2.008918 |
23 | 8.388.608 | 5.522.072 | 174.952 | 5.347.120 | 0.658282 | 0.020856 | 0.637426 | 2.005088 | 1.906418 | 2.008489 |
24 | 16.777.216 | 11.068.393 | 333.965 | 10.734.428 | 0.659728 | 0.019906 | 0.639822 | 2.004391 | 1.908895 | 2.007516 |
25 | 33.554.432 | 22.180.402 | 639.294 | 21.541.108 | 0.661027 | 0.019052 | 0.641975 | 2.003941 | 1.914255 | 2.006731 |
26 | 67.108.864 | 44.445.327 | 1.226.996 | 43.218.331 | 0.662287 | 0.018284 | 0.644003 | 2.003811 | 1.919299 | 2.006319 |
27 | 134.217.728 | 89.050.181 | 2.355.702 | 86.694.479 | 0.663476 | 0.017551 | 0.645924 | 2.003589 | 1.919894 | 2.005965 |
28 | 268.435.456 | 178.386.836 | 4.530.565 | 173.856.271 | 0.664543 | 0.016878 | 0.647665 | 2.003217 | 1.923234 | 2.005390 |
29 | 536.870.912 | 357.308.875 | 8.730.268 | 348.578.607 | 0.665540 | 0.016261 | 0.649278 | 2.003000 | 1.926971 | 2.004982 |
30 | 1.073.741.824 | 715.596.686 | 16.843.172 | 698.753.514 | 0.666451 | 0.015686 | 0.650765 | 2.002740 | 1.929285 | 2.004580 |
31 | 2.147.483.648 | 1.433.030.733 | 32.549.373 | 1.400.481.360 | 0.667307 | 0.015157 | 0.652150 | 2.002568 | 1.932497 | 2.004257 |
32 | 4.294.967.296 | 2.869.541.050 | 62.952.366 | 2.806.588.684 | 0.668117 | 0.014657 | 0.653460 | 2.002428 | 1.934058 | 2.004017 |
33 | 8.589.934.592 | 5.745.582.045 | 121.895.804 | 5.623.686.241 | 0.668874 | 0.014191 | 0.654683 | 2.002265 | 1.936318 | 2.003744 |
34 | 17.179.869.184 | 11.503.427.454 | 236.268.383 | 11.267.159.071 | 0.669588 | 0.013753 | 0.655835 | 2.002134 | 1.938281 | 2.003519 |
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 | 0 | 1 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 2 | 0 | 1 | 0 | 0 | 1 | 1 |
4 | 16 | 3 | 1 | 1 | 0 | 0 | 1 | 2 |
5 | 32 | 5 | 3 | 1 | 0 | 2 | 1 | 2 |
6 | 64 | 8 | 6 | 1 | 0 | 3 | 1 | 4 |
7 | 128 | 10 | 8 | 1 | 0 | 4 | 1 | 5 |
8 | 256 | 15 | 13 | 1 | 0 | 6 | 1 | 8 |
9 | 512 | 26 | 24 | 1 | 0 | 13 | 1 | 12 |
10 | 1.024 | 51 | 49 | 1 | 0 | 23 | 1 | 27 |
11 | 2.048 | 91 | 89 | 1 | 0 | 44 | 1 | 46 |
12 | 4.096 | 172 | 170 | 1 | 0 | 85 | 1 | 86 |
13 | 8.192 | 320 | 318 | 1 | 0 | 160 | 1 | 159 |
14 | 16.384 | 587 | 585 | 1 | 0 | 297 | 1 | 289 |
15 | 32.768 | 1.086 | 1.084 | 1 | 0 | 550 | 1 | 535 |
16 | 65.536 | 2.014 | 2.012 | 1 | 0 | 1.005 | 1 | 1.008 |
17 | 131.072 | 3.771 | 3.769 | 1 | 0 | 1.893 | 1 | 1.877 |
18 | 262.144 | 7.063 | 7.061 | 1 | 0 | 3.541 | 1 | 3.521 |
19 | 524.288 | 13.437 | 13.435 | 1 | 0 | 6.699 | 1 | 6.737 |
20 | 1.048.576 | 25.399 | 25.397 | 1 | 0 | 12.702 | 1 | 12.696 |
21 | 2.097.152 | 48.110 | 48.108 | 1 | 0 | 24.087 | 1 | 24.022 |
22 | 4.194.304 | 91.770 | 91.768 | 1 | 0 | 45.781 | 1 | 45.988 |
23 | 8.388.608 | 174.952 | 174.950 | 1 | 0 | 87.425 | 1 | 87.526 |
24 | 16.777.216 | 333.965 | 333.963 | 1 | 0 | 166.913 | 1 | 167.051 |
25 | 33.554.432 | 639.294 | 639.292 | 1 | 0 | 319.433 | 1 | 319.860 |
26 | 67.108.864 | 1.226.996 | 1.226.994 | 1 | 0 | 613.629 | 1 | 613.366 |
27 | 134.217.728 | 2.355.702 | 2.355.700 | 1 | 0 | 1.177.821 | 1 | 1.177.880 |
28 | 268.435.456 | 4.530.565 | 4.530.563 | 1 | 0 | 2.264.431 | 1 | 2.266.133 |
29 | 536.870.912 | 8.730.268 | 8.730.266 | 1 | 0 | 4.363.812 | 1 | 4.366.455 |
30 | 1.073.741.824 | 16.843.172 | 16.843.170 | 1 | 0 | 8.420.585 | 1 | 8.422.586 |
31 | 2.147.483.648 | 32.549.373 | 32.549.371 | 1 | 0 | 16.273.900 | 1 | 16.275.472 |
32 | 4.294.967.296 | 62.952.366 | 62.952.364 | 1 | 0 | 31.476.937 | 1 | 31.475.428 |
33 | 8.589.934.592 | 121.895.804 | 121.895.802 | 1 | 0 | 60.949.804 | 1 | 60.945.999 |
34 | 17.179.869.184 | 236.268.383 | 236.268.381 | 1 | 0 | 118.135.742 | 1 | 118.132.640 |
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 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 4 | 1 | 3 | 1 | 1 | 2 | 0 |
4 | 16 | 7 | 3 | 4 | 1 | 2 | 3 | 1 |
5 | 32 | 13 | 6 | 7 | 2 | 4 | 5 | 2 |
6 | 64 | 26 | 11 | 15 | 6 | 8 | 7 | 5 |
7 | 128 | 61 | 29 | 32 | 17 | 14 | 16 | 14 |
8 | 256 | 134 | 68 | 66 | 38 | 32 | 36 | 28 |
9 | 512 | 277 | 132 | 145 | 69 | 73 | 71 | 64 |
10 | 1.024 | 575 | 281 | 294 | 148 | 145 | 143 | 139 |
11 | 2.048 | 1.171 | 564 | 607 | 295 | 281 | 298 | 297 |
12 | 4.096 | 2.385 | 1.156 | 1.229 | 587 | 601 | 602 | 595 |
13 | 8.192 | 4.831 | 2.354 | 2.477 | 1.197 | 1.215 | 1.237 | 1.182 |
14 | 16.384 | 9.798 | 4.820 | 4.978 | 2.480 | 2.415 | 2.524 | 2.379 |
15 | 32.768 | 19.836 | 9.717 | 10.119 | 5.026 | 4.926 | 5.099 | 4.785 |
16 | 65.536 | 40.079 | 19.793 | 20.286 | 10.228 | 9.803 | 10.258 | 9.790 |
17 | 131.072 | 80.874 | 39.938 | 40.936 | 20.649 | 19.804 | 20.696 | 19.725 |
18 | 262.144 | 162.948 | 80.465 | 82.483 | 41.519 | 39.961 | 41.546 | 39.922 |
19 | 524.288 | 327.707 | 162.033 | 165.674 | 83.515 | 80.378 | 83.742 | 80.072 |
20 | 1.048.576 | 659.211 | 325.545 | 333.666 | 167.758 | 161.473 | 168.203 | 161.777 |
21 | 2.097.152 | 1.325.221 | 655.554 | 669.667 | 337.357 | 324.999 | 337.580 | 325.285 |
22 | 4.194.304 | 2.662.260 | 1.317.871 | 1.344.389 | 676.573 | 654.096 | 677.327 | 654.264 |
23 | 8.388.608 | 5.347.120 | 2.646.726 | 2.700.394 | 1.356.395 | 1.315.112 | 1.359.437 | 1.316.176 |
24 | 16.777.216 | 10.734.428 | 5.318.793 | 5.415.635 | 2.723.122 | 2.641.923 | 2.724.648 | 2.644.735 |
25 | 33.554.432 | 21.541.108 | 10.676.636 | 10.864.472 | 5.463.100 | 5.304.166 | 5.464.422 | 5.309.420 |
26 | 67.108.864 | 43.218.331 | 21.429.978 | 21.788.353 | 10.953.580 | 10.652.463 | 10.957.286 | 10.655.002 |
27 | 134.217.728 | 86.694.479 | 43.007.688 | 43.686.791 | 21.964.553 | 21.380.140 | 21.966.192 | 21.383.594 |
28 | 268.435.456 | 173.856.271 | 86.281.892 | 87.574.379 | 44.025.063 | 42.899.988 | 44.022.714 | 42.908.506 |
29 | 536.870.912 | 348.578.607 | 173.062.453 | 175.516.154 | 88.224.568 | 86.065.936 | 88.217.115 | 86.070.988 |
30 | 1.073.741.824 | 698.753.514 | 347.017.966 | 351.735.548 | 176.761.018 | 172.604.425 | 176.763.759 | 172.624.312 |
31 | 2.147.483.648 | 1.400.481.360 | 695.683.074 | 704.798.286 | 354.134.007 | 346.106.250 | 354.129.631 | 346.111.472 |
32 | 4.294.967.296 | 2.806.588.684 | 1.394.490.768 | 1.412.097.916 | 709.439.423 | 693.900.886 | 709.388.878 | 693.859.497 |
33 | 8.589.934.592 | 5.623.686.241 | 2.794.873.452 | 2.828.812.789 | 1.420.958.667 | 1.390.923.908 | 1.420.939.937 | 1.390.863.729 |
34 | 17.179.869.184 | 11.267.159.071 | 5.600.779.631 | 5.666.379.440 | 2.845.926.495 | 2.787.672.103 | 2.845.947.163 | 2.787.613.310 |