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+48x+7
f(0)=7
f(1)=1
f(2)=107
f(3)=5
f(4)=43
f(5)=17
f(6)=331
f(7)=1
f(8)=13
f(9)=1
f(10)=587
f(11)=41
f(12)=727
f(13)=1
f(14)=1
f(15)=1
f(16)=1031
f(17)=139
f(18)=239
f(19)=1
f(20)=1367
f(21)=1
f(22)=1
f(23)=1
f(24)=347
f(25)=229
f(26)=1931
f(27)=127
f(28)=61
f(29)=1
f(30)=2347
f(31)=307
f(32)=151
f(33)=67
f(34)=1
f(35)=1
f(36)=433
f(37)=197
f(38)=131
f(39)=1
f(40)=3527
f(41)=457
f(42)=541
f(43)=1
f(44)=811
f(45)=1
f(46)=71
f(47)=1
f(48)=1
f(49)=1
f(50)=701
f(51)=79
f(52)=1
f(53)=1
f(54)=1103
f(55)=709
f(56)=1
f(57)=1
f(58)=1231
f(59)=1
f(60)=499
f(61)=1
f(62)=6827
f(63)=1
f(64)=1
f(65)=919
f(66)=443
f(67)=241
f(68)=1579
f(69)=101
f(70)=1181
f(71)=1
f(72)=8647
f(73)=1
f(74)=1
f(75)=577
f(76)=9431
f(77)=1
f(78)=281
f(79)=251
f(80)=10247
f(81)=1307
f(82)=10667
f(83)=1
f(84)=317
f(85)=1
f(86)=887
f(87)=113
f(88)=479
f(89)=1
f(90)=1
f(91)=1
f(92)=263
f(93)=1
f(94)=2671
f(95)=1699
f(96)=13831
f(97)=1759
f(98)=409
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+48x+7 could be written as f(y)= y^2-569 with x=y-24
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+24
f'(x)>2x+47
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 | 56 | 31 | 25 | 0.560000 | 0.310000 | 0.250000 | 9.333333 | 6.200000 | 25.000000 |
3 | 1.000 | 601 | 211 | 390 | 0.601000 | 0.211000 | 0.390000 | 10.732142 | 6.806452 | 15.600000 |
4 | 10.000 | 6.340 | 1.485 | 4.855 | 0.634000 | 0.148500 | 0.485500 | 10.549085 | 7.037915 | 12.448718 |
5 | 100.000 | 64.612 | 11.359 | 53.253 | 0.646120 | 0.113590 | 0.532530 | 10.191167 | 7.649158 | 10.968692 |
6 | 1.000.000 | 654.024 | 91.225 | 562.799 | 0.654024 | 0.091225 | 0.562799 | 10.122331 | 8.031076 | 10.568399 |
7 | 10.000.000 | 6.598.552 | 763.702 | 5.834.850 | 0.659855 | 0.076370 | 0.583485 | 10.089159 | 8.371631 | 10.367556 |
8 | 100.000.000 | 66.408.953 | 6.574.800 | 59.834.153 | 0.664090 | 0.065748 | 0.598342 | 10.064171 | 8.609118 | 10.254617 |
9 | 1.000.000.000 | 667.341.211 | 57.734.277 | 609.606.934 | 0.667341 | 0.057734 | 0.609607 | 10.048965 | 8.781146 | 10.188277 |
10 | 10.000.000.000 | 6.699.431.708 | 514.420.958 | 6.185.010.750 | 0.669943 | 0.051442 | 0.618501 | 10.038991 | 8.910149 | 10.145900 |
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 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.500000 | 1.000000 | inf |
3 | 8 | 5 | 4 | 1 | 0.625000 | 0.500000 | 0.125000 | 1.666667 | 2.000000 | 1.000000 |
4 | 16 | 9 | 8 | 1 | 0.562500 | 0.500000 | 0.062500 | 1.800000 | 2.000000 | 1.000000 |
5 | 32 | 20 | 15 | 5 | 0.625000 | 0.468750 | 0.156250 | 2.222222 | 1.875000 | 5.000000 |
6 | 64 | 34 | 20 | 14 | 0.531250 | 0.312500 | 0.218750 | 1.700000 | 1.333333 | 2.800000 |
7 | 128 | 72 | 39 | 33 | 0.562500 | 0.304688 | 0.257812 | 2.117647 | 1.950000 | 2.357143 |
8 | 256 | 151 | 69 | 82 | 0.589844 | 0.269531 | 0.320312 | 2.097222 | 1.769231 | 2.484848 |
9 | 512 | 308 | 119 | 189 | 0.601562 | 0.232422 | 0.369141 | 2.039735 | 1.724638 | 2.304878 |
10 | 1.024 | 614 | 215 | 399 | 0.599609 | 0.209961 | 0.389648 | 1.993507 | 1.806723 | 2.111111 |
11 | 2.048 | 1.273 | 384 | 889 | 0.621582 | 0.187500 | 0.434082 | 2.073290 | 1.786047 | 2.228070 |
12 | 4.096 | 2.563 | 689 | 1.874 | 0.625732 | 0.168213 | 0.457520 | 2.013354 | 1.794271 | 2.107986 |
13 | 8.192 | 5.177 | 1.249 | 3.928 | 0.631958 | 0.152466 | 0.479492 | 2.019899 | 1.812772 | 2.096051 |
14 | 16.384 | 10.418 | 2.289 | 8.129 | 0.635864 | 0.139709 | 0.496155 | 2.012362 | 1.832666 | 2.069501 |
15 | 32.768 | 20.989 | 4.222 | 16.767 | 0.640533 | 0.128845 | 0.511688 | 2.014686 | 1.844474 | 2.062615 |
16 | 65.536 | 42.183 | 7.829 | 34.354 | 0.643661 | 0.119461 | 0.524200 | 2.009767 | 1.854334 | 2.048906 |
17 | 131.072 | 84.809 | 14.426 | 70.383 | 0.647041 | 0.110062 | 0.536980 | 2.010502 | 1.842636 | 2.048757 |
18 | 262.144 | 170.336 | 26.905 | 143.431 | 0.649780 | 0.102634 | 0.547146 | 2.008466 | 1.865035 | 2.037864 |
19 | 524.288 | 341.957 | 50.548 | 291.409 | 0.652231 | 0.096413 | 0.555819 | 2.007544 | 1.878759 | 2.031702 |
20 | 1.048.576 | 686.039 | 95.278 | 590.761 | 0.654258 | 0.090864 | 0.563394 | 2.006214 | 1.884902 | 2.027257 |
21 | 2.097.152 | 1.375.893 | 180.240 | 1.195.653 | 0.656077 | 0.085945 | 0.570132 | 2.005561 | 1.891727 | 2.023920 |
22 | 4.194.304 | 2.759.712 | 341.392 | 2.418.320 | 0.657967 | 0.081394 | 0.576572 | 2.005761 | 1.894097 | 2.022593 |
23 | 8.388.608 | 5.531.964 | 648.458 | 4.883.506 | 0.659461 | 0.077302 | 0.582159 | 2.004544 | 1.899453 | 2.019380 |
24 | 16.777.216 | 11.087.661 | 1.236.977 | 9.850.684 | 0.660876 | 0.073730 | 0.587147 | 2.004290 | 1.907567 | 2.017133 |
25 | 33.554.432 | 22.220.952 | 2.361.482 | 19.859.470 | 0.662236 | 0.070378 | 0.591858 | 2.004115 | 1.909075 | 2.016050 |
26 | 67.108.864 | 44.523.078 | 4.522.100 | 40.000.978 | 0.663446 | 0.067385 | 0.596061 | 2.003653 | 1.914942 | 2.014202 |
27 | 134.217.728 | 89.193.503 | 8.671.205 | 80.522.298 | 0.664543 | 0.064606 | 0.599938 | 2.003309 | 1.917517 | 2.013008 |
28 | 268.435.456 | 178.663.324 | 16.660.576 | 162.002.748 | 0.665573 | 0.062065 | 0.603507 | 2.003098 | 1.921368 | 2.011899 |
29 | 536.870.912 | 357.842.536 | 32.053.721 | 325.788.815 | 0.666534 | 0.059705 | 0.606829 | 2.002887 | 1.923926 | 2.011008 |
30 | 1.073.741.824 | 716.646.670 | 61.758.112 | 654.888.558 | 0.667429 | 0.057517 | 0.609913 | 2.002687 | 1.926707 | 2.010163 |
31 | 2.147.483.648 | 1.435.092.186 | 119.136.428 | 1.315.955.758 | 0.668267 | 0.055477 | 0.612790 | 2.002510 | 1.929082 | 2.009434 |
32 | 4.294.967.296 | 2.873.550.531 | 230.144.427 | 2.643.406.104 | 0.669051 | 0.053585 | 0.615466 | 2.002346 | 1.931772 | 2.008735 |
33 | 8.589.934.592 | 5.753.426.632 | 445.078.921 | 5.308.347.711 | 0.669787 | 0.051814 | 0.617973 | 2.002201 | 1.933911 | 2.008147 |
34 | 17.179.869.184 | 11.518.752.397 | 861.729.328 | 10.657.023.069 | 0.670480 | 0.050159 | 0.620320 | 2.002068 | 1.936127 | 2.007597 |
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 | 1 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 2 | 0 | 1 |
4 | 16 | 8 | 3 | 5 | 2 | 3 | 0 | 3 |
5 | 32 | 15 | 8 | 7 | 2 | 7 | 1 | 5 |
6 | 64 | 20 | 10 | 10 | 3 | 8 | 3 | 6 |
7 | 128 | 39 | 19 | 20 | 5 | 14 | 6 | 14 |
8 | 256 | 69 | 31 | 38 | 10 | 20 | 12 | 27 |
9 | 512 | 119 | 52 | 67 | 19 | 40 | 17 | 43 |
10 | 1.024 | 215 | 99 | 116 | 36 | 73 | 29 | 77 |
11 | 2.048 | 384 | 174 | 210 | 54 | 137 | 51 | 142 |
12 | 4.096 | 689 | 316 | 373 | 92 | 250 | 96 | 251 |
13 | 8.192 | 1.249 | 564 | 685 | 173 | 457 | 169 | 450 |
14 | 16.384 | 2.289 | 1.023 | 1.266 | 305 | 846 | 302 | 836 |
15 | 32.768 | 4.222 | 1.877 | 2.345 | 557 | 1.593 | 546 | 1.526 |
16 | 65.536 | 7.829 | 3.505 | 4.324 | 1.025 | 2.938 | 1.033 | 2.833 |
17 | 131.072 | 14.426 | 6.521 | 7.905 | 1.891 | 5.351 | 1.901 | 5.283 |
18 | 262.144 | 26.905 | 12.168 | 14.737 | 3.612 | 9.910 | 3.588 | 9.795 |
19 | 524.288 | 50.548 | 22.872 | 27.676 | 6.730 | 18.580 | 6.726 | 18.512 |
20 | 1.048.576 | 95.278 | 43.061 | 52.217 | 12.666 | 35.104 | 12.576 | 34.932 |
21 | 2.097.152 | 180.240 | 81.056 | 99.184 | 23.917 | 66.448 | 23.728 | 66.147 |
22 | 4.194.304 | 341.392 | 153.381 | 188.011 | 45.066 | 125.786 | 44.878 | 125.662 |
23 | 8.388.608 | 648.458 | 291.062 | 357.396 | 85.092 | 239.108 | 85.275 | 238.983 |
24 | 16.777.216 | 1.236.977 | 555.090 | 681.887 | 161.990 | 456.339 | 162.159 | 456.489 |
25 | 33.554.432 | 2.361.482 | 1.059.506 | 1.301.976 | 308.798 | 871.915 | 308.736 | 872.033 |
26 | 67.108.864 | 4.522.100 | 2.028.092 | 2.494.008 | 589.042 | 1.670.777 | 590.418 | 1.671.863 |
27 | 134.217.728 | 8.671.205 | 3.888.063 | 4.783.142 | 1.128.655 | 3.206.147 | 1.128.626 | 3.207.777 |
28 | 268.435.456 | 16.660.576 | 7.466.391 | 9.194.185 | 2.164.491 | 6.164.523 | 2.165.675 | 6.165.887 |
29 | 536.870.912 | 32.053.721 | 14.361.469 | 17.692.252 | 4.158.896 | 11.866.823 | 4.161.009 | 11.866.993 |
30 | 1.073.741.824 | 61.758.112 | 27.658.713 | 34.099.399 | 8.001.819 | 22.874.772 | 8.005.281 | 22.876.240 |
31 | 2.147.483.648 | 119.136.428 | 53.340.673 | 65.795.755 | 15.418.659 | 44.147.103 | 15.421.657 | 44.149.009 |
32 | 4.294.967.296 | 230.144.427 | 103.010.610 | 127.133.817 | 29.750.950 | 85.322.236 | 29.759.898 | 85.311.343 |
33 | 8.589.934.592 | 445.078.921 | 199.167.389 | 245.911.532 | 57.476.054 | 165.051.497 | 57.494.071 | 165.057.299 |
34 | 17.179.869.184 | 861.729.328 | 385.534.066 | 476.195.262 | 111.175.440 | 319.679.961 | 111.188.346 | 319.685.581 |
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 | 1 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 32 | 5 | 3 | 2 | 0 | 2 | 1 | 2 |
6 | 64 | 14 | 9 | 5 | 1 | 6 | 3 | 4 |
7 | 128 | 33 | 17 | 16 | 3 | 13 | 8 | 9 |
8 | 256 | 82 | 41 | 41 | 12 | 28 | 16 | 26 |
9 | 512 | 189 | 93 | 96 | 34 | 61 | 40 | 54 |
10 | 1.024 | 399 | 199 | 200 | 76 | 121 | 94 | 108 |
11 | 2.048 | 889 | 446 | 443 | 199 | 243 | 214 | 233 |
12 | 4.096 | 1.874 | 948 | 926 | 430 | 517 | 435 | 492 |
13 | 8.192 | 3.928 | 1.962 | 1.966 | 908 | 1.082 | 917 | 1.021 |
14 | 16.384 | 8.129 | 4.028 | 4.101 | 1.946 | 2.174 | 1.894 | 2.115 |
15 | 32.768 | 16.767 | 8.353 | 8.414 | 4.019 | 4.439 | 3.947 | 4.362 |
16 | 65.536 | 34.354 | 17.240 | 17.114 | 8.218 | 8.998 | 8.174 | 8.964 |
17 | 131.072 | 70.383 | 35.199 | 35.184 | 16.919 | 18.270 | 16.760 | 18.434 |
18 | 262.144 | 143.431 | 71.782 | 71.649 | 34.588 | 37.043 | 34.489 | 37.311 |
19 | 524.288 | 291.409 | 145.953 | 145.456 | 70.181 | 75.424 | 70.563 | 75.241 |
20 | 1.048.576 | 590.761 | 295.840 | 294.921 | 142.669 | 152.752 | 143.277 | 152.063 |
21 | 2.097.152 | 1.195.653 | 599.128 | 596.525 | 289.260 | 308.665 | 290.035 | 307.693 |
22 | 4.194.304 | 2.418.320 | 1.211.857 | 1.206.463 | 586.142 | 622.638 | 587.184 | 622.356 |
23 | 8.388.608 | 4.883.506 | 2.447.990 | 2.435.516 | 1.186.568 | 1.253.848 | 1.187.316 | 1.255.774 |
24 | 16.777.216 | 9.850.684 | 4.938.015 | 4.912.669 | 2.398.059 | 2.527.319 | 2.398.175 | 2.527.131 |
25 | 33.554.432 | 19.859.470 | 9.955.316 | 9.904.154 | 4.842.541 | 5.087.522 | 4.841.492 | 5.087.915 |
26 | 67.108.864 | 40.000.978 | 20.040.837 | 19.960.141 | 9.765.153 | 10.236.766 | 9.766.064 | 10.232.995 |
27 | 134.217.728 | 80.522.298 | 40.332.553 | 40.189.745 | 19.677.710 | 20.580.180 | 19.684.228 | 20.580.180 |
28 | 268.435.456 | 162.002.748 | 81.147.191 | 80.855.557 | 39.634.007 | 41.360.018 | 39.644.103 | 41.364.620 |
29 | 536.870.912 | 325.788.815 | 163.177.794 | 162.611.021 | 79.784.280 | 83.103.207 | 79.798.769 | 83.102.559 |
30 | 1.073.741.824 | 654.888.558 | 328.001.699 | 326.886.859 | 160.510.654 | 166.924.508 | 160.529.575 | 166.923.821 |
31 | 2.147.483.648 | 1.315.955.758 | 659.067.840 | 656.887.918 | 322.799.824 | 335.184.253 | 322.816.128 | 335.155.553 |
32 | 4.294.967.296 | 2.643.406.104 | 1.323.834.744 | 1.319.571.360 | 648.916.357 | 672.794.812 | 648.927.938 | 672.766.997 |
33 | 8.589.934.592 | 5.308.347.711 | 2.658.325.633 | 2.650.022.078 | 1.303.972.637 | 1.350.201.984 | 1.304.007.413 | 1.350.165.677 |
34 | 17.179.869.184 | 10.657.023.069 | 5.336.537.054 | 5.320.486.015 | 2.619.489.756 | 2.709.036.119 | 2.619.507.877 | 2.708.989.317 |