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+3x-7
f(0)=7
f(1)=3
f(2)=1
f(3)=11
f(4)=1
f(5)=1
f(6)=47
f(7)=1
f(8)=1
f(9)=101
f(10)=41
f(11)=1
f(12)=173
f(13)=67
f(14)=1
f(15)=263
f(16)=1
f(17)=37
f(18)=53
f(19)=137
f(20)=151
f(21)=71
f(22)=181
f(23)=197
f(24)=641
f(25)=1
f(26)=83
f(27)=73
f(28)=1
f(29)=307
f(30)=983
f(31)=349
f(32)=1
f(33)=1181
f(34)=139
f(35)=1
f(36)=127
f(37)=491
f(38)=1
f(39)=233
f(40)=571
f(41)=599
f(42)=269
f(43)=1
f(44)=229
f(45)=2153
f(46)=107
f(47)=1
f(48)=2441
f(49)=1
f(50)=881
f(51)=1
f(52)=317
f(53)=1
f(54)=1
f(55)=1061
f(56)=157
f(57)=3413
f(58)=1
f(59)=1217
f(60)=1
f(61)=433
f(62)=149
f(63)=593
f(64)=1427
f(65)=1471
f(66)=4547
f(67)=223
f(68)=1607
f(69)=1
f(70)=1
f(71)=1
f(72)=5393
f(73)=1847
f(74)=271
f(75)=5843
f(76)=1999
f(77)=293
f(78)=6311
f(79)=719
f(80)=1
f(81)=971
f(82)=211
f(83)=2377
f(84)=1
f(85)=1
f(86)=2549
f(87)=7823
f(88)=1
f(89)=1
f(90)=8363
f(91)=1
f(92)=1
f(93)=811
f(94)=3037
f(95)=443
f(96)=9497
f(97)=359
f(98)=1
f(99)=10091
b) Substitution of the polynom
The polynom f(x)=x^2+3x-7 could be written as f(y)= y^2-9.25 with x=y-1.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+1.5
f'(x)>2x+2
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 | 6 | 5 | 1 | 0.600000 | 0.500000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 68 | 22 | 46 | 0.680000 | 0.220000 | 0.460000 | 11.333333 | 4.400000 | 46.000000 |
3 | 1.000 | 702 | 112 | 590 | 0.702000 | 0.112000 | 0.590000 | 10.323529 | 5.090909 | 12.826087 |
4 | 10.000 | 7.004 | 786 | 6.218 | 0.700400 | 0.078600 | 0.621800 | 9.977208 | 7.017857 | 10.538983 |
5 | 100.000 | 69.920 | 5.992 | 63.928 | 0.699200 | 0.059920 | 0.639280 | 9.982867 | 7.623410 | 10.281119 |
6 | 1.000.000 | 698.234 | 48.817 | 649.417 | 0.698234 | 0.048817 | 0.649417 | 9.986184 | 8.147029 | 10.158569 |
7 | 10.000.000 | 6.971.835 | 413.116 | 6.558.719 | 0.697183 | 0.041312 | 0.655872 | 9.984955 | 8.462543 | 10.099396 |
8 | 100.000.000 | 69.639.457 | 3.581.439 | 66.058.018 | 0.696395 | 0.035814 | 0.660580 | 9.988684 | 8.669331 | 10.071786 |
9 | 1.000.000.000 | 695.882.803 | 31.593.894 | 664.288.909 | 0.695883 | 0.031594 | 0.664289 | 9.992652 | 8.821564 | 10.056144 |
10 | 10.000.000.000 | 6.954.833.499 | 282.773.378 | 6.672.060.121 | 0.695483 | 0.028277 | 0.667206 | 9.994260 | 8.950254 | 10.043913 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.500000 | 1.500000 | -nan |
3 | 8 | 4 | 4 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.333333 | 1.333333 | -nan |
4 | 16 | 9 | 7 | 2 | 0.562500 | 0.437500 | 0.125000 | 2.250000 | 1.750000 | inf |
5 | 32 | 22 | 10 | 12 | 0.687500 | 0.312500 | 0.375000 | 2.444444 | 1.428571 | 6.000000 |
6 | 64 | 44 | 14 | 30 | 0.687500 | 0.218750 | 0.468750 | 2.000000 | 1.400000 | 2.500000 |
7 | 128 | 87 | 27 | 60 | 0.679688 | 0.210938 | 0.468750 | 1.977273 | 1.928571 | 2.000000 |
8 | 256 | 177 | 42 | 135 | 0.691406 | 0.164062 | 0.527344 | 2.034483 | 1.555556 | 2.250000 |
9 | 512 | 359 | 68 | 291 | 0.701172 | 0.132812 | 0.568359 | 2.028249 | 1.619048 | 2.155555 |
10 | 1.024 | 718 | 115 | 603 | 0.701172 | 0.112305 | 0.588867 | 2.000000 | 1.691176 | 2.072165 |
11 | 2.048 | 1.433 | 207 | 1.226 | 0.699707 | 0.101074 | 0.598633 | 1.995822 | 1.800000 | 2.033168 |
12 | 4.096 | 2.867 | 356 | 2.511 | 0.699951 | 0.086914 | 0.613037 | 2.000698 | 1.719807 | 2.048124 |
13 | 8.192 | 5.731 | 665 | 5.066 | 0.699585 | 0.081177 | 0.618408 | 1.998954 | 1.867977 | 2.017523 |
14 | 16.384 | 11.483 | 1.193 | 10.290 | 0.700867 | 0.072815 | 0.628052 | 2.003664 | 1.793985 | 2.031188 |
15 | 32.768 | 22.939 | 2.202 | 20.737 | 0.700043 | 0.067200 | 0.632843 | 1.997649 | 1.845767 | 2.015258 |
16 | 65.536 | 45.866 | 4.137 | 41.729 | 0.699860 | 0.063126 | 0.636734 | 1.999477 | 1.878747 | 2.012297 |
17 | 131.072 | 91.660 | 7.643 | 84.017 | 0.699310 | 0.058311 | 0.640999 | 1.998430 | 1.847474 | 2.013396 |
18 | 262.144 | 183.196 | 14.292 | 168.904 | 0.698837 | 0.054520 | 0.644318 | 1.998647 | 1.869946 | 2.010355 |
19 | 524.288 | 366.083 | 26.961 | 339.122 | 0.698248 | 0.051424 | 0.646824 | 1.998313 | 1.886440 | 2.007780 |
20 | 1.048.576 | 732.150 | 51.037 | 681.113 | 0.698233 | 0.048673 | 0.649560 | 1.999956 | 1.892994 | 2.008460 |
21 | 2.097.152 | 1.463.322 | 96.552 | 1.366.770 | 0.697766 | 0.046040 | 0.651727 | 1.998664 | 1.891804 | 2.006671 |
22 | 4.194.304 | 2.925.185 | 184.278 | 2.740.907 | 0.697418 | 0.043935 | 0.653483 | 1.999003 | 1.908588 | 2.005390 |
23 | 8.388.608 | 5.848.849 | 350.680 | 5.498.169 | 0.697237 | 0.041804 | 0.655433 | 1.999480 | 1.902994 | 2.005967 |
24 | 16.777.216 | 11.693.696 | 670.302 | 11.023.394 | 0.696999 | 0.039953 | 0.657045 | 1.999316 | 1.911435 | 2.004921 |
25 | 33.554.432 | 23.377.938 | 1.282.902 | 22.095.036 | 0.696717 | 0.038233 | 0.658483 | 1.999192 | 1.913916 | 2.004377 |
26 | 67.108.864 | 46.742.397 | 2.459.921 | 44.282.476 | 0.696516 | 0.036656 | 0.659860 | 1.999423 | 1.917466 | 2.004182 |
27 | 134.217.728 | 93.458.089 | 4.725.973 | 88.732.116 | 0.696317 | 0.035211 | 0.661106 | 1.999429 | 1.921189 | 2.003775 |
28 | 268.435.456 | 186.873.059 | 9.088.876 | 177.784.183 | 0.696156 | 0.033859 | 0.662298 | 1.999539 | 1.923176 | 2.003606 |
29 | 536.870.912 | 373.664.627 | 17.515.225 | 356.149.402 | 0.696005 | 0.032625 | 0.663380 | 1.999564 | 1.927106 | 2.003268 |
30 | 1.073.741.824 | 747.183.031 | 33.802.048 | 713.380.983 | 0.695868 | 0.031481 | 0.664388 | 1.999609 | 1.929867 | 2.003039 |
31 | 2.147.483.648 | 1.494.081.401 | 65.307.284 | 1.428.774.117 | 0.695736 | 0.030411 | 0.665325 | 1.999619 | 1.932051 | 2.002820 |
32 | 4.294.967.296 | 2.987.645.780 | 126.323.619 | 2.861.322.161 | 0.695615 | 0.029412 | 0.666203 | 1.999654 | 1.934296 | 2.002641 |
33 | 8.589.934.592 | 5.974.335.764 | 244.599.190 | 5.729.736.574 | 0.695504 | 0.028475 | 0.667029 | 1.999680 | 1.936290 | 2.002479 |
34 | 17.179.869.184 | 11.946.961.514 | 474.099.551 | 11.472.861.963 | 0.695405 | 0.027596 | 0.667808 | 1.999714 | 1.938271 | 2.002337 |
35 | 34.359.738.368 | 23.890.714.499 | 919.848.228 | 22.970.866.271 | 0.695311 | 0.026771 | 0.668540 | 1.999731 | 1.940201 | 2.002191 |
36 | 68.719.476.736 | 47.775.467.389 | 1.786.239.208 | 45.989.228.181 | 0.695225 | 0.025993 | 0.669231 | 1.999750 | 1.941885 | 2.002068 |
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 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 1 | 2 | 0 | 2 | 0 | 2 |
4 | 16 | 7 | 1 | 5 | 0 | 2 | 2 | 3 |
5 | 32 | 10 | 1 | 7 | 1 | 2 | 3 | 4 |
6 | 64 | 14 | 1 | 11 | 3 | 2 | 5 | 4 |
7 | 128 | 27 | 1 | 24 | 7 | 7 | 6 | 7 |
8 | 256 | 42 | 1 | 39 | 11 | 11 | 9 | 11 |
9 | 512 | 68 | 1 | 65 | 18 | 20 | 15 | 15 |
10 | 1.024 | 115 | 1 | 112 | 30 | 31 | 29 | 25 |
11 | 2.048 | 207 | 1 | 204 | 50 | 52 | 54 | 51 |
12 | 4.096 | 356 | 1 | 353 | 88 | 86 | 89 | 93 |
13 | 8.192 | 665 | 1 | 662 | 162 | 161 | 165 | 177 |
14 | 16.384 | 1.193 | 1 | 1.190 | 294 | 298 | 296 | 305 |
15 | 32.768 | 2.202 | 1 | 2.199 | 543 | 564 | 536 | 559 |
16 | 65.536 | 4.137 | 1 | 4.134 | 1.024 | 1.058 | 1.025 | 1.030 |
17 | 131.072 | 7.643 | 1 | 7.640 | 1.897 | 1.927 | 1.890 | 1.929 |
18 | 262.144 | 14.292 | 1 | 14.289 | 3.524 | 3.573 | 3.594 | 3.601 |
19 | 524.288 | 26.961 | 1 | 26.958 | 6.660 | 6.797 | 6.789 | 6.715 |
20 | 1.048.576 | 51.037 | 1 | 51.034 | 12.753 | 12.680 | 12.809 | 12.795 |
21 | 2.097.152 | 96.552 | 1 | 96.549 | 24.030 | 24.019 | 24.230 | 24.273 |
22 | 4.194.304 | 184.278 | 1 | 184.275 | 45.998 | 45.816 | 46.371 | 46.093 |
23 | 8.388.608 | 350.680 | 1 | 350.677 | 87.579 | 87.492 | 88.105 | 87.504 |
24 | 16.777.216 | 670.302 | 1 | 670.299 | 167.261 | 167.321 | 168.217 | 167.503 |
25 | 33.554.432 | 1.282.902 | 1 | 1.282.899 | 320.184 | 320.402 | 321.360 | 320.956 |
26 | 67.108.864 | 2.459.921 | 1 | 2.459.918 | 614.381 | 614.542 | 615.775 | 615.223 |
27 | 134.217.728 | 4.725.973 | 1 | 4.725.970 | 1.180.967 | 1.181.184 | 1.181.432 | 1.182.390 |
28 | 268.435.456 | 9.088.876 | 1 | 9.088.873 | 2.271.892 | 2.271.343 | 2.272.153 | 2.273.488 |
29 | 536.870.912 | 17.515.225 | 1 | 17.515.222 | 4.376.907 | 4.378.959 | 4.379.448 | 4.379.911 |
30 | 1.073.741.824 | 33.802.048 | 1 | 33.802.045 | 8.449.298 | 8.451.035 | 8.449.945 | 8.451.770 |
31 | 2.147.483.648 | 65.307.284 | 1 | 65.307.281 | 16.327.500 | 16.327.986 | 16.326.945 | 16.324.853 |
32 | 4.294.967.296 | 126.323.619 | 1 | 126.323.616 | 31.586.213 | 31.581.281 | 31.578.154 | 31.577.971 |
33 | 8.589.934.592 | 244.599.190 | 1 | 244.599.187 | 61.155.347 | 61.146.596 | 61.149.597 | 61.147.650 |
34 | 17.179.869.184 | 474.099.551 | 1 | 474.099.548 | 118.524.496 | 118.530.080 | 118.515.689 | 118.529.286 |
35 | 34.359.738.368 | 919.848.228 | 1 | 919.848.225 | 229.967.325 | 229.970.347 | 229.950.064 | 229.960.492 |
36 | 68.719.476.736 | 1.786.239.208 | 1 | 1.786.239.205 | 446.558.495 | 446.559.577 | 446.555.494 | 446.565.642 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
5 | 32 | 12 | 6 | 6 | 3 | 3 | 4 | 2 |
6 | 64 | 30 | 12 | 18 | 8 | 8 | 10 | 4 |
7 | 128 | 60 | 28 | 32 | 12 | 17 | 18 | 13 |
8 | 256 | 135 | 64 | 71 | 29 | 38 | 37 | 31 |
9 | 512 | 291 | 150 | 141 | 68 | 76 | 78 | 69 |
10 | 1.024 | 603 | 303 | 300 | 136 | 163 | 160 | 144 |
11 | 2.048 | 1.226 | 620 | 606 | 292 | 321 | 311 | 302 |
12 | 4.096 | 2.511 | 1.276 | 1.235 | 605 | 627 | 637 | 642 |
13 | 8.192 | 5.066 | 2.555 | 2.511 | 1.219 | 1.261 | 1.274 | 1.312 |
14 | 16.384 | 10.290 | 5.120 | 5.170 | 2.502 | 2.564 | 2.575 | 2.649 |
15 | 32.768 | 20.737 | 10.314 | 10.423 | 5.152 | 5.173 | 5.218 | 5.194 |
16 | 65.536 | 41.729 | 20.851 | 20.878 | 10.417 | 10.525 | 10.375 | 10.412 |
17 | 131.072 | 84.017 | 41.985 | 42.032 | 20.962 | 21.140 | 20.953 | 20.962 |
18 | 262.144 | 168.904 | 84.402 | 84.502 | 42.001 | 42.390 | 42.253 | 42.260 |
19 | 524.288 | 339.122 | 169.532 | 169.590 | 84.491 | 84.914 | 84.750 | 84.967 |
20 | 1.048.576 | 681.113 | 340.262 | 340.851 | 170.052 | 170.343 | 170.375 | 170.343 |
21 | 2.097.152 | 1.366.770 | 683.671 | 683.099 | 341.327 | 341.579 | 342.105 | 341.759 |
22 | 4.194.304 | 2.740.907 | 1.370.452 | 1.370.455 | 684.377 | 685.138 | 685.928 | 685.464 |
23 | 8.388.608 | 5.498.169 | 2.749.923 | 2.748.246 | 1.373.578 | 1.374.821 | 1.374.897 | 1.374.873 |
24 | 16.777.216 | 11.023.394 | 5.513.331 | 5.510.063 | 2.754.360 | 2.757.112 | 2.755.789 | 2.756.133 |
25 | 33.554.432 | 22.095.036 | 11.050.180 | 11.044.856 | 5.521.976 | 5.524.857 | 5.523.676 | 5.524.527 |
26 | 67.108.864 | 44.282.476 | 22.143.353 | 22.139.123 | 11.069.757 | 11.072.917 | 11.069.010 | 11.070.792 |
27 | 134.217.728 | 88.732.116 | 44.369.149 | 44.362.967 | 22.180.030 | 22.185.581 | 22.182.757 | 22.183.748 |
28 | 268.435.456 | 177.784.183 | 88.897.468 | 88.886.715 | 44.448.340 | 44.449.353 | 44.438.133 | 44.448.357 |
29 | 536.870.912 | 356.149.402 | 178.084.151 | 178.065.251 | 89.037.654 | 89.039.416 | 89.031.705 | 89.040.627 |
30 | 1.073.741.824 | 713.380.983 | 356.705.590 | 356.675.393 | 178.339.809 | 178.354.206 | 178.343.188 | 178.343.780 |
31 | 2.147.483.648 | 1.428.774.117 | 714.408.340 | 714.365.777 | 357.204.920 | 357.186.420 | 357.192.840 | 357.189.937 |
32 | 4.294.967.296 | 2.861.322.161 | 1.430.691.766 | 1.430.630.395 | 715.327.848 | 715.323.663 | 715.363.173 | 715.307.477 |
33 | 8.589.934.592 | 5.729.736.574 | 2.864.844.899 | 2.864.891.675 | 1.432.443.251 | 1.432.423.785 | 1.432.448.010 | 1.432.421.528 |
34 | 17.179.869.184 | 11.472.861.963 | 5.736.345.401 | 5.736.516.562 | 2.868.176.274 | 2.868.213.109 | 2.868.254.274 | 2.868.218.306 |
35 | 34.359.738.368 | 22.970.866.271 | 11.485.027.439 | 11.485.838.832 | 5.742.707.978 | 5.742.696.261 | 5.742.672.982 | 5.742.789.050 |
36 | 68.719.476.736 | 45.989.228.181 | 22.993.690.531 | 22.995.537.650 | 11.497.273.358 | 11.497.302.387 | 11.497.216.171 | 11.497.436.265 |