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-84x-13
f(0)=13
f(1)=3
f(2)=59
f(3)=1
f(4)=37
f(5)=17
f(6)=1
f(7)=23
f(8)=1
f(9)=43
f(10)=251
f(11)=1
f(12)=877
f(13)=1
f(14)=331
f(15)=131
f(16)=367
f(17)=1
f(18)=1201
f(19)=1
f(20)=431
f(21)=167
f(22)=1
f(23)=1
f(24)=1453
f(25)=31
f(26)=1
f(27)=97
f(28)=1
f(29)=67
f(30)=71
f(31)=1
f(32)=1
f(33)=53
f(34)=571
f(35)=1
f(36)=1741
f(37)=73
f(38)=587
f(39)=1
f(40)=197
f(41)=1
f(42)=1777
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=113
f(89)=1
f(90)=1
f(91)=1
f(92)=241
f(93)=103
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=151
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-84x-13 could be written as f(y)= y^2-1777 with x=y+42
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-42
f'(x)>2x-85 with x > 42
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 | 8 | 3 | 5 | 0.800000 | 0.300000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 25 | 11 | 14 | 0.250000 | 0.110000 | 0.140000 | 3.125000 | 3.666667 | 2.800000 |
3 | 1.000 | 533 | 128 | 405 | 0.533000 | 0.128000 | 0.405000 | 21.320000 | 11.636364 | 28.928572 |
4 | 10.000 | 6.114 | 976 | 5.138 | 0.611400 | 0.097600 | 0.513800 | 11.470920 | 7.625000 | 12.686419 |
5 | 100.000 | 63.364 | 7.283 | 56.081 | 0.633640 | 0.072830 | 0.560810 | 10.363755 | 7.462090 | 10.914948 |
6 | 1.000.000 | 644.707 | 58.832 | 585.875 | 0.644707 | 0.058832 | 0.585875 | 10.174658 | 8.077990 | 10.446943 |
7 | 10.000.000 | 6.519.100 | 493.616 | 6.025.484 | 0.651910 | 0.049362 | 0.602548 | 10.111725 | 8.390264 | 10.284590 |
8 | 100.000.000 | 65.725.329 | 4.239.106 | 61.486.223 | 0.657253 | 0.042391 | 0.614862 | 10.081964 | 8.587862 | 10.204363 |
9 | 1.000.000.000 | 661.324.123 | 37.194.015 | 624.130.108 | 0.661324 | 0.037194 | 0.624130 | 10.061936 | 8.774024 | 10.150731 |
10 | 10.000.000.000 | 6.645.707.350 | 331.372.133 | 6.314.335.217 | 0.664571 | 0.033137 | 0.631434 | 10.049093 | 8.909286 | 10.117018 |
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 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.500000 | 1.000000 | 2.000000 |
4 | 16 | 12 | 5 | 7 | 0.750000 | 0.312500 | 0.437500 | 2.000000 | 2.500000 | 1.750000 |
5 | 32 | 19 | 9 | 10 | 0.593750 | 0.281250 | 0.312500 | 1.583333 | 1.800000 | 1.428571 |
6 | 64 | 24 | 11 | 13 | 0.375000 | 0.171875 | 0.203125 | 1.263158 | 1.222222 | 1.300000 |
7 | 128 | 33 | 16 | 17 | 0.257812 | 0.125000 | 0.132812 | 1.375000 | 1.454545 | 1.307692 |
8 | 256 | 100 | 35 | 65 | 0.390625 | 0.136719 | 0.253906 | 3.030303 | 2.187500 | 3.823529 |
9 | 512 | 243 | 70 | 173 | 0.474609 | 0.136719 | 0.337891 | 2.430000 | 2.000000 | 2.661538 |
10 | 1.024 | 545 | 130 | 415 | 0.532227 | 0.126953 | 0.405273 | 2.242798 | 1.857143 | 2.398844 |
11 | 2.048 | 1.165 | 251 | 914 | 0.568848 | 0.122559 | 0.446289 | 2.137615 | 1.930769 | 2.202410 |
12 | 4.096 | 2.424 | 439 | 1.985 | 0.591797 | 0.107178 | 0.484619 | 2.080687 | 1.749004 | 2.171772 |
13 | 8.192 | 4.982 | 819 | 4.163 | 0.608154 | 0.099976 | 0.508179 | 2.055280 | 1.865604 | 2.097229 |
14 | 16.384 | 10.125 | 1.502 | 8.623 | 0.617981 | 0.091675 | 0.526306 | 2.032316 | 1.833944 | 2.071343 |
15 | 32.768 | 20.488 | 2.723 | 17.765 | 0.625244 | 0.083099 | 0.542145 | 2.023506 | 1.812916 | 2.060188 |
16 | 65.536 | 41.335 | 5.002 | 36.333 | 0.630722 | 0.076324 | 0.554398 | 2.017522 | 1.836945 | 2.045201 |
17 | 131.072 | 83.260 | 9.230 | 74.030 | 0.635223 | 0.070419 | 0.564804 | 2.014274 | 1.845262 | 2.037542 |
18 | 262.144 | 167.543 | 17.284 | 150.259 | 0.639126 | 0.065933 | 0.573193 | 2.012287 | 1.872589 | 2.029704 |
19 | 524.288 | 336.594 | 32.586 | 304.008 | 0.642002 | 0.062153 | 0.579849 | 2.009001 | 1.885327 | 2.023226 |
20 | 1.048.576 | 676.117 | 61.420 | 614.697 | 0.644795 | 0.058575 | 0.586221 | 2.008702 | 1.884858 | 2.021976 |
21 | 2.097.152 | 1.357.680 | 115.961 | 1.241.719 | 0.647392 | 0.055295 | 0.592098 | 2.008055 | 1.888001 | 2.020051 |
22 | 4.194.304 | 2.724.355 | 220.502 | 2.503.853 | 0.649537 | 0.052572 | 0.596965 | 2.006625 | 1.901519 | 2.016441 |
23 | 8.388.608 | 5.464.454 | 419.420 | 5.045.034 | 0.651414 | 0.049999 | 0.601415 | 2.005779 | 1.902114 | 2.014908 |
24 | 16.777.216 | 10.959.519 | 798.651 | 10.160.868 | 0.653238 | 0.047603 | 0.605635 | 2.005602 | 1.904180 | 2.014034 |
25 | 33.554.432 | 21.974.884 | 1.523.762 | 20.451.122 | 0.654903 | 0.045412 | 0.609491 | 2.005096 | 1.907920 | 2.012734 |
26 | 67.108.864 | 44.052.542 | 2.915.066 | 41.137.476 | 0.656434 | 0.043438 | 0.612996 | 2.004677 | 1.913072 | 2.011502 |
27 | 134.217.728 | 88.292.520 | 5.589.117 | 82.703.403 | 0.657831 | 0.041642 | 0.616188 | 2.004255 | 1.917321 | 2.010415 |
28 | 268.435.456 | 176.931.144 | 10.734.505 | 166.196.639 | 0.659120 | 0.039989 | 0.619131 | 2.003920 | 1.920608 | 2.009550 |
29 | 536.870.912 | 354.505.914 | 20.653.094 | 333.852.820 | 0.660319 | 0.038469 | 0.621849 | 2.003638 | 1.923991 | 2.008782 |
30 | 1.073.741.824 | 710.212.189 | 39.785.026 | 670.427.163 | 0.661437 | 0.037053 | 0.624384 | 2.003386 | 1.926347 | 2.008152 |
31 | 2.147.483.648 | 1.422.670.850 | 76.752.895 | 1.345.917.955 | 0.662483 | 0.035741 | 0.626742 | 2.003163 | 1.929191 | 2.007553 |
32 | 4.294.967.296 | 2.849.543.760 | 148.252.565 | 2.701.291.195 | 0.663461 | 0.034518 | 0.628943 | 2.002954 | 1.931557 | 2.007025 |
33 | 8.589.934.592 | 5.706.958.081 | 286.712.589 | 5.420.245.492 | 0.664377 | 0.033378 | 0.631000 | 2.002762 | 1.933947 | 2.006539 |
34 | 17.179.869.184 | 11.428.686.192 | 555.117.927 | 10.873.568.265 | 0.665237 | 0.032312 | 0.632925 | 2.002588 | 1.936148 | 2.006103 |
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 | 1 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
4 | 16 | 5 | 3 | 1 | 0 | 3 | 2 | 0 |
5 | 32 | 9 | 6 | 2 | 2 | 3 | 3 | 1 |
6 | 64 | 11 | 8 | 2 | 3 | 3 | 4 | 1 |
7 | 128 | 16 | 9 | 6 | 3 | 4 | 5 | 4 |
8 | 256 | 35 | 17 | 17 | 7 | 11 | 7 | 10 |
9 | 512 | 70 | 29 | 40 | 13 | 24 | 10 | 23 |
10 | 1.024 | 130 | 51 | 78 | 24 | 44 | 16 | 46 |
11 | 2.048 | 251 | 90 | 160 | 35 | 89 | 30 | 97 |
12 | 4.096 | 439 | 161 | 277 | 61 | 152 | 62 | 164 |
13 | 8.192 | 819 | 297 | 521 | 109 | 302 | 107 | 301 |
14 | 16.384 | 1.502 | 536 | 965 | 207 | 540 | 205 | 550 |
15 | 32.768 | 2.723 | 992 | 1.730 | 370 | 976 | 385 | 992 |
16 | 65.536 | 5.002 | 1.788 | 3.213 | 666 | 1.813 | 683 | 1.840 |
17 | 131.072 | 9.230 | 3.265 | 5.964 | 1.231 | 3.350 | 1.262 | 3.387 |
18 | 262.144 | 17.284 | 6.068 | 11.215 | 2.302 | 6.312 | 2.320 | 6.350 |
19 | 524.288 | 32.586 | 11.441 | 21.144 | 4.347 | 11.946 | 4.310 | 11.983 |
20 | 1.048.576 | 61.420 | 21.497 | 39.922 | 8.142 | 22.553 | 8.135 | 22.590 |
21 | 2.097.152 | 115.961 | 40.430 | 75.530 | 15.275 | 42.598 | 15.307 | 42.781 |
22 | 4.194.304 | 220.502 | 76.755 | 143.746 | 28.895 | 81.198 | 29.136 | 81.273 |
23 | 8.388.608 | 419.420 | 145.549 | 273.870 | 54.825 | 154.654 | 55.238 | 154.703 |
24 | 16.777.216 | 798.651 | 276.635 | 522.015 | 104.247 | 294.396 | 104.769 | 295.239 |
25 | 33.554.432 | 1.523.762 | 526.523 | 997.238 | 198.898 | 562.365 | 199.138 | 563.361 |
26 | 67.108.864 | 2.915.066 | 1.005.251 | 1.909.814 | 379.687 | 1.077.853 | 379.915 | 1.077.611 |
27 | 134.217.728 | 5.589.117 | 1.925.559 | 3.663.557 | 727.170 | 2.067.408 | 727.380 | 2.067.159 |
28 | 268.435.456 | 10.734.505 | 3.694.527 | 7.039.977 | 1.395.633 | 3.973.358 | 1.394.591 | 3.970.923 |
29 | 536.870.912 | 20.653.094 | 7.101.059 | 13.552.034 | 2.681.464 | 7.647.138 | 2.679.657 | 7.644.835 |
30 | 1.073.741.824 | 39.785.026 | 13.664.450 | 26.120.575 | 5.158.586 | 14.735.977 | 5.156.115 | 14.734.348 |
31 | 2.147.483.648 | 76.752.895 | 26.331.347 | 50.421.547 | 9.935.541 | 28.440.903 | 9.934.429 | 28.442.022 |
32 | 4.294.967.296 | 148.252.565 | 50.814.862 | 97.437.702 | 19.171.092 | 54.953.664 | 19.167.445 | 54.960.364 |
33 | 8.589.934.592 | 286.712.589 | 98.176.879 | 188.535.709 | 37.032.362 | 106.320.687 | 37.027.897 | 106.331.643 |
34 | 17.179.869.184 | 555.117.927 | 189.935.243 | 365.182.683 | 71.626.207 | 205.922.894 | 71.612.822 | 205.956.004 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 3 | 1 | 1 | 1 | 1 |
4 | 16 | 7 | 3 | 4 | 1 | 3 | 1 | 2 |
5 | 32 | 10 | 4 | 6 | 1 | 4 | 1 | 4 |
6 | 64 | 13 | 5 | 8 | 1 | 6 | 2 | 4 |
7 | 128 | 17 | 7 | 10 | 3 | 7 | 3 | 4 |
8 | 256 | 65 | 30 | 35 | 19 | 14 | 17 | 15 |
9 | 512 | 173 | 84 | 89 | 54 | 32 | 52 | 35 |
10 | 1.024 | 415 | 202 | 213 | 106 | 93 | 122 | 94 |
11 | 2.048 | 914 | 464 | 450 | 245 | 198 | 271 | 200 |
12 | 4.096 | 1.985 | 993 | 992 | 509 | 457 | 579 | 440 |
13 | 8.192 | 4.163 | 2.074 | 2.089 | 1.119 | 948 | 1.152 | 944 |
14 | 16.384 | 8.623 | 4.231 | 4.392 | 2.306 | 1.997 | 2.335 | 1.985 |
15 | 32.768 | 17.765 | 8.759 | 9.006 | 4.688 | 4.176 | 4.765 | 4.136 |
16 | 65.536 | 36.333 | 18.048 | 18.285 | 9.589 | 8.488 | 9.710 | 8.546 |
17 | 131.072 | 74.030 | 37.047 | 36.983 | 19.502 | 17.321 | 19.818 | 17.389 |
18 | 262.144 | 150.259 | 75.128 | 75.131 | 39.471 | 35.348 | 39.862 | 35.578 |
19 | 524.288 | 304.008 | 151.659 | 152.349 | 79.581 | 72.106 | 80.260 | 72.061 |
20 | 1.048.576 | 614.697 | 306.047 | 308.650 | 160.535 | 146.389 | 161.259 | 146.514 |
21 | 2.097.152 | 1.241.719 | 619.127 | 622.592 | 323.969 | 296.688 | 324.397 | 296.665 |
22 | 4.194.304 | 2.503.853 | 1.249.315 | 1.254.538 | 652.428 | 599.717 | 652.385 | 599.323 |
23 | 8.388.608 | 5.045.034 | 2.517.597 | 2.527.437 | 1.312.278 | 1.210.334 | 1.312.313 | 1.210.109 |
24 | 16.777.216 | 10.160.868 | 5.069.929 | 5.090.939 | 2.637.714 | 2.442.804 | 2.637.627 | 2.442.723 |
25 | 33.554.432 | 20.451.122 | 10.206.458 | 10.244.664 | 5.297.675 | 4.925.946 | 5.299.480 | 4.928.021 |
26 | 67.108.864 | 41.137.476 | 20.530.547 | 20.606.929 | 10.642.644 | 9.927.966 | 10.644.392 | 9.922.474 |
27 | 134.217.728 | 82.703.403 | 41.280.734 | 41.422.669 | 21.364.327 | 19.990.583 | 21.365.824 | 19.982.669 |
28 | 268.435.456 | 166.196.639 | 82.963.641 | 83.232.998 | 42.872.260 | 40.230.881 | 42.876.759 | 40.216.739 |
29 | 536.870.912 | 333.852.820 | 166.677.781 | 167.175.039 | 86.019.589 | 80.915.950 | 85.999.092 | 80.918.189 |
30 | 1.073.741.824 | 670.427.163 | 334.748.380 | 335.678.783 | 172.529.560 | 162.695.933 | 172.509.853 | 162.691.817 |
31 | 2.147.483.648 | 1.345.917.955 | 672.038.669 | 673.879.286 | 345.965.366 | 327.014.056 | 345.946.234 | 326.992.299 |
32 | 4.294.967.296 | 2.701.291.195 | 1.348.840.823 | 1.352.450.372 | 693.633.610 | 657.031.347 | 693.617.329 | 657.008.909 |
33 | 8.589.934.592 | 5.420.245.492 | 2.706.644.932 | 2.713.600.560 | 1.390.455.030 | 1.319.633.725 | 1.390.531.864 | 1.319.624.873 |
34 | 17.179.869.184 | 10.873.568.265 | 5.430.059.199 | 5.443.509.066 | 2.786.968.809 | 2.649.754.254 | 2.787.071.459 | 2.649.773.743 |