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-37x+3
f(0)=3
f(1)=11
f(2)=67
f(3)=1
f(4)=43
f(5)=157
f(6)=61
f(7)=23
f(8)=229
f(9)=83
f(10)=89
f(11)=283
f(12)=1
f(13)=103
f(14)=29
f(15)=109
f(16)=37
f(17)=337
f(18)=113
f(19)=1
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=41
f(39)=1
f(40)=1
f(41)=167
f(42)=71
f(43)=1
f(44)=311
f(45)=1
f(46)=139
f(47)=1
f(48)=59
f(49)=197
f(50)=653
f(51)=239
f(52)=1
f(53)=1
f(54)=307
f(55)=331
f(56)=97
f(57)=127
f(58)=1
f(59)=1301
f(60)=461
f(61)=163
f(62)=1553
f(63)=547
f(64)=577
f(65)=1823
f(66)=1
f(67)=1
f(68)=2111
f(69)=1
f(70)=257
f(71)=2417
f(72)=1
f(73)=877
f(74)=2741
f(75)=317
f(76)=1
f(77)=3083
f(78)=1
f(79)=1
f(80)=313
f(81)=1
f(82)=1231
f(83)=3821
f(84)=439
f(85)=1361
f(86)=4217
f(87)=1451
f(88)=499
f(89)=421
f(90)=1
f(91)=149
f(92)=1
f(93)=193
f(94)=1787
f(95)=1
f(96)=1889
f(97)=647
f(98)=5981
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-37x+3 could be written as f(y)= y^2-339.25 with x=y+18.5
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.5
f'(x)>2x-38 with x > 18
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 | 5 | 5 | 1.000000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 55 | 21 | 34 | 0.550000 | 0.210000 | 0.550000 | 5.500000 | 4.200000 | 6.800000 |
3 | 1.000 | 667 | 122 | 545 | 0.667000 | 0.122000 | 0.667000 | 12.127273 | 5.809524 | 16.029411 |
4 | 10.000 | 6.895 | 872 | 6.023 | 0.689500 | 0.087200 | 0.689500 | 10.337332 | 7.147541 | 11.051376 |
5 | 100.000 | 69.477 | 6.851 | 62.626 | 0.694770 | 0.068510 | 0.694770 | 10.076432 | 7.856651 | 10.397808 |
6 | 1.000.000 | 694.681 | 56.246 | 638.435 | 0.694681 | 0.056246 | 0.694681 | 9.998719 | 8.209896 | 10.194408 |
7 | 10.000.000 | 6.941.608 | 476.047 | 6.465.561 | 0.694161 | 0.047605 | 0.694161 | 9.992512 | 8.463659 | 10.127203 |
8 | 100.000.000 | 69.393.358 | 4.117.991 | 65.275.367 | 0.693934 | 0.041180 | 0.693934 | 9.996727 | 8.650388 | 10.095856 |
9 | 1.000.000.000 | 693.741.998 | 36.339.900 | 657.402.098 | 0.693742 | 0.036340 | 0.693742 | 9.997239 | 8.824667 | 10.071213 |
10 | 10.000.000.000 | 6.936.022.324 | 325.169.985 | 6.610.852.339 | 0.693602 | 0.032517 | 0.693602 | 9.997986 | 8.948015 | 10.056026 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 8 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 2.000000 | 2.500000 | 1.500000 |
4 | 16 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 1.875000 | 1.200000 | 3.000000 |
5 | 32 | 17 | 7 | 10 | 0.531250 | 0.218750 | 0.312500 | 1.133333 | 1.166667 | 1.111111 |
6 | 64 | 33 | 13 | 20 | 0.515625 | 0.203125 | 0.312500 | 1.941176 | 1.857143 | 2.000000 |
7 | 128 | 72 | 23 | 49 | 0.562500 | 0.179688 | 0.382812 | 2.181818 | 1.769231 | 2.450000 |
8 | 256 | 154 | 41 | 113 | 0.601562 | 0.160156 | 0.441406 | 2.138889 | 1.782609 | 2.306123 |
9 | 512 | 331 | 69 | 262 | 0.646484 | 0.134766 | 0.511719 | 2.149351 | 1.682927 | 2.318584 |
10 | 1.024 | 684 | 124 | 560 | 0.667969 | 0.121094 | 0.546875 | 2.066465 | 1.797101 | 2.137405 |
11 | 2.048 | 1.376 | 225 | 1.151 | 0.671875 | 0.109863 | 0.562012 | 2.011696 | 1.814516 | 2.055357 |
12 | 4.096 | 2.788 | 409 | 2.379 | 0.680664 | 0.099854 | 0.580811 | 2.026163 | 1.817778 | 2.066898 |
13 | 8.192 | 5.641 | 749 | 4.892 | 0.688599 | 0.091431 | 0.597168 | 2.023314 | 1.831296 | 2.056326 |
14 | 16.384 | 11.345 | 1.342 | 10.003 | 0.692444 | 0.081909 | 0.610535 | 2.011168 | 1.791722 | 2.044767 |
15 | 32.768 | 22.727 | 2.514 | 20.213 | 0.693573 | 0.076721 | 0.616852 | 2.003261 | 1.873323 | 2.020694 |
16 | 65.536 | 45.495 | 4.689 | 40.806 | 0.694199 | 0.071548 | 0.622650 | 2.001804 | 1.865155 | 2.018800 |
17 | 131.072 | 91.061 | 8.788 | 82.273 | 0.694740 | 0.067047 | 0.627693 | 2.001561 | 1.874174 | 2.016199 |
18 | 262.144 | 182.194 | 16.448 | 165.746 | 0.695015 | 0.062744 | 0.632271 | 2.000791 | 1.871643 | 2.014585 |
19 | 524.288 | 364.254 | 31.022 | 333.232 | 0.694759 | 0.059170 | 0.635590 | 1.999264 | 1.886065 | 2.010498 |
20 | 1.048.576 | 728.442 | 58.688 | 669.754 | 0.694696 | 0.055969 | 0.638727 | 1.999819 | 1.891819 | 2.009873 |
21 | 2.097.152 | 1.456.354 | 111.593 | 1.344.761 | 0.694444 | 0.053212 | 0.641232 | 1.999272 | 1.901462 | 2.007843 |
22 | 4.194.304 | 2.912.398 | 211.968 | 2.700.430 | 0.694370 | 0.050537 | 0.643833 | 1.999787 | 1.899474 | 2.008111 |
23 | 8.388.608 | 5.823.045 | 404.251 | 5.418.794 | 0.694161 | 0.048190 | 0.645971 | 1.999399 | 1.907132 | 2.006641 |
24 | 16.777.216 | 11.644.410 | 771.295 | 10.873.115 | 0.694061 | 0.045973 | 0.648088 | 1.999712 | 1.907961 | 2.006556 |
25 | 33.554.432 | 23.287.099 | 1.475.317 | 21.811.782 | 0.694010 | 0.043968 | 0.650042 | 1.999852 | 1.912779 | 2.006029 |
26 | 67.108.864 | 46.570.992 | 2.828.877 | 43.742.115 | 0.693962 | 0.042154 | 0.651808 | 1.999862 | 1.917471 | 2.005435 |
27 | 134.217.728 | 93.132.908 | 5.433.482 | 87.699.426 | 0.693894 | 0.040483 | 0.653412 | 1.999805 | 1.920720 | 2.004920 |
28 | 268.435.456 | 186.251.572 | 10.455.913 | 175.795.659 | 0.693841 | 0.038951 | 0.654890 | 1.999847 | 1.924348 | 2.004525 |
29 | 536.870.912 | 372.474.007 | 20.149.996 | 352.324.011 | 0.693787 | 0.037532 | 0.656255 | 1.999844 | 1.927139 | 2.004168 |
30 | 1.073.741.824 | 744.892.542 | 38.878.858 | 706.013.684 | 0.693735 | 0.036209 | 0.657526 | 1.999851 | 1.929472 | 2.003876 |
31 | 2.147.483.648 | 1.489.691.719 | 75.108.988 | 1.414.582.731 | 0.693692 | 0.034975 | 0.658716 | 1.999875 | 1.931872 | 2.003619 |
32 | 4.294.967.296 | 2.979.205.062 | 145.266.907 | 2.833.938.155 | 0.693650 | 0.033823 | 0.659828 | 1.999880 | 1.934082 | 2.003374 |
33 | 8.589.934.592 | 5.958.075.879 | 281.273.864 | 5.676.802.015 | 0.693611 | 0.032745 | 0.660867 | 1.999888 | 1.936255 | 2.003150 |
34 | 17.179.869.184 | 11.915.533.772 | 545.172.378 | 11.370.361.394 | 0.693575 | 0.031733 | 0.661842 | 1.999896 | 1.938226 | 2.002952 |
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 | 5 | 3 | 0 | 0 | 2 | 2 | 1 |
4 | 16 | 6 | 4 | 0 | 0 | 3 | 2 | 1 |
5 | 32 | 7 | 5 | 0 | 1 | 3 | 2 | 1 |
6 | 64 | 13 | 5 | 5 | 2 | 4 | 4 | 3 |
7 | 128 | 23 | 5 | 15 | 4 | 7 | 7 | 5 |
8 | 256 | 41 | 5 | 33 | 11 | 11 | 12 | 7 |
9 | 512 | 69 | 5 | 61 | 18 | 18 | 18 | 15 |
10 | 1.024 | 124 | 5 | 116 | 30 | 29 | 35 | 30 |
11 | 2.048 | 225 | 5 | 217 | 54 | 59 | 52 | 60 |
12 | 4.096 | 409 | 5 | 401 | 105 | 106 | 98 | 100 |
13 | 8.192 | 749 | 5 | 741 | 191 | 184 | 180 | 194 |
14 | 16.384 | 1.342 | 5 | 1.334 | 339 | 326 | 337 | 340 |
15 | 32.768 | 2.514 | 5 | 2.506 | 619 | 619 | 637 | 639 |
16 | 65.536 | 4.689 | 5 | 4.681 | 1.176 | 1.176 | 1.165 | 1.172 |
17 | 131.072 | 8.788 | 5 | 8.780 | 2.177 | 2.217 | 2.191 | 2.203 |
18 | 262.144 | 16.448 | 5 | 16.440 | 4.091 | 4.111 | 4.116 | 4.130 |
19 | 524.288 | 31.022 | 5 | 31.014 | 7.716 | 7.750 | 7.807 | 7.749 |
20 | 1.048.576 | 58.688 | 5 | 58.680 | 14.553 | 14.751 | 14.737 | 14.647 |
21 | 2.097.152 | 111.593 | 5 | 111.585 | 27.843 | 28.024 | 27.833 | 27.893 |
22 | 4.194.304 | 211.968 | 5 | 211.960 | 53.022 | 53.120 | 52.845 | 52.981 |
23 | 8.388.608 | 404.251 | 5 | 404.243 | 100.974 | 101.293 | 101.034 | 100.950 |
24 | 16.777.216 | 771.295 | 5 | 771.287 | 192.589 | 193.161 | 192.915 | 192.630 |
25 | 33.554.432 | 1.475.317 | 5 | 1.475.309 | 368.699 | 368.742 | 369.348 | 368.528 |
26 | 67.108.864 | 2.828.877 | 5 | 2.828.869 | 707.221 | 706.704 | 707.488 | 707.464 |
27 | 134.217.728 | 5.433.482 | 5 | 5.433.474 | 1.358.466 | 1.357.463 | 1.359.514 | 1.358.039 |
28 | 268.435.456 | 10.455.913 | 5 | 10.455.905 | 2.613.485 | 2.612.557 | 2.615.517 | 2.614.354 |
29 | 536.870.912 | 20.149.996 | 5 | 20.149.988 | 5.037.851 | 5.034.508 | 5.039.488 | 5.038.149 |
30 | 1.073.741.824 | 38.878.858 | 5 | 38.878.850 | 9.717.910 | 9.716.330 | 9.724.882 | 9.719.736 |
31 | 2.147.483.648 | 75.108.988 | 5 | 75.108.980 | 18.772.877 | 18.775.644 | 18.783.039 | 18.777.428 |
32 | 4.294.967.296 | 145.266.907 | 5 | 145.266.899 | 36.314.829 | 36.314.046 | 36.318.985 | 36.319.047 |
33 | 8.589.934.592 | 281.273.864 | 5 | 281.273.856 | 70.319.878 | 70.318.023 | 70.319.627 | 70.316.336 |
34 | 17.179.869.184 | 545.172.378 | 5 | 545.172.370 | 136.290.953 | 136.286.585 | 136.293.656 | 136.301.184 |
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 | 0 | 1 | 0 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 2 | 1 | 0 | 2 | 1 | 0 |
4 | 16 | 9 | 5 | 4 | 1 | 3 | 4 | 1 |
5 | 32 | 10 | 5 | 5 | 2 | 3 | 4 | 1 |
6 | 64 | 20 | 12 | 8 | 3 | 8 | 6 | 3 |
7 | 128 | 49 | 28 | 21 | 11 | 14 | 14 | 10 |
8 | 256 | 113 | 59 | 54 | 27 | 29 | 27 | 30 |
9 | 512 | 262 | 142 | 120 | 70 | 60 | 62 | 70 |
10 | 1.024 | 560 | 281 | 279 | 135 | 136 | 142 | 147 |
11 | 2.048 | 1.151 | 602 | 549 | 277 | 280 | 293 | 301 |
12 | 4.096 | 2.379 | 1.251 | 1.128 | 591 | 588 | 581 | 619 |
13 | 8.192 | 4.892 | 2.502 | 2.390 | 1.232 | 1.200 | 1.234 | 1.226 |
14 | 16.384 | 10.003 | 5.111 | 4.892 | 2.519 | 2.515 | 2.489 | 2.480 |
15 | 32.768 | 20.213 | 10.438 | 9.775 | 5.004 | 5.079 | 5.105 | 5.025 |
16 | 65.536 | 40.806 | 21.011 | 19.795 | 10.324 | 10.117 | 10.185 | 10.180 |
17 | 131.072 | 82.273 | 42.019 | 40.254 | 20.587 | 20.490 | 20.487 | 20.709 |
18 | 262.144 | 165.746 | 84.600 | 81.146 | 41.349 | 41.445 | 41.590 | 41.362 |
19 | 524.288 | 333.232 | 169.962 | 163.270 | 83.402 | 83.272 | 83.275 | 83.283 |
20 | 1.048.576 | 669.754 | 341.059 | 328.695 | 167.464 | 167.570 | 167.197 | 167.523 |
21 | 2.097.152 | 1.344.761 | 684.391 | 660.370 | 336.202 | 336.787 | 335.516 | 336.256 |
22 | 4.194.304 | 2.700.430 | 1.372.875 | 1.327.555 | 674.564 | 675.769 | 675.058 | 675.039 |
23 | 8.388.608 | 5.418.794 | 2.753.014 | 2.665.780 | 1.354.201 | 1.354.508 | 1.355.209 | 1.354.876 |
24 | 16.777.216 | 10.873.115 | 5.520.965 | 5.352.150 | 2.717.427 | 2.718.193 | 2.717.837 | 2.719.658 |
25 | 33.554.432 | 21.811.782 | 11.067.017 | 10.744.765 | 5.453.061 | 5.452.165 | 5.452.337 | 5.454.219 |
26 | 67.108.864 | 43.742.115 | 22.179.780 | 21.562.335 | 10.935.163 | 10.932.178 | 10.936.574 | 10.938.200 |
27 | 134.217.728 | 87.699.426 | 44.442.458 | 43.256.968 | 21.921.676 | 21.922.773 | 21.928.720 | 21.926.257 |
28 | 268.435.456 | 175.795.659 | 89.036.636 | 86.759.023 | 43.947.617 | 43.946.133 | 43.957.084 | 43.944.825 |
29 | 536.870.912 | 352.324.011 | 178.361.020 | 173.962.991 | 88.078.071 | 88.077.334 | 88.087.502 | 88.081.104 |
30 | 1.073.741.824 | 706.013.684 | 357.234.021 | 348.779.663 | 176.496.694 | 176.495.944 | 176.514.416 | 176.506.630 |
31 | 2.147.483.648 | 1.414.582.731 | 715.460.342 | 699.122.389 | 353.640.825 | 353.648.354 | 353.646.823 | 353.646.729 |
32 | 4.294.967.296 | 2.833.938.155 | 1.432.700.048 | 1.401.238.107 | 708.483.302 | 708.470.201 | 708.478.558 | 708.506.094 |
33 | 8.589.934.592 | 5.676.802.015 | 2.868.805.405 | 2.807.996.610 | 1.419.178.446 | 1.419.201.959 | 1.419.198.386 | 1.419.223.224 |
34 | 17.179.869.184 | 11.370.361.394 | 5.744.088.957 | 5.626.272.437 | 2.842.533.882 | 2.842.640.902 | 2.842.592.249 | 2.842.594.361 |