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-250x-3
f(0)=3
f(1)=7
f(2)=499
f(3)=31
f(4)=47
f(5)=307
f(6)=163
f(7)=71
f(8)=277
f(9)=181
f(10)=89
f(11)=1
f(12)=953
f(13)=257
f(14)=3307
f(15)=1
f(16)=1249
f(17)=991
f(18)=199
f(19)=61
f(20)=4603
f(21)=401
f(22)=239
f(23)=653
f(24)=67
f(25)=1
f(26)=5827
f(27)=251
f(28)=691
f(29)=229
f(30)=1
f(31)=283
f(32)=997
f(33)=1
f(34)=79
f(35)=941
f(36)=367
f(37)=73
f(38)=8059
f(39)=1
f(40)=2801
f(41)=2143
f(42)=971
f(43)=53
f(44)=9067
f(45)=769
f(46)=149
f(47)=1193
f(48)=1
f(49)=821
f(50)=1429
f(51)=1
f(52)=3433
f(53)=373
f(54)=3529
f(55)=1
f(56)=10867
f(57)=131
f(58)=1
f(59)=1409
f(60)=1
f(61)=1
f(62)=1
f(63)=491
f(64)=1
f(65)=97
f(66)=4049
f(67)=1
f(68)=12379
f(69)=347
f(70)=4201
f(71)=227
f(72)=4273
f(73)=359
f(74)=1861
f(75)=547
f(76)=4409
f(77)=3331
f(78)=1
f(79)=563
f(80)=223
f(81)=1
f(82)=1531
f(83)=1733
f(84)=4649
f(85)=167
f(86)=14107
f(87)=197
f(88)=1
f(89)=3583
f(90)=4801
f(91)=1
f(92)=1
f(93)=1217
f(94)=4889
f(95)=263
f(96)=1
f(97)=1237
f(98)=317
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-250x-3 could be written as f(y)= y^2-15628 with x=y+125
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-125
f'(x)>2x-251 with x > 125
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 | 3 | 8 | 1.100000 | 0.300000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 75 | 20 | 55 | 0.750000 | 0.200000 | 0.550000 | 6.818182 | 6.666667 | 6.875000 |
3 | 1.000 | 539 | 121 | 418 | 0.539000 | 0.121000 | 0.418000 | 7.186666 | 6.050000 | 7.600000 |
4 | 10.000 | 6.424 | 923 | 5.501 | 0.642400 | 0.092300 | 0.550100 | 11.918367 | 7.628099 | 13.160287 |
5 | 100.000 | 66.288 | 7.194 | 59.094 | 0.662880 | 0.071940 | 0.590940 | 10.318805 | 7.794149 | 10.742411 |
6 | 1.000.000 | 669.689 | 58.202 | 611.487 | 0.669689 | 0.058202 | 0.611487 | 10.102718 | 8.090353 | 10.347700 |
7 | 10.000.000 | 6.733.449 | 490.441 | 6.243.008 | 0.673345 | 0.049044 | 0.624301 | 10.054591 | 8.426532 | 10.209552 |
8 | 100.000.000 | 67.586.099 | 4.229.672 | 63.356.427 | 0.675861 | 0.042297 | 0.633564 | 10.037367 | 8.624222 | 10.148381 |
9 | 1.000.000.000 | 677.729.669 | 37.211.872 | 640.517.797 | 0.677730 | 0.037212 | 0.640518 | 10.027649 | 8.797815 | 10.109753 |
10 | 10.000.000.000 | 6.792.415.938 | 332.159.805 | 6.460.256.133 | 0.679242 | 0.033216 | 0.646026 | 10.022308 | 8.926178 | 10.085990 |
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 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.500000 | 2.000000 |
4 | 16 | 15 | 4 | 11 | 0.937500 | 0.250000 | 0.687500 | 1.666667 | 1.333333 | 1.833333 |
5 | 32 | 29 | 8 | 21 | 0.906250 | 0.250000 | 0.656250 | 1.933333 | 2.000000 | 1.909091 |
6 | 64 | 49 | 15 | 34 | 0.765625 | 0.234375 | 0.531250 | 1.689655 | 1.875000 | 1.619048 |
7 | 128 | 94 | 25 | 69 | 0.734375 | 0.195312 | 0.539062 | 1.918367 | 1.666667 | 2.029412 |
8 | 256 | 95 | 26 | 69 | 0.371094 | 0.101562 | 0.269531 | 1.010638 | 1.040000 | 1.000000 |
9 | 512 | 231 | 61 | 170 | 0.451172 | 0.119141 | 0.332031 | 2.431579 | 2.346154 | 2.463768 |
10 | 1.024 | 553 | 123 | 430 | 0.540039 | 0.120117 | 0.419922 | 2.393939 | 2.016393 | 2.529412 |
11 | 2.048 | 1.202 | 241 | 961 | 0.586914 | 0.117676 | 0.469238 | 2.173599 | 1.959350 | 2.234884 |
12 | 4.096 | 2.538 | 429 | 2.109 | 0.619629 | 0.104736 | 0.514893 | 2.111481 | 1.780083 | 2.194589 |
13 | 8.192 | 5.239 | 766 | 4.473 | 0.639526 | 0.093506 | 0.546021 | 2.064224 | 1.785548 | 2.120910 |
14 | 16.384 | 10.632 | 1.432 | 9.200 | 0.648926 | 0.087402 | 0.561523 | 2.029395 | 1.869452 | 2.056785 |
15 | 32.768 | 21.478 | 2.627 | 18.851 | 0.655457 | 0.080170 | 0.575287 | 2.020128 | 1.834497 | 2.049022 |
16 | 65.536 | 43.284 | 4.912 | 38.372 | 0.660461 | 0.074951 | 0.585510 | 2.015271 | 1.869813 | 2.035542 |
17 | 131.072 | 87.019 | 9.177 | 77.842 | 0.663902 | 0.070015 | 0.593887 | 2.010420 | 1.868282 | 2.028615 |
18 | 262.144 | 174.759 | 17.138 | 157.621 | 0.666653 | 0.065376 | 0.601276 | 2.008286 | 1.867495 | 2.024884 |
19 | 524.288 | 350.401 | 32.195 | 318.206 | 0.668337 | 0.061407 | 0.606930 | 2.005053 | 1.878574 | 2.018805 |
20 | 1.048.576 | 702.445 | 60.748 | 641.697 | 0.669904 | 0.057934 | 0.611970 | 2.004689 | 1.886877 | 2.016609 |
21 | 2.097.152 | 1.407.422 | 115.308 | 1.292.114 | 0.671111 | 0.054983 | 0.616128 | 2.003605 | 1.898137 | 2.013589 |
22 | 4.194.304 | 2.819.521 | 218.927 | 2.600.594 | 0.672226 | 0.052196 | 0.620030 | 2.003323 | 1.898628 | 2.012666 |
23 | 8.388.608 | 5.647.071 | 416.726 | 5.230.345 | 0.673183 | 0.049678 | 0.623506 | 2.002848 | 1.903493 | 2.011212 |
24 | 16.777.216 | 11.309.224 | 794.725 | 10.514.499 | 0.674082 | 0.047369 | 0.626713 | 2.002671 | 1.907068 | 2.010288 |
25 | 33.554.432 | 22.642.742 | 1.518.730 | 21.124.012 | 0.674806 | 0.045262 | 0.629545 | 2.002148 | 1.911013 | 2.009037 |
26 | 67.108.864 | 45.331.827 | 2.906.794 | 42.425.033 | 0.675497 | 0.043315 | 0.632182 | 2.002047 | 1.913964 | 2.008379 |
27 | 134.217.728 | 90.748.213 | 5.579.103 | 85.169.110 | 0.676127 | 0.041568 | 0.634559 | 2.001865 | 1.919332 | 2.007520 |
28 | 268.435.456 | 181.653.023 | 10.727.306 | 170.925.717 | 0.676710 | 0.039962 | 0.636748 | 2.001726 | 1.922765 | 2.006898 |
29 | 536.870.912 | 363.603.931 | 20.649.577 | 342.954.354 | 0.677265 | 0.038463 | 0.638802 | 2.001640 | 1.924955 | 2.006453 |
30 | 1.073.741.824 | 727.761.568 | 39.805.953 | 687.955.615 | 0.677781 | 0.037072 | 0.640709 | 2.001523 | 1.927689 | 2.005968 |
31 | 2.147.483.648 | 1.456.575.967 | 76.836.555 | 1.379.739.412 | 0.678271 | 0.035780 | 0.642491 | 2.001447 | 1.930278 | 2.005565 |
32 | 4.294.967.296 | 2.915.087.074 | 148.500.722 | 2.766.586.352 | 0.678722 | 0.034576 | 0.644146 | 2.001328 | 1.932683 | 2.005152 |
33 | 8.589.934.592 | 5.833.854.739 | 287.352.949 | 5.546.501.790 | 0.679150 | 0.033452 | 0.645698 | 2.001263 | 1.935027 | 2.004818 |
34 | 17.179.869.184 | 11.674.663.301 | 556.608.231 | 11.118.055.070 | 0.679555 | 0.032399 | 0.647156 | 2.001192 | 1.937019 | 2.004517 |
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 | 0 | 0 | 2 | 0 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 2 | 0 | 0 | 3 | 0 | 0 |
4 | 16 | 4 | 3 | 0 | 0 | 4 | 0 | 0 |
5 | 32 | 8 | 6 | 1 | 0 | 6 | 1 | 1 |
6 | 64 | 15 | 10 | 4 | 2 | 9 | 2 | 2 |
7 | 128 | 25 | 17 | 7 | 3 | 15 | 4 | 3 |
8 | 256 | 26 | 17 | 8 | 3 | 15 | 5 | 3 |
9 | 512 | 61 | 27 | 33 | 7 | 18 | 26 | 10 |
10 | 1.024 | 123 | 45 | 77 | 15 | 26 | 62 | 20 |
11 | 2.048 | 241 | 78 | 162 | 29 | 44 | 133 | 35 |
12 | 4.096 | 429 | 124 | 304 | 59 | 65 | 245 | 60 |
13 | 8.192 | 766 | 202 | 563 | 103 | 103 | 460 | 100 |
14 | 16.384 | 1.432 | 383 | 1.048 | 177 | 201 | 871 | 183 |
15 | 32.768 | 2.627 | 709 | 1.917 | 335 | 360 | 1.582 | 350 |
16 | 65.536 | 4.912 | 1.289 | 3.622 | 649 | 658 | 2.973 | 632 |
17 | 131.072 | 9.177 | 2.381 | 6.795 | 1.195 | 1.191 | 5.600 | 1.191 |
18 | 262.144 | 17.138 | 4.502 | 12.635 | 2.228 | 2.241 | 10.407 | 2.262 |
19 | 524.288 | 32.195 | 8.475 | 23.719 | 4.099 | 4.207 | 19.620 | 4.269 |
20 | 1.048.576 | 60.748 | 15.938 | 44.809 | 7.734 | 7.928 | 37.075 | 8.011 |
21 | 2.097.152 | 115.308 | 30.269 | 85.038 | 14.639 | 15.160 | 70.399 | 15.110 |
22 | 4.194.304 | 218.927 | 57.292 | 161.634 | 27.830 | 28.696 | 133.804 | 28.597 |
23 | 8.388.608 | 416.726 | 108.532 | 308.193 | 53.052 | 54.351 | 255.141 | 54.182 |
24 | 16.777.216 | 794.725 | 206.712 | 588.012 | 100.825 | 103.518 | 487.187 | 103.195 |
25 | 33.554.432 | 1.518.730 | 394.658 | 1.124.071 | 192.632 | 197.314 | 931.439 | 197.345 |
26 | 67.108.864 | 2.906.794 | 754.235 | 2.152.558 | 368.169 | 377.342 | 1.784.389 | 376.894 |
27 | 134.217.728 | 5.579.103 | 1.443.944 | 4.135.158 | 707.535 | 722.003 | 3.427.623 | 721.942 |
28 | 268.435.456 | 10.727.306 | 2.773.488 | 7.953.817 | 1.360.012 | 1.386.557 | 6.593.805 | 1.386.932 |
29 | 536.870.912 | 20.649.577 | 5.334.033 | 15.315.543 | 2.616.129 | 2.665.995 | 12.699.414 | 2.668.039 |
30 | 1.073.741.824 | 39.805.953 | 10.270.815 | 29.535.137 | 5.042.085 | 5.134.892 | 24.493.052 | 5.135.924 |
31 | 2.147.483.648 | 76.836.555 | 19.801.429 | 57.035.125 | 9.728.599 | 9.898.249 | 47.306.526 | 9.903.181 |
32 | 4.294.967.296 | 148.500.722 | 38.225.113 | 110.275.608 | 18.791.118 | 19.110.159 | 91.484.490 | 19.114.955 |
33 | 8.589.934.592 | 287.352.949 | 73.901.819 | 213.451.129 | 36.350.394 | 36.949.181 | 177.100.735 | 36.952.639 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | 3 |
3 | 8 | 6 | 4 | 2 | 0 | 1 | 1 | 4 |
4 | 16 | 11 | 6 | 5 | 4 | 1 | 2 | 4 |
5 | 32 | 21 | 13 | 8 | 5 | 5 | 5 | 6 |
6 | 64 | 34 | 20 | 14 | 9 | 8 | 9 | 8 |
7 | 128 | 69 | 37 | 32 | 22 | 16 | 15 | 16 |
8 | 256 | 69 | 37 | 32 | 22 | 16 | 15 | 16 |
9 | 512 | 170 | 80 | 90 | 42 | 40 | 34 | 54 |
10 | 1.024 | 430 | 201 | 229 | 109 | 98 | 81 | 142 |
11 | 2.048 | 961 | 450 | 511 | 231 | 210 | 213 | 307 |
12 | 4.096 | 2.109 | 1.001 | 1.108 | 495 | 498 | 469 | 647 |
13 | 8.192 | 4.473 | 2.178 | 2.295 | 1.064 | 1.027 | 1.019 | 1.363 |
14 | 16.384 | 9.200 | 4.421 | 4.779 | 2.197 | 2.156 | 2.071 | 2.776 |
15 | 32.768 | 18.851 | 9.108 | 9.743 | 4.532 | 4.459 | 4.300 | 5.560 |
16 | 65.536 | 38.372 | 18.616 | 19.756 | 9.262 | 9.042 | 8.815 | 11.253 |
17 | 131.072 | 77.842 | 37.838 | 40.004 | 18.647 | 18.494 | 18.044 | 22.657 |
18 | 262.144 | 157.621 | 76.816 | 80.805 | 37.768 | 37.633 | 36.692 | 45.528 |
19 | 524.288 | 318.206 | 155.323 | 162.883 | 76.713 | 75.948 | 74.647 | 90.898 |
20 | 1.048.576 | 641.697 | 313.508 | 328.189 | 154.904 | 153.676 | 151.491 | 181.626 |
21 | 2.097.152 | 1.292.114 | 632.359 | 659.755 | 311.970 | 310.431 | 306.225 | 363.488 |
22 | 4.194.304 | 2.600.594 | 1.273.577 | 1.327.017 | 629.234 | 627.207 | 617.772 | 726.381 |
23 | 8.388.608 | 5.230.345 | 2.565.513 | 2.664.832 | 1.268.297 | 1.263.734 | 1.246.047 | 1.452.267 |
24 | 16.777.216 | 10.514.499 | 5.160.951 | 5.353.548 | 2.551.826 | 2.547.019 | 2.510.232 | 2.905.422 |
25 | 33.554.432 | 21.124.012 | 10.379.758 | 10.744.254 | 5.136.179 | 5.123.295 | 5.053.829 | 5.810.709 |
26 | 67.108.864 | 42.425.033 | 20.862.773 | 21.562.260 | 10.327.485 | 10.303.481 | 10.173.049 | 11.621.018 |
27 | 134.217.728 | 85.169.110 | 41.916.589 | 43.252.521 | 20.754.799 | 20.714.302 | 20.458.400 | 23.241.609 |
28 | 268.435.456 | 170.925.717 | 84.178.813 | 86.746.904 | 41.696.148 | 41.614.517 | 41.137.401 | 46.477.651 |
29 | 536.870.912 | 342.954.354 | 169.006.495 | 173.947.859 | 83.732.028 | 83.588.785 | 82.678.608 | 92.954.933 |
30 | 1.073.741.824 | 687.955.615 | 339.219.813 | 348.735.802 | 168.113.174 | 167.853.657 | 166.097.731 | 185.891.053 |
31 | 2.147.483.648 | 1.379.739.412 | 680.703.360 | 699.036.052 | 337.459.663 | 336.942.893 | 333.567.727 | 371.769.129 |
32 | 4.294.967.296 | 2.766.586.352 | 1.365.618.144 | 1.400.968.208 | 677.164.343 | 676.214.960 | 669.688.019 | 743.519.030 |
33 | 8.589.934.592 | 5.546.501.790 | 2.739.059.848 | 2.807.441.942 | 1.358.558.904 | 1.356.770.222 | 1.344.127.338 | 1.487.045.326 |