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+103x+3
f(0)=3
f(1)=107
f(2)=71
f(3)=1
f(4)=431
f(5)=181
f(6)=73
f(7)=773
f(8)=11
f(9)=337
f(10)=103
f(11)=419
f(12)=461
f(13)=1511
f(14)=547
f(15)=197
f(16)=1907
f(17)=227
f(18)=727
f(19)=211
f(20)=821
f(21)=79
f(22)=2753
f(23)=967
f(24)=113
f(25)=3203
f(26)=373
f(27)=1171
f(28)=3671
f(29)=1277
f(30)=1
f(31)=4157
f(32)=131
f(33)=499
f(34)=59
f(35)=179
f(36)=1669
f(37)=1
f(38)=1787
f(39)=1847
f(40)=97
f(41)=1
f(42)=677
f(43)=571
f(44)=719
f(45)=2221
f(46)=6857
f(47)=2351
f(48)=2417
f(49)=7451
f(50)=2551
f(51)=1
f(52)=733
f(53)=919
f(54)=257
f(55)=8693
f(56)=2969
f(57)=3041
f(58)=9341
f(59)=3187
f(60)=1087
f(61)=10007
f(62)=379
f(63)=317
f(64)=10691
f(65)=331
f(66)=3719
f(67)=11393
f(68)=3877
f(69)=1319
f(70)=12113
f(71)=1373
f(72)=4201
f(73)=1
f(74)=397
f(75)=4451
f(76)=1237
f(77)=4621
f(78)=523
f(79)=1
f(80)=1627
f(81)=4969
f(82)=15173
f(83)=5147
f(84)=5237
f(85)=1453
f(86)=5419
f(87)=167
f(88)=16811
f(89)=1
f(90)=5791
f(91)=17657
f(92)=5981
f(93)=1
f(94)=18521
f(95)=6271
f(96)=193
f(97)=19403
f(98)=199
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+103x+3 could be written as f(y)= y^2-2649.25 with x=y-51.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+51.5
f'(x)>2x+102
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 | 9 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 87 | 23 | 64 | 0.870000 | 0.230000 | 0.640000 | 9.666667 | 5.750000 | 12.800000 |
3 | 1.000 | 780 | 166 | 614 | 0.780000 | 0.166000 | 0.614000 | 8.965517 | 7.217391 | 9.593750 |
4 | 10.000 | 7.646 | 1.195 | 6.451 | 0.764600 | 0.119500 | 0.645100 | 9.802564 | 7.198795 | 10.506515 |
5 | 100.000 | 74.725 | 9.416 | 65.309 | 0.747250 | 0.094160 | 0.653090 | 9.773084 | 7.879498 | 10.123857 |
6 | 1.000.000 | 736.932 | 77.078 | 659.854 | 0.736932 | 0.077078 | 0.659854 | 9.861920 | 8.185854 | 10.103569 |
7 | 10.000.000 | 7.299.861 | 652.364 | 6.647.497 | 0.729986 | 0.065236 | 0.664750 | 9.905746 | 8.463686 | 10.074194 |
8 | 100.000.000 | 72.497.219 | 5.651.552 | 66.845.667 | 0.724972 | 0.056516 | 0.668457 | 9.931314 | 8.663188 | 10.055765 |
9 | 1.000.000.000 | 721.190.549 | 49.868.856 | 671.321.693 | 0.721191 | 0.049869 | 0.671322 | 9.947838 | 8.823922 | 10.042860 |
10 | 10.000.000.000 | 7.182.119.754 | 446.229.210 | 6.735.890.544 | 0.718212 | 0.044623 | 0.673589 | 9.958700 | 8.948054 | 10.033775 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.750000 | 1.333333 | 3.000000 |
4 | 16 | 15 | 6 | 9 | 0.937500 | 0.375000 | 0.562500 | 2.142857 | 1.500000 | 3.000000 |
5 | 32 | 30 | 10 | 20 | 0.937500 | 0.312500 | 0.625000 | 2.000000 | 1.666667 | 2.222222 |
6 | 64 | 58 | 16 | 42 | 0.906250 | 0.250000 | 0.656250 | 1.933333 | 1.600000 | 2.100000 |
7 | 128 | 109 | 29 | 80 | 0.851562 | 0.226562 | 0.625000 | 1.879310 | 1.812500 | 1.904762 |
8 | 256 | 207 | 53 | 154 | 0.808594 | 0.207031 | 0.601562 | 1.899083 | 1.827586 | 1.925000 |
9 | 512 | 408 | 94 | 314 | 0.796875 | 0.183594 | 0.613281 | 1.971014 | 1.773585 | 2.038961 |
10 | 1.024 | 801 | 169 | 632 | 0.782227 | 0.165039 | 0.617188 | 1.963235 | 1.797872 | 2.012739 |
11 | 2.048 | 1.593 | 308 | 1.285 | 0.777832 | 0.150391 | 0.627441 | 1.988764 | 1.822485 | 2.033228 |
12 | 4.096 | 3.162 | 561 | 2.601 | 0.771973 | 0.136963 | 0.635010 | 1.984934 | 1.821429 | 2.024125 |
13 | 8.192 | 6.286 | 1.008 | 5.278 | 0.767334 | 0.123047 | 0.644287 | 1.987982 | 1.796791 | 2.029220 |
14 | 16.384 | 12.425 | 1.860 | 10.565 | 0.758362 | 0.113525 | 0.644836 | 1.976615 | 1.845238 | 2.001705 |
15 | 32.768 | 24.692 | 3.447 | 21.245 | 0.753540 | 0.105194 | 0.648346 | 1.987284 | 1.853226 | 2.010885 |
16 | 65.536 | 49.128 | 6.445 | 42.683 | 0.749634 | 0.098343 | 0.651291 | 1.989632 | 1.869742 | 2.009084 |
17 | 131.072 | 97.758 | 12.050 | 85.708 | 0.745834 | 0.091934 | 0.653900 | 1.989863 | 1.869666 | 2.008013 |
18 | 262.144 | 194.627 | 22.558 | 172.069 | 0.742443 | 0.086052 | 0.656391 | 1.990906 | 1.872033 | 2.007619 |
19 | 524.288 | 387.730 | 42.462 | 345.268 | 0.739536 | 0.080990 | 0.658546 | 1.992170 | 1.882348 | 2.006567 |
20 | 1.048.576 | 772.480 | 80.525 | 691.955 | 0.736694 | 0.076795 | 0.659900 | 1.992314 | 1.896402 | 2.004110 |
21 | 2.097.152 | 1.539.995 | 152.766 | 1.387.229 | 0.734327 | 0.072845 | 0.661482 | 1.993573 | 1.897125 | 2.004797 |
22 | 4.194.304 | 3.071.466 | 290.357 | 2.781.109 | 0.732295 | 0.069227 | 0.663068 | 1.994465 | 1.900665 | 2.004794 |
23 | 8.388.608 | 6.127.374 | 553.429 | 5.573.945 | 0.730440 | 0.065974 | 0.664466 | 1.994935 | 1.906029 | 2.004217 |
24 | 16.777.216 | 12.225.705 | 1.057.578 | 11.168.127 | 0.728709 | 0.063037 | 0.665672 | 1.995260 | 1.910955 | 2.003631 |
25 | 33.554.432 | 24.398.763 | 2.024.314 | 22.374.449 | 0.727140 | 0.060329 | 0.666811 | 1.995694 | 1.914104 | 2.003420 |
26 | 67.108.864 | 48.702.452 | 3.881.569 | 44.820.883 | 0.725723 | 0.057840 | 0.667883 | 1.996103 | 1.917474 | 2.003217 |
27 | 134.217.728 | 97.232.219 | 7.457.140 | 89.775.079 | 0.724436 | 0.055560 | 0.668876 | 1.996454 | 1.921166 | 2.002974 |
28 | 268.435.456 | 194.144.118 | 14.348.825 | 179.795.293 | 0.723243 | 0.053454 | 0.669790 | 1.996706 | 1.924173 | 2.002731 |
29 | 536.870.912 | 387.687.811 | 27.646.257 | 360.041.554 | 0.722125 | 0.051495 | 0.670630 | 1.996907 | 1.926726 | 2.002508 |
30 | 1.073.741.824 | 774.264.760 | 53.352.289 | 720.912.471 | 0.721090 | 0.049688 | 0.671402 | 1.997135 | 1.929820 | 2.002303 |
31 | 2.147.483.648 | 1.546.463.981 | 103.069.619 | 1.443.394.362 | 0.720128 | 0.047996 | 0.672133 | 1.997332 | 1.931869 | 2.002177 |
32 | 4.294.967.296 | 3.089.072.038 | 199.338.911 | 2.889.733.127 | 0.719231 | 0.046412 | 0.672818 | 1.997507 | 1.934022 | 2.002040 |
33 | 8.589.934.592 | 6.170.921.894 | 385.980.357 | 5.784.941.537 | 0.718390 | 0.044934 | 0.673456 | 1.997662 | 1.936302 | 2.001895 |
34 | 17.179.869.184 | 12.328.308.016 | 748.146.708 | 11.580.161.308 | 0.717602 | 0.043548 | 0.674054 | 1.997806 | 1.938303 | 2.001777 |
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 | 0 | 2 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 0 | 3 | 0 | 2 | 1 | 1 |
4 | 16 | 6 | 0 | 5 | 0 | 3 | 1 | 2 |
5 | 32 | 10 | 0 | 9 | 1 | 4 | 2 | 3 |
6 | 64 | 16 | 0 | 15 | 2 | 6 | 4 | 4 |
7 | 128 | 29 | 0 | 28 | 7 | 10 | 7 | 5 |
8 | 256 | 53 | 0 | 52 | 11 | 16 | 15 | 11 |
9 | 512 | 94 | 0 | 93 | 22 | 26 | 22 | 24 |
10 | 1.024 | 169 | 0 | 168 | 39 | 46 | 44 | 40 |
11 | 2.048 | 308 | 0 | 307 | 79 | 82 | 75 | 72 |
12 | 4.096 | 561 | 0 | 560 | 143 | 144 | 145 | 129 |
13 | 8.192 | 1.008 | 0 | 1.006 | 265 | 246 | 248 | 249 |
14 | 16.384 | 1.860 | 0 | 1.858 | 486 | 454 | 461 | 459 |
15 | 32.768 | 3.447 | 0 | 3.445 | 874 | 876 | 867 | 830 |
16 | 65.536 | 6.445 | 0 | 6.443 | 1.616 | 1.662 | 1.583 | 1.584 |
17 | 131.072 | 12.050 | 0 | 12.048 | 2.956 | 3.085 | 3.037 | 2.972 |
18 | 262.144 | 22.558 | 0 | 22.556 | 5.546 | 5.771 | 5.656 | 5.585 |
19 | 524.288 | 42.462 | 0 | 42.460 | 10.511 | 10.712 | 10.582 | 10.657 |
20 | 1.048.576 | 80.525 | 0 | 80.523 | 20.011 | 20.198 | 20.126 | 20.190 |
21 | 2.097.152 | 152.766 | 0 | 152.764 | 37.949 | 38.275 | 38.289 | 38.253 |
22 | 4.194.304 | 290.357 | 0 | 290.355 | 72.259 | 72.814 | 72.587 | 72.697 |
23 | 8.388.608 | 553.429 | 0 | 553.427 | 137.916 | 138.810 | 138.311 | 138.392 |
24 | 16.777.216 | 1.057.578 | 0 | 1.057.576 | 264.072 | 264.890 | 264.124 | 264.492 |
25 | 33.554.432 | 2.024.314 | 0 | 2.024.312 | 505.917 | 506.227 | 505.709 | 506.461 |
26 | 67.108.864 | 3.881.569 | 0 | 3.881.567 | 970.245 | 970.744 | 970.315 | 970.265 |
27 | 134.217.728 | 7.457.140 | 0 | 7.457.138 | 1.864.936 | 1.863.834 | 1.864.680 | 1.863.690 |
28 | 268.435.456 | 14.348.825 | 0 | 14.348.823 | 3.586.590 | 3.586.745 | 3.589.663 | 3.585.827 |
29 | 536.870.912 | 27.646.257 | 0 | 27.646.255 | 6.910.459 | 6.912.998 | 6.912.844 | 6.909.956 |
30 | 1.073.741.824 | 53.352.289 | 0 | 53.352.287 | 13.338.939 | 13.339.497 | 13.337.441 | 13.336.412 |
31 | 2.147.483.648 | 103.069.619 | 0 | 103.069.617 | 25.769.522 | 25.765.311 | 25.766.283 | 25.768.503 |
32 | 4.294.967.296 | 199.338.911 | 0 | 199.338.909 | 49.838.669 | 49.832.164 | 49.834.731 | 49.833.347 |
33 | 8.589.934.592 | 385.980.357 | 0 | 385.980.355 | 96.496.058 | 96.498.585 | 96.488.252 | 96.497.462 |
34 | 17.179.869.184 | 748.146.708 | 0 | 748.146.706 | 187.033.249 | 187.042.588 | 187.030.937 | 187.039.934 |
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 | 1 | 0 | 0 | 0 | 1 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
3 | 8 | 3 | 2 | 1 | 1 | 0 | 1 | 1 |
4 | 16 | 9 | 5 | 4 | 2 | 2 | 3 | 2 |
5 | 32 | 20 | 11 | 9 | 3 | 6 | 6 | 5 |
6 | 64 | 42 | 22 | 20 | 8 | 12 | 11 | 11 |
7 | 128 | 80 | 44 | 36 | 15 | 22 | 23 | 20 |
8 | 256 | 154 | 83 | 71 | 33 | 44 | 35 | 42 |
9 | 512 | 314 | 168 | 146 | 72 | 81 | 79 | 82 |
10 | 1.024 | 632 | 341 | 291 | 150 | 160 | 164 | 158 |
11 | 2.048 | 1.285 | 688 | 597 | 306 | 334 | 324 | 321 |
12 | 4.096 | 2.601 | 1.374 | 1.227 | 659 | 639 | 668 | 635 |
13 | 8.192 | 5.278 | 2.767 | 2.511 | 1.302 | 1.307 | 1.367 | 1.302 |
14 | 16.384 | 10.565 | 5.550 | 5.015 | 2.615 | 2.612 | 2.685 | 2.653 |
15 | 32.768 | 21.245 | 10.991 | 10.254 | 5.256 | 5.309 | 5.327 | 5.353 |
16 | 65.536 | 42.683 | 22.067 | 20.616 | 10.601 | 10.668 | 10.716 | 10.698 |
17 | 131.072 | 85.708 | 44.116 | 41.592 | 21.336 | 21.408 | 21.527 | 21.437 |
18 | 262.144 | 172.069 | 88.530 | 83.539 | 43.162 | 42.875 | 43.134 | 42.898 |
19 | 524.288 | 345.268 | 176.907 | 168.361 | 86.332 | 86.088 | 86.522 | 86.326 |
20 | 1.048.576 | 691.955 | 354.251 | 337.704 | 173.098 | 172.806 | 172.927 | 173.124 |
21 | 2.097.152 | 1.387.229 | 709.534 | 677.695 | 347.253 | 346.319 | 346.460 | 347.197 |
22 | 4.194.304 | 2.781.109 | 1.421.930 | 1.359.179 | 695.614 | 694.326 | 695.041 | 696.128 |
23 | 8.388.608 | 5.573.945 | 2.847.208 | 2.726.737 | 1.394.043 | 1.392.798 | 1.393.208 | 1.393.896 |
24 | 16.777.216 | 11.168.127 | 5.700.464 | 5.467.663 | 2.792.237 | 2.791.657 | 2.790.442 | 2.793.791 |
25 | 33.554.432 | 22.374.449 | 11.407.844 | 10.966.605 | 5.593.904 | 5.592.410 | 5.591.703 | 5.596.432 |
26 | 67.108.864 | 44.820.883 | 22.830.203 | 21.990.680 | 11.205.548 | 11.206.607 | 11.205.797 | 11.202.931 |
27 | 134.217.728 | 89.775.079 | 45.694.616 | 44.080.463 | 22.441.999 | 22.445.897 | 22.447.113 | 22.440.070 |
28 | 268.435.456 | 179.795.293 | 91.450.334 | 88.344.959 | 44.945.649 | 44.952.370 | 44.951.885 | 44.945.389 |
29 | 536.870.912 | 360.041.554 | 182.991.012 | 177.050.542 | 90.000.575 | 90.012.464 | 90.016.117 | 90.012.398 |
30 | 1.073.741.824 | 720.912.471 | 366.186.435 | 354.726.036 | 180.212.872 | 180.233.744 | 180.242.980 | 180.222.875 |
31 | 2.147.483.648 | 1.443.394.362 | 732.746.172 | 710.648.190 | 360.833.007 | 360.851.168 | 360.861.036 | 360.849.151 |
32 | 4.294.967.296 | 2.889.733.127 | 1.466.204.938 | 1.423.528.189 | 722.449.732 | 722.430.063 | 722.422.238 | 722.431.094 |
33 | 8.589.934.592 | 5.784.941.537 | 2.933.720.069 | 2.851.221.468 | 1.446.249.148 | 1.446.214.187 | 1.446.226.249 | 1.446.251.953 |
34 | 17.179.869.184 | 11.580.161.308 | 5.869.842.357 | 5.710.318.951 | 2.895.058.512 | 2.894.996.098 | 2.895.033.413 | 2.895.073.285 |