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+92x-181
f(0)=181
f(1)=11
f(2)=7
f(3)=13
f(4)=29
f(5)=19
f(6)=37
f(7)=1
f(8)=619
f(9)=1
f(10)=839
f(11)=17
f(12)=97
f(13)=1
f(14)=1303
f(15)=89
f(16)=1
f(17)=1
f(18)=257
f(19)=241
f(20)=71
f(21)=137
f(22)=179
f(23)=1
f(24)=1
f(25)=1
f(26)=2887
f(27)=379
f(28)=1
f(29)=1
f(30)=1
f(31)=227
f(32)=541
f(33)=1
f(34)=373
f(35)=41
f(36)=233
f(37)=1
f(38)=4759
f(39)=1
f(40)=5099
f(41)=659
f(42)=419
f(43)=1
f(44)=829
f(45)=1
f(46)=881
f(47)=397
f(48)=503
f(49)=1
f(50)=1
f(51)=127
f(52)=7307
f(53)=67
f(54)=7703
f(55)=1
f(56)=1
f(57)=1039
f(58)=1217
f(59)=1091
f(60)=1277
f(61)=1
f(62)=1
f(63)=599
f(64)=9803
f(65)=1
f(66)=10247
f(67)=1
f(68)=823
f(69)=683
f(70)=11159
f(71)=1
f(72)=151
f(73)=1483
f(74)=1
f(75)=1543
f(76)=307
f(77)=401
f(78)=1
f(79)=1
f(80)=367
f(81)=1
f(82)=14087
f(83)=163
f(84)=859
f(85)=929
f(86)=2161
f(87)=1
f(88)=2237
f(89)=1
f(90)=167
f(91)=1
f(92)=16747
f(93)=1
f(94)=1
f(95)=157
f(96)=1051
f(97)=2269
f(98)=18439
f(99)=2341
b) Substitution of the polynom
The polynom f(x)=x^2+92x-181 could be written as f(y)= y^2-2297 with x=y-46
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+46
f'(x)>2x+91
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 | 7 | 2 | 0.900000 | 0.700000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 60 | 36 | 24 | 0.600000 | 0.360000 | 0.240000 | 6.666667 | 5.142857 | 12.000000 |
3 | 1.000 | 602 | 248 | 354 | 0.602000 | 0.248000 | 0.354000 | 10.033334 | 6.888889 | 14.750000 |
4 | 10.000 | 6.287 | 1.723 | 4.564 | 0.628700 | 0.172300 | 0.456400 | 10.443521 | 6.947581 | 12.892655 |
5 | 100.000 | 64.220 | 13.329 | 50.891 | 0.642200 | 0.133290 | 0.508910 | 10.214728 | 7.735926 | 11.150526 |
6 | 1.000.000 | 651.432 | 108.110 | 543.322 | 0.651432 | 0.108110 | 0.543322 | 10.143756 | 8.110886 | 10.676190 |
7 | 10.000.000 | 6.576.192 | 904.615 | 5.671.577 | 0.657619 | 0.090461 | 0.567158 | 10.094978 | 8.367542 | 10.438703 |
8 | 100.000.000 | 66.222.408 | 7.781.619 | 58.440.789 | 0.662224 | 0.077816 | 0.584408 | 10.070024 | 8.602134 | 10.304152 |
9 | 1.000.000.000 | 665.728.353 | 68.302.688 | 597.425.665 | 0.665728 | 0.068303 | 0.597426 | 10.052917 | 8.777439 | 10.222752 |
10 | 10.000.000.000 | 6.685.185.464 | 608.575.658 | 6.076.609.806 | 0.668519 | 0.060858 | 0.607661 | 10.041911 | 8.909982 | 10.171324 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 8 | 6 | 2 | 1.000000 | 0.750000 | 0.250000 | 1.600000 | 1.500000 | 2.000000 |
4 | 16 | 12 | 9 | 3 | 0.750000 | 0.562500 | 0.187500 | 1.500000 | 1.500000 | 1.500000 |
5 | 32 | 21 | 14 | 7 | 0.656250 | 0.437500 | 0.218750 | 1.750000 | 1.555556 | 2.333333 |
6 | 64 | 40 | 24 | 16 | 0.625000 | 0.375000 | 0.250000 | 1.904762 | 1.714286 | 2.285714 |
7 | 128 | 75 | 42 | 33 | 0.585938 | 0.328125 | 0.257812 | 1.875000 | 1.750000 | 2.062500 |
8 | 256 | 148 | 78 | 70 | 0.578125 | 0.304688 | 0.273438 | 1.973333 | 1.857143 | 2.121212 |
9 | 512 | 307 | 141 | 166 | 0.599609 | 0.275391 | 0.324219 | 2.074324 | 1.807692 | 2.371428 |
10 | 1.024 | 616 | 254 | 362 | 0.601562 | 0.248047 | 0.353516 | 2.006515 | 1.801418 | 2.180723 |
11 | 2.048 | 1.251 | 469 | 782 | 0.610840 | 0.229004 | 0.381836 | 2.030844 | 1.846457 | 2.160221 |
12 | 4.096 | 2.552 | 809 | 1.743 | 0.623047 | 0.197510 | 0.425537 | 2.039968 | 1.724947 | 2.228900 |
13 | 8.192 | 5.151 | 1.448 | 3.703 | 0.628784 | 0.176758 | 0.452026 | 2.018417 | 1.789864 | 2.124498 |
14 | 16.384 | 10.368 | 2.651 | 7.717 | 0.632812 | 0.161804 | 0.471008 | 2.012813 | 1.830801 | 2.083986 |
15 | 32.768 | 20.832 | 4.892 | 15.940 | 0.635742 | 0.149292 | 0.486450 | 2.009259 | 1.845341 | 2.065570 |
16 | 65.536 | 41.985 | 9.068 | 32.917 | 0.640640 | 0.138367 | 0.502274 | 2.015409 | 1.853639 | 2.065057 |
17 | 131.072 | 84.375 | 17.003 | 67.372 | 0.643730 | 0.129723 | 0.514008 | 2.009646 | 1.875055 | 2.046724 |
18 | 262.144 | 169.568 | 31.909 | 137.659 | 0.646851 | 0.121723 | 0.525127 | 2.009695 | 1.876669 | 2.043267 |
19 | 524.288 | 340.420 | 59.810 | 280.610 | 0.649300 | 0.114079 | 0.535221 | 2.007572 | 1.874393 | 2.038443 |
20 | 1.048.576 | 683.249 | 112.934 | 570.315 | 0.651597 | 0.107702 | 0.543895 | 2.007077 | 1.888213 | 2.032412 |
21 | 2.097.152 | 1.370.792 | 213.482 | 1.157.310 | 0.653645 | 0.101796 | 0.551848 | 2.006285 | 1.890325 | 2.029247 |
22 | 4.194.304 | 2.749.417 | 404.576 | 2.344.841 | 0.655512 | 0.096458 | 0.559054 | 2.005714 | 1.895129 | 2.026113 |
23 | 8.388.608 | 5.512.667 | 768.180 | 4.744.487 | 0.657161 | 0.091574 | 0.565587 | 2.005031 | 1.898728 | 2.023373 |
24 | 16.777.216 | 11.052.838 | 1.463.718 | 9.589.120 | 0.658800 | 0.087244 | 0.571556 | 2.004989 | 1.905436 | 2.021108 |
25 | 33.554.432 | 22.152.534 | 2.796.101 | 19.356.433 | 0.660197 | 0.083330 | 0.576867 | 2.004240 | 1.910273 | 2.018583 |
26 | 67.108.864 | 44.393.811 | 5.351.474 | 39.042.337 | 0.661519 | 0.079743 | 0.581776 | 2.004006 | 1.913906 | 2.017021 |
27 | 134.217.728 | 88.947.978 | 10.260.534 | 78.687.444 | 0.662714 | 0.076447 | 0.586267 | 2.003612 | 1.917329 | 2.015439 |
28 | 268.435.456 | 178.194.401 | 19.709.706 | 158.484.695 | 0.663826 | 0.073424 | 0.590401 | 2.003355 | 1.920924 | 2.014104 |
29 | 536.870.912 | 356.940.907 | 37.928.123 | 319.012.784 | 0.664854 | 0.070647 | 0.594208 | 2.003098 | 1.924337 | 2.012893 |
30 | 1.073.741.824 | 714.921.341 | 73.061.372 | 641.859.969 | 0.665822 | 0.068044 | 0.597779 | 2.002912 | 1.926311 | 2.012019 |
31 | 2.147.483.648 | 1.431.770.202 | 140.948.808 | 1.290.821.394 | 0.666720 | 0.065634 | 0.601086 | 2.002696 | 1.929183 | 2.011064 |
32 | 4.294.967.296 | 2.867.151.378 | 272.269.973 | 2.594.881.405 | 0.667561 | 0.063393 | 0.604168 | 2.002522 | 1.931694 | 2.010256 |
33 | 8.589.934.592 | 5.741.085.259 | 526.540.871 | 5.214.544.388 | 0.668350 | 0.061297 | 0.607053 | 2.002366 | 1.933892 | 2.009550 |
34 | 17.179.869.184 | 11.494.952.096 | 1.019.436.130 | 10.475.515.966 | 0.669094 | 0.059339 | 0.609755 | 2.002226 | 1.936101 | 2.008904 |
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 | 0 | 1 | 1 | 1 |
2 | 4 | 4 | 3 | 1 | 0 | 1 | 2 | 1 |
3 | 8 | 6 | 5 | 1 | 0 | 3 | 2 | 1 |
4 | 16 | 9 | 6 | 3 | 1 | 3 | 2 | 3 |
5 | 32 | 14 | 9 | 5 | 3 | 5 | 2 | 4 |
6 | 64 | 24 | 12 | 12 | 3 | 10 | 3 | 8 |
7 | 128 | 42 | 21 | 21 | 6 | 14 | 6 | 16 |
8 | 256 | 78 | 35 | 43 | 13 | 28 | 12 | 25 |
9 | 512 | 141 | 68 | 73 | 24 | 46 | 20 | 51 |
10 | 1.024 | 254 | 116 | 138 | 39 | 92 | 35 | 88 |
11 | 2.048 | 469 | 215 | 254 | 73 | 165 | 62 | 169 |
12 | 4.096 | 809 | 372 | 437 | 123 | 278 | 107 | 301 |
13 | 8.192 | 1.448 | 657 | 791 | 206 | 505 | 195 | 542 |
14 | 16.384 | 2.651 | 1.175 | 1.476 | 366 | 948 | 364 | 973 |
15 | 32.768 | 4.892 | 2.188 | 2.704 | 661 | 1.766 | 668 | 1.797 |
16 | 65.536 | 9.068 | 4.065 | 5.003 | 1.219 | 3.300 | 1.228 | 3.321 |
17 | 131.072 | 17.003 | 7.652 | 9.351 | 2.262 | 6.202 | 2.272 | 6.267 |
18 | 262.144 | 31.909 | 14.407 | 17.502 | 4.249 | 11.672 | 4.265 | 11.723 |
19 | 524.288 | 59.810 | 26.938 | 32.872 | 7.962 | 21.832 | 7.921 | 22.095 |
20 | 1.048.576 | 112.934 | 50.776 | 62.158 | 15.061 | 41.324 | 14.900 | 41.649 |
21 | 2.097.152 | 213.482 | 95.668 | 117.814 | 28.244 | 78.333 | 28.135 | 78.770 |
22 | 4.194.304 | 404.576 | 181.401 | 223.175 | 53.538 | 148.890 | 53.066 | 149.082 |
23 | 8.388.608 | 768.180 | 344.696 | 423.484 | 101.123 | 283.155 | 100.565 | 283.337 |
24 | 16.777.216 | 1.463.718 | 656.861 | 806.857 | 191.859 | 540.406 | 191.137 | 540.316 |
25 | 33.554.432 | 2.796.101 | 1.253.833 | 1.542.268 | 365.630 | 1.032.763 | 365.224 | 1.032.484 |
26 | 67.108.864 | 5.351.474 | 2.399.508 | 2.951.966 | 699.102 | 1.977.547 | 697.334 | 1.977.491 |
27 | 134.217.728 | 10.260.534 | 4.599.291 | 5.661.243 | 1.337.556 | 3.794.082 | 1.335.403 | 3.793.493 |
28 | 268.435.456 | 19.709.706 | 8.831.665 | 10.878.041 | 2.563.395 | 7.292.203 | 2.561.107 | 7.293.001 |
29 | 536.870.912 | 37.928.123 | 16.989.555 | 20.938.568 | 4.924.241 | 14.038.720 | 4.922.815 | 14.042.347 |
30 | 1.073.741.824 | 73.061.372 | 32.718.407 | 40.342.965 | 9.469.259 | 27.060.279 | 9.471.145 | 27.060.689 |
31 | 2.147.483.648 | 140.948.808 | 63.095.944 | 77.852.864 | 18.244.034 | 52.227.383 | 18.247.226 | 52.230.165 |
32 | 4.294.967.296 | 272.269.973 | 121.857.445 | 150.412.528 | 35.202.617 | 100.927.378 | 35.202.788 | 100.937.190 |
33 | 8.589.934.592 | 526.540.871 | 235.610.389 | 290.930.482 | 67.995.439 | 195.268.514 | 68.006.612 | 195.270.306 |
34 | 17.179.869.184 | 1.019.436.130 | 456.079.708 | 563.356.422 | 131.522.535 | 378.191.646 | 131.520.354 | 378.201.595 |
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 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
4 | 16 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
5 | 32 | 7 | 3 | 4 | 2 | 1 | 3 | 1 |
6 | 64 | 16 | 6 | 10 | 5 | 2 | 6 | 3 |
7 | 128 | 33 | 16 | 17 | 10 | 7 | 8 | 8 |
8 | 256 | 70 | 35 | 35 | 18 | 17 | 21 | 14 |
9 | 512 | 166 | 83 | 83 | 40 | 37 | 51 | 38 |
10 | 1.024 | 362 | 180 | 182 | 88 | 88 | 107 | 79 |
11 | 2.048 | 782 | 364 | 418 | 201 | 186 | 219 | 176 |
12 | 4.096 | 1.743 | 839 | 904 | 463 | 409 | 465 | 406 |
13 | 8.192 | 3.703 | 1.819 | 1.884 | 945 | 894 | 969 | 895 |
14 | 16.384 | 7.717 | 3.822 | 3.895 | 1.944 | 1.870 | 1.996 | 1.907 |
15 | 32.768 | 15.940 | 7.907 | 8.033 | 4.096 | 3.829 | 4.114 | 3.901 |
16 | 65.536 | 32.917 | 16.312 | 16.605 | 8.474 | 7.994 | 8.480 | 7.969 |
17 | 131.072 | 67.372 | 33.427 | 33.945 | 17.414 | 16.425 | 17.201 | 16.332 |
18 | 262.144 | 137.659 | 68.286 | 69.373 | 35.443 | 33.447 | 35.219 | 33.550 |
19 | 524.288 | 280.610 | 139.389 | 141.221 | 71.750 | 68.519 | 71.866 | 68.475 |
20 | 1.048.576 | 570.315 | 283.490 | 286.825 | 145.714 | 139.622 | 145.446 | 139.533 |
21 | 2.097.152 | 1.157.310 | 575.508 | 581.802 | 295.273 | 283.196 | 295.332 | 283.509 |
22 | 4.194.304 | 2.344.841 | 1.167.000 | 1.177.841 | 597.700 | 574.738 | 596.988 | 575.415 |
23 | 8.388.608 | 4.744.487 | 2.362.153 | 2.382.334 | 1.207.413 | 1.164.981 | 1.207.324 | 1.164.769 |
24 | 16.777.216 | 9.589.120 | 4.773.144 | 4.815.976 | 2.437.643 | 2.356.698 | 2.437.355 | 2.357.424 |
25 | 33.554.432 | 19.356.433 | 9.637.300 | 9.719.133 | 4.919.077 | 4.761.269 | 4.915.301 | 4.760.786 |
26 | 67.108.864 | 39.042.337 | 19.444.302 | 19.598.035 | 9.910.098 | 9.610.990 | 9.909.049 | 9.612.200 |
27 | 134.217.728 | 78.687.444 | 39.197.570 | 39.489.874 | 19.956.342 | 19.386.020 | 19.956.385 | 19.388.697 |
28 | 268.435.456 | 158.484.695 | 78.960.162 | 79.524.533 | 40.175.333 | 39.069.941 | 40.171.528 | 39.067.893 |
29 | 536.870.912 | 319.012.784 | 158.962.523 | 160.050.261 | 80.820.383 | 78.694.910 | 80.813.964 | 78.683.527 |
30 | 1.073.741.824 | 641.859.969 | 319.875.475 | 321.984.494 | 162.517.714 | 158.420.870 | 162.510.869 | 158.410.516 |
31 | 2.147.483.648 | 1.290.821.394 | 643.376.922 | 647.444.472 | 326.642.398 | 318.770.136 | 326.652.507 | 318.756.353 |
32 | 4.294.967.296 | 2.594.881.405 | 1.293.515.895 | 1.301.365.510 | 656.315.056 | 641.104.285 | 656.352.920 | 641.109.144 |
33 | 8.589.934.592 | 5.214.544.388 | 2.599.681.612 | 2.614.862.776 | 1.318.353.474 | 1.288.895.222 | 1.318.374.249 | 1.288.921.443 |
34 | 17.179.869.184 | 10.475.515.966 | 5.223.069.014 | 5.252.446.952 | 2.647.414.582 | 2.590.369.139 | 2.647.414.551 | 2.590.317.694 |