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-59
f(0)=59
f(1)=29
f(2)=3
f(3)=37
f(4)=73
f(5)=1
f(6)=151
f(7)=193
f(8)=79
f(9)=283
f(10)=331
f(11)=127
f(12)=433
f(13)=487
f(14)=181
f(15)=601
f(16)=661
f(17)=241
f(18)=787
f(19)=853
f(20)=307
f(21)=991
f(22)=1063
f(23)=379
f(24)=1213
f(25)=1291
f(26)=457
f(27)=1453
f(28)=53
f(29)=541
f(30)=1
f(31)=1801
f(32)=631
f(33)=1987
f(34)=2083
f(35)=727
f(36)=2281
f(37)=2383
f(38)=829
f(39)=2593
f(40)=1
f(41)=937
f(42)=1
f(43)=3037
f(44)=1051
f(45)=3271
f(46)=3391
f(47)=1171
f(48)=3637
f(49)=71
f(50)=1297
f(51)=4021
f(52)=4153
f(53)=1429
f(54)=4423
f(55)=4561
f(56)=1567
f(57)=167
f(58)=4987
f(59)=1
f(60)=5281
f(61)=5431
f(62)=1861
f(63)=5737
f(64)=83
f(65)=2017
f(66)=6211
f(67)=6373
f(68)=2179
f(69)=6703
f(70)=6871
f(71)=2347
f(72)=7213
f(73)=89
f(74)=2521
f(75)=7741
f(76)=1
f(77)=1
f(78)=8287
f(79)=229
f(80)=2887
f(81)=1
f(82)=9043
f(83)=3079
f(84)=9433
f(85)=9631
f(86)=113
f(87)=1
f(88)=353
f(89)=1
f(90)=10651
f(91)=10861
f(92)=3691
f(93)=11287
f(94)=11503
f(95)=3907
f(96)=11941
f(97)=12163
f(98)=4129
f(99)=12613
b) Substitution of the polynom
The polynom f(x)=x^2+29x-59 could be written as f(y)= y^2-269.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+28
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 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 86 | 56 | 30 | 0.860000 | 0.560000 | 0.860000 | 8.600000 | 6.222222 | 30.000000 |
3 | 1.000 | 828 | 350 | 478 | 0.828000 | 0.350000 | 0.828000 | 9.627907 | 6.250000 | 15.933333 |
4 | 10.000 | 7.929 | 2.513 | 5.416 | 0.792900 | 0.251300 | 0.792900 | 9.576087 | 7.180000 | 11.330544 |
5 | 100.000 | 77.028 | 19.546 | 57.482 | 0.770280 | 0.195460 | 0.770280 | 9.714718 | 7.777955 | 10.613368 |
6 | 1.000.000 | 756.893 | 158.653 | 598.240 | 0.756893 | 0.158653 | 0.756893 | 9.826206 | 8.116903 | 10.407432 |
7 | 10.000.000 | 7.472.368 | 1.343.861 | 6.128.507 | 0.747237 | 0.134386 | 0.747237 | 9.872423 | 8.470442 | 10.244228 |
8 | 100.000.000 | 74.028.151 | 11.640.186 | 62.387.965 | 0.740282 | 0.116402 | 0.740282 | 9.906920 | 8.661749 | 10.179961 |
9 | 1.000.000.000 | 734.857.894 | 102.718.009 | 632.139.885 | 0.734858 | 0.102718 | 0.734858 | 9.926736 | 8.824430 | 10.132401 |
10 | 10.000.000.000 | 7.305.543.607 | 919.169.530 | 6.386.374.077 | 0.730554 | 0.091917 | 0.730554 | 9.941437 | 8.948475 | 10.102786 |
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 | 16 | 13 | 3 | 1.000000 | 0.812500 | 0.187500 | 2.000000 | 1.857143 | 3.000000 |
5 | 32 | 30 | 21 | 9 | 0.937500 | 0.656250 | 0.281250 | 1.875000 | 1.615385 | 3.000000 |
6 | 64 | 57 | 38 | 19 | 0.890625 | 0.593750 | 0.296875 | 1.900000 | 1.809524 | 2.111111 |
7 | 128 | 109 | 66 | 43 | 0.851562 | 0.515625 | 0.335938 | 1.912281 | 1.736842 | 2.263158 |
8 | 256 | 211 | 120 | 91 | 0.824219 | 0.468750 | 0.355469 | 1.935780 | 1.818182 | 2.116279 |
9 | 512 | 430 | 207 | 223 | 0.839844 | 0.404297 | 0.435547 | 2.037915 | 1.725000 | 2.450549 |
10 | 1.024 | 846 | 358 | 488 | 0.826172 | 0.349609 | 0.476562 | 1.967442 | 1.729469 | 2.188341 |
11 | 2.048 | 1.666 | 638 | 1.028 | 0.813477 | 0.311523 | 0.501953 | 1.969267 | 1.782123 | 2.106557 |
12 | 4.096 | 3.285 | 1.168 | 2.117 | 0.802002 | 0.285156 | 0.516846 | 1.971789 | 1.830721 | 2.059339 |
13 | 8.192 | 6.511 | 2.098 | 4.413 | 0.794800 | 0.256104 | 0.538696 | 1.982040 | 1.796233 | 2.084554 |
14 | 16.384 | 12.914 | 3.883 | 9.031 | 0.788208 | 0.237000 | 0.551208 | 1.983413 | 1.850810 | 2.046454 |
15 | 32.768 | 25.570 | 7.179 | 18.391 | 0.780334 | 0.219086 | 0.561249 | 1.980022 | 1.848828 | 2.036430 |
16 | 65.536 | 50.614 | 13.365 | 37.249 | 0.772308 | 0.203934 | 0.568375 | 1.979429 | 1.861680 | 2.025393 |
17 | 131.072 | 100.703 | 24.859 | 75.844 | 0.768303 | 0.189659 | 0.578644 | 1.989627 | 1.860008 | 2.036135 |
18 | 262.144 | 200.219 | 46.696 | 153.523 | 0.763775 | 0.178131 | 0.585644 | 1.988213 | 1.878434 | 2.024194 |
19 | 524.288 | 398.477 | 87.618 | 310.859 | 0.760035 | 0.167118 | 0.592916 | 1.990206 | 1.876349 | 2.024837 |
20 | 1.048.576 | 793.452 | 165.736 | 627.716 | 0.756695 | 0.158058 | 0.598637 | 1.991212 | 1.891575 | 2.019295 |
21 | 2.097.152 | 1.580.255 | 314.406 | 1.265.849 | 0.753524 | 0.149920 | 0.603604 | 1.991620 | 1.897029 | 2.016595 |
22 | 4.194.304 | 3.147.739 | 598.394 | 2.549.345 | 0.750479 | 0.142668 | 0.607811 | 1.991918 | 1.903252 | 2.013941 |
23 | 8.388.608 | 6.273.591 | 1.140.401 | 5.133.190 | 0.747870 | 0.135946 | 0.611924 | 1.993047 | 1.905769 | 2.013533 |
24 | 16.777.216 | 12.507.296 | 2.178.191 | 10.329.105 | 0.745493 | 0.129830 | 0.615663 | 1.993642 | 1.910022 | 2.012219 |
25 | 33.554.432 | 24.943.741 | 4.168.780 | 20.774.961 | 0.743381 | 0.124239 | 0.619142 | 1.994335 | 1.913873 | 2.011303 |
26 | 67.108.864 | 49.753.753 | 7.994.296 | 41.759.457 | 0.741389 | 0.119124 | 0.622264 | 1.994639 | 1.917658 | 2.010086 |
27 | 134.217.728 | 99.256.345 | 15.359.623 | 83.896.722 | 0.739517 | 0.114438 | 0.625079 | 1.994952 | 1.921323 | 2.009047 |
28 | 268.435.456 | 198.053.976 | 29.552.392 | 168.501.584 | 0.737809 | 0.110091 | 0.627717 | 1.995379 | 1.924031 | 2.008441 |
29 | 536.870.912 | 395.246.588 | 56.951.630 | 338.294.958 | 0.736204 | 0.106081 | 0.630123 | 1.995651 | 1.927141 | 2.007666 |
30 | 1.073.741.824 | 788.890.671 | 109.891.804 | 678.998.867 | 0.734712 | 0.102345 | 0.632367 | 1.995946 | 1.929564 | 2.007121 |
31 | 2.147.483.648 | 1.574.800.951 | 212.305.528 | 1.362.495.423 | 0.733324 | 0.098862 | 0.634461 | 1.996222 | 1.931951 | 2.006624 |
32 | 4.294.967.296 | 3.144.045.204 | 410.614.218 | 2.733.430.986 | 0.732030 | 0.095604 | 0.636427 | 1.996472 | 1.934072 | 2.006195 |
33 | 8.589.934.592 | 6.277.606.452 | 795.077.468 | 5.482.528.984 | 0.730810 | 0.092559 | 0.638250 | 1.996665 | 1.936313 | 2.005732 |
34 | 17.179.869.184 | 12.535.596.738 | 1.541.036.522 | 10.994.560.216 | 0.729668 | 0.089700 | 0.639968 | 1.996875 | 1.938222 | 2.005381 |
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 | 0 | 2 | 0 | 2 | 1 | 0 |
2 | 4 | 5 | 2 | 2 | 1 | 2 | 2 | 0 |
3 | 8 | 7 | 4 | 2 | 2 | 2 | 2 | 1 |
4 | 16 | 13 | 10 | 2 | 4 | 4 | 3 | 2 |
5 | 32 | 21 | 18 | 2 | 5 | 6 | 6 | 4 |
6 | 64 | 38 | 35 | 2 | 11 | 9 | 9 | 9 |
7 | 128 | 66 | 63 | 2 | 17 | 15 | 17 | 17 |
8 | 256 | 120 | 117 | 2 | 28 | 30 | 31 | 31 |
9 | 512 | 207 | 204 | 2 | 44 | 51 | 56 | 56 |
10 | 1.024 | 358 | 355 | 2 | 84 | 91 | 91 | 92 |
11 | 2.048 | 638 | 635 | 2 | 164 | 160 | 154 | 160 |
12 | 4.096 | 1.168 | 1.165 | 2 | 294 | 294 | 288 | 292 |
13 | 8.192 | 2.098 | 2.095 | 2 | 532 | 536 | 515 | 515 |
14 | 16.384 | 3.883 | 3.880 | 2 | 976 | 983 | 969 | 955 |
15 | 32.768 | 7.179 | 7.176 | 2 | 1.793 | 1.782 | 1.835 | 1.769 |
16 | 65.536 | 13.365 | 13.362 | 2 | 3.372 | 3.308 | 3.377 | 3.308 |
17 | 131.072 | 24.859 | 24.856 | 2 | 6.175 | 6.203 | 6.293 | 6.188 |
18 | 262.144 | 46.696 | 46.693 | 2 | 11.618 | 11.664 | 11.755 | 11.659 |
19 | 524.288 | 87.618 | 87.615 | 2 | 21.904 | 21.920 | 21.927 | 21.867 |
20 | 1.048.576 | 165.736 | 165.733 | 2 | 41.396 | 41.474 | 41.603 | 41.263 |
21 | 2.097.152 | 314.406 | 314.403 | 2 | 78.464 | 78.727 | 78.823 | 78.392 |
22 | 4.194.304 | 598.394 | 598.391 | 2 | 149.421 | 149.684 | 149.719 | 149.570 |
23 | 8.388.608 | 1.140.401 | 1.140.398 | 2 | 284.780 | 285.294 | 285.129 | 285.198 |
24 | 16.777.216 | 2.178.191 | 2.178.188 | 2 | 544.204 | 545.010 | 544.110 | 544.867 |
25 | 33.554.432 | 4.168.780 | 4.168.777 | 2 | 1.042.269 | 1.042.641 | 1.041.137 | 1.042.733 |
26 | 67.108.864 | 7.994.296 | 7.994.293 | 2 | 1.997.268 | 1.999.927 | 1.997.348 | 1.999.753 |
27 | 134.217.728 | 15.359.623 | 15.359.620 | 2 | 3.838.137 | 3.841.189 | 3.839.314 | 3.840.983 |
28 | 268.435.456 | 29.552.392 | 29.552.389 | 2 | 7.386.709 | 7.390.536 | 7.386.430 | 7.388.717 |
29 | 536.870.912 | 56.951.630 | 56.951.627 | 2 | 14.236.988 | 14.239.501 | 14.235.453 | 14.239.688 |
30 | 1.073.741.824 | 109.891.804 | 109.891.801 | 2 | 27.470.247 | 27.476.969 | 27.470.319 | 27.474.269 |
31 | 2.147.483.648 | 212.305.528 | 212.305.525 | 2 | 53.078.504 | 53.083.784 | 53.068.504 | 53.074.736 |
32 | 4.294.967.296 | 410.614.218 | 410.614.215 | 2 | 102.653.528 | 102.659.508 | 102.645.958 | 102.655.224 |
33 | 8.589.934.592 | 795.077.468 | 795.077.465 | 2 | 198.773.859 | 198.774.894 | 198.754.506 | 198.774.209 |
34 | 17.179.869.184 | 1.541.036.522 | 1.541.036.519 | 2 | 385.269.970 | 385.266.740 | 385.242.430 | 385.257.382 |
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 | 0 | 0 | 1 |
4 | 16 | 3 | 3 | 0 | 0 | 0 | 1 | 2 |
5 | 32 | 9 | 9 | 0 | 2 | 2 | 2 | 3 |
6 | 64 | 19 | 18 | 1 | 4 | 4 | 5 | 6 |
7 | 128 | 43 | 37 | 6 | 10 | 11 | 10 | 12 |
8 | 256 | 91 | 70 | 21 | 26 | 23 | 20 | 22 |
9 | 512 | 223 | 147 | 76 | 52 | 56 | 61 | 54 |
10 | 1.024 | 488 | 295 | 193 | 118 | 129 | 120 | 121 |
11 | 2.048 | 1.028 | 600 | 428 | 242 | 267 | 261 | 258 |
12 | 4.096 | 2.117 | 1.217 | 900 | 489 | 560 | 534 | 534 |
13 | 8.192 | 4.413 | 2.460 | 1.953 | 1.066 | 1.130 | 1.095 | 1.122 |
14 | 16.384 | 9.031 | 5.020 | 4.011 | 2.209 | 2.283 | 2.257 | 2.282 |
15 | 32.768 | 18.391 | 10.151 | 8.240 | 4.474 | 4.664 | 4.653 | 4.600 |
16 | 65.536 | 37.249 | 20.389 | 16.860 | 9.213 | 9.289 | 9.416 | 9.331 |
17 | 131.072 | 75.844 | 41.228 | 34.616 | 18.770 | 19.039 | 19.070 | 18.965 |
18 | 262.144 | 153.523 | 83.145 | 70.378 | 38.305 | 38.295 | 38.423 | 38.500 |
19 | 524.288 | 310.859 | 167.675 | 143.184 | 77.640 | 77.542 | 77.717 | 77.960 |
20 | 1.048.576 | 627.716 | 336.763 | 290.953 | 156.865 | 157.123 | 156.826 | 156.902 |
21 | 2.097.152 | 1.265.849 | 676.645 | 589.204 | 316.393 | 316.390 | 316.494 | 316.572 |
22 | 4.194.304 | 2.549.345 | 1.359.092 | 1.190.253 | 637.082 | 637.730 | 637.106 | 637.427 |
23 | 8.388.608 | 5.133.190 | 2.727.356 | 2.405.834 | 1.282.401 | 1.283.673 | 1.283.595 | 1.283.521 |
24 | 16.777.216 | 10.329.105 | 5.472.335 | 4.856.770 | 2.581.557 | 2.582.275 | 2.584.056 | 2.581.217 |
25 | 33.554.432 | 20.774.961 | 10.980.144 | 9.794.817 | 5.190.741 | 5.193.152 | 5.196.757 | 5.194.311 |
26 | 67.108.864 | 41.759.457 | 22.019.008 | 19.740.449 | 10.437.260 | 10.443.089 | 10.441.459 | 10.437.649 |
27 | 134.217.728 | 83.896.722 | 44.142.808 | 39.753.914 | 20.966.977 | 20.977.786 | 20.975.957 | 20.976.002 |
28 | 268.435.456 | 168.501.584 | 88.488.842 | 80.012.742 | 42.120.810 | 42.129.652 | 42.126.864 | 42.124.258 |
29 | 536.870.912 | 338.294.958 | 177.323.775 | 160.971.183 | 84.560.671 | 84.579.923 | 84.573.546 | 84.580.818 |
30 | 1.073.741.824 | 678.998.867 | 355.311.291 | 323.687.576 | 169.747.101 | 169.750.246 | 169.749.381 | 169.752.139 |
31 | 2.147.483.648 | 1.362.495.423 | 711.844.977 | 650.650.446 | 340.611.319 | 340.618.998 | 340.638.331 | 340.626.775 |
32 | 4.294.967.296 | 2.733.430.986 | 1.425.987.439 | 1.307.443.547 | 683.336.872 | 683.341.663 | 683.374.996 | 683.377.455 |
33 | 8.589.934.592 | 5.482.528.984 | 2.856.216.991 | 2.626.311.993 | 1.370.605.618 | 1.370.631.861 | 1.370.638.057 | 1.370.653.448 |
34 | 17.179.869.184 | 10.994.560.216 | 5.720.366.070 | 5.274.194.146 | 2.748.579.961 | 2.748.611.684 | 2.748.696.270 | 2.748.672.301 |