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+43
f(0)=43
f(1)=11
f(2)=47
f(3)=13
f(4)=59
f(5)=17
f(6)=79
f(7)=23
f(8)=107
f(9)=31
f(10)=1
f(11)=41
f(12)=1
f(13)=53
f(14)=239
f(15)=67
f(16)=1
f(17)=83
f(18)=367
f(19)=101
f(20)=443
f(21)=1
f(22)=1
f(23)=1
f(24)=619
f(25)=167
f(26)=719
f(27)=193
f(28)=827
f(29)=1
f(30)=1
f(31)=251
f(32)=97
f(33)=283
f(34)=109
f(35)=317
f(36)=103
f(37)=353
f(38)=1487
f(39)=1
f(40)=1
f(41)=431
f(42)=139
f(43)=1
f(44)=1979
f(45)=1
f(46)=127
f(47)=563
f(48)=2347
f(49)=1
f(50)=2543
f(51)=661
f(52)=1
f(53)=1
f(54)=269
f(55)=1
f(56)=1
f(57)=823
f(58)=3407
f(59)=881
f(60)=3643
f(61)=941
f(62)=1
f(63)=1
f(64)=4139
f(65)=1
f(66)=1
f(67)=1
f(68)=359
f(69)=1201
f(70)=4943
f(71)=1
f(72)=5227
f(73)=1
f(74)=5519
f(75)=1
f(76)=1
f(77)=1493
f(78)=557
f(79)=1571
f(80)=379
f(81)=1
f(82)=1
f(83)=1733
f(84)=229
f(85)=1
f(86)=173
f(87)=1
f(88)=599
f(89)=181
f(90)=479
f(91)=2081
f(92)=1
f(93)=1
f(94)=683
f(95)=2267
f(96)=197
f(97)=1
f(98)=877
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+43 could be written as f(y)= y^2+43 with x=y+0
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+0
f'(x)>2x-1 with x > 7
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 | 10 | 0 | 1.000000 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 66 | 49 | 17 | 0.660000 | 0.490000 | 0.660000 | 6.600000 | 4.900000 | inf |
3 | 1.000 | 669 | 305 | 364 | 0.669000 | 0.305000 | 0.669000 | 10.136364 | 6.224490 | 21.411764 |
4 | 10.000 | 6.785 | 2.149 | 4.636 | 0.678500 | 0.214900 | 0.678500 | 10.142003 | 7.045902 | 12.736263 |
5 | 100.000 | 68.353 | 16.365 | 51.988 | 0.683530 | 0.163650 | 0.683530 | 10.074134 | 7.615170 | 11.213978 |
6 | 1.000.000 | 685.029 | 132.146 | 552.883 | 0.685029 | 0.132146 | 0.685029 | 10.021931 | 8.074916 | 10.634820 |
7 | 10.000.000 | 6.860.866 | 1.109.858 | 5.751.008 | 0.686087 | 0.110986 | 0.686087 | 10.015439 | 8.398726 | 10.401854 |
8 | 100.000.000 | 68.691.733 | 9.587.280 | 59.104.453 | 0.686917 | 0.095873 | 0.686917 | 10.012109 | 8.638294 | 10.277233 |
9 | 1.000.000.000 | 687.535.675 | 84.385.872 | 603.149.803 | 0.687536 | 0.084386 | 0.687536 | 10.009002 | 8.801857 | 10.204812 |
10 | 10.000.000.000 | 6.880.452.826 | 753.727.784 | 6.126.725.042 | 0.688045 | 0.075373 | 0.688045 | 10.007412 | 8.931919 | 10.157883 |
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 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 14 | 14 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.555556 | 1.555556 | -nan |
5 | 32 | 25 | 24 | 1 | 0.781250 | 0.750000 | 0.031250 | 1.785714 | 1.714286 | inf |
6 | 64 | 46 | 40 | 6 | 0.718750 | 0.625000 | 0.093750 | 1.840000 | 1.666667 | 6.000000 |
7 | 128 | 87 | 63 | 24 | 0.679688 | 0.492188 | 0.187500 | 1.891304 | 1.575000 | 4.000000 |
8 | 256 | 170 | 108 | 62 | 0.664062 | 0.421875 | 0.242188 | 1.954023 | 1.714286 | 2.583333 |
9 | 512 | 339 | 183 | 156 | 0.662109 | 0.357422 | 0.304688 | 1.994118 | 1.694444 | 2.516129 |
10 | 1.024 | 685 | 311 | 374 | 0.668945 | 0.303711 | 0.365234 | 2.020649 | 1.699454 | 2.397436 |
11 | 2.048 | 1.370 | 560 | 810 | 0.668945 | 0.273438 | 0.395508 | 2.000000 | 1.800643 | 2.165775 |
12 | 4.096 | 2.762 | 1.005 | 1.757 | 0.674316 | 0.245361 | 0.428955 | 2.016058 | 1.794643 | 2.169136 |
13 | 8.192 | 5.551 | 1.813 | 3.738 | 0.677612 | 0.221313 | 0.456299 | 2.009776 | 1.803980 | 2.127490 |
14 | 16.384 | 11.165 | 3.317 | 7.848 | 0.681458 | 0.202454 | 0.479004 | 2.011349 | 1.829564 | 2.099519 |
15 | 32.768 | 22.361 | 6.068 | 16.293 | 0.682404 | 0.185181 | 0.497223 | 2.002777 | 1.829364 | 2.076070 |
16 | 65.536 | 44.778 | 11.265 | 33.513 | 0.683258 | 0.171890 | 0.511368 | 2.002504 | 1.856460 | 2.056895 |
17 | 131.072 | 89.637 | 20.774 | 68.863 | 0.683876 | 0.158493 | 0.525383 | 2.001809 | 1.844119 | 2.054815 |
18 | 262.144 | 179.499 | 38.795 | 140.704 | 0.684734 | 0.147991 | 0.536743 | 2.002510 | 1.867479 | 2.043245 |
19 | 524.288 | 359.047 | 73.059 | 285.988 | 0.684828 | 0.139349 | 0.545479 | 2.000273 | 1.883207 | 2.032551 |
20 | 1.048.576 | 718.367 | 137.957 | 580.410 | 0.685088 | 0.131566 | 0.553522 | 2.000760 | 1.888296 | 2.029491 |
21 | 2.097.152 | 1.437.546 | 261.052 | 1.176.494 | 0.685475 | 0.124479 | 0.560996 | 2.001130 | 1.892271 | 2.027005 |
22 | 4.194.304 | 2.876.389 | 495.639 | 2.380.750 | 0.685785 | 0.118170 | 0.567615 | 2.000902 | 1.898622 | 2.023597 |
23 | 8.388.608 | 5.754.926 | 942.559 | 4.812.367 | 0.686041 | 0.112362 | 0.573679 | 2.000747 | 1.901705 | 2.021366 |
24 | 16.777.216 | 11.514.363 | 1.798.434 | 9.715.929 | 0.686310 | 0.107195 | 0.579114 | 2.000784 | 1.908033 | 2.018950 |
25 | 33.554.432 | 23.037.569 | 3.439.114 | 19.598.455 | 0.686573 | 0.102494 | 0.584080 | 2.000768 | 1.912283 | 2.017147 |
26 | 67.108.864 | 46.089.733 | 6.587.241 | 39.502.492 | 0.686791 | 0.098158 | 0.588633 | 2.000633 | 1.915389 | 2.015592 |
27 | 134.217.728 | 92.208.681 | 12.646.876 | 79.561.805 | 0.687008 | 0.094227 | 0.592782 | 2.000634 | 1.919905 | 2.014096 |
28 | 268.435.456 | 184.465.416 | 24.318.240 | 160.147.176 | 0.687187 | 0.090593 | 0.596595 | 2.000521 | 1.922865 | 2.012865 |
29 | 536.870.912 | 369.029.478 | 46.821.131 | 322.208.347 | 0.687371 | 0.087211 | 0.600160 | 2.000535 | 1.925350 | 2.011952 |
30 | 1.073.741.824 | 738.253.383 | 90.273.551 | 647.979.832 | 0.687552 | 0.084074 | 0.603478 | 2.000527 | 1.928051 | 2.011059 |
31 | 2.147.483.648 | 1.476.851.099 | 174.301.503 | 1.302.549.596 | 0.687712 | 0.081165 | 0.606547 | 2.000466 | 1.930815 | 2.010170 |
32 | 4.294.967.296 | 2.954.362.680 | 336.935.824 | 2.617.426.856 | 0.687866 | 0.078449 | 0.609417 | 2.000447 | 1.933063 | 2.009464 |
33 | 8.589.934.592 | 5.910.000.560 | 652.037.043 | 5.257.963.517 | 0.688015 | 0.075907 | 0.612108 | 2.000432 | 1.935197 | 2.008829 |
34 | 17.179.869.184 | 11.822.370.161 | 1.263.187.424 | 10.559.182.737 | 0.688152 | 0.073527 | 0.614625 | 2.000401 | 1.937294 | 2.008227 |
35 | 34.359.738.368 | 23.649.266.690 | 2.449.577.625 | 21.199.689.065 | 0.688284 | 0.071292 | 0.616992 | 2.000383 | 1.939204 | 2.007702 |
36 | 68.719.476.736 | 47.307.097.506 | 4.754.612.465 | 42.552.485.041 | 0.688409 | 0.069189 | 0.619220 | 2.000362 | 1.940993 | 2.007222 |
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 | 2 | 0 | 1 |
2 | 4 | 5 | 2 | 3 | 0 | 3 | 1 | 1 |
3 | 8 | 9 | 3 | 6 | 1 | 4 | 1 | 3 |
4 | 16 | 14 | 5 | 9 | 2 | 5 | 2 | 5 |
5 | 32 | 24 | 8 | 16 | 3 | 10 | 3 | 8 |
6 | 64 | 40 | 13 | 27 | 5 | 16 | 6 | 13 |
7 | 128 | 63 | 19 | 44 | 9 | 23 | 9 | 22 |
8 | 256 | 108 | 37 | 71 | 16 | 39 | 14 | 39 |
9 | 512 | 183 | 59 | 124 | 24 | 66 | 24 | 69 |
10 | 1.024 | 311 | 102 | 209 | 41 | 115 | 39 | 116 |
11 | 2.048 | 560 | 185 | 375 | 71 | 206 | 73 | 210 |
12 | 4.096 | 1.005 | 335 | 670 | 123 | 372 | 133 | 377 |
13 | 8.192 | 1.813 | 622 | 1.191 | 228 | 663 | 241 | 681 |
14 | 16.384 | 3.317 | 1.119 | 2.198 | 428 | 1.211 | 435 | 1.243 |
15 | 32.768 | 6.068 | 2.013 | 4.055 | 802 | 2.234 | 783 | 2.249 |
16 | 65.536 | 11.265 | 3.738 | 7.527 | 1.446 | 4.151 | 1.480 | 4.188 |
17 | 131.072 | 20.774 | 6.977 | 13.797 | 2.659 | 7.706 | 2.697 | 7.712 |
18 | 262.144 | 38.795 | 12.971 | 25.824 | 5.026 | 14.357 | 4.939 | 14.473 |
19 | 524.288 | 73.059 | 24.461 | 48.598 | 9.406 | 27.183 | 9.378 | 27.092 |
20 | 1.048.576 | 137.957 | 46.107 | 91.850 | 17.749 | 51.064 | 17.829 | 51.315 |
21 | 2.097.152 | 261.052 | 87.162 | 173.890 | 33.510 | 96.994 | 33.540 | 97.008 |
22 | 4.194.304 | 495.639 | 165.167 | 330.472 | 63.248 | 184.486 | 63.465 | 184.440 |
23 | 8.388.608 | 942.559 | 314.427 | 628.132 | 120.245 | 350.556 | 120.914 | 350.844 |
24 | 16.777.216 | 1.798.434 | 600.132 | 1.198.302 | 229.178 | 669.630 | 230.113 | 669.513 |
25 | 33.554.432 | 3.439.114 | 1.148.054 | 2.291.060 | 438.766 | 1.280.093 | 439.404 | 1.280.851 |
26 | 67.108.864 | 6.587.241 | 2.196.656 | 4.390.585 | 840.711 | 2.453.876 | 840.124 | 2.452.530 |
27 | 134.217.728 | 12.646.876 | 4.216.002 | 8.430.874 | 1.612.590 | 4.711.848 | 1.612.140 | 4.710.298 |
28 | 268.435.456 | 24.318.240 | 8.108.443 | 16.209.797 | 3.098.226 | 9.060.559 | 3.099.294 | 9.060.161 |
29 | 536.870.912 | 46.821.131 | 15.610.285 | 31.210.846 | 5.962.787 | 17.449.415 | 5.961.373 | 17.447.556 |
30 | 1.073.741.824 | 90.273.551 | 30.096.198 | 60.177.353 | 11.490.664 | 33.651.394 | 11.482.560 | 33.648.933 |
31 | 2.147.483.648 | 174.301.503 | 58.109.826 | 116.191.677 | 22.169.569 | 64.987.583 | 22.158.162 | 64.986.189 |
32 | 4.294.967.296 | 336.935.824 | 112.315.943 | 224.619.881 | 42.820.820 | 125.645.018 | 42.813.985 | 125.656.001 |
33 | 8.589.934.592 | 652.037.043 | 217.340.905 | 434.696.138 | 82.827.076 | 243.190.356 | 82.812.868 | 243.206.743 |
34 | 17.179.869.184 | 1.263.187.424 | 421.054.766 | 842.132.658 | 160.374.294 | 471.228.034 | 160.355.433 | 471.229.663 |
35 | 34.359.738.368 | 2.449.577.625 | 816.515.912 | 1.633.061.713 | 310.858.685 | 913.956.488 | 310.832.648 | 913.929.804 |
36 | 68.719.476.736 | 4.754.612.465 | 1.584.857.216 | 3.169.755.249 | 603.112.487 | 1.774.216.703 | 603.069.399 | 1.774.213.876 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
6 | 64 | 6 | 5 | 1 | 1 | 1 | 2 | 2 |
7 | 128 | 24 | 13 | 11 | 3 | 5 | 9 | 7 |
8 | 256 | 62 | 33 | 29 | 16 | 13 | 18 | 15 |
9 | 512 | 156 | 84 | 72 | 37 | 40 | 46 | 33 |
10 | 1.024 | 374 | 200 | 174 | 99 | 94 | 105 | 76 |
11 | 2.048 | 810 | 432 | 378 | 192 | 214 | 220 | 184 |
12 | 4.096 | 1.757 | 923 | 834 | 447 | 424 | 472 | 414 |
13 | 8.192 | 3.738 | 1.956 | 1.782 | 969 | 897 | 979 | 893 |
14 | 16.384 | 7.848 | 4.098 | 3.750 | 2.013 | 1.906 | 2.002 | 1.927 |
15 | 32.768 | 16.293 | 8.453 | 7.840 | 4.135 | 3.943 | 4.227 | 3.988 |
16 | 65.536 | 33.513 | 17.299 | 16.214 | 8.595 | 8.057 | 8.689 | 8.172 |
17 | 131.072 | 68.863 | 35.489 | 33.374 | 17.562 | 16.703 | 17.784 | 16.814 |
18 | 262.144 | 140.704 | 72.317 | 68.387 | 35.833 | 34.384 | 36.167 | 34.320 |
19 | 524.288 | 285.988 | 146.620 | 139.368 | 72.617 | 70.060 | 73.303 | 70.008 |
20 | 1.048.576 | 580.410 | 296.747 | 283.663 | 147.642 | 142.473 | 148.201 | 142.094 |
21 | 2.097.152 | 1.176.494 | 599.934 | 576.560 | 298.880 | 288.584 | 299.954 | 289.076 |
22 | 4.194.304 | 2.380.750 | 1.213.289 | 1.167.461 | 605.096 | 584.962 | 605.835 | 584.857 |
23 | 8.388.608 | 4.812.367 | 2.450.052 | 2.362.315 | 1.222.590 | 1.184.207 | 1.223.124 | 1.182.446 |
24 | 16.777.216 | 9.715.929 | 4.941.326 | 4.774.603 | 2.467.159 | 2.391.111 | 2.466.286 | 2.391.373 |
25 | 33.554.432 | 19.598.455 | 9.959.156 | 9.639.299 | 4.971.559 | 4.828.157 | 4.971.457 | 4.827.282 |
26 | 67.108.864 | 39.502.492 | 20.059.723 | 19.442.769 | 10.012.261 | 9.737.954 | 10.012.704 | 9.739.573 |
27 | 134.217.728 | 79.561.805 | 40.372.033 | 39.189.772 | 20.149.596 | 19.623.769 | 20.156.722 | 19.631.718 |
28 | 268.435.456 | 160.147.176 | 81.202.385 | 78.944.791 | 40.535.223 | 39.530.543 | 40.539.001 | 39.542.409 |
29 | 536.870.912 | 322.208.347 | 163.290.289 | 158.918.058 | 81.500.725 | 79.597.426 | 81.508.395 | 79.601.801 |
30 | 1.073.741.824 | 647.979.832 | 328.179.887 | 319.799.945 | 163.827.071 | 160.154.716 | 163.834.631 | 160.163.414 |
31 | 2.147.483.648 | 1.302.549.596 | 659.342.512 | 643.207.084 | 329.162.974 | 322.106.726 | 329.164.481 | 322.115.415 |
32 | 4.294.967.296 | 2.617.426.856 | 1.324.250.429 | 1.293.176.427 | 661.130.455 | 647.560.518 | 661.171.587 | 647.564.296 |
33 | 8.589.934.592 | 5.257.963.517 | 2.658.960.081 | 2.599.003.436 | 1.327.613.881 | 1.301.334.764 | 1.327.632.344 | 1.301.382.528 |
34 | 17.179.869.184 | 10.559.182.737 | 5.337.514.808 | 5.221.667.929 | 2.665.145.403 | 2.614.422.471 | 2.665.176.792 | 2.614.438.071 |
35 | 34.359.738.368 | 21.199.689.065 | 10.712.005.177 | 10.487.683.888 | 5.348.983.591 | 5.250.843.489 | 5.349.066.166 | 5.250.795.819 |
36 | 68.719.476.736 | 42.552.485.041 | 21.493.469.002 | 21.059.016.039 | 10.733.134.162 | 10.543.083.351 | 10.733.287.800 | 10.542.979.728 |