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+9x-83
f(0)=83
f(1)=73
f(2)=61
f(3)=47
f(4)=31
f(5)=13
f(6)=7
f(7)=29
f(8)=53
f(9)=79
f(10)=107
f(11)=137
f(12)=1
f(13)=1
f(14)=239
f(15)=277
f(16)=317
f(17)=359
f(18)=1
f(19)=449
f(20)=71
f(21)=547
f(22)=599
f(23)=653
f(24)=709
f(25)=59
f(26)=827
f(27)=127
f(28)=953
f(29)=1019
f(30)=1087
f(31)=89
f(32)=1229
f(33)=1303
f(34)=197
f(35)=1
f(36)=1
f(37)=1619
f(38)=131
f(39)=1789
f(40)=1877
f(41)=281
f(42)=1
f(43)=2153
f(44)=173
f(45)=2347
f(46)=2447
f(47)=2549
f(48)=379
f(49)=1
f(50)=1
f(51)=229
f(52)=3089
f(53)=3203
f(54)=3319
f(55)=491
f(56)=3557
f(57)=283
f(58)=3803
f(59)=3929
f(60)=4057
f(61)=1
f(62)=617
f(63)=1
f(64)=353
f(65)=163
f(66)=157
f(67)=5009
f(68)=5153
f(69)=757
f(70)=419
f(71)=193
f(72)=5749
f(73)=5903
f(74)=1
f(75)=6217
f(76)=911
f(77)=503
f(78)=6703
f(79)=6869
f(80)=227
f(81)=7207
f(82)=1
f(83)=1
f(84)=1
f(85)=7907
f(86)=8087
f(87)=8269
f(88)=1
f(89)=1
f(90)=97
f(91)=1
f(92)=9209
f(93)=9403
f(94)=331
f(95)=101
f(96)=769
f(97)=1
f(98)=103
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+9x-83 could be written as f(y)= y^2-103.25 with x=y-4.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+4.5
f'(x)>2x+8
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 | 11 | 11 | 0 | 1.100000 | 1.100000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 79 | 55 | 24 | 0.790000 | 0.550000 | 0.790000 | 7.181818 | 5.000000 | inf |
3 | 1.000 | 762 | 350 | 412 | 0.762000 | 0.350000 | 0.762000 | 9.645570 | 6.363636 | 17.166666 |
4 | 10.000 | 7.416 | 2.417 | 4.999 | 0.741600 | 0.241700 | 0.741600 | 9.732284 | 6.905715 | 12.133495 |
5 | 100.000 | 73.442 | 18.773 | 54.669 | 0.734420 | 0.187730 | 0.734420 | 9.903182 | 7.767066 | 10.935987 |
6 | 1.000.000 | 727.502 | 152.825 | 574.677 | 0.727502 | 0.152825 | 0.727502 | 9.905804 | 8.140680 | 10.511935 |
7 | 10.000.000 | 7.225.087 | 1.291.803 | 5.933.284 | 0.722509 | 0.129180 | 0.722509 | 9.931364 | 8.452826 | 10.324554 |
8 | 100.000.000 | 71.858.749 | 11.203.038 | 60.655.711 | 0.718588 | 0.112030 | 0.718588 | 9.945728 | 8.672404 | 10.222958 |
9 | 1.000.000.000 | 715.594.318 | 98.881.147 | 616.713.171 | 0.715594 | 0.098881 | 0.715594 | 9.958345 | 8.826280 | 10.167438 |
10 | 10.000.000.000 | 7.132.546.919 | 884.927.038 | 6.247.619.881 | 0.713255 | 0.088493 | 0.713255 | 9.967305 | 8.949401 | 10.130512 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 15 | 15 | 0 | 0.937500 | 0.937500 | 0.000000 | 1.666667 | 1.666667 | -nan |
5 | 32 | 30 | 27 | 3 | 0.937500 | 0.843750 | 0.093750 | 2.000000 | 1.800000 | inf |
6 | 64 | 55 | 42 | 13 | 0.859375 | 0.656250 | 0.203125 | 1.833333 | 1.555556 | 4.333333 |
7 | 128 | 103 | 68 | 35 | 0.804688 | 0.531250 | 0.273438 | 1.872727 | 1.619048 | 2.692308 |
8 | 256 | 198 | 115 | 83 | 0.773438 | 0.449219 | 0.324219 | 1.922330 | 1.691176 | 2.371428 |
9 | 512 | 398 | 201 | 197 | 0.777344 | 0.392578 | 0.384766 | 2.010101 | 1.747826 | 2.373494 |
10 | 1.024 | 780 | 355 | 425 | 0.761719 | 0.346680 | 0.415039 | 1.959799 | 1.766169 | 2.157360 |
11 | 2.048 | 1.545 | 627 | 918 | 0.754395 | 0.306152 | 0.448242 | 1.980769 | 1.766197 | 2.160000 |
12 | 4.096 | 3.055 | 1.114 | 1.941 | 0.745850 | 0.271973 | 0.473877 | 1.977346 | 1.776715 | 2.114379 |
13 | 8.192 | 6.098 | 2.022 | 4.076 | 0.744385 | 0.246826 | 0.497559 | 1.996072 | 1.815081 | 2.099948 |
14 | 16.384 | 12.150 | 3.700 | 8.450 | 0.741577 | 0.225830 | 0.515747 | 1.992457 | 1.829871 | 2.073111 |
15 | 32.768 | 24.190 | 6.870 | 17.320 | 0.738220 | 0.209656 | 0.528564 | 1.990947 | 1.856757 | 2.049704 |
16 | 65.536 | 48.239 | 12.796 | 35.443 | 0.736069 | 0.195251 | 0.540817 | 1.994171 | 1.862591 | 2.046363 |
17 | 131.072 | 96.161 | 23.894 | 72.267 | 0.733650 | 0.182297 | 0.551353 | 1.993429 | 1.867302 | 2.038964 |
18 | 262.144 | 191.842 | 44.756 | 147.086 | 0.731819 | 0.170731 | 0.561089 | 1.995008 | 1.873106 | 2.035314 |
19 | 524.288 | 382.438 | 84.515 | 297.923 | 0.729443 | 0.161200 | 0.568243 | 1.993505 | 1.888350 | 2.025502 |
20 | 1.048.576 | 762.769 | 159.665 | 603.104 | 0.727433 | 0.152268 | 0.575165 | 1.994491 | 1.889191 | 2.024362 |
21 | 2.097.152 | 1.522.255 | 302.305 | 1.219.950 | 0.725868 | 0.144150 | 0.581717 | 1.995696 | 1.893371 | 2.022785 |
22 | 4.194.304 | 3.037.862 | 575.565 | 2.462.297 | 0.724283 | 0.137225 | 0.587057 | 1.995633 | 1.903921 | 2.018359 |
23 | 8.388.608 | 6.063.775 | 1.096.766 | 4.967.009 | 0.722858 | 0.130745 | 0.592114 | 1.996067 | 1.905547 | 2.017226 |
24 | 16.777.216 | 12.103.906 | 2.096.923 | 10.006.983 | 0.721449 | 0.124986 | 0.596463 | 1.996101 | 1.911915 | 2.014690 |
25 | 33.554.432 | 24.168.193 | 4.013.107 | 20.155.086 | 0.720268 | 0.119600 | 0.600668 | 1.996727 | 1.913808 | 2.014102 |
26 | 67.108.864 | 48.262.835 | 7.696.852 | 40.565.983 | 0.719172 | 0.114692 | 0.604480 | 1.996957 | 1.917928 | 2.012692 |
27 | 134.217.728 | 96.389.770 | 14.786.832 | 81.602.938 | 0.718160 | 0.110170 | 0.607989 | 1.997184 | 1.921153 | 2.011610 |
28 | 268.435.456 | 192.525.961 | 28.447.878 | 164.078.083 | 0.717215 | 0.105977 | 0.611238 | 1.997369 | 1.923866 | 2.010689 |
29 | 536.870.912 | 384.576.610 | 54.824.261 | 329.752.349 | 0.716330 | 0.102118 | 0.614212 | 1.997531 | 1.927183 | 2.009728 |
30 | 1.073.741.824 | 768.278.876 | 105.789.158 | 662.489.718 | 0.715515 | 0.098524 | 0.616992 | 1.997726 | 1.929605 | 2.009052 |
31 | 2.147.483.648 | 1.534.941.065 | 204.382.240 | 1.330.558.825 | 0.714763 | 0.095173 | 0.619590 | 1.997896 | 1.931977 | 2.008422 |
32 | 4.294.967.296 | 3.066.850.957 | 395.313.712 | 2.671.537.245 | 0.714057 | 0.092041 | 0.622016 | 1.998025 | 1.934188 | 2.007831 |
33 | 8.589.934.592 | 6.128.003.223 | 765.439.278 | 5.362.563.945 | 0.713393 | 0.089109 | 0.624285 | 1.998142 | 1.936283 | 2.007295 |
34 | 17.179.869.184 | 12.245.337.548 | 1.483.642.796 | 10.761.694.752 | 0.712772 | 0.086359 | 0.626413 | 1.998259 | 1.938289 | 2.006819 |
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 | 3 | 2 | 1 | 1 | 1 | 1 | 0 |
2 | 4 | 5 | 3 | 2 | 1 | 1 | 1 | 2 |
3 | 8 | 9 | 5 | 4 | 1 | 1 | 4 | 3 |
4 | 16 | 15 | 7 | 8 | 2 | 2 | 6 | 5 |
5 | 32 | 27 | 10 | 17 | 4 | 5 | 9 | 9 |
6 | 64 | 42 | 15 | 27 | 8 | 9 | 13 | 12 |
7 | 128 | 68 | 25 | 43 | 15 | 13 | 19 | 21 |
8 | 256 | 115 | 40 | 75 | 27 | 28 | 26 | 34 |
9 | 512 | 201 | 70 | 131 | 51 | 46 | 53 | 51 |
10 | 1.024 | 355 | 117 | 238 | 92 | 87 | 93 | 83 |
11 | 2.048 | 627 | 209 | 418 | 160 | 158 | 160 | 149 |
12 | 4.096 | 1.114 | 371 | 743 | 279 | 295 | 278 | 262 |
13 | 8.192 | 2.022 | 678 | 1.344 | 500 | 527 | 501 | 494 |
14 | 16.384 | 3.700 | 1.245 | 2.455 | 921 | 933 | 920 | 926 |
15 | 32.768 | 6.870 | 2.302 | 4.568 | 1.726 | 1.738 | 1.703 | 1.703 |
16 | 65.536 | 12.796 | 4.290 | 8.506 | 3.235 | 3.217 | 3.207 | 3.137 |
17 | 131.072 | 23.894 | 7.965 | 15.929 | 6.047 | 5.981 | 5.963 | 5.903 |
18 | 262.144 | 44.756 | 14.924 | 29.832 | 11.241 | 11.218 | 11.105 | 11.192 |
19 | 524.288 | 84.515 | 28.177 | 56.338 | 21.135 | 21.181 | 21.079 | 21.120 |
20 | 1.048.576 | 159.665 | 53.360 | 106.305 | 39.850 | 39.955 | 39.958 | 39.902 |
21 | 2.097.152 | 302.305 | 100.798 | 201.507 | 75.539 | 75.465 | 75.572 | 75.729 |
22 | 4.194.304 | 575.565 | 191.834 | 383.731 | 143.863 | 143.748 | 143.851 | 144.103 |
23 | 8.388.608 | 1.096.766 | 365.876 | 730.890 | 274.002 | 273.865 | 274.337 | 274.562 |
24 | 16.777.216 | 2.096.923 | 699.442 | 1.397.481 | 523.801 | 523.930 | 524.364 | 524.828 |
25 | 33.554.432 | 4.013.107 | 1.338.164 | 2.674.943 | 1.003.084 | 1.002.161 | 1.003.596 | 1.004.266 |
26 | 67.108.864 | 7.696.852 | 2.566.735 | 5.130.117 | 1.923.977 | 1.923.043 | 1.925.080 | 1.924.752 |
27 | 134.217.728 | 14.786.832 | 4.928.464 | 9.858.368 | 3.697.716 | 3.694.249 | 3.697.757 | 3.697.110 |
28 | 268.435.456 | 28.447.878 | 9.482.252 | 18.965.626 | 7.111.870 | 7.108.934 | 7.113.927 | 7.113.147 |
29 | 536.870.912 | 54.824.261 | 18.272.422 | 36.551.839 | 13.703.743 | 13.702.657 | 13.709.044 | 13.708.817 |
30 | 1.073.741.824 | 105.789.158 | 35.263.550 | 70.525.608 | 26.440.777 | 26.446.039 | 26.450.867 | 26.451.475 |
31 | 2.147.483.648 | 204.382.240 | 68.129.527 | 136.252.713 | 51.092.806 | 51.095.435 | 51.097.160 | 51.096.839 |
32 | 4.294.967.296 | 395.313.712 | 131.777.078 | 263.536.634 | 98.829.961 | 98.825.776 | 98.825.579 | 98.832.396 |
33 | 8.589.934.592 | 765.439.278 | 255.142.988 | 510.296.290 | 191.366.210 | 191.355.361 | 191.361.649 | 191.356.058 |
34 | 17.179.869.184 | 1.483.642.796 | 494.537.839 | 989.104.957 | 370.920.200 | 370.904.912 | 370.904.680 | 370.913.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 | 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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 3 | 1 | 2 | 1 | 0 | 0 | 2 |
6 | 64 | 13 | 4 | 9 | 4 | 4 | 3 | 2 |
7 | 128 | 35 | 11 | 24 | 8 | 10 | 10 | 7 |
8 | 256 | 83 | 35 | 48 | 20 | 20 | 20 | 23 |
9 | 512 | 197 | 87 | 110 | 45 | 49 | 45 | 58 |
10 | 1.024 | 425 | 202 | 223 | 96 | 117 | 112 | 100 |
11 | 2.048 | 918 | 427 | 491 | 222 | 238 | 228 | 230 |
12 | 4.096 | 1.941 | 928 | 1.013 | 482 | 515 | 462 | 482 |
13 | 8.192 | 4.076 | 1.992 | 2.084 | 1.017 | 1.036 | 1.018 | 1.005 |
14 | 16.384 | 8.450 | 4.075 | 4.375 | 2.119 | 2.132 | 2.107 | 2.092 |
15 | 32.768 | 17.320 | 8.389 | 8.931 | 4.350 | 4.368 | 4.338 | 4.264 |
16 | 65.536 | 35.443 | 17.262 | 18.181 | 8.900 | 8.948 | 8.845 | 8.750 |
17 | 131.072 | 72.267 | 35.239 | 37.028 | 18.071 | 18.125 | 18.113 | 17.958 |
18 | 262.144 | 147.086 | 71.868 | 75.218 | 36.575 | 36.840 | 36.966 | 36.705 |
19 | 524.288 | 297.923 | 145.972 | 151.951 | 74.467 | 74.403 | 74.714 | 74.339 |
20 | 1.048.576 | 603.104 | 295.486 | 307.618 | 150.894 | 150.637 | 150.698 | 150.875 |
21 | 2.097.152 | 1.219.950 | 598.158 | 621.792 | 305.033 | 304.949 | 304.652 | 305.316 |
22 | 4.194.304 | 2.462.297 | 1.210.690 | 1.251.607 | 615.762 | 615.496 | 615.184 | 615.855 |
23 | 8.388.608 | 4.967.009 | 2.441.673 | 2.525.336 | 1.242.521 | 1.241.179 | 1.240.992 | 1.242.317 |
24 | 16.777.216 | 10.006.983 | 4.925.469 | 5.081.514 | 2.503.963 | 2.500.129 | 2.500.050 | 2.502.841 |
25 | 33.554.432 | 20.155.086 | 9.930.185 | 10.224.901 | 5.040.930 | 5.039.032 | 5.036.444 | 5.038.680 |
26 | 67.108.864 | 40.565.983 | 19.998.592 | 20.567.391 | 10.143.561 | 10.141.736 | 10.139.538 | 10.141.148 |
27 | 134.217.728 | 81.602.938 | 40.250.123 | 41.352.815 | 20.401.726 | 20.399.570 | 20.399.304 | 20.402.338 |
28 | 268.435.456 | 164.078.083 | 80.987.870 | 83.090.213 | 41.024.546 | 41.016.241 | 41.017.839 | 41.019.457 |
29 | 536.870.912 | 329.752.349 | 162.853.956 | 166.898.393 | 82.440.750 | 82.438.478 | 82.435.505 | 82.437.616 |
30 | 1.073.741.824 | 662.489.718 | 327.338.136 | 335.151.582 | 165.612.752 | 165.622.958 | 165.620.836 | 165.633.172 |
31 | 2.147.483.648 | 1.330.558.825 | 657.740.927 | 672.817.898 | 332.617.110 | 332.647.533 | 332.625.638 | 332.668.544 |
32 | 4.294.967.296 | 2.671.537.245 | 1.321.203.503 | 1.350.333.742 | 667.855.236 | 667.891.856 | 667.897.098 | 667.893.055 |
33 | 8.589.934.592 | 5.362.563.945 | 2.653.084.569 | 2.709.479.376 | 1.340.638.920 | 1.340.647.619 | 1.340.627.366 | 1.340.650.040 |
34 | 17.179.869.184 | 10.761.694.752 | 5.326.133.148 | 5.435.561.604 | 2.690.432.091 | 2.690.434.285 | 2.690.435.228 | 2.690.393.148 |