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+41
f(0)=41
f(1)=3
f(2)=1
f(3)=29
f(4)=1
f(5)=19
f(6)=139
f(7)=1
f(8)=61
f(9)=101
f(10)=73
f(11)=13
f(12)=1
f(13)=43
f(14)=89
f(15)=137
f(16)=31
f(17)=47
f(18)=283
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)=1
f(39)=79
f(40)=67
f(41)=1
f(42)=293
f(43)=1
f(44)=131
f(45)=223
f(46)=167
f(47)=1
f(48)=617
f(49)=113
f(50)=1
f(51)=1
f(52)=97
f(53)=157
f(54)=1013
f(55)=181
f(56)=1
f(57)=619
f(58)=439
f(59)=233
f(60)=1481
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=107
f(66)=1
f(67)=353
f(68)=739
f(69)=1
f(70)=269
f(71)=421
f(72)=2633
f(73)=457
f(74)=317
f(75)=1483
f(76)=1
f(77)=1
f(78)=1
f(79)=191
f(80)=1187
f(81)=1
f(82)=1
f(83)=1
f(84)=4073
f(85)=701
f(86)=1447
f(87)=2239
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=577
f(93)=2671
f(94)=1831
f(95)=941
f(96)=5801
f(97)=331
f(98)=2039
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-36x+41 could be written as f(y)= y^2-283 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-37 with x > 17
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 | 8 | 5 | 3 | 0.800000 | 0.500000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 48 | 20 | 28 | 0.480000 | 0.200000 | 0.280000 | 6.000000 | 4.000000 | 9.333333 |
3 | 1.000 | 628 | 119 | 509 | 0.628000 | 0.119000 | 0.509000 | 13.083333 | 5.950000 | 18.178572 |
4 | 10.000 | 6.678 | 894 | 5.784 | 0.667800 | 0.089400 | 0.578400 | 10.633758 | 7.512605 | 11.363458 |
5 | 100.000 | 67.633 | 6.735 | 60.898 | 0.676330 | 0.067350 | 0.608980 | 10.127733 | 7.533557 | 10.528700 |
6 | 1.000.000 | 678.690 | 55.120 | 623.570 | 0.678690 | 0.055120 | 0.623570 | 10.034894 | 8.184113 | 10.239581 |
7 | 10.000.000 | 6.808.498 | 464.875 | 6.343.623 | 0.680850 | 0.046487 | 0.634362 | 10.031823 | 8.433871 | 10.173073 |
8 | 100.000.000 | 68.233.090 | 4.019.405 | 64.213.685 | 0.682331 | 0.040194 | 0.642137 | 10.021753 | 8.646206 | 10.122557 |
9 | 1.000.000.000 | 683.447.124 | 35.419.330 | 648.027.794 | 0.683447 | 0.035419 | 0.648028 | 10.016359 | 8.812082 | 10.091740 |
10 | 10.000.000.000 | 6.843.593.241 | 316.654.391 | 6.526.938.850 | 0.684359 | 0.031665 | 0.652694 | 10.013348 | 8.940158 | 10.072004 |
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 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 6 | 4 | 2 | 0.750000 | 0.500000 | 0.250000 | 2.000000 | 1.333333 | inf |
4 | 16 | 11 | 6 | 5 | 0.687500 | 0.375000 | 0.312500 | 1.833333 | 1.500000 | 2.500000 |
5 | 32 | 13 | 7 | 6 | 0.406250 | 0.218750 | 0.187500 | 1.181818 | 1.166667 | 1.200000 |
6 | 64 | 27 | 14 | 13 | 0.421875 | 0.218750 | 0.203125 | 2.076923 | 2.000000 | 2.166667 |
7 | 128 | 65 | 24 | 41 | 0.507812 | 0.187500 | 0.320312 | 2.407408 | 1.714286 | 3.153846 |
8 | 256 | 144 | 41 | 103 | 0.562500 | 0.160156 | 0.402344 | 2.215385 | 1.708333 | 2.512195 |
9 | 512 | 311 | 70 | 241 | 0.607422 | 0.136719 | 0.470703 | 2.159722 | 1.707317 | 2.339806 |
10 | 1.024 | 644 | 124 | 520 | 0.628906 | 0.121094 | 0.507812 | 2.070740 | 1.771429 | 2.157676 |
11 | 2.048 | 1.324 | 226 | 1.098 | 0.646484 | 0.110352 | 0.536133 | 2.055901 | 1.822581 | 2.111538 |
12 | 4.096 | 2.703 | 417 | 2.286 | 0.659912 | 0.101807 | 0.558105 | 2.041541 | 1.845133 | 2.081967 |
13 | 8.192 | 5.475 | 754 | 4.721 | 0.668335 | 0.092041 | 0.576294 | 2.025527 | 1.808154 | 2.065179 |
14 | 16.384 | 10.978 | 1.375 | 9.603 | 0.670044 | 0.083923 | 0.586121 | 2.005114 | 1.823607 | 2.034103 |
15 | 32.768 | 22.066 | 2.529 | 19.537 | 0.673401 | 0.077179 | 0.596222 | 2.010020 | 1.839273 | 2.034468 |
16 | 65.536 | 44.265 | 4.598 | 39.667 | 0.675430 | 0.070160 | 0.605270 | 2.006027 | 1.818110 | 2.030353 |
17 | 131.072 | 88.676 | 8.616 | 80.060 | 0.676544 | 0.065735 | 0.610809 | 2.003298 | 1.873858 | 2.018302 |
18 | 262.144 | 177.517 | 16.079 | 161.438 | 0.677174 | 0.061337 | 0.615837 | 2.001861 | 1.866179 | 2.016463 |
19 | 524.288 | 355.526 | 30.395 | 325.131 | 0.678112 | 0.057974 | 0.620138 | 2.002772 | 1.890354 | 2.013968 |
20 | 1.048.576 | 711.828 | 57.544 | 654.284 | 0.678852 | 0.054878 | 0.623974 | 2.002183 | 1.893206 | 2.012370 |
21 | 2.097.152 | 1.424.898 | 109.044 | 1.315.854 | 0.679444 | 0.051996 | 0.627448 | 2.001745 | 1.894967 | 2.011136 |
22 | 4.194.304 | 2.852.659 | 207.350 | 2.645.309 | 0.680127 | 0.049436 | 0.630691 | 2.002009 | 1.901526 | 2.010336 |
23 | 8.388.608 | 5.710.239 | 394.647 | 5.315.592 | 0.680714 | 0.047046 | 0.633668 | 2.001725 | 1.903289 | 2.009441 |
24 | 16.777.216 | 11.428.796 | 753.390 | 10.675.406 | 0.681209 | 0.044906 | 0.636304 | 2.001457 | 1.909022 | 2.008319 |
25 | 33.554.432 | 22.873.875 | 1.440.652 | 21.433.223 | 0.681695 | 0.042935 | 0.638760 | 2.001425 | 1.912226 | 2.007720 |
26 | 67.108.864 | 45.776.296 | 2.760.598 | 43.015.698 | 0.682120 | 0.041136 | 0.640984 | 2.001248 | 1.916214 | 2.006963 |
27 | 134.217.728 | 91.599.701 | 5.303.464 | 86.296.237 | 0.682471 | 0.039514 | 0.642957 | 2.001029 | 1.921129 | 2.006157 |
28 | 268.435.456 | 183.293.501 | 10.200.855 | 173.092.646 | 0.682822 | 0.038001 | 0.644820 | 2.001027 | 1.923432 | 2.005796 |
29 | 536.870.912 | 366.771.320 | 19.646.916 | 347.124.404 | 0.683165 | 0.036595 | 0.646570 | 2.001006 | 1.926007 | 2.005426 |
30 | 1.073.741.824 | 733.879.312 | 37.893.804 | 695.985.508 | 0.683478 | 0.035291 | 0.648187 | 2.000918 | 1.928741 | 2.005003 |
31 | 2.147.483.648 | 1.468.378.742 | 73.178.161 | 1.395.200.581 | 0.683767 | 0.034076 | 0.649691 | 2.000845 | 1.931138 | 2.004640 |
32 | 4.294.967.296 | 2.937.944.145 | 141.501.837 | 2.796.442.308 | 0.684043 | 0.032946 | 0.651097 | 2.000808 | 1.933662 | 2.004330 |
33 | 8.589.934.592 | 5.878.119.329 | 273.919.672 | 5.604.199.657 | 0.684303 | 0.031888 | 0.652415 | 2.000759 | 1.935803 | 2.004046 |
34 | 17.179.869.184 | 11.760.453.486 | 530.783.174 | 11.229.670.312 | 0.684548 | 0.030896 | 0.653653 | 2.000717 | 1.937733 | 2.003796 |
35 | 34.359.738.368 | 23.528.890.293 | 1.029.554.782 | 22.499.335.511 | 0.684781 | 0.029964 | 0.654817 | 2.000679 | 1.939690 | 2.003561 |
36 | 68.719.476.736 | 47.072.859.104 | 1.998.861.065 | 45.073.998.039 | 0.685000 | 0.029087 | 0.655913 | 2.000641 | 1.941481 | 2.003348 |
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 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 1 | 2 | 1 | 0 |
4 | 16 | 6 | 1 | 4 | 2 | 2 | 2 | 0 |
5 | 32 | 7 | 2 | 4 | 2 | 3 | 2 | 0 |
6 | 64 | 14 | 5 | 8 | 4 | 4 | 4 | 2 |
7 | 128 | 24 | 10 | 13 | 8 | 6 | 5 | 5 |
8 | 256 | 41 | 21 | 19 | 11 | 12 | 8 | 10 |
9 | 512 | 70 | 36 | 33 | 19 | 21 | 14 | 16 |
10 | 1.024 | 124 | 63 | 60 | 29 | 33 | 31 | 31 |
11 | 2.048 | 226 | 114 | 111 | 58 | 59 | 53 | 56 |
12 | 4.096 | 417 | 211 | 205 | 108 | 108 | 97 | 104 |
13 | 8.192 | 754 | 391 | 362 | 190 | 205 | 172 | 187 |
14 | 16.384 | 1.375 | 711 | 663 | 328 | 359 | 335 | 353 |
15 | 32.768 | 2.529 | 1.292 | 1.236 | 624 | 643 | 612 | 650 |
16 | 65.536 | 4.598 | 2.358 | 2.239 | 1.133 | 1.170 | 1.106 | 1.189 |
17 | 131.072 | 8.616 | 4.347 | 4.268 | 2.156 | 2.185 | 2.112 | 2.163 |
18 | 262.144 | 16.079 | 8.115 | 7.963 | 4.001 | 4.089 | 3.962 | 4.027 |
19 | 524.288 | 30.395 | 15.339 | 15.055 | 7.577 | 7.730 | 7.478 | 7.610 |
20 | 1.048.576 | 57.544 | 29.102 | 28.441 | 14.248 | 14.603 | 14.193 | 14.500 |
21 | 2.097.152 | 109.044 | 55.277 | 53.766 | 26.977 | 27.623 | 26.789 | 27.655 |
22 | 4.194.304 | 207.350 | 104.961 | 102.388 | 51.403 | 52.411 | 50.985 | 52.551 |
23 | 8.388.608 | 394.647 | 199.487 | 195.159 | 97.689 | 99.654 | 97.470 | 99.834 |
24 | 16.777.216 | 753.390 | 381.029 | 372.360 | 186.144 | 190.557 | 186.216 | 190.473 |
25 | 33.554.432 | 1.440.652 | 728.174 | 712.477 | 356.308 | 363.916 | 356.169 | 364.259 |
26 | 67.108.864 | 2.760.598 | 1.394.953 | 1.365.644 | 682.914 | 697.424 | 682.730 | 697.530 |
27 | 134.217.728 | 5.303.464 | 2.678.686 | 2.624.777 | 1.312.369 | 1.339.107 | 1.312.408 | 1.339.580 |
28 | 268.435.456 | 10.200.855 | 5.148.719 | 5.052.135 | 2.526.232 | 2.573.708 | 2.525.903 | 2.575.012 |
29 | 536.870.912 | 19.646.916 | 9.910.959 | 9.735.956 | 4.868.457 | 4.955.522 | 4.867.499 | 4.955.438 |
30 | 1.073.741.824 | 37.893.804 | 19.114.240 | 18.779.563 | 9.389.020 | 9.558.439 | 9.390.543 | 9.555.802 |
31 | 2.147.483.648 | 73.178.161 | 36.906.787 | 36.271.373 | 18.135.975 | 18.457.972 | 18.135.398 | 18.448.816 |
32 | 4.294.967.296 | 141.501.837 | 71.343.624 | 70.158.212 | 35.073.788 | 35.676.173 | 35.084.424 | 35.667.452 |
33 | 8.589.934.592 | 273.919.672 | 138.063.788 | 135.855.883 | 67.918.066 | 69.037.693 | 67.937.817 | 69.026.096 |
34 | 17.179.869.184 | 530.783.174 | 267.461.157 | 263.322.016 | 131.654.464 | 133.733.222 | 131.667.552 | 133.727.936 |
35 | 34.359.738.368 | 1.029.554.782 | 518.661.615 | 510.893.166 | 255.432.695 | 259.328.430 | 255.460.471 | 259.333.186 |
36 | 68.719.476.736 | 1.998.861.065 | 1.006.761.708 | 992.099.356 | 496.034.907 | 503.370.996 | 496.064.449 | 503.390.713 |
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 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
4 | 16 | 5 | 4 | 1 | 2 | 2 | 1 | 0 |
5 | 32 | 6 | 4 | 2 | 2 | 2 | 1 | 1 |
6 | 64 | 13 | 7 | 6 | 4 | 3 | 3 | 3 |
7 | 128 | 41 | 22 | 19 | 10 | 8 | 12 | 11 |
8 | 256 | 103 | 51 | 52 | 20 | 27 | 27 | 29 |
9 | 512 | 241 | 116 | 125 | 52 | 63 | 61 | 65 |
10 | 1.024 | 520 | 250 | 270 | 116 | 141 | 128 | 135 |
11 | 2.048 | 1.098 | 548 | 550 | 272 | 265 | 274 | 287 |
12 | 4.096 | 2.286 | 1.152 | 1.134 | 547 | 568 | 581 | 590 |
13 | 8.192 | 4.721 | 2.393 | 2.328 | 1.164 | 1.160 | 1.200 | 1.197 |
14 | 16.384 | 9.603 | 4.816 | 4.787 | 2.355 | 2.418 | 2.398 | 2.432 |
15 | 32.768 | 19.537 | 9.777 | 9.760 | 4.813 | 4.930 | 4.932 | 4.862 |
16 | 65.536 | 39.667 | 19.871 | 19.796 | 9.840 | 9.869 | 10.007 | 9.951 |
17 | 131.072 | 80.060 | 40.138 | 39.922 | 19.864 | 20.063 | 20.129 | 20.004 |
18 | 262.144 | 161.438 | 80.809 | 80.629 | 40.405 | 40.385 | 40.484 | 40.164 |
19 | 524.288 | 325.131 | 162.575 | 162.556 | 81.054 | 81.450 | 81.405 | 81.222 |
20 | 1.048.576 | 654.284 | 327.055 | 327.229 | 163.250 | 163.603 | 164.174 | 163.257 |
21 | 2.097.152 | 1.315.854 | 658.031 | 657.823 | 328.433 | 328.869 | 329.562 | 328.990 |
22 | 4.194.304 | 2.645.309 | 1.323.301 | 1.322.008 | 661.471 | 660.664 | 661.746 | 661.428 |
23 | 8.388.608 | 5.315.592 | 2.658.096 | 2.657.496 | 1.329.178 | 1.327.543 | 1.330.706 | 1.328.165 |
24 | 16.777.216 | 10.675.406 | 5.337.601 | 5.337.805 | 2.669.672 | 2.666.973 | 2.671.071 | 2.667.690 |
25 | 33.554.432 | 21.433.223 | 10.715.798 | 10.717.425 | 5.359.593 | 5.355.351 | 5.362.400 | 5.355.879 |
26 | 67.108.864 | 43.015.698 | 21.511.480 | 21.504.218 | 10.760.333 | 10.745.846 | 10.761.966 | 10.747.553 |
27 | 134.217.728 | 86.296.237 | 43.150.065 | 43.146.172 | 21.586.637 | 21.555.810 | 21.590.348 | 21.563.442 |
28 | 268.435.456 | 173.092.646 | 86.551.493 | 86.541.153 | 43.298.913 | 43.242.339 | 43.299.927 | 43.251.467 |
29 | 536.870.912 | 347.124.404 | 173.580.623 | 173.543.781 | 86.823.928 | 86.724.882 | 86.832.892 | 86.742.702 |
30 | 1.073.741.824 | 695.985.508 | 348.038.319 | 347.947.189 | 174.087.774 | 173.903.607 | 174.084.063 | 173.910.064 |
31 | 2.147.483.648 | 1.395.200.581 | 697.695.259 | 697.505.322 | 348.968.238 | 348.638.923 | 348.942.670 | 348.650.750 |
32 | 4.294.967.296 | 2.796.442.308 | 1.398.390.857 | 1.398.051.451 | 699.430.056 | 698.804.614 | 699.408.614 | 698.799.024 |
33 | 8.589.934.592 | 5.604.199.657 | 2.802.433.409 | 2.801.766.248 | 1.401.638.093 | 1.400.485.178 | 1.401.603.581 | 1.400.472.805 |
34 | 17.179.869.184 | 11.229.670.312 | 5.615.487.250 | 5.614.183.062 | 2.808.476.254 | 2.806.337.476 | 2.808.519.450 | 2.806.337.132 |
35 | 34.359.738.368 | 22.499.335.511 | 11.250.896.938 | 11.248.438.573 | 5.626.884.414 | 5.622.796.592 | 5.626.854.679 | 5.622.799.826 |
36 | 68.719.476.736 | 45.073.998.039 | 22.539.245.928 | 22.534.752.111 | 11.272.354.046 | 11.264.706.891 | 11.272.311.564 | 11.264.625.538 |