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+36x-23
f(0)=23
f(1)=7
f(2)=53
f(3)=47
f(4)=137
f(5)=13
f(6)=229
f(7)=139
f(8)=1
f(9)=191
f(10)=19
f(11)=1
f(12)=79
f(13)=307
f(14)=677
f(15)=1
f(16)=809
f(17)=439
f(18)=73
f(19)=1
f(20)=1097
f(21)=587
f(22)=179
f(23)=29
f(24)=109
f(25)=751
f(26)=227
f(27)=839
f(28)=61
f(29)=1
f(30)=103
f(31)=1
f(32)=2153
f(33)=1
f(34)=2357
f(35)=1231
f(36)=367
f(37)=1
f(38)=2789
f(39)=1451
f(40)=431
f(41)=1567
f(42)=3253
f(43)=241
f(44)=269
f(45)=1811
f(46)=163
f(47)=277
f(48)=211
f(49)=1
f(50)=1
f(51)=2207
f(52)=157
f(53)=2347
f(54)=691
f(55)=1
f(56)=223
f(57)=1
f(58)=89
f(59)=2791
f(60)=5737
f(61)=421
f(62)=6053
f(63)=239
f(64)=911
f(65)=3271
f(66)=6709
f(67)=181
f(68)=1
f(69)=1
f(70)=569
f(71)=541
f(72)=7753
f(73)=3967
f(74)=8117
f(75)=593
f(76)=653
f(77)=4339
f(78)=1
f(79)=197
f(80)=9257
f(81)=1
f(82)=1
f(83)=379
f(84)=113
f(85)=733
f(86)=1
f(87)=281
f(88)=10889
f(89)=1
f(90)=11317
f(91)=1
f(92)=1
f(93)=5987
f(94)=12197
f(95)=6211
f(96)=1
f(97)=1
f(98)=13109
f(99)=953
b) Substitution of the polynom
The polynom f(x)=x^2+36x-23 could be written as f(y)= y^2-347 with x=y-18
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+18
f'(x)>2x+35
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 | 9 | 8 | 1 | 0.900000 | 0.800000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 74 | 43 | 31 | 0.740000 | 0.430000 | 0.310000 | 8.222222 | 5.375000 | 31.000000 |
3 | 1.000 | 687 | 273 | 414 | 0.687000 | 0.273000 | 0.414000 | 9.283784 | 6.348837 | 13.354838 |
4 | 10.000 | 6.978 | 1.944 | 5.034 | 0.697800 | 0.194400 | 0.503400 | 10.157206 | 7.120879 | 12.159420 |
5 | 100.000 | 69.826 | 14.853 | 54.973 | 0.698260 | 0.148530 | 0.549730 | 10.006592 | 7.640432 | 10.920341 |
6 | 1.000.000 | 697.319 | 120.263 | 577.056 | 0.697319 | 0.120263 | 0.577056 | 9.986524 | 8.096883 | 10.497081 |
7 | 10.000.000 | 6.963.787 | 1.016.046 | 5.947.741 | 0.696379 | 0.101605 | 0.594774 | 9.986515 | 8.448534 | 10.307043 |
8 | 100.000.000 | 69.586.357 | 8.786.124 | 60.800.233 | 0.695864 | 0.087861 | 0.608002 | 9.992603 | 8.647368 | 10.222407 |
9 | 1.000.000.000 | 695.461.273 | 77.438.862 | 618.022.411 | 0.695461 | 0.077439 | 0.618022 | 9.994218 | 8.813768 | 10.164804 |
10 | 10.000.000.000 | 6.951.540.061 | 692.341.117 | 6.259.198.944 | 0.695154 | 0.069234 | 0.625920 | 9.995583 | 8.940487 | 10.127787 |
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 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 13 | 11 | 2 | 0.812500 | 0.687500 | 0.125000 | 1.625000 | 1.571429 | 2.000000 |
5 | 32 | 25 | 17 | 8 | 0.781250 | 0.531250 | 0.250000 | 1.923077 | 1.545455 | 4.000000 |
6 | 64 | 50 | 29 | 21 | 0.781250 | 0.453125 | 0.328125 | 2.000000 | 1.705882 | 2.625000 |
7 | 128 | 93 | 53 | 40 | 0.726562 | 0.414062 | 0.312500 | 1.860000 | 1.827586 | 1.904762 |
8 | 256 | 181 | 89 | 92 | 0.707031 | 0.347656 | 0.359375 | 1.946237 | 1.679245 | 2.300000 |
9 | 512 | 355 | 157 | 198 | 0.693359 | 0.306641 | 0.386719 | 1.961326 | 1.764045 | 2.152174 |
10 | 1.024 | 703 | 276 | 427 | 0.686523 | 0.269531 | 0.416992 | 1.980282 | 1.757962 | 2.156566 |
11 | 2.048 | 1.419 | 500 | 919 | 0.692871 | 0.244141 | 0.448730 | 2.018492 | 1.811594 | 2.152225 |
12 | 4.096 | 2.849 | 899 | 1.950 | 0.695557 | 0.219482 | 0.476074 | 2.007752 | 1.798000 | 2.121872 |
13 | 8.192 | 5.711 | 1.623 | 4.088 | 0.697144 | 0.198120 | 0.499023 | 2.004563 | 1.805339 | 2.096410 |
14 | 16.384 | 11.386 | 2.999 | 8.387 | 0.694946 | 0.183044 | 0.511902 | 1.993696 | 1.847813 | 2.051615 |
15 | 32.768 | 22.870 | 5.470 | 17.400 | 0.697937 | 0.166931 | 0.531006 | 2.008607 | 1.823941 | 2.074639 |
16 | 65.536 | 45.747 | 10.143 | 35.604 | 0.698044 | 0.154770 | 0.543274 | 2.000306 | 1.854296 | 2.046207 |
17 | 131.072 | 91.471 | 18.996 | 72.475 | 0.697868 | 0.144928 | 0.552940 | 1.999497 | 1.872819 | 2.035586 |
18 | 262.144 | 182.974 | 35.391 | 147.583 | 0.697990 | 0.135006 | 0.562984 | 2.000350 | 1.863076 | 2.036330 |
19 | 524.288 | 365.785 | 66.630 | 299.155 | 0.697680 | 0.127087 | 0.570593 | 1.999109 | 1.882682 | 2.027029 |
20 | 1.048.576 | 731.163 | 125.648 | 605.515 | 0.697291 | 0.119827 | 0.577464 | 1.998887 | 1.885757 | 2.024085 |
21 | 2.097.152 | 1.461.851 | 237.884 | 1.223.967 | 0.697065 | 0.113432 | 0.583633 | 1.999350 | 1.893257 | 2.021365 |
22 | 4.194.304 | 2.922.279 | 452.447 | 2.469.832 | 0.696726 | 0.107872 | 0.588854 | 1.999027 | 1.901965 | 2.017891 |
23 | 8.388.608 | 5.842.244 | 862.164 | 4.980.080 | 0.696450 | 0.102778 | 0.593672 | 1.999208 | 1.905558 | 2.016364 |
24 | 16.777.216 | 11.680.754 | 1.647.247 | 10.033.507 | 0.696227 | 0.098184 | 0.598044 | 1.999361 | 1.910596 | 2.014728 |
25 | 33.554.432 | 23.357.127 | 3.150.421 | 20.206.706 | 0.696097 | 0.093890 | 0.602207 | 1.999625 | 1.912537 | 2.013922 |
26 | 67.108.864 | 46.703.728 | 6.036.182 | 40.667.546 | 0.695940 | 0.089946 | 0.605994 | 1.999549 | 1.915992 | 2.012577 |
27 | 134.217.728 | 93.390.615 | 11.594.609 | 81.796.006 | 0.695814 | 0.086387 | 0.609428 | 1.999639 | 1.920851 | 2.011334 |
28 | 268.435.456 | 186.744.333 | 22.299.477 | 164.444.856 | 0.695677 | 0.083072 | 0.612605 | 1.999605 | 1.923262 | 2.010427 |
29 | 536.870.912 | 373.422.479 | 42.954.551 | 330.467.928 | 0.695554 | 0.080009 | 0.615544 | 1.999645 | 1.926258 | 2.009597 |
30 | 1.073.741.824 | 746.734.241 | 82.846.081 | 663.888.160 | 0.695450 | 0.077156 | 0.618294 | 1.999704 | 1.928692 | 2.008934 |
31 | 2.147.483.648 | 1.493.251.293 | 160.003.738 | 1.333.247.555 | 0.695349 | 0.074508 | 0.620842 | 1.999709 | 1.931338 | 2.008241 |
32 | 4.294.967.296 | 2.986.109.279 | 309.382.191 | 2.676.727.088 | 0.695258 | 0.072034 | 0.623224 | 1.999737 | 1.933593 | 2.007674 |
33 | 8.589.934.592 | 5.971.475.455 | 598.894.087 | 5.372.581.368 | 0.695171 | 0.069720 | 0.625451 | 1.999751 | 1.935774 | 2.007146 |
34 | 17.179.869.184 | 11.941.568.772 | 1.160.584.832 | 10.780.983.940 | 0.695091 | 0.067555 | 0.627536 | 1.999768 | 1.937880 | 2.006667 |
35 | 34.359.738.368 | 23.880.593.375 | 2.251.190.047 | 21.629.403.328 | 0.695017 | 0.065518 | 0.629498 | 1.999787 | 1.939703 | 2.006255 |
36 | 68.719.476.736 | 47.756.507.660 | 4.370.568.760 | 43.385.938.900 | 0.694949 | 0.063600 | 0.631348 | 1.999804 | 1.941448 | 2.005878 |
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 | 0 | 1 | 2 |
2 | 4 | 5 | 1 | 4 | 1 | 0 | 1 | 3 |
3 | 8 | 7 | 3 | 4 | 1 | 1 | 2 | 3 |
4 | 16 | 11 | 4 | 7 | 2 | 2 | 3 | 4 |
5 | 32 | 17 | 6 | 11 | 4 | 3 | 3 | 7 |
6 | 64 | 29 | 12 | 17 | 5 | 6 | 7 | 11 |
7 | 128 | 53 | 23 | 30 | 12 | 11 | 15 | 15 |
8 | 256 | 89 | 44 | 45 | 23 | 19 | 22 | 25 |
9 | 512 | 157 | 82 | 75 | 36 | 37 | 37 | 47 |
10 | 1.024 | 276 | 144 | 132 | 61 | 70 | 68 | 77 |
11 | 2.048 | 500 | 259 | 241 | 112 | 133 | 122 | 133 |
12 | 4.096 | 899 | 463 | 436 | 216 | 236 | 209 | 238 |
13 | 8.192 | 1.623 | 813 | 810 | 389 | 425 | 393 | 416 |
14 | 16.384 | 2.999 | 1.513 | 1.486 | 735 | 778 | 725 | 761 |
15 | 32.768 | 5.470 | 2.760 | 2.710 | 1.330 | 1.412 | 1.329 | 1.399 |
16 | 65.536 | 10.143 | 5.114 | 5.029 | 2.470 | 2.599 | 2.472 | 2.602 |
17 | 131.072 | 18.996 | 9.589 | 9.407 | 4.685 | 4.821 | 4.659 | 4.831 |
18 | 262.144 | 35.391 | 17.800 | 17.591 | 8.702 | 9.029 | 8.682 | 8.978 |
19 | 524.288 | 66.630 | 33.525 | 33.105 | 16.396 | 16.918 | 16.390 | 16.926 |
20 | 1.048.576 | 125.648 | 63.182 | 62.466 | 30.844 | 31.818 | 31.043 | 31.943 |
21 | 2.097.152 | 237.884 | 119.714 | 118.170 | 58.478 | 60.388 | 58.641 | 60.377 |
22 | 4.194.304 | 452.447 | 227.331 | 225.116 | 111.365 | 114.642 | 111.826 | 114.614 |
23 | 8.388.608 | 862.164 | 432.751 | 429.413 | 212.836 | 218.232 | 212.770 | 218.326 |
24 | 16.777.216 | 1.647.247 | 826.745 | 820.502 | 407.319 | 416.610 | 406.614 | 416.704 |
25 | 33.554.432 | 3.150.421 | 1.580.330 | 1.570.091 | 778.908 | 796.023 | 779.264 | 796.226 |
26 | 67.108.864 | 6.036.182 | 3.028.528 | 3.007.654 | 1.492.559 | 1.524.159 | 1.493.805 | 1.525.659 |
27 | 134.217.728 | 11.594.609 | 5.817.483 | 5.777.126 | 2.869.291 | 2.927.740 | 2.869.606 | 2.927.972 |
28 | 268.435.456 | 22.299.477 | 11.185.231 | 11.114.246 | 5.520.441 | 5.629.273 | 5.521.942 | 5.627.821 |
29 | 536.870.912 | 42.954.551 | 21.541.861 | 21.412.690 | 10.639.114 | 10.838.559 | 10.640.985 | 10.835.893 |
30 | 1.073.741.824 | 82.846.081 | 41.547.273 | 41.298.808 | 20.529.411 | 20.895.747 | 20.528.149 | 20.892.774 |
31 | 2.147.483.648 | 160.003.738 | 80.228.678 | 79.775.060 | 39.663.591 | 40.341.017 | 39.658.598 | 40.340.532 |
32 | 4.294.967.296 | 309.382.191 | 155.116.104 | 154.266.087 | 76.705.973 | 77.980.675 | 76.708.124 | 77.987.419 |
33 | 8.589.934.592 | 598.894.087 | 300.248.469 | 298.645.618 | 148.519.971 | 150.922.342 | 148.530.147 | 150.921.627 |
34 | 17.179.869.184 | 1.160.584.832 | 581.797.132 | 578.787.700 | 287.884.145 | 292.390.061 | 287.909.278 | 292.401.348 |
35 | 34.359.738.368 | 2.251.190.047 | 1.128.430.256 | 1.122.759.791 | 558.560.824 | 567.025.090 | 558.569.943 | 567.034.190 |
36 | 68.719.476.736 | 4.370.568.760 | 2.190.618.670 | 2.179.950.090 | 1.084.646.507 | 1.100.635.639 | 1.084.675.349 | 1.100.611.265 |
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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
4 | 16 | 2 | 2 | 0 | 0 | 0 | 1 | 1 |
5 | 32 | 8 | 6 | 2 | 1 | 2 | 3 | 2 |
6 | 64 | 21 | 15 | 6 | 2 | 5 | 7 | 7 |
7 | 128 | 40 | 23 | 17 | 8 | 6 | 17 | 9 |
8 | 256 | 92 | 49 | 43 | 22 | 22 | 25 | 23 |
9 | 512 | 198 | 99 | 99 | 41 | 54 | 54 | 49 |
10 | 1.024 | 427 | 208 | 219 | 96 | 115 | 112 | 104 |
11 | 2.048 | 919 | 445 | 474 | 224 | 224 | 237 | 234 |
12 | 4.096 | 1.950 | 983 | 967 | 494 | 480 | 481 | 495 |
13 | 8.192 | 4.088 | 2.069 | 2.019 | 1.027 | 986 | 1.039 | 1.036 |
14 | 16.384 | 8.387 | 4.205 | 4.182 | 2.153 | 2.059 | 2.092 | 2.083 |
15 | 32.768 | 17.400 | 8.650 | 8.750 | 4.397 | 4.358 | 4.348 | 4.297 |
16 | 65.536 | 35.604 | 17.695 | 17.909 | 9.015 | 8.844 | 8.897 | 8.848 |
17 | 131.072 | 72.475 | 36.086 | 36.389 | 18.315 | 17.970 | 18.267 | 17.923 |
18 | 262.144 | 147.583 | 73.803 | 73.780 | 36.983 | 36.870 | 36.930 | 36.800 |
19 | 524.288 | 299.155 | 149.690 | 149.465 | 74.934 | 74.680 | 74.822 | 74.719 |
20 | 1.048.576 | 605.515 | 303.201 | 302.314 | 151.434 | 151.474 | 151.285 | 151.322 |
21 | 2.097.152 | 1.223.967 | 612.173 | 611.794 | 305.855 | 305.845 | 306.387 | 305.880 |
22 | 4.194.304 | 2.469.832 | 1.235.287 | 1.234.545 | 617.388 | 617.702 | 618.227 | 616.515 |
23 | 8.388.608 | 4.980.080 | 2.491.090 | 2.488.990 | 1.245.351 | 1.245.139 | 1.246.637 | 1.242.953 |
24 | 16.777.216 | 10.033.507 | 5.018.737 | 5.014.770 | 2.509.606 | 2.507.153 | 2.510.597 | 2.506.151 |
25 | 33.554.432 | 20.206.706 | 10.109.606 | 10.097.100 | 5.054.098 | 5.047.715 | 5.055.252 | 5.049.641 |
26 | 67.108.864 | 40.667.546 | 20.340.820 | 20.326.726 | 10.173.038 | 10.161.889 | 10.169.620 | 10.162.999 |
27 | 134.217.728 | 81.796.006 | 40.904.784 | 40.891.222 | 20.455.326 | 20.439.993 | 20.455.940 | 20.444.747 |
28 | 268.435.456 | 164.444.856 | 82.242.539 | 82.202.317 | 41.126.010 | 41.094.739 | 41.126.474 | 41.097.633 |
29 | 536.870.912 | 330.467.928 | 165.264.168 | 165.203.760 | 82.639.062 | 82.585.063 | 82.642.246 | 82.601.557 |
30 | 1.073.741.824 | 663.888.160 | 332.022.105 | 331.866.055 | 166.025.176 | 165.923.610 | 166.013.608 | 165.925.766 |
31 | 2.147.483.648 | 1.333.247.555 | 666.757.078 | 666.490.477 | 333.409.081 | 333.205.183 | 333.414.120 | 333.219.171 |
32 | 4.294.967.296 | 2.676.727.088 | 1.338.648.524 | 1.338.078.564 | 669.365.842 | 669.012.845 | 669.363.816 | 668.984.585 |
33 | 8.589.934.592 | 5.372.581.368 | 2.686.819.289 | 2.685.762.079 | 1.343.472.813 | 1.342.799.279 | 1.343.515.129 | 1.342.794.147 |
34 | 17.179.869.184 | 10.780.983.940 | 5.391.397.787 | 5.389.586.153 | 2.695.874.555 | 2.694.630.508 | 2.695.901.876 | 2.694.577.001 |
35 | 34.359.738.368 | 21.629.403.328 | 10.816.317.807 | 10.813.085.521 | 5.408.473.154 | 5.406.255.513 | 5.408.517.376 | 5.406.157.285 |
36 | 68.719.476.736 | 43.385.938.900 | 21.695.998.053 | 21.689.940.847 | 10.848.534.944 | 10.844.396.605 | 10.848.699.960 | 10.844.307.391 |