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-200x+103
f(0)=103
f(1)=3
f(2)=293
f(3)=61
f(4)=227
f(5)=109
f(6)=1061
f(7)=13
f(8)=1433
f(9)=101
f(10)=599
f(11)=19
f(12)=2153
f(13)=97
f(14)=41
f(15)=167
f(16)=947
f(17)=47
f(18)=1
f(19)=139
f(20)=269
f(21)=457
f(22)=31
f(23)=1
f(24)=317
f(25)=89
f(26)=4421
f(27)=571
f(28)=1571
f(29)=607
f(30)=263
f(31)=107
f(32)=5273
f(33)=1
f(34)=1847
f(35)=709
f(36)=5801
f(37)=1
f(38)=6053
f(39)=193
f(40)=2099
f(41)=401
f(42)=1
f(43)=277
f(44)=6761
f(45)=859
f(46)=179
f(47)=443
f(48)=7193
f(49)=1
f(50)=569
f(51)=937
f(52)=2531
f(53)=1
f(54)=251
f(55)=1
f(56)=419
f(57)=503
f(58)=2711
f(59)=79
f(60)=8297
f(61)=349
f(62)=1
f(63)=1
f(64)=1
f(65)=271
f(66)=8741
f(67)=367
f(68)=467
f(69)=1117
f(70)=2999
f(71)=283
f(72)=701
f(73)=191
f(74)=9221
f(75)=1
f(76)=239
f(77)=1171
f(78)=9413
f(79)=197
f(80)=9497
f(81)=149
f(82)=3191
f(83)=1201
f(84)=311
f(85)=1
f(86)=1
f(87)=1
f(88)=3251
f(89)=1
f(90)=1
f(91)=409
f(92)=9833
f(93)=1231
f(94)=173
f(95)=617
f(96)=241
f(97)=1
f(98)=761
f(99)=1237
b) Substitution of the polynom
The polynom f(x)=x^2-200x+103 could be written as f(y)= y^2-9897 with x=y+100
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-100
f'(x)>2x-201 with x > 99
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 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 77 | 17 | 60 | 0.770000 | 0.170000 | 0.770000 | 7.700000 | 4.250000 | 10.000000 |
3 | 1.000 | 566 | 128 | 438 | 0.566000 | 0.128000 | 0.566000 | 7.350649 | 7.529412 | 7.300000 |
4 | 10.000 | 6.502 | 927 | 5.575 | 0.650200 | 0.092700 | 0.650200 | 11.487633 | 7.242188 | 12.728311 |
5 | 100.000 | 66.866 | 7.345 | 59.521 | 0.668660 | 0.073450 | 0.668660 | 10.283913 | 7.923409 | 10.676413 |
6 | 1.000.000 | 674.871 | 60.122 | 614.749 | 0.674871 | 0.060122 | 0.674871 | 10.092887 | 8.185432 | 10.328271 |
7 | 10.000.000 | 6.777.310 | 507.331 | 6.269.979 | 0.677731 | 0.050733 | 0.677731 | 10.042378 | 8.438358 | 10.199250 |
8 | 100.000.000 | 67.963.614 | 4.396.610 | 63.567.004 | 0.679636 | 0.043966 | 0.679636 | 10.028111 | 8.666157 | 10.138312 |
9 | 1.000.000.000 | 681.127.500 | 38.808.101 | 642.319.399 | 0.681127 | 0.038808 | 0.681127 | 10.021943 | 8.826823 | 10.104605 |
10 | 10.000.000.000 | 6.823.211.318 | 347.315.590 | 6.475.895.728 | 0.682321 | 0.034732 | 0.682321 | 10.017525 | 8.949564 | 10.082048 |
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 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 2.000000 | 1.333333 |
4 | 16 | 15 | 5 | 10 | 0.937500 | 0.312500 | 0.625000 | 1.875000 | 1.250000 | 2.500000 |
5 | 32 | 28 | 7 | 21 | 0.875000 | 0.218750 | 0.656250 | 1.866667 | 1.400000 | 2.100000 |
6 | 64 | 50 | 12 | 38 | 0.781250 | 0.187500 | 0.593750 | 1.785714 | 1.714286 | 1.809524 |
7 | 128 | 77 | 17 | 60 | 0.601562 | 0.132812 | 0.468750 | 1.540000 | 1.416667 | 1.578947 |
8 | 256 | 105 | 28 | 77 | 0.410156 | 0.109375 | 0.300781 | 1.363636 | 1.647059 | 1.283333 |
9 | 512 | 254 | 66 | 188 | 0.496094 | 0.128906 | 0.367188 | 2.419048 | 2.357143 | 2.441558 |
10 | 1.024 | 578 | 130 | 448 | 0.564453 | 0.126953 | 0.437500 | 2.275591 | 1.969697 | 2.382979 |
11 | 2.048 | 1.242 | 228 | 1.014 | 0.606445 | 0.111328 | 0.495117 | 2.148789 | 1.753846 | 2.263393 |
12 | 4.096 | 2.593 | 420 | 2.173 | 0.633057 | 0.102539 | 0.530518 | 2.087762 | 1.842105 | 2.142998 |
13 | 8.192 | 5.290 | 788 | 4.502 | 0.645752 | 0.096191 | 0.549561 | 2.040108 | 1.876190 | 2.071790 |
14 | 16.384 | 10.741 | 1.470 | 9.271 | 0.655579 | 0.089722 | 0.565857 | 2.030435 | 1.865482 | 2.059307 |
15 | 32.768 | 21.701 | 2.715 | 18.986 | 0.662262 | 0.082855 | 0.579407 | 2.020389 | 1.846939 | 2.047891 |
16 | 65.536 | 43.656 | 5.031 | 38.625 | 0.666138 | 0.076767 | 0.589371 | 2.011704 | 1.853039 | 2.034394 |
17 | 131.072 | 87.798 | 9.356 | 78.442 | 0.669846 | 0.071381 | 0.598465 | 2.011132 | 1.859670 | 2.030861 |
18 | 262.144 | 176.234 | 17.596 | 158.638 | 0.672279 | 0.067123 | 0.605156 | 2.007267 | 1.880718 | 2.022361 |
19 | 524.288 | 353.143 | 33.267 | 319.876 | 0.673567 | 0.063452 | 0.610115 | 2.003830 | 1.890600 | 2.016390 |
20 | 1.048.576 | 707.896 | 62.757 | 645.139 | 0.675102 | 0.059850 | 0.615252 | 2.004559 | 1.886464 | 2.016841 |
21 | 2.097.152 | 1.417.470 | 118.732 | 1.298.738 | 0.675902 | 0.056616 | 0.619287 | 2.002370 | 1.891932 | 2.013113 |
22 | 4.194.304 | 2.839.076 | 225.768 | 2.613.308 | 0.676888 | 0.053827 | 0.623061 | 2.002918 | 1.901492 | 2.012190 |
23 | 8.388.608 | 5.683.776 | 430.583 | 5.253.193 | 0.677559 | 0.051329 | 0.626229 | 2.001981 | 1.907192 | 2.010170 |
24 | 16.777.216 | 11.379.150 | 822.838 | 10.556.312 | 0.678250 | 0.049045 | 0.629205 | 2.002041 | 1.910986 | 2.009504 |
25 | 33.554.432 | 22.777.338 | 1.574.357 | 21.202.981 | 0.678818 | 0.046919 | 0.631898 | 2.001673 | 1.913326 | 2.008559 |
26 | 67.108.864 | 45.591.319 | 3.020.140 | 42.571.179 | 0.679364 | 0.045004 | 0.634360 | 2.001609 | 1.918332 | 2.007792 |
27 | 134.217.728 | 91.250.324 | 5.802.085 | 85.448.239 | 0.679868 | 0.043229 | 0.636639 | 2.001484 | 1.921131 | 2.007185 |
28 | 268.435.456 | 182.621.491 | 11.165.430 | 171.456.061 | 0.680318 | 0.041594 | 0.638724 | 2.001324 | 1.924382 | 2.006549 |
29 | 536.870.912 | 365.480.727 | 21.517.917 | 343.962.810 | 0.680761 | 0.040080 | 0.640681 | 2.001302 | 1.927191 | 2.006128 |
30 | 1.073.741.824 | 731.398.791 | 41.519.335 | 689.879.456 | 0.681168 | 0.038668 | 0.642500 | 2.001197 | 1.929524 | 2.005680 |
31 | 2.147.483.648 | 1.463.620.919 | 80.213.503 | 1.383.407.416 | 0.681552 | 0.037352 | 0.644199 | 2.001126 | 1.931955 | 2.005289 |
32 | 4.294.967.296 | 2.928.802.944 | 155.152.086 | 2.773.650.858 | 0.681915 | 0.036124 | 0.645791 | 2.001067 | 1.934239 | 2.004942 |
33 | 8.589.934.592 | 5.860.478.477 | 300.427.202 | 5.560.051.275 | 0.682249 | 0.034974 | 0.647275 | 2.000981 | 1.936340 | 2.004596 |
34 | 17.179.869.184 | 11.726.418.467 | 582.317.282 | 11.144.101.185 | 0.682567 | 0.033895 | 0.648672 | 2.000932 | 1.938298 | 2.004316 |
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 | 0 | 0 | 1 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 1 | 3 | 1 | 0 | 2 | 1 |
4 | 16 | 5 | 1 | 4 | 2 | 0 | 2 | 1 |
5 | 32 | 7 | 1 | 6 | 3 | 0 | 3 | 1 |
6 | 64 | 12 | 1 | 11 | 7 | 0 | 4 | 1 |
7 | 128 | 17 | 1 | 16 | 9 | 0 | 7 | 1 |
8 | 256 | 28 | 12 | 16 | 9 | 5 | 7 | 7 |
9 | 512 | 66 | 50 | 16 | 9 | 24 | 7 | 26 |
10 | 1.024 | 130 | 114 | 16 | 9 | 56 | 7 | 58 |
11 | 2.048 | 228 | 212 | 16 | 9 | 102 | 7 | 110 |
12 | 4.096 | 420 | 404 | 16 | 9 | 197 | 7 | 207 |
13 | 8.192 | 788 | 772 | 16 | 9 | 378 | 7 | 394 |
14 | 16.384 | 1.470 | 1.454 | 16 | 9 | 718 | 7 | 736 |
15 | 32.768 | 2.715 | 2.699 | 16 | 9 | 1.344 | 7 | 1.355 |
16 | 65.536 | 5.031 | 5.015 | 16 | 9 | 2.507 | 7 | 2.508 |
17 | 131.072 | 9.356 | 9.340 | 16 | 9 | 4.690 | 7 | 4.650 |
18 | 262.144 | 17.596 | 17.580 | 16 | 9 | 8.842 | 7 | 8.738 |
19 | 524.288 | 33.267 | 33.251 | 16 | 9 | 16.644 | 7 | 16.607 |
20 | 1.048.576 | 62.757 | 62.741 | 16 | 9 | 31.435 | 7 | 31.306 |
21 | 2.097.152 | 118.732 | 118.716 | 16 | 9 | 59.398 | 7 | 59.318 |
22 | 4.194.304 | 225.768 | 225.752 | 16 | 9 | 112.970 | 7 | 112.782 |
23 | 8.388.608 | 430.583 | 430.567 | 16 | 9 | 215.290 | 7 | 215.277 |
24 | 16.777.216 | 822.838 | 822.822 | 16 | 9 | 411.229 | 7 | 411.593 |
25 | 33.554.432 | 1.574.357 | 1.574.341 | 16 | 9 | 786.730 | 7 | 787.611 |
26 | 67.108.864 | 3.020.140 | 3.020.124 | 16 | 9 | 1.509.726 | 7 | 1.510.398 |
27 | 134.217.728 | 5.802.085 | 5.802.069 | 16 | 9 | 2.900.833 | 7 | 2.901.236 |
28 | 268.435.456 | 11.165.430 | 11.165.414 | 16 | 9 | 5.581.873 | 7 | 5.583.541 |
29 | 536.870.912 | 21.517.917 | 21.517.901 | 16 | 9 | 10.757.121 | 7 | 10.760.780 |
30 | 1.073.741.824 | 41.519.335 | 41.519.319 | 16 | 9 | 20.758.985 | 7 | 20.760.334 |
31 | 2.147.483.648 | 80.213.503 | 80.213.487 | 16 | 9 | 40.107.080 | 7 | 40.106.407 |
32 | 4.294.967.296 | 155.152.086 | 155.152.070 | 16 | 9 | 77.576.638 | 7 | 77.575.432 |
33 | 8.589.934.592 | 300.427.202 | 300.427.186 | 16 | 9 | 150.211.732 | 7 | 150.215.454 |
34 | 17.179.869.184 | 582.317.282 | 582.317.266 | 16 | 9 | 291.157.276 | 7 | 291.159.990 |
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 | 0 | 0 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
3 | 8 | 4 | 2 | 1 | 0 | 2 | 2 | 0 |
4 | 16 | 10 | 3 | 6 | 2 | 3 | 3 | 2 |
5 | 32 | 21 | 7 | 13 | 4 | 7 | 5 | 5 |
6 | 64 | 38 | 13 | 24 | 8 | 14 | 8 | 8 |
7 | 128 | 60 | 23 | 36 | 13 | 19 | 12 | 16 |
8 | 256 | 77 | 35 | 41 | 20 | 22 | 16 | 19 |
9 | 512 | 188 | 97 | 90 | 47 | 48 | 53 | 40 |
10 | 1.024 | 448 | 245 | 202 | 115 | 103 | 132 | 98 |
11 | 2.048 | 1.014 | 540 | 473 | 273 | 235 | 285 | 221 |
12 | 4.096 | 2.173 | 1.150 | 1.022 | 598 | 483 | 592 | 500 |
13 | 8.192 | 4.502 | 2.361 | 2.140 | 1.246 | 1.010 | 1.219 | 1.027 |
14 | 16.384 | 9.271 | 4.844 | 4.426 | 2.506 | 2.131 | 2.505 | 2.129 |
15 | 32.768 | 18.986 | 9.787 | 9.198 | 5.098 | 4.389 | 5.103 | 4.396 |
16 | 65.536 | 38.625 | 19.948 | 18.676 | 10.209 | 9.060 | 10.330 | 9.026 |
17 | 131.072 | 78.442 | 40.295 | 38.146 | 20.787 | 18.346 | 20.871 | 18.438 |
18 | 262.144 | 158.638 | 81.358 | 77.279 | 41.854 | 37.439 | 41.798 | 37.547 |
19 | 524.288 | 319.876 | 163.678 | 156.197 | 83.987 | 75.764 | 84.347 | 75.778 |
20 | 1.048.576 | 645.139 | 329.891 | 315.247 | 168.875 | 153.531 | 169.181 | 153.552 |
21 | 2.097.152 | 1.298.738 | 663.599 | 635.138 | 339.782 | 309.689 | 339.810 | 309.457 |
22 | 4.194.304 | 2.613.308 | 1.333.327 | 1.279.980 | 681.063 | 625.240 | 682.606 | 624.399 |
23 | 8.388.608 | 5.253.193 | 2.676.616 | 2.576.576 | 1.366.719 | 1.259.084 | 1.369.030 | 1.258.360 |
24 | 16.777.216 | 10.556.312 | 5.373.006 | 5.183.305 | 2.740.793 | 2.535.064 | 2.744.010 | 2.536.445 |
25 | 33.554.432 | 21.202.981 | 10.784.092 | 10.418.888 | 5.496.073 | 5.101.650 | 5.501.164 | 5.104.094 |
26 | 67.108.864 | 42.571.179 | 21.639.651 | 20.931.527 | 11.020.554 | 10.258.002 | 11.026.143 | 10.266.480 |
27 | 134.217.728 | 85.448.239 | 43.405.362 | 42.042.876 | 22.087.410 | 20.627.821 | 22.095.019 | 20.637.989 |
28 | 268.435.456 | 171.456.061 | 87.041.022 | 84.415.038 | 44.258.563 | 41.464.345 | 44.264.477 | 41.468.676 |
29 | 536.870.912 | 343.962.810 | 174.522.964 | 169.439.845 | 88.680.987 | 83.296.569 | 88.680.700 | 83.304.554 |
30 | 1.073.741.824 | 689.879.456 | 349.854.875 | 340.024.580 | 177.656.503 | 167.290.539 | 177.651.237 | 167.281.177 |
31 | 2.147.483.648 | 1.383.407.416 | 701.217.576 | 682.189.839 | 355.859.938 | 335.857.008 | 355.842.688 | 335.847.782 |
32 | 4.294.967.296 | 2.773.650.858 | 1.405.242.929 | 1.368.407.928 | 712.757.472 | 674.076.166 | 712.747.716 | 674.069.504 |
33 | 8.589.934.592 | 5.560.051.275 | 2.815.709.402 | 2.744.341.872 | 1.427.418.332 | 1.352.566.325 | 1.427.468.629 | 1.352.597.989 |
34 | 17.179.869.184 | 11.144.101.185 | 5.641.323.206 | 5.502.777.978 | 2.858.446.250 | 2.713.526.512 | 2.858.575.737 | 2.713.552.686 |