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-94x+149
f(0)=149
f(1)=7
f(2)=5
f(3)=31
f(4)=211
f(5)=37
f(6)=379
f(7)=23
f(8)=11
f(9)=1
f(10)=691
f(11)=191
f(12)=167
f(13)=113
f(14)=971
f(15)=1
f(16)=157
f(17)=29
f(18)=53
f(19)=1
f(20)=1
f(21)=173
f(22)=41
f(23)=1
f(24)=1531
f(25)=197
f(26)=1619
f(27)=83
f(28)=1699
f(29)=1
f(30)=1
f(31)=1
f(32)=367
f(33)=233
f(34)=61
f(35)=479
f(36)=277
f(37)=1
f(38)=1979
f(39)=499
f(40)=2011
f(41)=1
f(42)=1
f(43)=73
f(44)=293
f(45)=257
f(46)=71
f(47)=103
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)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=541
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-94x+149 could be written as f(y)= y^2-2060 with x=y+47
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-47
f'(x)>2x-95 with x > 45
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 | 5 | 4 | 0.900000 | 0.500000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 32 | 12 | 20 | 0.320000 | 0.120000 | 0.320000 | 3.555556 | 2.400000 | 5.000000 |
3 | 1.000 | 572 | 90 | 482 | 0.572000 | 0.090000 | 0.572000 | 17.875000 | 7.500000 | 24.100000 |
4 | 10.000 | 6.407 | 739 | 5.668 | 0.640700 | 0.073900 | 0.640700 | 11.201049 | 8.211111 | 11.759336 |
5 | 100.000 | 65.768 | 5.660 | 60.108 | 0.657680 | 0.056600 | 0.657680 | 10.265022 | 7.658998 | 10.604799 |
6 | 1.000.000 | 663.996 | 46.372 | 617.624 | 0.663996 | 0.046372 | 0.663996 | 10.096035 | 8.192933 | 10.275238 |
7 | 10.000.000 | 6.683.479 | 392.792 | 6.290.687 | 0.668348 | 0.039279 | 0.668348 | 10.065541 | 8.470456 | 10.185302 |
8 | 100.000.000 | 67.150.818 | 3.408.331 | 63.742.487 | 0.671508 | 0.034083 | 0.671508 | 10.047285 | 8.677191 | 10.132834 |
9 | 1.000.000.000 | 673.927.824 | 30.080.735 | 643.847.089 | 0.673928 | 0.030081 | 0.673928 | 10.036033 | 8.825650 | 10.100753 |
10 | 10.000.000.000 | 6.758.534.457 | 269.185.825 | 6.489.348.632 | 0.675853 | 0.026919 | 0.675853 | 10.028574 | 8.948778 | 10.079021 |
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 | 5 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 14 | 6 | 8 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
5 | 32 | 22 | 9 | 13 | 0.687500 | 0.281250 | 0.406250 | 1.571429 | 1.500000 | 1.625000 |
6 | 64 | 31 | 11 | 20 | 0.484375 | 0.171875 | 0.312500 | 1.409091 | 1.222222 | 1.538462 |
7 | 128 | 43 | 12 | 31 | 0.335938 | 0.093750 | 0.242188 | 1.387097 | 1.090909 | 1.550000 |
8 | 256 | 115 | 27 | 88 | 0.449219 | 0.105469 | 0.343750 | 2.674419 | 2.250000 | 2.838710 |
9 | 512 | 268 | 53 | 215 | 0.523438 | 0.103516 | 0.419922 | 2.330435 | 1.962963 | 2.443182 |
10 | 1.024 | 586 | 91 | 495 | 0.572266 | 0.088867 | 0.483398 | 2.186567 | 1.716981 | 2.302325 |
11 | 2.048 | 1.237 | 167 | 1.070 | 0.604004 | 0.081543 | 0.522461 | 2.110921 | 1.835165 | 2.161616 |
12 | 4.096 | 2.544 | 314 | 2.230 | 0.621094 | 0.076660 | 0.544434 | 2.056588 | 1.880239 | 2.084112 |
13 | 8.192 | 5.206 | 620 | 4.586 | 0.635498 | 0.075684 | 0.559814 | 2.046384 | 1.974522 | 2.056502 |
14 | 16.384 | 10.560 | 1.151 | 9.409 | 0.644531 | 0.070251 | 0.574280 | 2.028429 | 1.856452 | 2.051679 |
15 | 32.768 | 21.360 | 2.074 | 19.286 | 0.651855 | 0.063293 | 0.588562 | 2.022727 | 1.801911 | 2.049740 |
16 | 65.536 | 43.028 | 3.857 | 39.171 | 0.656555 | 0.058853 | 0.597702 | 2.014420 | 1.859691 | 2.031059 |
17 | 131.072 | 86.365 | 7.184 | 79.181 | 0.658913 | 0.054810 | 0.604103 | 2.007181 | 1.862587 | 2.021419 |
18 | 262.144 | 173.258 | 13.520 | 159.738 | 0.660927 | 0.051575 | 0.609352 | 2.006114 | 1.881960 | 2.017378 |
19 | 524.288 | 347.429 | 25.691 | 321.738 | 0.662668 | 0.049002 | 0.613667 | 2.005270 | 1.900222 | 2.014161 |
20 | 1.048.576 | 696.414 | 48.402 | 648.012 | 0.664152 | 0.046160 | 0.617992 | 2.004479 | 1.884006 | 2.014098 |
21 | 2.097.152 | 1.395.929 | 91.884 | 1.304.045 | 0.665631 | 0.043814 | 0.621817 | 2.004453 | 1.898351 | 2.012378 |
22 | 4.194.304 | 2.797.291 | 174.817 | 2.622.474 | 0.666926 | 0.041680 | 0.625247 | 2.003892 | 1.902584 | 2.011030 |
23 | 8.388.608 | 5.604.504 | 333.505 | 5.270.999 | 0.668109 | 0.039757 | 0.628352 | 2.003547 | 1.907738 | 2.009934 |
24 | 16.777.216 | 11.227.194 | 637.340 | 10.589.854 | 0.669193 | 0.037988 | 0.631204 | 2.003245 | 1.911036 | 2.009079 |
25 | 33.554.432 | 22.486.374 | 1.220.376 | 21.265.998 | 0.670146 | 0.036370 | 0.633776 | 2.002849 | 1.914796 | 2.008148 |
26 | 67.108.864 | 45.032.610 | 2.341.806 | 42.690.804 | 0.671038 | 0.034896 | 0.636143 | 2.002662 | 1.918922 | 2.007468 |
27 | 134.217.728 | 90.176.005 | 4.499.389 | 85.676.616 | 0.671864 | 0.033523 | 0.638341 | 2.002460 | 1.921333 | 2.006910 |
28 | 268.435.456 | 180.557.610 | 8.655.722 | 171.901.888 | 0.672630 | 0.032245 | 0.640384 | 2.002280 | 1.923755 | 2.006404 |
29 | 536.870.912 | 361.494.396 | 16.678.527 | 344.815.869 | 0.673336 | 0.031066 | 0.642270 | 2.002100 | 1.926879 | 2.005888 |
30 | 1.073.741.824 | 723.697.204 | 32.182.685 | 691.514.519 | 0.673996 | 0.029972 | 0.644023 | 2.001960 | 1.929588 | 2.005460 |
31 | 2.147.483.648 | 1.448.724.304 | 62.167.796 | 1.386.556.508 | 0.674615 | 0.028949 | 0.645666 | 2.001838 | 1.931716 | 2.005101 |
32 | 4.294.967.296 | 2.899.929.903 | 120.255.810 | 2.779.674.093 | 0.675193 | 0.027999 | 0.647193 | 2.001713 | 1.934375 | 2.004732 |
33 | 8.589.934.592 | 5.804.557.611 | 232.845.525 | 5.571.712.086 | 0.675739 | 0.027107 | 0.648633 | 2.001620 | 1.936252 | 2.004448 |
34 | 17.179.869.184 | 11.617.924.809 | 451.324.347 | 11.166.600.462 | 0.676252 | 0.026271 | 0.649982 | 2.001518 | 1.938300 | 2.004160 |
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 | 2 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 2 | 0 | 2 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 3 | 1 | 0 |
4 | 16 | 6 | 3 | 3 | 0 | 5 | 1 | 0 |
5 | 32 | 9 | 5 | 4 | 0 | 8 | 1 | 0 |
6 | 64 | 11 | 6 | 5 | 0 | 10 | 1 | 0 |
7 | 128 | 12 | 7 | 5 | 0 | 10 | 2 | 0 |
8 | 256 | 27 | 9 | 18 | 0 | 10 | 17 | 0 |
9 | 512 | 53 | 19 | 34 | 0 | 10 | 43 | 0 |
10 | 1.024 | 91 | 31 | 60 | 0 | 10 | 81 | 0 |
11 | 2.048 | 167 | 59 | 108 | 0 | 10 | 157 | 0 |
12 | 4.096 | 314 | 110 | 204 | 0 | 10 | 304 | 0 |
13 | 8.192 | 620 | 214 | 406 | 0 | 10 | 610 | 0 |
14 | 16.384 | 1.151 | 386 | 765 | 0 | 10 | 1.141 | 0 |
15 | 32.768 | 2.074 | 687 | 1.387 | 0 | 10 | 2.064 | 0 |
16 | 65.536 | 3.857 | 1.298 | 2.559 | 0 | 10 | 3.847 | 0 |
17 | 131.072 | 7.184 | 2.407 | 4.777 | 0 | 10 | 7.174 | 0 |
18 | 262.144 | 13.520 | 4.499 | 9.021 | 0 | 10 | 13.510 | 0 |
19 | 524.288 | 25.691 | 8.591 | 17.100 | 0 | 10 | 25.681 | 0 |
20 | 1.048.576 | 48.402 | 16.179 | 32.223 | 0 | 10 | 48.392 | 0 |
21 | 2.097.152 | 91.884 | 30.699 | 61.185 | 0 | 10 | 91.874 | 0 |
22 | 4.194.304 | 174.817 | 58.364 | 116.453 | 0 | 10 | 174.807 | 0 |
23 | 8.388.608 | 333.505 | 110.911 | 222.594 | 0 | 10 | 333.495 | 0 |
24 | 16.777.216 | 637.340 | 212.265 | 425.075 | 0 | 10 | 637.330 | 0 |
25 | 33.554.432 | 1.220.376 | 406.735 | 813.641 | 0 | 10 | 1.220.366 | 0 |
26 | 67.108.864 | 2.341.806 | 779.666 | 1.562.140 | 0 | 10 | 2.341.796 | 0 |
27 | 134.217.728 | 4.499.389 | 1.498.666 | 3.000.723 | 0 | 10 | 4.499.379 | 0 |
28 | 268.435.456 | 8.655.722 | 2.883.734 | 5.771.988 | 0 | 10 | 8.655.712 | 0 |
29 | 536.870.912 | 16.678.527 | 5.558.577 | 11.119.950 | 0 | 10 | 16.678.517 | 0 |
30 | 1.073.741.824 | 32.182.685 | 10.724.235 | 21.458.450 | 0 | 10 | 32.182.675 | 0 |
31 | 2.147.483.648 | 62.167.796 | 20.717.465 | 41.450.331 | 0 | 10 | 62.167.786 | 0 |
32 | 4.294.967.296 | 120.255.810 | 40.079.596 | 80.176.214 | 0 | 10 | 120.255.800 | 0 |
33 | 8.589.934.592 | 232.845.525 | 77.610.266 | 155.235.259 | 0 | 10 | 232.845.515 | 0 |
34 | 17.179.869.184 | 451.324.347 | 150.430.418 | 300.893.929 | 0 | 10 | 451.324.337 | 0 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 2 | 2 | 0 | 0 | 0 | 0 | 2 |
3 | 8 | 4 | 3 | 1 | 0 | 0 | 1 | 3 |
4 | 16 | 8 | 4 | 4 | 1 | 0 | 2 | 5 |
5 | 32 | 13 | 5 | 8 | 1 | 1 | 5 | 6 |
6 | 64 | 20 | 8 | 12 | 3 | 2 | 7 | 8 |
7 | 128 | 31 | 12 | 19 | 6 | 5 | 9 | 11 |
8 | 256 | 88 | 41 | 47 | 19 | 22 | 21 | 26 |
9 | 512 | 215 | 108 | 107 | 50 | 61 | 46 | 58 |
10 | 1.024 | 495 | 246 | 249 | 133 | 137 | 105 | 120 |
11 | 2.048 | 1.070 | 542 | 528 | 291 | 292 | 236 | 251 |
12 | 4.096 | 2.230 | 1.143 | 1.087 | 603 | 609 | 476 | 542 |
13 | 8.192 | 4.586 | 2.347 | 2.239 | 1.207 | 1.254 | 995 | 1.130 |
14 | 16.384 | 9.409 | 4.771 | 4.638 | 2.466 | 2.528 | 2.083 | 2.332 |
15 | 32.768 | 19.286 | 9.712 | 9.574 | 5.026 | 5.232 | 4.284 | 4.744 |
16 | 65.536 | 39.171 | 19.722 | 19.449 | 10.298 | 10.547 | 8.755 | 9.571 |
17 | 131.072 | 79.181 | 39.770 | 39.411 | 20.611 | 21.162 | 17.943 | 19.465 |
18 | 262.144 | 159.738 | 80.251 | 79.487 | 41.603 | 42.304 | 36.485 | 39.346 |
19 | 524.288 | 321.738 | 161.819 | 159.919 | 83.266 | 84.790 | 73.963 | 79.719 |
20 | 1.048.576 | 648.012 | 326.395 | 321.617 | 167.360 | 170.392 | 149.692 | 160.568 |
21 | 2.097.152 | 1.304.045 | 656.017 | 648.028 | 336.515 | 341.430 | 303.205 | 322.895 |
22 | 4.194.304 | 2.622.474 | 1.319.462 | 1.303.012 | 676.015 | 685.159 | 611.400 | 649.900 |
23 | 8.388.608 | 5.270.999 | 2.650.430 | 2.620.569 | 1.355.500 | 1.375.514 | 1.233.329 | 1.306.656 |
24 | 16.777.216 | 10.589.854 | 5.321.462 | 5.268.392 | 2.718.731 | 2.757.777 | 2.486.256 | 2.627.090 |
25 | 33.554.432 | 21.265.998 | 10.685.579 | 10.580.419 | 5.454.369 | 5.525.348 | 5.011.714 | 5.274.567 |
26 | 67.108.864 | 42.690.804 | 21.447.603 | 21.243.201 | 10.939.617 | 11.068.464 | 10.086.879 | 10.595.844 |
27 | 134.217.728 | 85.676.616 | 43.030.792 | 42.645.824 | 21.926.376 | 22.174.871 | 20.301.716 | 21.273.653 |
28 | 268.435.456 | 171.901.888 | 86.324.948 | 85.576.940 | 43.948.592 | 44.430.138 | 40.835.294 | 42.687.864 |
29 | 536.870.912 | 344.815.869 | 173.132.847 | 171.683.022 | 88.073.443 | 88.999.303 | 82.099.825 | 85.643.298 |
30 | 1.073.741.824 | 691.514.519 | 347.164.821 | 344.349.698 | 176.470.290 | 178.264.266 | 164.978.867 | 171.801.096 |
31 | 2.147.483.648 | 1.386.556.508 | 695.983.040 | 690.573.468 | 353.574.553 | 357.020.719 | 331.396.280 | 344.564.956 |
32 | 4.294.967.296 | 2.779.674.093 | 1.395.048.561 | 1.384.625.532 | 708.321.131 | 714.952.442 | 665.513.955 | 690.886.565 |
33 | 8.589.934.592 | 5.571.712.086 | 2.795.962.176 | 2.775.749.910 | 1.418.832.935 | 1.431.644.562 | 1.336.099.075 | 1.385.135.514 |
34 | 17.179.869.184 | 11.166.600.462 | 5.602.929.007 | 5.563.671.455 | 2.841.767.343 | 2.866.588.814 | 2.681.732.022 | 2.776.512.283 |