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-29x+7
f(0)=7
f(1)=3
f(2)=47
f(3)=71
f(4)=31
f(5)=113
f(6)=131
f(7)=1
f(8)=23
f(9)=173
f(10)=61
f(11)=191
f(12)=197
f(13)=67
f(14)=29
f(15)=1
f(16)=1
f(17)=1
f(18)=1
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)=37
f(31)=1
f(32)=103
f(33)=139
f(34)=59
f(35)=1
f(36)=1
f(37)=101
f(38)=349
f(39)=397
f(40)=149
f(41)=499
f(42)=79
f(43)=1
f(44)=1
f(45)=727
f(46)=263
f(47)=853
f(48)=919
f(49)=1
f(50)=151
f(51)=1129
f(52)=401
f(53)=1279
f(54)=1
f(55)=479
f(56)=1
f(57)=229
f(58)=563
f(59)=1777
f(60)=1867
f(61)=653
f(62)=2053
f(63)=307
f(64)=107
f(65)=2347
f(66)=1
f(67)=1
f(68)=2659
f(69)=2767
f(70)=137
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=3457
f(76)=1193
f(77)=1
f(78)=547
f(79)=1319
f(80)=1
f(81)=4219
f(82)=1451
f(83)=1
f(84)=661
f(85)=227
f(86)=4909
f(87)=163
f(88)=1733
f(89)=5347
f(90)=239
f(91)=269
f(92)=829
f(93)=1
f(94)=2039
f(95)=6277
f(96)=1
f(97)=1
f(98)=967
f(99)=991
b) Substitution of the polynom
The polynom f(x)=x^2-29x+7 could be written as f(y)= y^2-203.25 with x=y+14.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-14.5
f'(x)>2x-30 with x > 14
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 | 7 | 3 | 1.000000 | 0.700000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 30 | 28 | 0.580000 | 0.300000 | 0.580000 | 5.800000 | 4.285714 | 9.333333 |
3 | 1.000 | 701 | 197 | 504 | 0.701000 | 0.197000 | 0.701000 | 12.086206 | 6.566667 | 18.000000 |
4 | 10.000 | 7.118 | 1.453 | 5.665 | 0.711800 | 0.145300 | 0.711800 | 10.154066 | 7.375635 | 11.240079 |
5 | 100.000 | 71.123 | 11.156 | 59.967 | 0.711230 | 0.111560 | 0.711230 | 9.991992 | 7.677908 | 10.585526 |
6 | 1.000.000 | 707.632 | 91.766 | 615.866 | 0.707632 | 0.091766 | 0.707632 | 9.949411 | 8.225708 | 10.270082 |
7 | 10.000.000 | 7.052.506 | 776.355 | 6.276.151 | 0.705251 | 0.077635 | 0.705251 | 9.966347 | 8.460159 | 10.190774 |
8 | 100.000.000 | 70.362.546 | 6.724.304 | 63.638.242 | 0.703625 | 0.067243 | 0.703625 | 9.976956 | 8.661378 | 10.139692 |
9 | 1.000.000.000 | 702.338.548 | 59.337.300 | 643.001.248 | 0.702339 | 0.059337 | 0.702339 | 9.981710 | 8.824304 | 10.104007 |
10 | 10.000.000.000 | 7.013.279.380 | 531.037.715 | 6.482.241.665 | 0.701328 | 0.053104 | 0.701328 | 9.985610 | 8.949475 | 10.081227 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 1.600000 | 1.500000 | 2.000000 |
4 | 16 | 14 | 9 | 5 | 0.875000 | 0.562500 | 0.312500 | 1.750000 | 1.500000 | 2.500000 |
5 | 32 | 15 | 10 | 5 | 0.468750 | 0.312500 | 0.156250 | 1.071429 | 1.111111 | 1.000000 |
6 | 64 | 37 | 22 | 15 | 0.578125 | 0.343750 | 0.234375 | 2.466667 | 2.200000 | 3.000000 |
7 | 128 | 81 | 38 | 43 | 0.632812 | 0.296875 | 0.335938 | 2.189189 | 1.727273 | 2.866667 |
8 | 256 | 166 | 70 | 96 | 0.648438 | 0.273438 | 0.375000 | 2.049383 | 1.842105 | 2.232558 |
9 | 512 | 347 | 114 | 233 | 0.677734 | 0.222656 | 0.455078 | 2.090361 | 1.628571 | 2.427083 |
10 | 1.024 | 718 | 202 | 516 | 0.701172 | 0.197266 | 0.503906 | 2.069164 | 1.771930 | 2.214592 |
11 | 2.048 | 1.439 | 378 | 1.061 | 0.702637 | 0.184570 | 0.518066 | 2.004178 | 1.871287 | 2.056201 |
12 | 4.096 | 2.894 | 680 | 2.214 | 0.706543 | 0.166016 | 0.540527 | 2.011119 | 1.798942 | 2.086711 |
13 | 8.192 | 5.807 | 1.224 | 4.583 | 0.708862 | 0.149414 | 0.559448 | 2.006565 | 1.800000 | 2.070009 |
14 | 16.384 | 11.639 | 2.249 | 9.390 | 0.710388 | 0.137268 | 0.573120 | 2.004305 | 1.837418 | 2.048876 |
15 | 32.768 | 23.301 | 4.125 | 19.176 | 0.711090 | 0.125885 | 0.585205 | 2.001976 | 1.834149 | 2.042172 |
16 | 65.536 | 46.647 | 7.600 | 39.047 | 0.711777 | 0.115967 | 0.595810 | 2.001931 | 1.842424 | 2.036243 |
17 | 131.072 | 93.148 | 14.244 | 78.904 | 0.710663 | 0.108673 | 0.601990 | 1.996870 | 1.874210 | 2.020744 |
18 | 262.144 | 186.032 | 26.779 | 159.253 | 0.709656 | 0.102154 | 0.607502 | 1.997166 | 1.880020 | 2.018313 |
19 | 524.288 | 371.429 | 50.706 | 320.723 | 0.708445 | 0.096714 | 0.611731 | 1.996587 | 1.893499 | 2.013921 |
20 | 1.048.576 | 741.997 | 95.845 | 646.152 | 0.707623 | 0.091405 | 0.616219 | 1.997682 | 1.890210 | 2.014673 |
21 | 2.097.152 | 1.482.083 | 181.831 | 1.300.252 | 0.706712 | 0.086704 | 0.620008 | 1.997424 | 1.897136 | 2.012300 |
22 | 4.194.304 | 2.961.541 | 345.527 | 2.616.014 | 0.706086 | 0.082380 | 0.623706 | 1.998229 | 1.900265 | 2.011929 |
23 | 8.388.608 | 5.917.418 | 659.027 | 5.258.391 | 0.705411 | 0.078562 | 0.626849 | 1.998088 | 1.907310 | 2.010077 |
24 | 16.777.216 | 11.825.561 | 1.258.364 | 10.567.197 | 0.704858 | 0.075004 | 0.629854 | 1.998433 | 1.909427 | 2.009588 |
25 | 33.554.432 | 23.634.486 | 2.409.302 | 21.225.184 | 0.704363 | 0.071803 | 0.632560 | 1.998593 | 1.914630 | 2.008592 |
26 | 67.108.864 | 47.236.301 | 4.619.244 | 42.617.057 | 0.703876 | 0.068832 | 0.635044 | 1.998618 | 1.917254 | 2.007853 |
27 | 134.217.728 | 94.412.963 | 8.873.642 | 85.539.321 | 0.703431 | 0.066114 | 0.637318 | 1.998737 | 1.921016 | 2.007162 |
28 | 268.435.456 | 188.719.011 | 17.074.433 | 171.644.578 | 0.703033 | 0.063607 | 0.639426 | 1.998868 | 1.924174 | 2.006616 |
29 | 536.870.912 | 377.236.120 | 32.904.496 | 344.331.624 | 0.702657 | 0.061289 | 0.641368 | 1.998930 | 1.927121 | 2.006073 |
30 | 1.073.741.824 | 754.092.394 | 63.482.680 | 690.609.714 | 0.702303 | 0.059123 | 0.643180 | 1.998993 | 1.929301 | 2.005653 |
31 | 2.147.483.648 | 1.507.484.110 | 122.645.753 | 1.384.838.357 | 0.701977 | 0.057111 | 0.644866 | 1.999071 | 1.931956 | 2.005240 |
32 | 4.294.967.296 | 3.013.666.521 | 237.220.143 | 2.776.446.378 | 0.701674 | 0.055232 | 0.646442 | 1.999136 | 1.934190 | 2.004888 |
33 | 8.589.934.592 | 6.024.879.220 | 459.345.937 | 5.565.533.283 | 0.701388 | 0.053475 | 0.647913 | 1.999186 | 1.936370 | 2.004553 |
34 | 17.179.869.184 | 12.045.181.729 | 890.352.722 | 11.154.829.007 | 0.701122 | 0.051825 | 0.649297 | 1.999240 | 1.938305 | 2.004270 |
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 | 1 | 0 | 0 | 1 | 2 |
2 | 4 | 4 | 1 | 2 | 0 | 0 | 1 | 3 |
3 | 8 | 6 | 1 | 4 | 1 | 1 | 1 | 3 |
4 | 16 | 9 | 1 | 7 | 1 | 1 | 3 | 4 |
5 | 32 | 10 | 2 | 7 | 1 | 1 | 3 | 5 |
6 | 64 | 22 | 14 | 7 | 3 | 4 | 7 | 8 |
7 | 128 | 38 | 30 | 7 | 7 | 10 | 10 | 11 |
8 | 256 | 70 | 62 | 7 | 14 | 19 | 20 | 17 |
9 | 512 | 114 | 106 | 7 | 24 | 28 | 32 | 30 |
10 | 1.024 | 202 | 194 | 7 | 48 | 49 | 55 | 50 |
11 | 2.048 | 378 | 370 | 7 | 97 | 94 | 94 | 93 |
12 | 4.096 | 680 | 672 | 7 | 171 | 167 | 177 | 165 |
13 | 8.192 | 1.224 | 1.216 | 7 | 305 | 301 | 306 | 312 |
14 | 16.384 | 2.249 | 2.241 | 7 | 551 | 558 | 563 | 577 |
15 | 32.768 | 4.125 | 4.117 | 7 | 995 | 1.047 | 1.036 | 1.047 |
16 | 65.536 | 7.600 | 7.592 | 7 | 1.865 | 1.916 | 1.888 | 1.931 |
17 | 131.072 | 14.244 | 14.236 | 7 | 3.527 | 3.565 | 3.553 | 3.599 |
18 | 262.144 | 26.779 | 26.771 | 7 | 6.669 | 6.748 | 6.636 | 6.726 |
19 | 524.288 | 50.706 | 50.698 | 7 | 12.630 | 12.701 | 12.642 | 12.733 |
20 | 1.048.576 | 95.845 | 95.837 | 7 | 23.884 | 24.058 | 23.833 | 24.070 |
21 | 2.097.152 | 181.831 | 181.823 | 7 | 45.388 | 45.693 | 45.270 | 45.480 |
22 | 4.194.304 | 345.527 | 345.519 | 7 | 86.118 | 86.806 | 86.289 | 86.314 |
23 | 8.388.608 | 659.027 | 659.019 | 7 | 164.606 | 165.324 | 164.528 | 164.569 |
24 | 16.777.216 | 1.258.364 | 1.258.356 | 7 | 314.433 | 314.873 | 314.477 | 314.581 |
25 | 33.554.432 | 2.409.302 | 2.409.294 | 7 | 602.699 | 602.362 | 601.575 | 602.666 |
26 | 67.108.864 | 4.619.244 | 4.619.236 | 7 | 1.155.449 | 1.154.693 | 1.154.352 | 1.154.750 |
27 | 134.217.728 | 8.873.642 | 8.873.634 | 7 | 2.218.339 | 2.217.418 | 2.217.971 | 2.219.914 |
28 | 268.435.456 | 17.074.433 | 17.074.425 | 7 | 4.268.191 | 4.267.325 | 4.269.589 | 4.269.328 |
29 | 536.870.912 | 32.904.496 | 32.904.488 | 7 | 8.227.164 | 8.223.870 | 8.228.270 | 8.225.192 |
30 | 1.073.741.824 | 63.482.680 | 63.482.672 | 7 | 15.873.739 | 15.868.866 | 15.870.413 | 15.869.662 |
31 | 2.147.483.648 | 122.645.753 | 122.645.745 | 7 | 30.662.120 | 30.659.148 | 30.662.915 | 30.661.570 |
32 | 4.294.967.296 | 237.220.143 | 237.220.135 | 7 | 59.302.319 | 59.306.627 | 59.301.286 | 59.309.911 |
33 | 8.589.934.592 | 459.345.937 | 459.345.929 | 7 | 114.831.488 | 114.842.519 | 114.830.991 | 114.840.939 |
34 | 17.179.869.184 | 890.352.722 | 890.352.714 | 7 | 222.586.313 | 222.594.272 | 222.585.302 | 222.586.835 |
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 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 0 | 2 |
4 | 16 | 5 | 3 | 2 | 0 | 1 | 2 | 2 |
5 | 32 | 5 | 3 | 2 | 0 | 1 | 2 | 2 |
6 | 64 | 15 | 6 | 9 | 1 | 3 | 6 | 5 |
7 | 128 | 43 | 16 | 27 | 7 | 12 | 12 | 12 |
8 | 256 | 96 | 35 | 61 | 20 | 25 | 25 | 26 |
9 | 512 | 233 | 97 | 136 | 49 | 57 | 66 | 61 |
10 | 1.024 | 516 | 223 | 293 | 121 | 131 | 138 | 126 |
11 | 2.048 | 1.061 | 459 | 602 | 268 | 276 | 263 | 254 |
12 | 4.096 | 2.214 | 950 | 1.264 | 559 | 547 | 570 | 538 |
13 | 8.192 | 4.583 | 2.018 | 2.565 | 1.147 | 1.148 | 1.171 | 1.117 |
14 | 16.384 | 9.390 | 4.226 | 5.164 | 2.354 | 2.383 | 2.375 | 2.278 |
15 | 32.768 | 19.176 | 8.702 | 10.474 | 4.817 | 4.805 | 4.842 | 4.712 |
16 | 65.536 | 39.047 | 17.880 | 21.167 | 9.803 | 9.766 | 9.778 | 9.700 |
17 | 131.072 | 78.904 | 36.304 | 42.600 | 19.825 | 19.734 | 19.645 | 19.700 |
18 | 262.144 | 159.253 | 73.736 | 85.517 | 39.808 | 39.958 | 39.744 | 39.743 |
19 | 524.288 | 320.723 | 149.253 | 171.470 | 80.226 | 80.215 | 80.199 | 80.083 |
20 | 1.048.576 | 646.152 | 302.305 | 343.847 | 161.639 | 161.546 | 161.638 | 161.329 |
21 | 2.097.152 | 1.300.252 | 611.367 | 688.885 | 324.847 | 325.130 | 325.106 | 325.169 |
22 | 4.194.304 | 2.616.014 | 1.235.814 | 1.380.200 | 653.523 | 653.344 | 654.003 | 655.144 |
23 | 8.388.608 | 5.258.391 | 2.491.577 | 2.766.814 | 1.313.609 | 1.314.841 | 1.314.505 | 1.315.436 |
24 | 16.777.216 | 10.567.197 | 5.020.485 | 5.546.712 | 2.640.899 | 2.642.651 | 2.641.049 | 2.642.598 |
25 | 33.554.432 | 21.225.184 | 10.110.125 | 11.115.059 | 5.308.191 | 5.305.823 | 5.304.017 | 5.307.153 |
26 | 67.108.864 | 42.617.057 | 20.347.711 | 22.269.346 | 10.655.759 | 10.656.451 | 10.651.420 | 10.653.427 |
27 | 134.217.728 | 85.539.321 | 40.926.126 | 44.613.195 | 21.383.834 | 21.387.950 | 21.383.253 | 21.384.284 |
28 | 268.435.456 | 171.644.578 | 82.283.066 | 89.361.512 | 42.907.769 | 42.917.285 | 42.906.625 | 42.912.899 |
29 | 536.870.912 | 344.331.624 | 165.353.263 | 178.978.361 | 86.074.368 | 86.089.419 | 86.077.467 | 86.090.370 |
30 | 1.073.741.824 | 690.609.714 | 332.199.570 | 358.410.144 | 172.629.586 | 172.675.521 | 172.645.458 | 172.659.149 |
31 | 2.147.483.648 | 1.384.838.357 | 667.157.836 | 717.680.521 | 346.180.524 | 346.231.168 | 346.214.263 | 346.212.402 |
32 | 4.294.967.296 | 2.776.446.378 | 1.339.403.427 | 1.437.042.951 | 694.078.134 | 694.146.167 | 694.120.267 | 694.101.810 |
33 | 8.589.934.592 | 5.565.533.283 | 2.688.369.387 | 2.877.163.896 | 1.391.332.468 | 1.391.426.594 | 1.391.388.177 | 1.391.386.044 |
34 | 17.179.869.184 | 11.154.829.007 | 5.394.703.156 | 5.760.125.851 | 2.788.658.650 | 2.788.730.032 | 2.788.776.904 | 2.788.663.421 |