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-41x+17
f(0)=17
f(1)=23
f(2)=61
f(3)=97
f(4)=131
f(5)=163
f(6)=193
f(7)=13
f(8)=19
f(9)=271
f(10)=293
f(11)=313
f(12)=331
f(13)=347
f(14)=1
f(15)=373
f(16)=383
f(17)=1
f(18)=397
f(19)=401
f(20)=31
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)=1
f(40)=1
f(41)=1
f(42)=59
f(43)=103
f(44)=149
f(45)=197
f(46)=1
f(47)=1
f(48)=353
f(49)=409
f(50)=467
f(51)=1
f(52)=1
f(53)=653
f(54)=719
f(55)=787
f(56)=857
f(57)=929
f(58)=1
f(59)=83
f(60)=89
f(61)=1237
f(62)=1319
f(63)=1
f(64)=1489
f(65)=1
f(66)=1667
f(67)=1759
f(68)=109
f(69)=1949
f(70)=1
f(71)=113
f(72)=173
f(73)=181
f(74)=2459
f(75)=151
f(76)=2677
f(77)=2789
f(78)=2903
f(79)=3019
f(80)=3137
f(81)=3257
f(82)=1
f(83)=1
f(84)=191
f(85)=1
f(86)=1
f(87)=4019
f(88)=4153
f(89)=4289
f(90)=233
f(91)=4567
f(92)=277
f(93)=211
f(94)=4999
f(95)=5147
f(96)=5297
f(97)=5449
f(98)=431
f(99)=443
b) Substitution of the polynom
The polynom f(x)=x^2-41x+17 could be written as f(y)= y^2-403.25 with x=y+20.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-20.5
f'(x)>2x-42 with x > 20
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 | 9 | 1 | 1.000000 | 0.900000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 48 | 10 | 0.580000 | 0.480000 | 0.100000 | 5.800000 | 5.333333 | 10.000000 |
3 | 1.000 | 728 | 345 | 383 | 0.728000 | 0.345000 | 0.383000 | 12.551724 | 7.187500 | 38.299999 |
4 | 10.000 | 7.410 | 2.465 | 4.945 | 0.741000 | 0.246500 | 0.494500 | 10.178572 | 7.144928 | 12.911227 |
5 | 100.000 | 73.399 | 19.166 | 54.233 | 0.733990 | 0.191660 | 0.542330 | 9.905398 | 7.775254 | 10.967239 |
6 | 1.000.000 | 727.564 | 156.844 | 570.720 | 0.727564 | 0.156844 | 0.570720 | 9.912451 | 8.183450 | 10.523482 |
7 | 10.000.000 | 7.225.181 | 1.324.978 | 5.900.203 | 0.722518 | 0.132498 | 0.590020 | 9.930647 | 8.447744 | 10.338175 |
8 | 100.000.000 | 71.866.620 | 11.478.470 | 60.388.150 | 0.718666 | 0.114785 | 0.603882 | 9.946689 | 8.663140 | 10.234928 |
9 | 1.000.000.000 | 715.705.060 | 101.283.526 | 614.421.534 | 0.715705 | 0.101284 | 0.614421 | 9.958797 | 8.823783 | 10.174538 |
10 | 10.000.000.000 | 7.133.487.590 | 906.471.669 | 6.227.015.921 | 0.713349 | 0.090647 | 0.622702 | 9.967077 | 8.949843 | 10.134762 |
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 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 15 | 14 | 1 | 0.937500 | 0.875000 | 0.062500 | 1.875000 | 2.000000 | 1.000000 |
5 | 32 | 17 | 16 | 1 | 0.531250 | 0.500000 | 0.031250 | 1.133333 | 1.142857 | 1.000000 |
6 | 64 | 31 | 30 | 1 | 0.484375 | 0.468750 | 0.015625 | 1.823529 | 1.875000 | 1.000000 |
7 | 128 | 82 | 60 | 22 | 0.640625 | 0.468750 | 0.171875 | 2.645161 | 2.000000 | 22.000000 |
8 | 256 | 182 | 108 | 74 | 0.710938 | 0.421875 | 0.289062 | 2.219512 | 1.800000 | 3.363636 |
9 | 512 | 372 | 196 | 176 | 0.726562 | 0.382812 | 0.343750 | 2.043956 | 1.814815 | 2.378378 |
10 | 1.024 | 745 | 352 | 393 | 0.727539 | 0.343750 | 0.383789 | 2.002688 | 1.795918 | 2.232955 |
11 | 2.048 | 1.518 | 637 | 881 | 0.741211 | 0.311035 | 0.430176 | 2.037584 | 1.809659 | 2.241730 |
12 | 4.096 | 3.032 | 1.150 | 1.882 | 0.740234 | 0.280762 | 0.459473 | 1.997365 | 1.805338 | 2.136209 |
13 | 8.192 | 6.066 | 2.077 | 3.989 | 0.740479 | 0.253540 | 0.486938 | 2.000660 | 1.806087 | 2.119554 |
14 | 16.384 | 12.121 | 3.811 | 8.310 | 0.739807 | 0.232605 | 0.507202 | 1.998187 | 1.834858 | 2.083229 |
15 | 32.768 | 24.186 | 7.027 | 17.159 | 0.738098 | 0.214447 | 0.523651 | 1.995380 | 1.843873 | 2.064862 |
16 | 65.536 | 48.185 | 13.096 | 35.089 | 0.735245 | 0.199829 | 0.535416 | 1.992268 | 1.863669 | 2.044933 |
17 | 131.072 | 96.122 | 24.512 | 71.610 | 0.733353 | 0.187012 | 0.546341 | 1.994853 | 1.871716 | 2.040811 |
18 | 262.144 | 191.589 | 45.985 | 145.604 | 0.730854 | 0.175419 | 0.555435 | 1.993186 | 1.876020 | 2.033291 |
19 | 524.288 | 382.262 | 86.489 | 295.773 | 0.729107 | 0.164965 | 0.564142 | 1.995219 | 1.880809 | 2.031352 |
20 | 1.048.576 | 762.792 | 163.837 | 598.955 | 0.727455 | 0.156247 | 0.571208 | 1.995469 | 1.894310 | 2.025050 |
21 | 2.097.152 | 1.522.084 | 310.410 | 1.211.674 | 0.725786 | 0.148015 | 0.577771 | 1.995412 | 1.894627 | 2.022980 |
22 | 4.194.304 | 3.038.012 | 589.860 | 2.448.152 | 0.724319 | 0.140634 | 0.583685 | 1.995956 | 1.900261 | 2.020471 |
23 | 8.388.608 | 6.063.613 | 1.124.554 | 4.939.059 | 0.722839 | 0.134057 | 0.588782 | 1.995915 | 1.906476 | 2.017464 |
24 | 16.777.216 | 12.106.114 | 2.147.188 | 9.958.926 | 0.721581 | 0.127982 | 0.593598 | 1.996518 | 1.909369 | 2.016361 |
25 | 33.554.432 | 24.172.436 | 4.111.176 | 20.061.260 | 0.720395 | 0.122523 | 0.597872 | 1.996713 | 1.914679 | 2.014400 |
26 | 67.108.864 | 48.269.103 | 7.886.281 | 40.382.822 | 0.719266 | 0.117515 | 0.601751 | 1.996866 | 1.918254 | 2.012975 |
27 | 134.217.728 | 96.401.679 | 15.147.998 | 81.253.681 | 0.718248 | 0.112861 | 0.605387 | 1.997172 | 1.920804 | 2.012085 |
28 | 268.435.456 | 192.551.019 | 29.146.307 | 163.404.712 | 0.717308 | 0.108578 | 0.608730 | 1.997382 | 1.924103 | 2.011044 |
29 | 536.870.912 | 384.628.771 | 56.159.964 | 328.468.807 | 0.716427 | 0.104606 | 0.611821 | 1.997542 | 1.926829 | 2.010155 |
30 | 1.073.741.824 | 768.391.392 | 108.360.554 | 660.030.838 | 0.715620 | 0.100919 | 0.614702 | 1.997748 | 1.929498 | 2.009417 |
31 | 2.147.483.648 | 1.535.149.730 | 209.352.470 | 1.325.797.260 | 0.714860 | 0.097487 | 0.617372 | 1.997875 | 1.931999 | 2.008690 |
32 | 4.294.967.296 | 3.067.265.353 | 404.929.274 | 2.662.336.079 | 0.714153 | 0.094280 | 0.619873 | 1.998024 | 1.934199 | 2.008102 |
33 | 8.589.934.592 | 6.128.818.473 | 784.089.273 | 5.344.729.200 | 0.713488 | 0.091280 | 0.622208 | 1.998138 | 1.936361 | 2.007534 |
34 | 17.179.869.184 | 12.246.910.682 | 1.519.796.148 | 10.727.114.534 | 0.712864 | 0.088464 | 0.624400 | 1.998250 | 1.938295 | 2.007046 |
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 | 2 | 1 | 0 | 1 | 1 |
2 | 4 | 5 | 2 | 3 | 2 | 1 | 1 | 1 |
3 | 8 | 7 | 4 | 3 | 3 | 2 | 1 | 1 |
4 | 16 | 14 | 8 | 6 | 4 | 4 | 3 | 3 |
5 | 32 | 16 | 9 | 7 | 5 | 4 | 4 | 3 |
6 | 64 | 30 | 14 | 16 | 10 | 6 | 8 | 6 |
7 | 128 | 60 | 26 | 34 | 20 | 13 | 12 | 15 |
8 | 256 | 108 | 40 | 68 | 29 | 23 | 29 | 27 |
9 | 512 | 196 | 70 | 126 | 50 | 47 | 52 | 47 |
10 | 1.024 | 352 | 122 | 230 | 87 | 86 | 88 | 91 |
11 | 2.048 | 637 | 208 | 429 | 158 | 163 | 160 | 156 |
12 | 4.096 | 1.150 | 392 | 758 | 298 | 294 | 283 | 275 |
13 | 8.192 | 2.077 | 696 | 1.381 | 532 | 507 | 529 | 509 |
14 | 16.384 | 3.811 | 1.259 | 2.552 | 976 | 932 | 963 | 940 |
15 | 32.768 | 7.027 | 2.344 | 4.683 | 1.749 | 1.750 | 1.781 | 1.747 |
16 | 65.536 | 13.096 | 4.348 | 8.748 | 3.281 | 3.218 | 3.293 | 3.304 |
17 | 131.072 | 24.512 | 8.175 | 16.337 | 6.178 | 6.085 | 6.077 | 6.172 |
18 | 262.144 | 45.985 | 15.396 | 30.589 | 11.564 | 11.444 | 11.429 | 11.548 |
19 | 524.288 | 86.489 | 28.778 | 57.711 | 21.736 | 21.677 | 21.420 | 21.656 |
20 | 1.048.576 | 163.837 | 54.324 | 109.513 | 41.083 | 40.979 | 40.741 | 41.034 |
21 | 2.097.152 | 310.410 | 103.098 | 207.312 | 77.406 | 77.700 | 77.431 | 77.873 |
22 | 4.194.304 | 589.860 | 196.338 | 393.522 | 147.298 | 147.489 | 147.423 | 147.650 |
23 | 8.388.608 | 1.124.554 | 374.311 | 750.243 | 281.254 | 280.826 | 281.444 | 281.030 |
24 | 16.777.216 | 2.147.188 | 714.964 | 1.432.224 | 537.031 | 536.586 | 536.741 | 536.830 |
25 | 33.554.432 | 4.111.176 | 1.369.479 | 2.741.697 | 1.028.022 | 1.027.621 | 1.027.546 | 1.027.987 |
26 | 67.108.864 | 7.886.281 | 2.628.003 | 5.258.278 | 1.972.750 | 1.970.836 | 1.970.952 | 1.971.743 |
27 | 134.217.728 | 15.147.998 | 5.047.980 | 10.100.018 | 3.787.251 | 3.786.467 | 3.786.494 | 3.787.786 |
28 | 268.435.456 | 29.146.307 | 9.714.376 | 19.431.931 | 7.287.993 | 7.286.538 | 7.283.670 | 7.288.106 |
29 | 536.870.912 | 56.159.964 | 18.720.979 | 37.438.985 | 14.043.160 | 14.040.133 | 14.036.840 | 14.039.831 |
30 | 1.073.741.824 | 108.360.554 | 36.121.927 | 72.238.627 | 27.094.569 | 27.089.073 | 27.087.603 | 27.089.309 |
31 | 2.147.483.648 | 209.352.470 | 69.790.869 | 139.561.601 | 52.345.706 | 52.335.108 | 52.336.155 | 52.335.501 |
32 | 4.294.967.296 | 404.929.274 | 134.985.836 | 269.943.438 | 101.233.617 | 101.232.122 | 101.232.495 | 101.231.040 |
33 | 8.589.934.592 | 784.089.273 | 261.377.970 | 522.711.303 | 196.018.476 | 196.018.288 | 196.027.151 | 196.025.358 |
34 | 17.179.869.184 | 1.519.796.148 | 506.614.011 | 1.013.182.137 | 379.943.744 | 379.946.740 | 379.953.956 | 379.951.708 |
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 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 32 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
6 | 64 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
7 | 128 | 22 | 11 | 11 | 4 | 6 | 5 | 7 |
8 | 256 | 74 | 35 | 39 | 14 | 19 | 20 | 21 |
9 | 512 | 176 | 83 | 93 | 43 | 44 | 42 | 47 |
10 | 1.024 | 393 | 187 | 206 | 92 | 102 | 99 | 100 |
11 | 2.048 | 881 | 417 | 464 | 207 | 234 | 219 | 221 |
12 | 4.096 | 1.882 | 921 | 961 | 453 | 486 | 475 | 468 |
13 | 8.192 | 3.989 | 1.975 | 2.014 | 967 | 1.010 | 1.010 | 1.002 |
14 | 16.384 | 8.310 | 4.092 | 4.218 | 2.042 | 2.083 | 2.089 | 2.096 |
15 | 32.768 | 17.159 | 8.531 | 8.628 | 4.218 | 4.327 | 4.317 | 4.297 |
16 | 65.536 | 35.089 | 17.334 | 17.755 | 8.610 | 8.763 | 8.884 | 8.832 |
17 | 131.072 | 71.610 | 35.388 | 36.222 | 17.634 | 17.939 | 18.021 | 18.016 |
18 | 262.144 | 145.604 | 71.941 | 73.663 | 36.175 | 36.314 | 36.682 | 36.433 |
19 | 524.288 | 295.773 | 146.430 | 149.343 | 73.897 | 73.809 | 73.884 | 74.183 |
20 | 1.048.576 | 598.955 | 296.732 | 302.223 | 149.392 | 149.663 | 149.853 | 150.047 |
21 | 2.097.152 | 1.211.674 | 600.936 | 610.738 | 302.382 | 303.142 | 302.815 | 303.335 |
22 | 4.194.304 | 2.448.152 | 1.214.523 | 1.233.629 | 611.395 | 612.167 | 612.414 | 612.176 |
23 | 8.388.608 | 4.939.059 | 2.451.886 | 2.487.173 | 1.234.734 | 1.235.538 | 1.234.060 | 1.234.727 |
24 | 16.777.216 | 9.958.926 | 4.945.711 | 5.013.215 | 2.488.789 | 2.488.920 | 2.489.784 | 2.491.433 |
25 | 33.554.432 | 20.061.260 | 9.967.091 | 10.094.169 | 5.014.368 | 5.014.477 | 5.015.467 | 5.016.948 |
26 | 67.108.864 | 40.382.822 | 20.070.179 | 20.312.643 | 10.095.112 | 10.093.035 | 10.096.575 | 10.098.100 |
27 | 134.217.728 | 81.253.681 | 40.390.351 | 40.863.330 | 20.312.033 | 20.314.216 | 20.314.195 | 20.313.237 |
28 | 268.435.456 | 163.404.712 | 81.244.360 | 82.160.352 | 40.848.595 | 40.851.269 | 40.854.217 | 40.850.631 |
29 | 536.870.912 | 328.468.807 | 163.356.479 | 165.112.328 | 82.109.661 | 82.116.621 | 82.119.531 | 82.122.994 |
30 | 1.073.741.824 | 660.030.838 | 328.328.634 | 331.702.204 | 165.006.655 | 165.002.220 | 165.007.297 | 165.014.666 |
31 | 2.147.483.648 | 1.325.797.260 | 659.642.437 | 666.154.823 | 331.459.678 | 331.438.119 | 331.453.594 | 331.445.869 |
32 | 4.294.967.296 | 2.662.336.079 | 1.324.891.048 | 1.337.445.031 | 665.591.152 | 665.584.416 | 665.586.324 | 665.574.187 |
33 | 8.589.934.592 | 5.344.729.200 | 2.660.176.467 | 2.684.552.733 | 1.336.191.936 | 1.336.219.626 | 1.336.165.276 | 1.336.152.362 |
34 | 17.179.869.184 | 10.727.114.534 | 5.339.923.829 | 5.387.190.705 | 2.681.776.737 | 2.681.797.755 | 2.681.757.831 | 2.681.782.211 |