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+192x-1
f(0)=1
f(1)=3
f(2)=43
f(3)=73
f(4)=29
f(5)=41
f(6)=1187
f(7)=1
f(8)=13
f(9)=113
f(10)=673
f(11)=31
f(12)=2447
f(13)=37
f(14)=1
f(15)=97
f(16)=1109
f(17)=1
f(18)=3779
f(19)=167
f(20)=157
f(21)=1
f(22)=523
f(23)=103
f(24)=71
f(25)=1
f(26)=1889
f(27)=739
f(28)=2053
f(29)=89
f(30)=6659
f(31)=1
f(32)=2389
f(33)=1
f(34)=197
f(35)=331
f(36)=283
f(37)=353
f(38)=971
f(39)=563
f(40)=1031
f(41)=199
f(42)=317
f(43)=421
f(44)=3461
f(45)=1
f(46)=1
f(47)=1
f(48)=11519
f(49)=1
f(50)=109
f(51)=1549
f(52)=4229
f(53)=541
f(54)=359
f(55)=1
f(56)=1543
f(57)=887
f(58)=179
f(59)=617
f(60)=1163
f(61)=643
f(62)=181
f(63)=251
f(64)=127
f(65)=1
f(66)=17027
f(67)=241
f(68)=83
f(69)=2251
f(70)=6113
f(71)=389
f(72)=229
f(73)=1
f(74)=1
f(75)=2503
f(76)=1
f(77)=863
f(78)=21059
f(79)=223
f(80)=7253
f(81)=691
f(82)=7489
f(83)=1
f(84)=239
f(85)=1
f(86)=613
f(87)=1
f(88)=191
f(89)=521
f(90)=619
f(91)=1
f(92)=2903
f(93)=3313
f(94)=1
f(95)=1
f(96)=27647
f(97)=1
f(98)=9473
f(99)=277
b) Substitution of the polynom
The polynom f(x)=x^2+192x-1 could be written as f(y)= y^2-9217 with x=y-96
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+96
f'(x)>2x+191
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 | 2 | 7 | 0.900000 | 0.200000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 75 | 9 | 66 | 0.750000 | 0.090000 | 0.750000 | 8.333333 | 4.500000 | 9.428572 |
3 | 1.000 | 620 | 66 | 554 | 0.620000 | 0.066000 | 0.620000 | 8.266666 | 7.333333 | 8.393939 |
4 | 10.000 | 6.287 | 510 | 5.777 | 0.628700 | 0.051000 | 0.628700 | 10.140323 | 7.727273 | 10.427798 |
5 | 100.000 | 64.429 | 3.948 | 60.481 | 0.644290 | 0.039480 | 0.644290 | 10.247972 | 7.741177 | 10.469275 |
6 | 1.000.000 | 653.347 | 31.970 | 621.377 | 0.653347 | 0.031970 | 0.653347 | 10.140574 | 8.097771 | 10.273921 |
7 | 10.000.000 | 6.591.008 | 272.240 | 6.318.768 | 0.659101 | 0.027224 | 0.659101 | 10.088066 | 8.515483 | 10.168977 |
8 | 100.000.000 | 66.345.147 | 2.360.054 | 63.985.093 | 0.663451 | 0.023601 | 0.663451 | 10.066010 | 8.669020 | 10.126198 |
9 | 1.000.000.000 | 666.816.937 | 20.838.238 | 645.978.699 | 0.666817 | 0.020838 | 0.666817 | 10.050727 | 8.829560 | 10.095769 |
10 | 10.000.000.000 | 6.695.050.576 | 186.465.281 | 6.508.585.295 | 0.669505 | 0.018647 | 0.669505 | 10.040313 | 8.948227 | 10.075542 |
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 | 2 | 0 | 2 | 1.000000 | 0.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 0 | 4 | 1.000000 | 0.000000 | 1.000000 | 2.000000 | -nan | 2.000000 |
3 | 8 | 7 | 2 | 5 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | inf | 1.250000 |
4 | 16 | 14 | 3 | 11 | 0.875000 | 0.187500 | 0.687500 | 2.000000 | 1.500000 | 2.200000 |
5 | 32 | 26 | 5 | 21 | 0.812500 | 0.156250 | 0.656250 | 1.857143 | 1.666667 | 1.909091 |
6 | 64 | 51 | 6 | 45 | 0.796875 | 0.093750 | 0.703125 | 1.961538 | 1.200000 | 2.142857 |
7 | 128 | 88 | 10 | 78 | 0.687500 | 0.078125 | 0.609375 | 1.725490 | 1.666667 | 1.733333 |
8 | 256 | 168 | 18 | 150 | 0.656250 | 0.070312 | 0.585938 | 1.909091 | 1.800000 | 1.923077 |
9 | 512 | 318 | 35 | 283 | 0.621094 | 0.068359 | 0.552734 | 1.892857 | 1.944444 | 1.886667 |
10 | 1.024 | 638 | 67 | 571 | 0.623047 | 0.065430 | 0.557617 | 2.006289 | 1.914286 | 2.017668 |
11 | 2.048 | 1.273 | 127 | 1.146 | 0.621582 | 0.062012 | 0.559570 | 1.995298 | 1.895522 | 2.007005 |
12 | 4.096 | 2.540 | 234 | 2.306 | 0.620117 | 0.057129 | 0.562988 | 1.995287 | 1.842520 | 2.012216 |
13 | 8.192 | 5.128 | 430 | 4.698 | 0.625977 | 0.052490 | 0.573486 | 2.018898 | 1.837607 | 2.037294 |
14 | 16.384 | 10.363 | 776 | 9.587 | 0.632507 | 0.047363 | 0.585144 | 2.020866 | 1.804651 | 2.040656 |
15 | 32.768 | 20.918 | 1.420 | 19.498 | 0.638367 | 0.043335 | 0.595032 | 2.018528 | 1.829897 | 2.033796 |
16 | 65.536 | 42.090 | 2.712 | 39.378 | 0.642242 | 0.041382 | 0.600861 | 2.012143 | 1.909859 | 2.019592 |
17 | 131.072 | 84.555 | 5.037 | 79.518 | 0.645103 | 0.038429 | 0.606674 | 2.008909 | 1.857301 | 2.019351 |
18 | 262.144 | 170.114 | 9.347 | 160.767 | 0.648933 | 0.035656 | 0.613277 | 2.011874 | 1.855668 | 2.021769 |
19 | 524.288 | 341.397 | 17.708 | 323.689 | 0.651163 | 0.033775 | 0.617388 | 2.006872 | 1.894512 | 2.013405 |
20 | 1.048.576 | 685.177 | 33.430 | 651.747 | 0.653436 | 0.031881 | 0.621554 | 2.006980 | 1.887847 | 2.013498 |
21 | 2.097.152 | 1.374.615 | 63.472 | 1.311.143 | 0.655468 | 0.030266 | 0.625202 | 2.006219 | 1.898654 | 2.011736 |
22 | 4.194.304 | 2.756.505 | 120.899 | 2.635.606 | 0.657202 | 0.028825 | 0.628377 | 2.005292 | 1.904761 | 2.010159 |
23 | 8.388.608 | 5.525.615 | 231.119 | 5.294.496 | 0.658705 | 0.027552 | 0.631153 | 2.004573 | 1.911670 | 2.008834 |
24 | 16.777.216 | 11.076.733 | 441.530 | 10.635.203 | 0.660225 | 0.026317 | 0.633907 | 2.004615 | 1.910401 | 2.008728 |
25 | 33.554.432 | 22.197.257 | 845.255 | 21.352.002 | 0.661530 | 0.025191 | 0.636339 | 2.003953 | 1.914377 | 2.007672 |
26 | 67.108.864 | 44.477.078 | 1.620.776 | 42.856.302 | 0.662760 | 0.024151 | 0.638609 | 2.003720 | 1.917499 | 2.007133 |
27 | 134.217.728 | 89.111.086 | 3.114.682 | 85.996.404 | 0.663929 | 0.023206 | 0.640723 | 2.003528 | 1.921723 | 2.006622 |
28 | 268.435.456 | 178.507.057 | 5.994.451 | 172.512.606 | 0.664991 | 0.022331 | 0.642660 | 2.003197 | 1.924579 | 2.006045 |
29 | 536.870.912 | 357.549.489 | 11.552.891 | 345.996.598 | 0.665988 | 0.021519 | 0.644469 | 2.002999 | 1.927264 | 2.005631 |
30 | 1.073.741.824 | 716.091.438 | 22.294.797 | 693.796.641 | 0.666912 | 0.020764 | 0.646149 | 2.002776 | 1.929802 | 2.005212 |
31 | 2.147.483.648 | 1.434.036.796 | 43.073.790 | 1.390.963.006 | 0.667775 | 0.020058 | 0.647718 | 2.002589 | 1.932011 | 2.004857 |
32 | 4.294.967.296 | 2.871.550.560 | 83.307.481 | 2.788.243.079 | 0.668585 | 0.019397 | 0.649188 | 2.002425 | 1.934064 | 2.004542 |
33 | 8.589.934.592 | 5.749.629.956 | 161.290.162 | 5.588.339.794 | 0.669345 | 0.018777 | 0.650568 | 2.002274 | 1.936083 | 2.004251 |
34 | 17.179.869.184 | 11.511.492.431 | 312.623.725 | 11.198.868.706 | 0.670057 | 0.018197 | 0.651860 | 2.002128 | 1.938269 | 2.003971 |
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 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
4 | 16 | 3 | 0 | 2 | 0 | 1 | 0 | 2 |
5 | 32 | 5 | 0 | 4 | 0 | 3 | 0 | 2 |
6 | 64 | 6 | 0 | 5 | 0 | 3 | 0 | 3 |
7 | 128 | 10 | 0 | 9 | 0 | 6 | 0 | 4 |
8 | 256 | 18 | 0 | 17 | 0 | 8 | 0 | 10 |
9 | 512 | 35 | 0 | 34 | 0 | 16 | 0 | 19 |
10 | 1.024 | 67 | 0 | 66 | 0 | 31 | 0 | 36 |
11 | 2.048 | 127 | 0 | 126 | 0 | 60 | 0 | 67 |
12 | 4.096 | 234 | 0 | 233 | 0 | 116 | 0 | 118 |
13 | 8.192 | 430 | 0 | 429 | 0 | 215 | 0 | 215 |
14 | 16.384 | 776 | 0 | 775 | 0 | 379 | 0 | 397 |
15 | 32.768 | 1.420 | 0 | 1.419 | 0 | 708 | 0 | 712 |
16 | 65.536 | 2.712 | 0 | 2.711 | 0 | 1.359 | 0 | 1.353 |
17 | 131.072 | 5.037 | 0 | 5.036 | 0 | 2.526 | 0 | 2.511 |
18 | 262.144 | 9.347 | 0 | 9.346 | 0 | 4.681 | 0 | 4.666 |
19 | 524.288 | 17.708 | 0 | 17.707 | 0 | 8.866 | 0 | 8.842 |
20 | 1.048.576 | 33.430 | 0 | 33.429 | 0 | 16.736 | 0 | 16.694 |
21 | 2.097.152 | 63.472 | 0 | 63.471 | 0 | 31.724 | 0 | 31.748 |
22 | 4.194.304 | 120.899 | 0 | 120.898 | 0 | 60.485 | 0 | 60.414 |
23 | 8.388.608 | 231.119 | 0 | 231.118 | 0 | 115.446 | 0 | 115.673 |
24 | 16.777.216 | 441.530 | 0 | 441.529 | 0 | 220.504 | 0 | 221.026 |
25 | 33.554.432 | 845.255 | 0 | 845.254 | 0 | 422.484 | 0 | 422.771 |
26 | 67.108.864 | 1.620.776 | 0 | 1.620.775 | 0 | 810.454 | 0 | 810.322 |
27 | 134.217.728 | 3.114.682 | 0 | 3.114.681 | 0 | 1.557.568 | 0 | 1.557.114 |
28 | 268.435.456 | 5.994.451 | 0 | 5.994.450 | 0 | 2.997.756 | 0 | 2.996.695 |
29 | 536.870.912 | 11.552.891 | 0 | 11.552.890 | 0 | 5.777.599 | 0 | 5.775.292 |
30 | 1.073.741.824 | 22.294.797 | 0 | 22.294.796 | 0 | 11.150.344 | 0 | 11.144.453 |
31 | 2.147.483.648 | 43.073.790 | 0 | 43.073.789 | 0 | 21.537.946 | 0 | 21.535.844 |
32 | 4.294.967.296 | 83.307.481 | 0 | 83.307.480 | 0 | 41.651.827 | 0 | 41.655.654 |
33 | 8.589.934.592 | 161.290.162 | 0 | 161.290.161 | 0 | 80.641.243 | 0 | 80.648.919 |
34 | 17.179.869.184 | 312.623.725 | 0 | 312.623.724 | 0 | 156.308.789 | 0 | 156.314.936 |
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 | 1 | 0 | 0 | 2 | 0 | 0 |
2 | 4 | 4 | 2 | 1 | 1 | 2 | 1 | 0 |
3 | 8 | 5 | 2 | 2 | 2 | 2 | 1 | 0 |
4 | 16 | 11 | 6 | 4 | 5 | 2 | 3 | 1 |
5 | 32 | 21 | 12 | 8 | 7 | 4 | 6 | 4 |
6 | 64 | 45 | 22 | 22 | 9 | 12 | 15 | 9 |
7 | 128 | 78 | 40 | 37 | 17 | 19 | 23 | 19 |
8 | 256 | 150 | 78 | 71 | 43 | 30 | 45 | 32 |
9 | 512 | 283 | 152 | 130 | 74 | 64 | 82 | 63 |
10 | 1.024 | 571 | 297 | 272 | 162 | 128 | 157 | 124 |
11 | 2.048 | 1.146 | 574 | 570 | 320 | 262 | 314 | 250 |
12 | 4.096 | 2.306 | 1.176 | 1.128 | 632 | 524 | 637 | 513 |
13 | 8.192 | 4.698 | 2.350 | 2.346 | 1.280 | 1.071 | 1.285 | 1.062 |
14 | 16.384 | 9.587 | 4.848 | 4.737 | 2.559 | 2.208 | 2.609 | 2.211 |
15 | 32.768 | 19.498 | 9.859 | 9.637 | 5.178 | 4.581 | 5.255 | 4.484 |
16 | 65.536 | 39.378 | 19.925 | 19.451 | 10.440 | 9.236 | 10.531 | 9.171 |
17 | 131.072 | 79.518 | 40.314 | 39.202 | 21.116 | 18.633 | 21.123 | 18.646 |
18 | 262.144 | 160.767 | 81.583 | 79.182 | 42.554 | 37.806 | 42.620 | 37.787 |
19 | 524.288 | 323.689 | 164.195 | 159.492 | 85.393 | 76.480 | 85.458 | 76.358 |
20 | 1.048.576 | 651.747 | 330.245 | 321.500 | 171.627 | 154.214 | 171.484 | 154.422 |
21 | 2.097.152 | 1.311.143 | 664.277 | 646.864 | 344.084 | 311.171 | 344.359 | 311.529 |
22 | 4.194.304 | 2.635.606 | 1.334.360 | 1.301.244 | 690.413 | 627.480 | 689.465 | 628.248 |
23 | 8.388.608 | 5.294.496 | 2.678.149 | 2.616.345 | 1.383.526 | 1.264.029 | 1.382.694 | 1.264.247 |
24 | 16.777.216 | 10.635.203 | 5.375.508 | 5.259.693 | 2.773.495 | 2.543.118 | 2.772.893 | 2.545.697 |
25 | 33.554.432 | 21.352.002 | 10.785.427 | 10.566.573 | 5.557.786 | 5.118.464 | 5.555.573 | 5.120.179 |
26 | 67.108.864 | 42.856.302 | 21.636.495 | 21.219.805 | 11.132.779 | 10.297.067 | 11.130.615 | 10.295.841 |
27 | 134.217.728 | 85.996.404 | 43.401.406 | 42.594.996 | 22.301.321 | 20.701.956 | 22.300.464 | 20.692.663 |
28 | 268.435.456 | 172.512.606 | 87.023.901 | 85.488.703 | 44.669.725 | 41.593.697 | 44.665.736 | 41.583.448 |
29 | 536.870.912 | 345.996.598 | 174.477.962 | 171.518.634 | 89.460.578 | 83.549.182 | 89.461.903 | 83.524.935 |
30 | 1.073.741.824 | 693.796.641 | 349.760.510 | 344.036.129 | 179.169.333 | 167.735.892 | 179.150.436 | 167.740.980 |
31 | 2.147.483.648 | 1.390.963.006 | 701.019.499 | 689.943.505 | 358.766.144 | 336.713.725 | 358.757.768 | 336.725.369 |
32 | 4.294.967.296 | 2.788.243.079 | 1.404.842.888 | 1.383.400.189 | 718.373.937 | 675.747.414 | 718.376.512 | 675.745.216 |
33 | 8.589.934.592 | 5.588.339.794 | 2.814.857.848 | 2.773.481.944 | 1.438.308.379 | 1.355.844.724 | 1.438.349.613 | 1.355.837.078 |
34 | 17.179.869.184 | 11.198.868.706 | 5.639.420.420 | 5.559.448.284 | 2.879.608.623 | 2.719.839.690 | 2.879.638.097 | 2.719.782.296 |