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+108x+83
f(0)=83
f(1)=3
f(2)=101
f(3)=13
f(4)=59
f(5)=1
f(6)=1
f(7)=37
f(8)=337
f(9)=71
f(10)=421
f(11)=29
f(12)=1523
f(13)=23
f(14)=199
f(15)=241
f(16)=53
f(17)=1
f(18)=2351
f(19)=1
f(20)=881
f(21)=349
f(22)=109
f(23)=43
f(24)=3251
f(25)=1
f(26)=41
f(27)=233
f(28)=1297
f(29)=1
f(30)=103
f(31)=61
f(32)=1
f(33)=1
f(34)=1637
f(35)=1
f(36)=229
f(37)=227
f(38)=1877
f(39)=727
f(40)=1
f(41)=1
f(42)=491
f(43)=137
f(44)=1
f(45)=67
f(46)=2389
f(47)=307
f(48)=113
f(49)=1
f(50)=887
f(51)=1
f(52)=2801
f(53)=359
f(54)=8831
f(55)=1
f(56)=3089
f(57)=593
f(58)=1
f(59)=1
f(60)=10163
f(61)=433
f(62)=3541
f(63)=1
f(64)=3697
f(65)=1
f(66)=269
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=13043
f(73)=277
f(74)=4517
f(75)=863
f(76)=521
f(77)=1
f(78)=14591
f(79)=619
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=2131
f(88)=1
f(89)=367
f(90)=17903
f(91)=379
f(92)=1
f(93)=2347
f(94)=163
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=643
b) Substitution of the polynom
The polynom f(x)=x^2+108x+83 could be written as f(y)= y^2-2833 with x=y-54
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+54
f'(x)>2x+107
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 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 57 | 21 | 36 | 0.570000 | 0.210000 | 0.360000 | 6.333333 | 5.250000 | 7.200000 |
3 | 1.000 | 585 | 133 | 452 | 0.585000 | 0.133000 | 0.452000 | 10.263158 | 6.333333 | 12.555555 |
4 | 10.000 | 6.184 | 978 | 5.206 | 0.618400 | 0.097800 | 0.520600 | 10.570940 | 7.353384 | 11.517699 |
5 | 100.000 | 63.515 | 7.631 | 55.884 | 0.635150 | 0.076310 | 0.558840 | 10.270861 | 7.802659 | 10.734537 |
6 | 1.000.000 | 645.845 | 61.333 | 584.512 | 0.645845 | 0.061333 | 0.584512 | 10.168386 | 8.037348 | 10.459380 |
7 | 10.000.000 | 6.529.584 | 511.879 | 6.017.705 | 0.652958 | 0.051188 | 0.601771 | 10.110141 | 8.345899 | 10.295263 |
8 | 100.000.000 | 65.809.754 | 4.406.365 | 61.403.389 | 0.658098 | 0.044064 | 0.614034 | 10.078705 | 8.608216 | 10.203789 |
9 | 1.000.000.000 | 662.085.224 | 38.671.960 | 623.413.264 | 0.662085 | 0.038672 | 0.623413 | 10.060595 | 8.776386 | 10.152750 |
10 | 10.000.000.000 | 6.652.547.845 | 344.610.718 | 6.307.937.127 | 0.665255 | 0.034461 | 0.630794 | 10.047873 | 8.911126 | 10.118388 |
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 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.400000 | 1.000000 | 2.000000 |
4 | 16 | 14 | 6 | 8 | 0.875000 | 0.375000 | 0.500000 | 2.000000 | 2.000000 | 2.000000 |
5 | 32 | 22 | 10 | 12 | 0.687500 | 0.312500 | 0.375000 | 1.571429 | 1.666667 | 1.500000 |
6 | 64 | 42 | 14 | 28 | 0.656250 | 0.218750 | 0.437500 | 1.909091 | 1.400000 | 2.333333 |
7 | 128 | 72 | 26 | 46 | 0.562500 | 0.203125 | 0.359375 | 1.714286 | 1.857143 | 1.642857 |
8 | 256 | 147 | 42 | 105 | 0.574219 | 0.164062 | 0.410156 | 2.041667 | 1.615385 | 2.282609 |
9 | 512 | 301 | 77 | 224 | 0.587891 | 0.150391 | 0.437500 | 2.047619 | 1.833333 | 2.133333 |
10 | 1.024 | 597 | 135 | 462 | 0.583008 | 0.131836 | 0.451172 | 1.983389 | 1.753247 | 2.062500 |
11 | 2.048 | 1.219 | 252 | 967 | 0.595215 | 0.123047 | 0.472168 | 2.041876 | 1.866667 | 2.093074 |
12 | 4.096 | 2.507 | 447 | 2.060 | 0.612061 | 0.109131 | 0.502930 | 2.056604 | 1.773810 | 2.130300 |
13 | 8.192 | 5.070 | 830 | 4.240 | 0.618896 | 0.101318 | 0.517578 | 2.022337 | 1.856823 | 2.058252 |
14 | 16.384 | 10.246 | 1.519 | 8.727 | 0.625366 | 0.092712 | 0.532654 | 2.020907 | 1.830120 | 2.058255 |
15 | 32.768 | 20.631 | 2.793 | 17.838 | 0.629608 | 0.085236 | 0.544373 | 2.013566 | 1.838710 | 2.044001 |
16 | 65.536 | 41.504 | 5.219 | 36.285 | 0.633301 | 0.079636 | 0.553665 | 2.011730 | 1.868600 | 2.034141 |
17 | 131.072 | 83.519 | 9.723 | 73.796 | 0.637199 | 0.074181 | 0.563019 | 2.012312 | 1.863001 | 2.033788 |
18 | 262.144 | 167.817 | 18.136 | 149.681 | 0.640171 | 0.069183 | 0.570988 | 2.009327 | 1.865268 | 2.028308 |
19 | 524.288 | 337.251 | 34.002 | 303.249 | 0.643255 | 0.064854 | 0.578402 | 2.009635 | 1.874835 | 2.025969 |
20 | 1.048.576 | 677.413 | 64.040 | 613.373 | 0.646031 | 0.061073 | 0.584958 | 2.008631 | 1.883419 | 2.022671 |
21 | 2.097.152 | 1.359.930 | 121.074 | 1.238.856 | 0.648465 | 0.057733 | 0.590733 | 2.007535 | 1.890600 | 2.019743 |
22 | 4.194.304 | 2.728.502 | 229.079 | 2.499.423 | 0.650526 | 0.054617 | 0.595909 | 2.006355 | 1.892058 | 2.017525 |
23 | 8.388.608 | 5.473.483 | 435.069 | 5.038.414 | 0.652490 | 0.051864 | 0.600626 | 2.006040 | 1.899209 | 2.015831 |
24 | 16.777.216 | 10.976.936 | 829.164 | 10.147.772 | 0.654276 | 0.049422 | 0.604854 | 2.005476 | 1.905822 | 2.014081 |
25 | 33.554.432 | 22.005.927 | 1.584.825 | 20.421.102 | 0.655828 | 0.047231 | 0.608596 | 2.004742 | 1.911353 | 2.012373 |
26 | 67.108.864 | 44.111.422 | 3.031.026 | 41.080.396 | 0.657311 | 0.045166 | 0.612146 | 2.004525 | 1.912530 | 2.011664 |
27 | 134.217.728 | 88.404.631 | 5.810.728 | 82.593.903 | 0.658666 | 0.043293 | 0.615373 | 2.004121 | 1.917083 | 2.010543 |
28 | 268.435.456 | 177.150.157 | 11.161.915 | 165.988.242 | 0.659936 | 0.041581 | 0.618354 | 2.003856 | 1.920915 | 2.009691 |
29 | 536.870.912 | 354.929.109 | 21.469.424 | 333.459.685 | 0.661107 | 0.039990 | 0.621117 | 2.003550 | 1.923453 | 2.008936 |
30 | 1.073.741.824 | 711.024.217 | 41.365.869 | 669.658.348 | 0.662193 | 0.038525 | 0.623668 | 2.003285 | 1.926734 | 2.008214 |
31 | 2.147.483.648 | 1.424.243.572 | 79.807.496 | 1.344.436.076 | 0.663215 | 0.037163 | 0.626052 | 2.003087 | 1.929308 | 2.007645 |
32 | 4.294.967.296 | 2.852.588.589 | 154.168.543 | 2.698.420.046 | 0.664170 | 0.035895 | 0.628275 | 2.002880 | 1.931755 | 2.007102 |
33 | 8.589.934.592 | 5.712.855.823 | 298.169.507 | 5.414.686.316 | 0.665064 | 0.034711 | 0.630352 | 2.002692 | 1.934049 | 2.006613 |
34 | 17.179.869.184 | 11.440.204.286 | 577.299.136 | 10.862.905.150 | 0.665908 | 0.033603 | 0.632304 | 2.002537 | 1.936144 | 2.006193 |
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 | 2 | 0 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
4 | 16 | 6 | 2 | 3 | 1 | 3 | 1 | 1 |
5 | 32 | 10 | 3 | 6 | 2 | 4 | 2 | 2 |
6 | 64 | 14 | 4 | 9 | 3 | 5 | 2 | 4 |
7 | 128 | 26 | 9 | 16 | 4 | 9 | 3 | 10 |
8 | 256 | 42 | 14 | 27 | 7 | 15 | 3 | 17 |
9 | 512 | 77 | 30 | 46 | 13 | 27 | 7 | 30 |
10 | 1.024 | 135 | 52 | 82 | 21 | 53 | 8 | 53 |
11 | 2.048 | 252 | 88 | 163 | 35 | 92 | 27 | 98 |
12 | 4.096 | 447 | 161 | 285 | 61 | 167 | 56 | 163 |
13 | 8.192 | 830 | 299 | 530 | 120 | 306 | 107 | 297 |
14 | 16.384 | 1.519 | 547 | 971 | 212 | 570 | 206 | 531 |
15 | 32.768 | 2.793 | 1.002 | 1.790 | 373 | 1.052 | 383 | 985 |
16 | 65.536 | 5.219 | 1.880 | 3.338 | 677 | 1.959 | 708 | 1.875 |
17 | 131.072 | 9.723 | 3.422 | 6.300 | 1.324 | 3.548 | 1.271 | 3.580 |
18 | 262.144 | 18.136 | 6.362 | 11.773 | 2.436 | 6.706 | 2.382 | 6.612 |
19 | 524.288 | 34.002 | 11.818 | 22.183 | 4.544 | 12.535 | 4.486 | 12.437 |
20 | 1.048.576 | 64.040 | 22.244 | 41.795 | 8.493 | 23.622 | 8.439 | 23.486 |
21 | 2.097.152 | 121.074 | 42.085 | 78.988 | 16.069 | 44.699 | 15.840 | 44.466 |
22 | 4.194.304 | 229.079 | 79.531 | 149.547 | 30.243 | 84.359 | 29.996 | 84.481 |
23 | 8.388.608 | 435.069 | 151.043 | 284.025 | 57.148 | 160.412 | 57.011 | 160.498 |
24 | 16.777.216 | 829.164 | 287.179 | 541.984 | 109.035 | 305.842 | 108.528 | 305.759 |
25 | 33.554.432 | 1.584.825 | 547.737 | 1.037.087 | 207.171 | 585.128 | 207.265 | 585.261 |
26 | 67.108.864 | 3.031.026 | 1.045.331 | 1.985.694 | 394.937 | 1.121.302 | 395.142 | 1.119.645 |
27 | 134.217.728 | 5.810.728 | 2.001.849 | 3.808.878 | 756.092 | 2.149.442 | 756.782 | 2.148.412 |
28 | 268.435.456 | 11.161.915 | 3.841.977 | 7.319.937 | 1.451.371 | 4.129.883 | 1.451.239 | 4.129.422 |
29 | 536.870.912 | 21.469.424 | 7.381.463 | 14.087.960 | 2.785.943 | 7.948.546 | 2.787.097 | 7.947.838 |
30 | 1.073.741.824 | 41.365.869 | 14.202.666 | 27.163.202 | 5.361.872 | 15.322.262 | 5.361.611 | 15.320.124 |
31 | 2.147.483.648 | 79.807.496 | 27.375.986 | 52.431.509 | 10.332.542 | 29.576.130 | 10.330.820 | 29.568.004 |
32 | 4.294.967.296 | 154.168.543 | 52.831.354 | 101.337.188 | 19.935.818 | 57.154.568 | 19.932.939 | 57.145.218 |
33 | 8.589.934.592 | 298.169.507 | 102.098.607 | 196.070.899 | 38.510.700 | 110.571.367 | 38.508.584 | 110.578.856 |
34 | 17.179.869.184 | 577.299.136 | 197.518.108 | 379.781.027 | 74.481.802 | 214.164.860 | 74.484.580 | 214.167.894 |
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 | 0 | 1 | 0 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 2 | 0 |
4 | 16 | 8 | 4 | 4 | 1 | 1 | 5 | 1 |
5 | 32 | 12 | 7 | 5 | 3 | 1 | 6 | 2 |
6 | 64 | 28 | 13 | 15 | 9 | 4 | 11 | 4 |
7 | 128 | 46 | 23 | 23 | 15 | 9 | 15 | 7 |
8 | 256 | 105 | 58 | 47 | 33 | 18 | 32 | 22 |
9 | 512 | 224 | 111 | 113 | 65 | 45 | 65 | 49 |
10 | 1.024 | 462 | 235 | 227 | 128 | 101 | 138 | 95 |
11 | 2.048 | 967 | 471 | 496 | 271 | 206 | 279 | 211 |
12 | 4.096 | 2.060 | 1.015 | 1.045 | 561 | 459 | 582 | 458 |
13 | 8.192 | 4.240 | 2.096 | 2.144 | 1.118 | 974 | 1.187 | 961 |
14 | 16.384 | 8.727 | 4.356 | 4.371 | 2.339 | 2.029 | 2.355 | 2.004 |
15 | 32.768 | 17.838 | 8.906 | 8.932 | 4.735 | 4.156 | 4.824 | 4.123 |
16 | 65.536 | 36.285 | 18.116 | 18.169 | 9.671 | 8.485 | 9.762 | 8.367 |
17 | 131.072 | 73.796 | 36.644 | 37.152 | 19.404 | 17.296 | 19.833 | 17.263 |
18 | 262.144 | 149.681 | 74.598 | 75.083 | 39.348 | 35.269 | 39.893 | 35.171 |
19 | 524.288 | 303.249 | 151.063 | 152.186 | 79.599 | 71.683 | 80.304 | 71.663 |
20 | 1.048.576 | 613.373 | 305.868 | 307.505 | 161.020 | 145.542 | 161.596 | 145.215 |
21 | 2.097.152 | 1.238.856 | 618.464 | 620.392 | 324.177 | 294.921 | 324.699 | 295.059 |
22 | 4.194.304 | 2.499.423 | 1.248.312 | 1.251.111 | 652.160 | 596.934 | 653.284 | 597.045 |
23 | 8.388.608 | 5.038.414 | 2.516.977 | 2.521.437 | 1.312.556 | 1.206.308 | 1.314.195 | 1.205.355 |
24 | 16.777.216 | 10.147.772 | 5.070.995 | 5.076.777 | 2.637.219 | 2.435.871 | 2.639.895 | 2.434.787 |
25 | 33.554.432 | 20.421.102 | 10.207.036 | 10.214.066 | 5.298.020 | 4.913.113 | 5.301.019 | 4.908.950 |
26 | 67.108.864 | 41.080.396 | 20.533.333 | 20.547.063 | 10.641.972 | 9.897.639 | 10.644.666 | 9.896.119 |
27 | 134.217.728 | 82.593.903 | 41.280.754 | 41.313.149 | 21.364.404 | 19.939.791 | 21.362.816 | 19.926.892 |
28 | 268.435.456 | 165.988.242 | 82.955.079 | 83.033.163 | 42.868.439 | 40.126.966 | 42.875.240 | 40.117.597 |
29 | 536.870.912 | 333.459.685 | 166.658.023 | 166.801.662 | 86.019.072 | 80.719.584 | 86.011.583 | 80.709.446 |
30 | 1.073.741.824 | 669.658.348 | 334.692.864 | 334.965.484 | 172.538.574 | 162.309.319 | 172.514.264 | 162.296.191 |
31 | 2.147.483.648 | 1.344.436.076 | 671.964.952 | 672.471.124 | 345.995.448 | 326.250.836 | 345.957.072 | 326.232.720 |
32 | 4.294.967.296 | 2.698.420.046 | 1.348.704.961 | 1.349.715.085 | 693.685.612 | 655.542.717 | 693.672.212 | 655.519.505 |
33 | 8.589.934.592 | 5.414.686.316 | 2.706.380.623 | 2.708.305.693 | 1.390.532.810 | 1.316.777.465 | 1.390.592.810 | 1.316.783.231 |
34 | 17.179.869.184 | 10.862.905.150 | 5.429.573.656 | 5.433.331.494 | 2.787.138.724 | 2.644.229.007 | 2.787.245.854 | 2.644.291.565 |