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-188x+59
f(0)=59
f(1)=1
f(2)=313
f(3)=31
f(4)=677
f(5)=107
f(6)=1033
f(7)=151
f(8)=1381
f(9)=97
f(10)=1721
f(11)=1
f(12)=2053
f(13)=277
f(14)=2377
f(15)=317
f(16)=2693
f(17)=89
f(18)=3001
f(19)=197
f(20)=3301
f(21)=431
f(22)=3593
f(23)=467
f(24)=3877
f(25)=251
f(26)=4153
f(27)=67
f(28)=4421
f(29)=569
f(30)=1
f(31)=601
f(32)=4933
f(33)=79
f(34)=167
f(35)=331
f(36)=5413
f(37)=691
f(38)=5641
f(39)=719
f(40)=5861
f(41)=373
f(42)=6073
f(43)=193
f(44)=6277
f(45)=797
f(46)=6473
f(47)=821
f(48)=6661
f(49)=211
f(50)=6841
f(51)=433
f(52)=7013
f(53)=887
f(54)=7177
f(55)=907
f(56)=7333
f(57)=463
f(58)=7481
f(59)=1
f(60)=7621
f(61)=1
f(62)=7753
f(63)=977
f(64)=7877
f(65)=1
f(66)=7993
f(67)=503
f(68)=8101
f(69)=1019
f(70)=139
f(71)=1031
f(72)=8293
f(73)=521
f(74)=8377
f(75)=263
f(76)=1
f(77)=1061
f(78)=8521
f(79)=1069
f(80)=8581
f(81)=269
f(82)=1
f(83)=541
f(84)=8677
f(85)=1087
f(86)=8713
f(87)=1091
f(88)=8741
f(89)=547
f(90)=8761
f(91)=137
f(92)=283
f(93)=1097
f(94)=131
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-188x+59 could be written as f(y)= y^2-8777 with x=y+94
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-94
f'(x)>2x-189 with x > 94
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 | 6 | 4 | 1.000000 | 0.600000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 85 | 41 | 44 | 0.850000 | 0.410000 | 0.850000 | 8.500000 | 6.833333 | 11.000000 |
3 | 1.000 | 720 | 288 | 432 | 0.720000 | 0.288000 | 0.720000 | 8.470589 | 7.024390 | 9.818182 |
4 | 10.000 | 7.710 | 2.253 | 5.457 | 0.771000 | 0.225300 | 0.771000 | 10.708333 | 7.822917 | 12.631945 |
5 | 100.000 | 76.481 | 17.576 | 58.905 | 0.764810 | 0.175760 | 0.764810 | 9.919715 | 7.801154 | 10.794393 |
6 | 1.000.000 | 752.573 | 143.872 | 608.701 | 0.752573 | 0.143872 | 0.752573 | 9.839999 | 8.185708 | 10.333605 |
7 | 10.000.000 | 7.435.606 | 1.217.377 | 6.218.229 | 0.743561 | 0.121738 | 0.743561 | 9.880245 | 8.461529 | 10.215572 |
8 | 100.000.000 | 73.681.997 | 10.549.938 | 63.132.059 | 0.736820 | 0.105499 | 0.736820 | 9.909347 | 8.666122 | 10.152740 |
9 | 1.000.000.000 | 731.634.071 | 93.087.323 | 638.546.748 | 0.731634 | 0.093087 | 0.731634 | 9.929617 | 8.823495 | 10.114461 |
10 | 10.000.000.000 | 7.275.712.671 | 833.032.829 | 6.442.679.842 | 0.727571 | 0.083303 | 0.727571 | 9.944469 | 8.948940 | 10.089598 |
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 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 2.000000 | 1.500000 | inf |
3 | 8 | 8 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 2.000000 | 1.666667 | 3.000000 |
4 | 16 | 15 | 9 | 6 | 0.937500 | 0.562500 | 0.375000 | 1.875000 | 1.800000 | 2.000000 |
5 | 32 | 30 | 16 | 14 | 0.937500 | 0.500000 | 0.437500 | 2.000000 | 1.777778 | 2.333333 |
6 | 64 | 60 | 31 | 29 | 0.937500 | 0.484375 | 0.453125 | 2.000000 | 1.937500 | 2.071429 |
7 | 128 | 85 | 41 | 44 | 0.664062 | 0.320312 | 0.343750 | 1.416667 | 1.322581 | 1.517241 |
8 | 256 | 131 | 70 | 61 | 0.511719 | 0.273438 | 0.238281 | 1.541176 | 1.707317 | 1.386364 |
9 | 512 | 335 | 151 | 184 | 0.654297 | 0.294922 | 0.359375 | 2.557252 | 2.157143 | 3.016393 |
10 | 1.024 | 740 | 294 | 446 | 0.722656 | 0.287109 | 0.435547 | 2.208955 | 1.947020 | 2.423913 |
11 | 2.048 | 1.551 | 549 | 1.002 | 0.757324 | 0.268066 | 0.489258 | 2.095946 | 1.867347 | 2.246637 |
12 | 4.096 | 3.152 | 1.022 | 2.130 | 0.769531 | 0.249512 | 0.520020 | 2.032237 | 1.861567 | 2.125748 |
13 | 8.192 | 6.316 | 1.877 | 4.439 | 0.770996 | 0.229126 | 0.541870 | 2.003807 | 1.836595 | 2.084038 |
14 | 16.384 | 12.619 | 3.475 | 9.144 | 0.770203 | 0.212097 | 0.558105 | 1.997942 | 1.851359 | 2.059923 |
15 | 32.768 | 25.198 | 6.411 | 18.787 | 0.768982 | 0.195648 | 0.573334 | 1.996830 | 1.844892 | 2.054571 |
16 | 65.536 | 50.264 | 11.939 | 38.325 | 0.766968 | 0.182175 | 0.584793 | 1.994761 | 1.862268 | 2.039974 |
17 | 131.072 | 99.990 | 22.383 | 77.607 | 0.762863 | 0.170769 | 0.592094 | 1.989297 | 1.874780 | 2.024971 |
18 | 262.144 | 199.023 | 42.162 | 156.861 | 0.759212 | 0.160835 | 0.598377 | 1.990429 | 1.883662 | 2.021222 |
19 | 524.288 | 396.125 | 79.688 | 316.437 | 0.755548 | 0.151993 | 0.603556 | 1.990348 | 1.890043 | 2.017308 |
20 | 1.048.576 | 788.969 | 150.296 | 638.673 | 0.752419 | 0.143333 | 0.609086 | 1.991717 | 1.886056 | 2.018326 |
21 | 2.097.152 | 1.571.445 | 284.908 | 1.286.537 | 0.749323 | 0.135855 | 0.613469 | 1.991770 | 1.895646 | 2.014391 |
22 | 4.194.304 | 3.131.423 | 542.232 | 2.589.191 | 0.746589 | 0.129278 | 0.617311 | 1.992703 | 1.903183 | 2.012527 |
23 | 8.388.608 | 6.242.850 | 1.033.204 | 5.209.646 | 0.744206 | 0.123168 | 0.621038 | 1.993614 | 1.905465 | 2.012075 |
24 | 16.777.216 | 12.446.854 | 1.974.324 | 10.472.530 | 0.741890 | 0.117679 | 0.624211 | 1.993778 | 1.910875 | 2.010219 |
25 | 33.554.432 | 24.822.544 | 3.779.873 | 21.042.671 | 0.739769 | 0.112649 | 0.627120 | 1.994283 | 1.914515 | 2.009321 |
26 | 67.108.864 | 49.515.778 | 7.248.101 | 42.267.677 | 0.737843 | 0.108005 | 0.629837 | 1.994791 | 1.917552 | 2.008665 |
27 | 134.217.728 | 98.793.532 | 13.921.785 | 84.871.747 | 0.736069 | 0.103725 | 0.632344 | 1.995193 | 1.920749 | 2.007959 |
28 | 268.435.456 | 197.145.355 | 26.785.907 | 170.359.448 | 0.734424 | 0.099785 | 0.634638 | 1.995529 | 1.924028 | 2.007258 |
29 | 536.870.912 | 393.477.125 | 51.612.632 | 341.864.493 | 0.732908 | 0.096136 | 0.636772 | 1.995873 | 1.926858 | 2.006724 |
30 | 1.073.741.824 | 785.433.837 | 99.589.338 | 685.844.499 | 0.731492 | 0.092750 | 0.638742 | 1.996136 | 1.929554 | 2.006188 |
31 | 2.147.483.648 | 1.568.054.175 | 192.404.700 | 1.375.649.475 | 0.730182 | 0.089595 | 0.640587 | 1.996418 | 1.931981 | 2.005775 |
32 | 4.294.967.296 | 3.130.856.128 | 372.129.796 | 2.758.726.332 | 0.728959 | 0.086643 | 0.642316 | 1.996651 | 1.934099 | 2.005399 |
33 | 8.589.934.592 | 6.251.857.817 | 720.568.439 | 5.531.289.378 | 0.727812 | 0.083885 | 0.643927 | 1.996853 | 1.936336 | 2.005016 |
34 | 17.179.869.184 | 12.485.203.940 | 1.396.666.649 | 11.088.537.291 | 0.726735 | 0.081297 | 0.645438 | 1.997039 | 1.938285 | 2.004693 |
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 | 1 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 5 | 3 | 2 | 2 | 1 | 2 | 0 |
4 | 16 | 9 | 5 | 4 | 4 | 1 | 4 | 0 |
5 | 32 | 16 | 10 | 6 | 7 | 1 | 8 | 0 |
6 | 64 | 31 | 20 | 11 | 14 | 1 | 16 | 0 |
7 | 128 | 41 | 29 | 12 | 19 | 1 | 21 | 0 |
8 | 256 | 70 | 40 | 30 | 19 | 14 | 21 | 16 |
9 | 512 | 151 | 71 | 80 | 19 | 52 | 21 | 59 |
10 | 1.024 | 294 | 113 | 181 | 19 | 123 | 21 | 131 |
11 | 2.048 | 549 | 195 | 354 | 19 | 250 | 21 | 259 |
12 | 4.096 | 1.022 | 360 | 662 | 19 | 487 | 21 | 495 |
13 | 8.192 | 1.877 | 658 | 1.219 | 19 | 913 | 21 | 924 |
14 | 16.384 | 3.475 | 1.170 | 2.305 | 19 | 1.728 | 21 | 1.707 |
15 | 32.768 | 6.411 | 2.148 | 4.263 | 19 | 3.177 | 21 | 3.194 |
16 | 65.536 | 11.939 | 4.004 | 7.935 | 19 | 5.942 | 21 | 5.957 |
17 | 131.072 | 22.383 | 7.495 | 14.888 | 19 | 11.190 | 21 | 11.153 |
18 | 262.144 | 42.162 | 14.089 | 28.073 | 19 | 21.067 | 21 | 21.055 |
19 | 524.288 | 79.688 | 26.539 | 53.149 | 19 | 39.752 | 21 | 39.896 |
20 | 1.048.576 | 150.296 | 49.991 | 100.305 | 19 | 75.086 | 21 | 75.170 |
21 | 2.097.152 | 284.908 | 94.857 | 190.051 | 19 | 142.466 | 21 | 142.402 |
22 | 4.194.304 | 542.232 | 180.669 | 361.563 | 19 | 271.167 | 21 | 271.025 |
23 | 8.388.608 | 1.033.204 | 344.037 | 689.167 | 19 | 516.858 | 21 | 516.306 |
24 | 16.777.216 | 1.974.324 | 657.617 | 1.316.707 | 19 | 986.974 | 21 | 987.310 |
25 | 33.554.432 | 3.779.873 | 1.259.313 | 2.520.560 | 19 | 1.889.342 | 21 | 1.890.491 |
26 | 67.108.864 | 7.248.101 | 2.415.756 | 4.832.345 | 19 | 3.623.443 | 21 | 3.624.618 |
27 | 134.217.728 | 13.921.785 | 4.640.547 | 9.281.238 | 19 | 6.960.013 | 21 | 6.961.732 |
28 | 268.435.456 | 26.785.907 | 8.929.365 | 17.856.542 | 19 | 13.391.121 | 21 | 13.394.746 |
29 | 536.870.912 | 51.612.632 | 17.204.676 | 34.407.956 | 19 | 25.803.657 | 21 | 25.808.935 |
30 | 1.073.741.824 | 99.589.338 | 33.198.697 | 66.390.641 | 19 | 49.796.310 | 21 | 49.792.988 |
31 | 2.147.483.648 | 192.404.700 | 64.132.662 | 128.272.038 | 19 | 96.204.624 | 21 | 96.200.036 |
32 | 4.294.967.296 | 372.129.796 | 124.035.330 | 248.094.466 | 19 | 186.069.943 | 21 | 186.059.813 |
33 | 8.589.934.592 | 720.568.439 | 240.184.382 | 480.384.057 | 19 | 360.290.407 | 21 | 360.277.992 |
34 | 17.179.869.184 | 1.396.666.649 | 465.560.648 | 931.106.001 | 19 | 698.333.971 | 21 | 698.332.638 |
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 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 1 | 0 | 2 |
4 | 16 | 6 | 4 | 2 | 1 | 1 | 2 | 2 |
5 | 32 | 14 | 6 | 8 | 4 | 4 | 3 | 3 |
6 | 64 | 29 | 15 | 14 | 7 | 8 | 6 | 8 |
7 | 128 | 44 | 20 | 24 | 9 | 13 | 10 | 12 |
8 | 256 | 61 | 29 | 32 | 13 | 18 | 13 | 17 |
9 | 512 | 184 | 96 | 88 | 44 | 45 | 47 | 48 |
10 | 1.024 | 446 | 231 | 215 | 119 | 105 | 113 | 109 |
11 | 2.048 | 1.002 | 521 | 481 | 272 | 230 | 265 | 235 |
12 | 4.096 | 2.130 | 1.108 | 1.022 | 547 | 489 | 581 | 513 |
13 | 8.192 | 4.439 | 2.303 | 2.136 | 1.157 | 1.033 | 1.194 | 1.055 |
14 | 16.384 | 9.144 | 4.739 | 4.405 | 2.385 | 2.127 | 2.444 | 2.188 |
15 | 32.768 | 18.787 | 9.699 | 9.088 | 4.876 | 4.454 | 4.935 | 4.522 |
16 | 65.536 | 38.325 | 19.706 | 18.619 | 9.919 | 9.201 | 9.926 | 9.279 |
17 | 131.072 | 77.607 | 39.907 | 37.700 | 20.031 | 18.706 | 20.126 | 18.744 |
18 | 262.144 | 156.861 | 80.587 | 76.274 | 40.467 | 37.859 | 40.598 | 37.937 |
19 | 524.288 | 316.437 | 162.125 | 154.312 | 81.557 | 76.499 | 81.594 | 76.787 |
20 | 1.048.576 | 638.673 | 327.011 | 311.662 | 164.100 | 154.825 | 164.239 | 155.509 |
21 | 2.097.152 | 1.286.537 | 658.133 | 628.404 | 329.986 | 313.004 | 330.136 | 313.411 |
22 | 4.194.304 | 2.589.191 | 1.322.385 | 1.266.806 | 663.033 | 631.345 | 663.539 | 631.274 |
23 | 8.388.608 | 5.209.646 | 2.657.433 | 2.552.213 | 1.332.248 | 1.271.945 | 1.333.851 | 1.271.602 |
24 | 16.777.216 | 10.472.530 | 5.336.513 | 5.136.017 | 2.674.940 | 2.560.266 | 2.676.018 | 2.561.306 |
25 | 33.554.432 | 21.042.671 | 10.714.812 | 10.327.859 | 5.370.870 | 5.149.420 | 5.372.323 | 5.150.058 |
26 | 67.108.864 | 42.267.677 | 21.502.882 | 20.764.795 | 10.779.625 | 10.355.121 | 10.780.056 | 10.352.875 |
27 | 134.217.728 | 84.871.747 | 43.150.701 | 41.721.046 | 21.622.021 | 20.813.748 | 21.627.590 | 20.808.388 |
28 | 268.435.456 | 170.359.448 | 86.556.115 | 83.803.333 | 43.371.480 | 41.810.995 | 43.372.149 | 41.804.824 |
29 | 536.870.912 | 341.864.493 | 173.587.614 | 168.276.879 | 86.966.695 | 83.959.249 | 86.970.480 | 83.968.069 |
30 | 1.073.741.824 | 685.844.499 | 348.039.406 | 337.805.093 | 174.339.212 | 168.566.595 | 174.357.146 | 168.581.546 |
31 | 2.147.483.648 | 1.375.649.475 | 697.673.880 | 677.975.595 | 349.462.424 | 338.342.598 | 349.474.646 | 338.369.807 |
32 | 4.294.967.296 | 2.758.726.332 | 1.398.409.197 | 1.360.317.135 | 700.389.440 | 678.952.490 | 700.404.632 | 678.979.770 |
33 | 8.589.934.592 | 5.531.289.378 | 2.802.481.798 | 2.728.807.580 | 1.403.485.203 | 1.362.129.485 | 1.403.522.157 | 1.362.152.533 |
34 | 17.179.869.184 | 11.088.537.291 | 5.615.614.799 | 5.472.922.492 | 2.812.100.452 | 2.732.111.904 | 2.812.130.224 | 2.732.194.711 |