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+82x-3
f(0)=3
f(1)=5
f(2)=11
f(3)=7
f(4)=31
f(5)=1
f(6)=1
f(7)=1
f(8)=239
f(9)=17
f(10)=131
f(11)=1
f(12)=1
f(13)=1
f(14)=149
f(15)=1
f(16)=313
f(17)=1
f(18)=599
f(19)=479
f(20)=97
f(21)=1
f(22)=457
f(23)=67
f(24)=1
f(25)=167
f(26)=1
f(27)=1
f(28)=181
f(29)=1
f(30)=373
f(31)=1
f(32)=1
f(33)=79
f(34)=563
f(35)=1
f(36)=283
f(37)=1
f(38)=1
f(39)=1
f(40)=4877
f(41)=1
f(42)=347
f(43)=1
f(44)=1847
f(45)=1
f(46)=107
f(47)=101
f(48)=1
f(49)=401
f(50)=733
f(51)=113
f(52)=199
f(53)=1
f(54)=2447
f(55)=269
f(56)=103
f(57)=1
f(58)=8117
f(59)=1
f(60)=1
f(61)=109
f(62)=1
f(63)=761
f(64)=9341
f(65)=1
f(66)=1
f(67)=499
f(68)=1
f(69)=1
f(70)=967
f(71)=1
f(72)=739
f(73)=1
f(74)=3847
f(75)=1
f(76)=1
f(77)=1
f(78)=4159
f(79)=1
f(80)=617
f(81)=1
f(82)=2689
f(83)=163
f(84)=1549
f(85)=887
f(86)=1
f(87)=1
f(88)=14957
f(89)=317
f(90)=1
f(91)=787
f(92)=1
f(93)=1
f(94)=139
f(95)=467
f(96)=1
f(97)=1
f(98)=5879
f(99)=1493
b) Substitution of the polynom
The polynom f(x)=x^2+82x-3 could be written as f(y)= y^2-1684 with x=y-41
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+41
f'(x)>2x+81
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 | 7 | 2 | 5 | 0.700000 | 0.200000 | 0.500000 | |||
2 | 100 | 50 | 10 | 40 | 0.500000 | 0.100000 | 0.400000 | 7.142857 | 5.000000 | 8.000000 |
3 | 1.000 | 548 | 65 | 483 | 0.548000 | 0.065000 | 0.483000 | 10.960000 | 6.500000 | 12.075000 |
4 | 10.000 | 5.858 | 459 | 5.399 | 0.585800 | 0.045900 | 0.539900 | 10.689781 | 7.061539 | 11.178054 |
5 | 100.000 | 61.031 | 3.636 | 57.395 | 0.610310 | 0.036360 | 0.573950 | 10.418402 | 7.921568 | 10.630672 |
6 | 1.000.000 | 625.033 | 29.559 | 595.474 | 0.625033 | 0.029559 | 0.595474 | 10.241238 | 8.129538 | 10.375015 |
7 | 10.000.000 | 6.351.232 | 247.753 | 6.103.479 | 0.635123 | 0.024775 | 0.610348 | 10.161435 | 8.381643 | 10.249783 |
8 | 100.000.000 | 64.262.119 | 2.138.500 | 62.123.619 | 0.642621 | 0.021385 | 0.621236 | 10.118056 | 8.631580 | 10.178395 |
9 | 1.000.000.000 | 648.406.665 | 18.794.112 | 629.612.553 | 0.648407 | 0.018794 | 0.629613 | 10.090029 | 8.788455 | 10.134833 |
10 | 10.000.000.000 | 6.530.005.666 | 167.628.613 | 6.362.377.053 | 0.653001 | 0.016763 | 0.636238 | 10.070849 | 8.919209 | 10.105227 |
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 | |||
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 6 | 2 | 4 | 0.750000 | 0.250000 | 0.500000 | 1.200000 | 1.000000 | 1.333333 |
4 | 16 | 9 | 2 | 7 | 0.562500 | 0.125000 | 0.437500 | 1.500000 | 1.000000 | 1.750000 |
5 | 32 | 17 | 4 | 13 | 0.531250 | 0.125000 | 0.406250 | 1.888889 | 2.000000 | 1.857143 |
6 | 64 | 34 | 8 | 26 | 0.531250 | 0.125000 | 0.406250 | 2.000000 | 2.000000 | 2.000000 |
7 | 128 | 67 | 12 | 55 | 0.523438 | 0.093750 | 0.429688 | 1.970588 | 1.500000 | 2.115385 |
8 | 256 | 133 | 21 | 112 | 0.519531 | 0.082031 | 0.437500 | 1.985075 | 1.750000 | 2.036364 |
9 | 512 | 270 | 37 | 233 | 0.527344 | 0.072266 | 0.455078 | 2.030075 | 1.761905 | 2.080357 |
10 | 1.024 | 563 | 67 | 496 | 0.549805 | 0.065430 | 0.484375 | 2.085185 | 1.810811 | 2.128755 |
11 | 2.048 | 1.151 | 119 | 1.032 | 0.562012 | 0.058105 | 0.503906 | 2.044405 | 1.776119 | 2.080645 |
12 | 4.096 | 2.337 | 214 | 2.123 | 0.570557 | 0.052246 | 0.518311 | 2.030408 | 1.798319 | 2.057171 |
13 | 8.192 | 4.779 | 387 | 4.392 | 0.583374 | 0.047241 | 0.536133 | 2.044930 | 1.808411 | 2.068771 |
14 | 16.384 | 9.711 | 723 | 8.988 | 0.592712 | 0.044128 | 0.548584 | 2.032015 | 1.868217 | 2.046448 |
15 | 32.768 | 19.672 | 1.350 | 18.322 | 0.600342 | 0.041199 | 0.559143 | 2.025744 | 1.867220 | 2.038496 |
16 | 65.536 | 39.754 | 2.512 | 37.242 | 0.606598 | 0.038330 | 0.568268 | 2.020842 | 1.860741 | 2.032638 |
17 | 131.072 | 80.267 | 4.608 | 75.659 | 0.612389 | 0.035156 | 0.577232 | 2.019092 | 1.834395 | 2.031550 |
18 | 262.144 | 161.706 | 8.691 | 153.015 | 0.616859 | 0.033154 | 0.583706 | 2.014601 | 1.886068 | 2.022429 |
19 | 524.288 | 325.849 | 16.386 | 309.463 | 0.621508 | 0.031254 | 0.590254 | 2.015071 | 1.885399 | 2.022436 |
20 | 1.048.576 | 655.566 | 30.859 | 624.707 | 0.625196 | 0.029429 | 0.595767 | 2.011871 | 1.883254 | 2.018681 |
21 | 2.097.152 | 1.318.121 | 58.438 | 1.259.683 | 0.628529 | 0.027865 | 0.600664 | 2.010661 | 1.893710 | 2.016438 |
22 | 4.194.304 | 2.649.141 | 110.679 | 2.538.462 | 0.631604 | 0.026388 | 0.605217 | 2.009786 | 1.893956 | 2.015159 |
23 | 8.388.608 | 5.322.264 | 210.385 | 5.111.879 | 0.634463 | 0.025080 | 0.609383 | 2.009053 | 1.900857 | 2.013770 |
24 | 16.777.216 | 10.686.927 | 401.656 | 10.285.271 | 0.636990 | 0.023941 | 0.613050 | 2.007966 | 1.909148 | 2.012033 |
25 | 33.554.432 | 21.452.160 | 767.883 | 20.684.277 | 0.639324 | 0.022885 | 0.616439 | 2.007327 | 1.911793 | 2.011058 |
26 | 67.108.864 | 43.047.474 | 1.470.480 | 41.576.994 | 0.641457 | 0.021912 | 0.619545 | 2.006673 | 1.914979 | 2.010077 |
27 | 134.217.728 | 86.361.553 | 2.819.849 | 83.541.704 | 0.643444 | 0.021010 | 0.622434 | 2.006193 | 1.917638 | 2.009325 |
28 | 268.435.456 | 173.216.962 | 5.421.520 | 167.795.442 | 0.645283 | 0.020197 | 0.625087 | 2.005718 | 1.922628 | 2.008523 |
29 | 536.870.912 | 347.346.806 | 10.432.762 | 336.914.044 | 0.646984 | 0.019433 | 0.627551 | 2.005270 | 1.924324 | 2.007886 |
30 | 1.073.741.824 | 696.392.243 | 20.104.878 | 676.287.365 | 0.648566 | 0.018724 | 0.629842 | 2.004890 | 1.927091 | 2.007299 |
31 | 2.147.483.648 | 1.395.967.225 | 38.796.725 | 1.357.170.500 | 0.650048 | 0.018066 | 0.631982 | 2.004570 | 1.929717 | 2.006796 |
32 | 4.294.967.296 | 2.797.865.669 | 74.971.237 | 2.722.894.432 | 0.651429 | 0.017456 | 0.633973 | 2.004249 | 1.932412 | 2.006302 |
33 | 8.589.934.592 | 5.606.884.543 | 145.028.850 | 5.461.855.693 | 0.652727 | 0.016884 | 0.635844 | 2.003986 | 1.934460 | 2.005901 |
34 | 17.179.869.184 | 11.234.680.060 | 280.873.036 | 10.953.807.024 | 0.653944 | 0.016349 | 0.637595 | 2.003730 | 1.936670 | 2.005510 |
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 | 1 | 1 | 0 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 2 | 0 | 1 | 0 | 1 | 1 | 0 |
4 | 16 | 2 | 0 | 1 | 0 | 1 | 1 | 0 |
5 | 32 | 4 | 0 | 3 | 0 | 1 | 1 | 2 |
6 | 64 | 8 | 0 | 7 | 1 | 1 | 4 | 2 |
7 | 128 | 12 | 0 | 11 | 1 | 1 | 7 | 3 |
8 | 256 | 21 | 0 | 20 | 2 | 4 | 12 | 3 |
9 | 512 | 37 | 0 | 36 | 3 | 7 | 20 | 7 |
10 | 1.024 | 67 | 0 | 66 | 7 | 14 | 33 | 13 |
11 | 2.048 | 119 | 0 | 118 | 9 | 24 | 64 | 22 |
12 | 4.096 | 214 | 0 | 213 | 16 | 50 | 112 | 36 |
13 | 8.192 | 387 | 0 | 386 | 26 | 85 | 209 | 67 |
14 | 16.384 | 723 | 0 | 722 | 54 | 145 | 388 | 136 |
15 | 32.768 | 1.350 | 0 | 1.349 | 96 | 267 | 725 | 262 |
16 | 65.536 | 2.512 | 0 | 2.511 | 172 | 499 | 1.342 | 499 |
17 | 131.072 | 4.608 | 0 | 4.607 | 327 | 904 | 2.470 | 907 |
18 | 262.144 | 8.691 | 0 | 8.690 | 592 | 1.680 | 4.705 | 1.714 |
19 | 524.288 | 16.386 | 0 | 16.385 | 1.144 | 3.242 | 8.807 | 3.193 |
20 | 1.048.576 | 30.859 | 0 | 30.858 | 2.100 | 5.972 | 16.802 | 5.985 |
21 | 2.097.152 | 58.438 | 0 | 58.437 | 3.975 | 11.284 | 31.875 | 11.304 |
22 | 4.194.304 | 110.679 | 0 | 110.678 | 7.407 | 21.375 | 60.445 | 21.452 |
23 | 8.388.608 | 210.385 | 0 | 210.384 | 13.929 | 40.608 | 115.114 | 40.734 |
24 | 16.777.216 | 401.656 | 0 | 401.655 | 26.427 | 77.552 | 220.287 | 77.390 |
25 | 33.554.432 | 767.883 | 0 | 767.882 | 50.602 | 147.470 | 421.976 | 147.835 |
26 | 67.108.864 | 1.470.480 | 0 | 1.470.479 | 97.143 | 282.238 | 808.362 | 282.737 |
27 | 134.217.728 | 2.819.849 | 0 | 2.819.848 | 185.656 | 540.654 | 1.551.690 | 541.849 |
28 | 268.435.456 | 5.421.520 | 0 | 5.421.519 | 356.022 | 1.038.910 | 2.986.456 | 1.040.132 |
29 | 536.870.912 | 10.432.762 | 0 | 10.432.761 | 683.391 | 1.997.992 | 5.751.786 | 1.999.593 |
30 | 1.073.741.824 | 20.104.878 | 0 | 20.104.877 | 1.315.069 | 3.848.030 | 11.091.879 | 3.849.900 |
31 | 2.147.483.648 | 38.796.725 | 0 | 38.796.724 | 2.533.872 | 7.419.688 | 21.420.822 | 7.422.343 |
32 | 4.294.967.296 | 74.971.237 | 0 | 74.971.236 | 4.888.813 | 14.330.721 | 41.418.891 | 14.332.812 |
33 | 8.589.934.592 | 145.028.850 | 0 | 145.028.849 | 9.444.093 | 27.703.209 | 80.172.365 | 27.709.183 |
34 | 17.179.869.184 | 280.873.036 | 0 | 280.873.035 | 18.268.326 | 53.622.214 | 155.348.213 | 53.634.283 |
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 | 3 | 2 | 1 | 0 | 1 | 0 | 2 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 0 | 3 |
4 | 16 | 7 | 3 | 4 | 1 | 2 | 1 | 3 |
5 | 32 | 13 | 8 | 5 | 3 | 3 | 3 | 4 |
6 | 64 | 26 | 12 | 14 | 5 | 7 | 6 | 8 |
7 | 128 | 55 | 29 | 26 | 13 | 16 | 12 | 14 |
8 | 256 | 112 | 62 | 50 | 27 | 27 | 29 | 29 |
9 | 512 | 233 | 124 | 109 | 61 | 54 | 49 | 69 |
10 | 1.024 | 496 | 256 | 240 | 125 | 112 | 120 | 139 |
11 | 2.048 | 1.032 | 526 | 506 | 251 | 247 | 257 | 277 |
12 | 4.096 | 2.123 | 1.086 | 1.037 | 515 | 510 | 523 | 575 |
13 | 8.192 | 4.392 | 2.276 | 2.116 | 1.080 | 1.046 | 1.070 | 1.196 |
14 | 16.384 | 8.988 | 4.623 | 4.365 | 2.222 | 2.118 | 2.195 | 2.453 |
15 | 32.768 | 18.322 | 9.374 | 8.948 | 4.550 | 4.376 | 4.450 | 4.946 |
16 | 65.536 | 37.242 | 19.090 | 18.152 | 9.358 | 9.023 | 8.925 | 9.936 |
17 | 131.072 | 75.659 | 38.901 | 36.758 | 19.011 | 18.347 | 18.243 | 20.058 |
18 | 262.144 | 153.015 | 78.316 | 74.699 | 38.301 | 37.374 | 37.058 | 40.282 |
19 | 524.288 | 309.463 | 158.267 | 151.196 | 77.380 | 75.520 | 75.331 | 81.232 |
20 | 1.048.576 | 624.707 | 318.634 | 306.073 | 156.089 | 152.571 | 152.407 | 163.640 |
21 | 2.097.152 | 1.259.683 | 641.558 | 618.125 | 314.978 | 307.853 | 307.658 | 329.194 |
22 | 4.194.304 | 2.538.462 | 1.291.500 | 1.246.962 | 634.679 | 620.714 | 621.400 | 661.669 |
23 | 8.388.608 | 5.111.879 | 2.597.126 | 2.514.753 | 1.278.134 | 1.251.985 | 1.253.398 | 1.328.362 |
24 | 16.777.216 | 10.285.271 | 5.221.038 | 5.064.233 | 2.572.464 | 2.521.928 | 2.523.955 | 2.666.924 |
25 | 33.554.432 | 20.684.277 | 10.493.739 | 10.190.538 | 5.172.793 | 5.078.294 | 5.077.117 | 5.356.073 |
26 | 67.108.864 | 41.576.994 | 21.079.498 | 20.497.496 | 10.397.061 | 10.213.099 | 10.216.351 | 10.750.483 |
27 | 134.217.728 | 83.541.704 | 42.326.615 | 41.215.089 | 20.893.326 | 20.535.842 | 20.541.528 | 21.571.008 |
28 | 268.435.456 | 167.795.442 | 84.965.977 | 82.829.465 | 41.964.619 | 41.271.053 | 41.291.833 | 43.267.937 |
29 | 536.870.912 | 336.914.044 | 170.519.129 | 166.394.915 | 84.258.584 | 82.922.933 | 82.957.127 | 86.775.400 |
30 | 1.073.741.824 | 676.287.365 | 342.109.965 | 334.177.400 | 169.119.708 | 166.560.274 | 166.617.072 | 173.990.311 |
31 | 2.147.483.648 | 1.357.170.500 | 686.228.437 | 670.942.063 | 339.380.981 | 334.435.831 | 334.568.764 | 348.784.924 |
32 | 4.294.967.296 | 2.722.894.432 | 1.376.169.298 | 1.346.725.134 | 680.877.102 | 671.328.395 | 671.608.125 | 699.080.810 |
33 | 8.589.934.592 | 5.461.855.693 | 2.759.361.678 | 2.702.494.015 | 1.365.696.186 | 1.347.283.035 | 1.347.798.071 | 1.401.078.401 |
34 | 17.179.869.184 | 10.953.807.024 | 5.531.941.385 | 5.421.865.639 | 2.738.905.580 | 2.703.220.682 | 2.704.203.653 | 2.807.477.109 |