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+67
f(0)=67
f(1)=17
f(2)=71
f(3)=19
f(4)=83
f(5)=23
f(6)=103
f(7)=29
f(8)=131
f(9)=37
f(10)=167
f(11)=47
f(12)=211
f(13)=59
f(14)=263
f(15)=73
f(16)=1
f(17)=89
f(18)=1
f(19)=107
f(20)=467
f(21)=127
f(22)=1
f(23)=149
f(24)=643
f(25)=173
f(26)=743
f(27)=199
f(28)=1
f(29)=227
f(30)=967
f(31)=257
f(32)=1091
f(33)=1
f(34)=1223
f(35)=1
f(36)=1
f(37)=359
f(38)=1511
f(39)=397
f(40)=1667
f(41)=1
f(42)=1831
f(43)=479
f(44)=2003
f(45)=523
f(46)=1
f(47)=569
f(48)=2371
f(49)=617
f(50)=151
f(51)=1
f(52)=163
f(53)=719
f(54)=157
f(55)=773
f(56)=3203
f(57)=829
f(58)=1
f(59)=887
f(60)=193
f(61)=947
f(62)=3911
f(63)=1009
f(64)=181
f(65)=1
f(66)=4423
f(67)=1
f(68)=4691
f(69)=1
f(70)=4967
f(71)=1277
f(72)=1
f(73)=1
f(74)=241
f(75)=1423
f(76)=5843
f(77)=1499
f(78)=6151
f(79)=1
f(80)=223
f(81)=1657
f(82)=6791
f(83)=1
f(84)=419
f(85)=1823
f(86)=439
f(87)=1
f(88)=1
f(89)=1997
f(90)=8167
f(91)=2087
f(92)=449
f(93)=2179
f(94)=307
f(95)=2273
f(96)=9283
f(97)=1
f(98)=509
f(99)=2467
b) Substitution of the polynom
The polynom f(x)=x^2+67 could be written as f(y)= y^2+67 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 > 8
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 | 11 | 11 | 0 | 1.100000 | 1.100000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 80 | 68 | 12 | 0.800000 | 0.680000 | 0.800000 | 7.272727 | 6.181818 | inf |
3 | 1.000 | 716 | 393 | 323 | 0.716000 | 0.393000 | 0.716000 | 8.950000 | 5.779412 | 26.916666 |
4 | 10.000 | 7.034 | 2.725 | 4.309 | 0.703400 | 0.272500 | 0.703400 | 9.824022 | 6.933842 | 13.340557 |
5 | 100.000 | 70.418 | 20.869 | 49.549 | 0.704180 | 0.208690 | 0.704180 | 10.011089 | 7.658349 | 11.498956 |
6 | 1.000.000 | 702.573 | 169.158 | 533.415 | 0.702573 | 0.169158 | 0.702573 | 9.977180 | 8.105707 | 10.765404 |
7 | 10.000.000 | 7.010.541 | 1.421.890 | 5.588.651 | 0.701054 | 0.142189 | 0.701054 | 9.978381 | 8.405692 | 10.477117 |
8 | 100.000.000 | 69.986.877 | 12.278.849 | 57.708.028 | 0.699869 | 0.122788 | 0.699869 | 9.983092 | 8.635583 | 10.325932 |
9 | 1.000.000.000 | 699.029.551 | 108.086.061 | 590.943.490 | 0.699030 | 0.108086 | 0.699030 | 9.988008 | 8.802622 | 10.240231 |
10 | 10.000.000.000 | 6.983.656.729 | 965.350.035 | 6.018.306.694 | 0.698366 | 0.096535 | 0.698366 | 9.990503 | 8.931309 | 10.184234 |
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 | 16 | 16 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.777778 | 1.777778 | -nan |
5 | 32 | 29 | 29 | 0 | 0.906250 | 0.906250 | 0.000000 | 1.812500 | 1.812500 | -nan |
6 | 64 | 54 | 49 | 5 | 0.843750 | 0.765625 | 0.078125 | 1.862069 | 1.689655 | inf |
7 | 128 | 97 | 83 | 14 | 0.757812 | 0.648438 | 0.109375 | 1.796296 | 1.693878 | 2.800000 |
8 | 256 | 185 | 132 | 53 | 0.722656 | 0.515625 | 0.207031 | 1.907217 | 1.590361 | 3.785714 |
9 | 512 | 369 | 230 | 139 | 0.720703 | 0.449219 | 0.271484 | 1.994595 | 1.742424 | 2.622642 |
10 | 1.024 | 732 | 398 | 334 | 0.714844 | 0.388672 | 0.326172 | 1.983740 | 1.730435 | 2.402878 |
11 | 2.048 | 1.447 | 712 | 735 | 0.706543 | 0.347656 | 0.358887 | 1.976776 | 1.788945 | 2.200599 |
12 | 4.096 | 2.884 | 1.257 | 1.627 | 0.704102 | 0.306885 | 0.397217 | 1.993089 | 1.765449 | 2.213605 |
13 | 8.192 | 5.784 | 2.308 | 3.476 | 0.706055 | 0.281738 | 0.424316 | 2.005548 | 1.836118 | 2.136447 |
14 | 16.384 | 11.513 | 4.214 | 7.299 | 0.702698 | 0.257202 | 0.445496 | 1.990491 | 1.825823 | 2.099827 |
15 | 32.768 | 23.091 | 7.676 | 15.415 | 0.704681 | 0.234253 | 0.470428 | 2.005646 | 1.821547 | 2.111933 |
16 | 65.536 | 46.117 | 14.279 | 31.838 | 0.703690 | 0.217880 | 0.485809 | 1.997185 | 1.860214 | 2.065391 |
17 | 131.072 | 92.254 | 26.652 | 65.602 | 0.703842 | 0.203339 | 0.500504 | 2.000434 | 1.866517 | 2.060494 |
18 | 262.144 | 184.422 | 49.879 | 134.543 | 0.703514 | 0.190273 | 0.513241 | 1.999068 | 1.871492 | 2.050898 |
19 | 524.288 | 368.499 | 93.969 | 274.530 | 0.702856 | 0.179232 | 0.523624 | 1.998129 | 1.883939 | 2.040463 |
20 | 1.048.576 | 736.671 | 176.730 | 559.941 | 0.702544 | 0.168543 | 0.534001 | 1.999113 | 1.880727 | 2.039635 |
21 | 2.097.152 | 1.472.273 | 334.100 | 1.138.173 | 0.702034 | 0.159311 | 0.542723 | 1.998549 | 1.890454 | 2.032666 |
22 | 4.194.304 | 2.942.638 | 634.692 | 2.307.946 | 0.701580 | 0.151322 | 0.550257 | 1.998704 | 1.899707 | 2.027764 |
23 | 8.388.608 | 5.881.430 | 1.207.549 | 4.673.881 | 0.701121 | 0.143951 | 0.557170 | 1.998693 | 1.902575 | 2.025126 |
24 | 16.777.216 | 11.756.238 | 2.303.541 | 9.452.697 | 0.700726 | 0.137302 | 0.563425 | 1.998874 | 1.907617 | 2.022451 |
25 | 33.554.432 | 23.500.685 | 4.404.020 | 19.096.665 | 0.700375 | 0.131250 | 0.569125 | 1.998997 | 1.911848 | 2.020234 |
26 | 67.108.864 | 46.978.976 | 8.439.236 | 38.539.740 | 0.700041 | 0.125754 | 0.574287 | 1.999047 | 1.916257 | 2.018140 |
27 | 134.217.728 | 93.919.063 | 16.199.037 | 77.720.026 | 0.699752 | 0.120692 | 0.579059 | 1.999172 | 1.919491 | 2.016620 |
28 | 268.435.456 | 187.764.970 | 31.142.370 | 156.622.600 | 0.699479 | 0.116014 | 0.583465 | 1.999221 | 1.922483 | 2.015215 |
29 | 536.870.912 | 375.402.170 | 59.965.174 | 315.436.996 | 0.699241 | 0.111694 | 0.587547 | 1.999319 | 1.925517 | 2.013994 |
30 | 1.073.741.824 | 750.554.623 | 115.628.351 | 634.926.272 | 0.699008 | 0.107687 | 0.591321 | 1.999335 | 1.928258 | 2.012846 |
31 | 2.147.483.648 | 1.500.643.590 | 223.238.536 | 1.277.405.054 | 0.698792 | 0.103954 | 0.594838 | 1.999380 | 1.930656 | 2.011895 |
32 | 4.294.967.296 | 3.000.423.126 | 431.553.123 | 2.568.870.003 | 0.698590 | 0.100479 | 0.598112 | 1.999424 | 1.933148 | 2.011007 |
33 | 8.589.934.592 | 5.999.242.887 | 835.121.480 | 5.164.121.407 | 0.698404 | 0.097221 | 0.601183 | 1.999466 | 1.935153 | 2.010270 |
34 | 17.179.869.184 | 11.995.557.415 | 1.617.826.975 | 10.377.730.440 | 0.698233 | 0.094170 | 0.604063 | 1.999512 | 1.937235 | 2.009583 |
35 | 34.359.738.368 | 23.985.455.954 | 3.137.347.294 | 20.848.108.660 | 0.698069 | 0.091309 | 0.606760 | 1.999528 | 1.939235 | 2.008928 |
36 | 68.719.476.736 | 47.960.352.677 | 6.089.659.793 | 41.870.692.884 | 0.697915 | 0.088616 | 0.609299 | 1.999560 | 1.941022 | 2.008369 |
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 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 2 | 3 | 1 | 3 | 0 | 1 |
3 | 8 | 9 | 3 | 6 | 1 | 4 | 1 | 3 |
4 | 16 | 16 | 6 | 10 | 2 | 6 | 2 | 6 |
5 | 32 | 29 | 10 | 19 | 4 | 11 | 4 | 10 |
6 | 64 | 49 | 16 | 33 | 7 | 17 | 7 | 18 |
7 | 128 | 83 | 26 | 57 | 11 | 32 | 11 | 29 |
8 | 256 | 132 | 44 | 88 | 20 | 50 | 17 | 45 |
9 | 512 | 230 | 77 | 153 | 30 | 88 | 31 | 81 |
10 | 1.024 | 398 | 135 | 263 | 56 | 143 | 49 | 150 |
11 | 2.048 | 712 | 243 | 469 | 93 | 258 | 86 | 275 |
12 | 4.096 | 1.257 | 422 | 835 | 169 | 461 | 153 | 474 |
13 | 8.192 | 2.308 | 779 | 1.529 | 327 | 853 | 283 | 845 |
14 | 16.384 | 4.214 | 1.417 | 2.797 | 567 | 1.574 | 519 | 1.554 |
15 | 32.768 | 7.676 | 2.554 | 5.122 | 1.016 | 2.879 | 965 | 2.816 |
16 | 65.536 | 14.279 | 4.781 | 9.498 | 1.869 | 5.330 | 1.809 | 5.271 |
17 | 131.072 | 26.652 | 8.869 | 17.783 | 3.474 | 9.849 | 3.423 | 9.906 |
18 | 262.144 | 49.879 | 16.633 | 33.246 | 6.452 | 18.562 | 6.466 | 18.399 |
19 | 524.288 | 93.969 | 31.417 | 62.552 | 12.118 | 34.930 | 12.174 | 34.747 |
20 | 1.048.576 | 176.730 | 59.028 | 117.702 | 22.788 | 65.650 | 22.702 | 65.590 |
21 | 2.097.152 | 334.100 | 111.479 | 222.621 | 43.002 | 124.244 | 42.806 | 124.048 |
22 | 4.194.304 | 634.692 | 211.498 | 423.194 | 81.641 | 235.790 | 81.258 | 236.003 |
23 | 8.388.608 | 1.207.549 | 402.393 | 805.156 | 154.838 | 449.085 | 154.374 | 449.252 |
24 | 16.777.216 | 2.303.541 | 768.350 | 1.535.191 | 294.836 | 856.889 | 294.518 | 857.298 |
25 | 33.554.432 | 4.404.020 | 1.468.613 | 2.935.407 | 562.825 | 1.639.376 | 562.384 | 1.639.435 |
26 | 67.108.864 | 8.439.236 | 2.813.615 | 5.625.621 | 1.077.608 | 3.142.122 | 1.076.801 | 3.142.705 |
27 | 134.217.728 | 16.199.037 | 5.399.702 | 10.799.335 | 2.065.775 | 6.032.526 | 2.066.578 | 6.034.158 |
28 | 268.435.456 | 31.142.370 | 10.381.612 | 20.760.758 | 3.969.821 | 11.602.560 | 3.966.804 | 11.603.185 |
29 | 536.870.912 | 59.965.174 | 19.985.305 | 39.979.869 | 7.636.042 | 22.350.315 | 7.633.069 | 22.345.748 |
30 | 1.073.741.824 | 115.628.351 | 38.538.610 | 77.089.741 | 14.710.659 | 43.104.559 | 14.712.542 | 43.100.591 |
31 | 2.147.483.648 | 223.238.536 | 74.407.201 | 148.831.335 | 28.391.095 | 83.225.291 | 28.390.285 | 83.231.865 |
32 | 4.294.967.296 | 431.553.123 | 143.836.265 | 287.716.858 | 54.850.140 | 160.922.071 | 54.848.352 | 160.932.560 |
33 | 8.589.934.592 | 835.121.480 | 278.356.681 | 556.764.799 | 106.077.366 | 311.476.754 | 106.090.636 | 311.476.724 |
34 | 17.179.869.184 | 1.617.826.975 | 539.265.227 | 1.078.561.748 | 205.406.774 | 603.513.649 | 205.412.440 | 603.494.112 |
35 | 34.359.738.368 | 3.137.347.294 | 1.045.786.761 | 2.091.560.533 | 398.139.963 | 1.170.545.004 | 398.149.928 | 1.170.512.399 |
36 | 68.719.476.736 | 6.089.659.793 | 2.029.912.197 | 4.059.747.596 | 772.458.790 | 2.272.397.482 | 772.450.374 | 2.272.353.147 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 64 | 5 | 5 | 0 | 1 | 1 | 2 | 1 |
7 | 128 | 14 | 11 | 3 | 3 | 4 | 3 | 4 |
8 | 256 | 53 | 31 | 22 | 11 | 13 | 17 | 12 |
9 | 512 | 139 | 70 | 69 | 35 | 35 | 37 | 32 |
10 | 1.024 | 334 | 185 | 149 | 89 | 79 | 95 | 71 |
11 | 2.048 | 735 | 392 | 343 | 180 | 175 | 201 | 179 |
12 | 4.096 | 1.627 | 872 | 755 | 406 | 394 | 435 | 392 |
13 | 8.192 | 3.476 | 1.813 | 1.663 | 897 | 824 | 922 | 833 |
14 | 16.384 | 7.299 | 3.791 | 3.508 | 1.857 | 1.751 | 1.933 | 1.758 |
15 | 32.768 | 15.415 | 8.054 | 7.361 | 3.935 | 3.754 | 3.975 | 3.751 |
16 | 65.536 | 31.838 | 16.530 | 15.308 | 8.161 | 7.729 | 8.225 | 7.723 |
17 | 131.072 | 65.602 | 33.904 | 31.698 | 16.767 | 16.028 | 16.792 | 16.015 |
18 | 262.144 | 134.543 | 69.373 | 65.170 | 34.350 | 32.803 | 34.450 | 32.940 |
19 | 524.288 | 274.530 | 140.939 | 133.591 | 70.326 | 67.106 | 70.179 | 66.919 |
20 | 1.048.576 | 559.941 | 286.674 | 273.267 | 142.736 | 137.194 | 143.123 | 136.888 |
21 | 2.097.152 | 1.138.173 | 581.124 | 557.049 | 290.000 | 279.319 | 289.831 | 279.023 |
22 | 4.194.304 | 2.307.946 | 1.177.320 | 1.130.626 | 587.151 | 566.630 | 586.867 | 567.298 |
23 | 8.388.608 | 4.673.881 | 2.382.283 | 2.291.598 | 1.187.288 | 1.149.568 | 1.187.780 | 1.149.245 |
24 | 16.777.216 | 9.452.697 | 4.812.447 | 4.640.250 | 2.398.494 | 2.328.818 | 2.398.434 | 2.326.951 |
25 | 33.554.432 | 19.096.665 | 9.712.680 | 9.383.985 | 4.839.274 | 4.708.902 | 4.841.534 | 4.706.955 |
26 | 67.108.864 | 38.539.740 | 19.582.731 | 18.957.009 | 9.760.642 | 9.508.130 | 9.764.960 | 9.506.008 |
27 | 134.217.728 | 77.720.026 | 39.458.594 | 38.261.432 | 19.672.908 | 19.186.093 | 19.674.245 | 19.186.780 |
28 | 268.435.456 | 156.622.600 | 79.453.091 | 77.169.509 | 39.621.796 | 38.687.869 | 39.629.514 | 38.683.421 |
29 | 536.870.912 | 315.436.996 | 159.903.827 | 155.533.169 | 79.758.532 | 77.958.419 | 79.770.400 | 77.949.645 |
30 | 1.073.741.824 | 634.926.272 | 321.671.313 | 313.254.959 | 160.461.222 | 157.001.549 | 160.481.129 | 156.982.372 |
31 | 2.147.483.648 | 1.277.405.054 | 646.803.334 | 630.601.720 | 322.674.391 | 316.016.593 | 322.709.247 | 316.004.823 |
32 | 4.294.967.296 | 2.568.870.003 | 1.300.046.476 | 1.268.823.527 | 648.605.127 | 635.797.714 | 648.675.390 | 635.791.772 |
33 | 8.589.934.592 | 5.164.121.407 | 2.612.245.596 | 2.551.875.811 | 1.303.360.641 | 1.278.664.481 | 1.303.470.792 | 1.278.625.493 |
34 | 17.179.869.184 | 10.377.730.440 | 5.247.158.274 | 5.130.572.166 | 2.618.344.673 | 2.570.496.472 | 2.618.425.700 | 2.570.463.595 |
35 | 34.359.738.368 | 20.848.108.660 | 10.536.816.425 | 10.311.292.235 | 5.258.285.387 | 5.165.779.520 | 5.258.361.971 | 5.165.681.782 |
36 | 68.719.476.736 | 41.870.692.884 | 21.153.754.718 | 20.716.938.166 | 10.557.192.999 | 10.378.068.277 | 10.557.391.794 | 10.378.039.814 |