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+134x-3
f(0)=3
f(1)=11
f(2)=269
f(3)=17
f(4)=61
f(5)=173
f(6)=31
f(7)=41
f(8)=103
f(9)=107
f(10)=479
f(11)=199
f(12)=53
f(13)=1
f(14)=2069
f(15)=1
f(16)=47
f(17)=641
f(18)=911
f(19)=1
f(20)=181
f(21)=271
f(22)=127
f(23)=1
f(24)=421
f(25)=331
f(26)=4157
f(27)=1
f(28)=1511
f(29)=1181
f(30)=149
f(31)=71
f(32)=5309
f(33)=1
f(34)=1
f(35)=739
f(36)=2039
f(37)=1
f(38)=139
f(39)=281
f(40)=773
f(41)=163
f(42)=821
f(43)=317
f(44)=7829
f(45)=1
f(46)=89
f(47)=1063
f(48)=1
f(49)=83
f(50)=541
f(51)=131
f(52)=293
f(53)=2477
f(54)=1
f(55)=433
f(56)=967
f(57)=907
f(58)=1237
f(59)=1423
f(60)=431
f(61)=991
f(62)=12149
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=443
f(69)=389
f(70)=4759
f(71)=1
f(72)=4943
f(73)=1259
f(74)=1399
f(75)=653
f(76)=197
f(77)=1
f(78)=167
f(79)=701
f(80)=17117
f(81)=1451
f(82)=5903
f(83)=2251
f(84)=359
f(85)=1
f(86)=18917
f(87)=1
f(88)=383
f(89)=1
f(90)=6719
f(91)=853
f(92)=20789
f(93)=1759
f(94)=2381
f(95)=2719
f(96)=223
f(97)=1867
f(98)=179
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+134x-3 could be written as f(y)= y^2-4492 with x=y-67
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+67
f'(x)>2x+133
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 | 3 | 8 | 1.100000 | 0.300000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 76 | 20 | 56 | 0.760000 | 0.200000 | 0.560000 | 6.909091 | 6.666667 | 7.000000 |
3 | 1.000 | 624 | 133 | 491 | 0.624000 | 0.133000 | 0.491000 | 8.210526 | 6.650000 | 8.767858 |
4 | 10.000 | 6.403 | 897 | 5.506 | 0.640300 | 0.089700 | 0.550600 | 10.261218 | 6.744361 | 11.213849 |
5 | 100.000 | 65.254 | 6.989 | 58.265 | 0.652540 | 0.069890 | 0.582650 | 10.191160 | 7.791527 | 10.582092 |
6 | 1.000.000 | 660.125 | 56.757 | 603.368 | 0.660125 | 0.056757 | 0.603368 | 10.116238 | 8.120904 | 10.355582 |
7 | 10.000.000 | 6.647.285 | 479.143 | 6.168.142 | 0.664729 | 0.047914 | 0.616814 | 10.069736 | 8.442007 | 10.222853 |
8 | 100.000.000 | 66.833.169 | 4.140.009 | 62.693.160 | 0.668332 | 0.041400 | 0.626932 | 10.054205 | 8.640446 | 10.164026 |
9 | 1.000.000.000 | 671.101.586 | 36.423.587 | 634.677.999 | 0.671102 | 0.036424 | 0.634678 | 10.041445 | 8.797949 | 10.123561 |
10 | 10.000.000.000 | 6.733.199.340 | 325.135.194 | 6.408.064.146 | 0.673320 | 0.032514 | 0.640806 | 10.033055 | 8.926501 | 10.096559 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.500000 | 2.000000 |
4 | 16 | 15 | 5 | 10 | 0.937500 | 0.312500 | 0.625000 | 1.666667 | 1.666667 | 1.666667 |
5 | 32 | 28 | 9 | 19 | 0.875000 | 0.281250 | 0.593750 | 1.866667 | 1.800000 | 1.900000 |
6 | 64 | 50 | 15 | 35 | 0.781250 | 0.234375 | 0.546875 | 1.785714 | 1.666667 | 1.842105 |
7 | 128 | 91 | 24 | 67 | 0.710938 | 0.187500 | 0.523438 | 1.820000 | 1.600000 | 1.914286 |
8 | 256 | 166 | 41 | 125 | 0.648438 | 0.160156 | 0.488281 | 1.824176 | 1.708333 | 1.865672 |
9 | 512 | 318 | 76 | 242 | 0.621094 | 0.148438 | 0.472656 | 1.915663 | 1.853659 | 1.936000 |
10 | 1.024 | 636 | 136 | 500 | 0.621094 | 0.132812 | 0.488281 | 2.000000 | 1.789474 | 2.066116 |
11 | 2.048 | 1.284 | 241 | 1.043 | 0.626953 | 0.117676 | 0.509277 | 2.018868 | 1.772059 | 2.086000 |
12 | 4.096 | 2.593 | 425 | 2.168 | 0.633057 | 0.103760 | 0.529297 | 2.019470 | 1.763485 | 2.078619 |
13 | 8.192 | 5.241 | 760 | 4.481 | 0.639771 | 0.092773 | 0.546997 | 2.021211 | 1.788235 | 2.066882 |
14 | 16.384 | 10.528 | 1.407 | 9.121 | 0.642578 | 0.085876 | 0.556702 | 2.008777 | 1.851316 | 2.035483 |
15 | 32.768 | 21.201 | 2.588 | 18.613 | 0.647003 | 0.078979 | 0.568024 | 2.013773 | 1.839375 | 2.040675 |
16 | 65.536 | 42.611 | 4.835 | 37.776 | 0.650192 | 0.073776 | 0.576416 | 2.009858 | 1.868238 | 2.029549 |
17 | 131.072 | 85.648 | 8.903 | 76.745 | 0.653442 | 0.067924 | 0.585518 | 2.009997 | 1.841365 | 2.031581 |
18 | 262.144 | 172.006 | 16.815 | 155.191 | 0.656151 | 0.064144 | 0.592007 | 2.008290 | 1.888689 | 2.022164 |
19 | 524.288 | 345.025 | 31.599 | 313.426 | 0.658083 | 0.060270 | 0.597813 | 2.005889 | 1.879215 | 2.019614 |
20 | 1.048.576 | 692.246 | 59.322 | 632.924 | 0.660177 | 0.056574 | 0.603603 | 2.006365 | 1.877338 | 2.019373 |
21 | 2.097.152 | 1.387.865 | 112.547 | 1.275.318 | 0.661786 | 0.053667 | 0.608119 | 2.004873 | 1.897222 | 2.014962 |
22 | 4.194.304 | 2.781.975 | 213.427 | 2.568.548 | 0.663275 | 0.050885 | 0.612390 | 2.004500 | 1.896337 | 2.014045 |
23 | 8.388.608 | 5.574.130 | 406.842 | 5.167.288 | 0.664488 | 0.048499 | 0.615989 | 2.003659 | 1.906235 | 2.011755 |
24 | 16.777.216 | 11.167.344 | 776.772 | 10.390.572 | 0.665626 | 0.046299 | 0.619326 | 2.003424 | 1.909272 | 2.010837 |
25 | 33.554.432 | 22.372.980 | 1.484.972 | 20.888.008 | 0.666767 | 0.044256 | 0.622511 | 2.003429 | 1.911722 | 2.010285 |
26 | 67.108.864 | 44.814.573 | 2.844.627 | 41.969.946 | 0.667789 | 0.042388 | 0.625401 | 2.003067 | 1.915610 | 2.009284 |
27 | 134.217.728 | 89.754.980 | 5.459.816 | 84.295.164 | 0.668727 | 0.040679 | 0.628048 | 2.002808 | 1.919343 | 2.008465 |
28 | 268.435.456 | 179.745.623 | 10.495.814 | 169.249.809 | 0.669605 | 0.039100 | 0.630505 | 2.002626 | 1.922375 | 2.007823 |
29 | 536.870.912 | 359.925.293 | 20.208.755 | 339.716.538 | 0.670413 | 0.037642 | 0.632771 | 2.002415 | 1.925411 | 2.007190 |
30 | 1.073.741.824 | 720.669.498 | 38.964.928 | 681.704.570 | 0.671176 | 0.036289 | 0.634887 | 2.002275 | 1.928121 | 2.006686 |
31 | 2.147.483.648 | 1.442.878.047 | 75.213.681 | 1.367.664.366 | 0.671892 | 0.035024 | 0.636868 | 2.002136 | 1.930292 | 2.006242 |
32 | 4.294.967.296 | 2.888.623.828 | 145.373.153 | 2.743.250.675 | 0.672560 | 0.033847 | 0.638713 | 2.001987 | 1.932802 | 2.005792 |
33 | 8.589.934.592 | 5.782.620.506 | 281.284.284 | 5.501.336.222 | 0.673186 | 0.032746 | 0.640440 | 2.001860 | 1.934912 | 2.005408 |
34 | 17.179.869.184 | 11.575.375.904 | 544.859.801 | 11.030.516.103 | 0.673776 | 0.031715 | 0.642061 | 2.001753 | 1.937043 | 2.005061 |
35 | 34.359.738.368 | 23.169.805.122 | 1.056.471.940 | 22.113.333.182 | 0.674330 | 0.030747 | 0.643583 | 2.001646 | 1.938980 | 2.004742 |
36 | 68.719.476.736 | 46.375.661.313 | 2.050.363.455 | 44.325.297.858 | 0.674855 | 0.029837 | 0.645018 | 2.001556 | 1.940765 | 2.004460 |
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 | 1 | 1 | 0 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 0 | 2 | 0 | 1 | 2 | 0 |
4 | 16 | 5 | 1 | 3 | 0 | 1 | 3 | 1 |
5 | 32 | 9 | 1 | 7 | 1 | 1 | 6 | 1 |
6 | 64 | 15 | 4 | 10 | 1 | 2 | 9 | 3 |
7 | 128 | 24 | 6 | 17 | 2 | 3 | 15 | 4 |
8 | 256 | 41 | 10 | 30 | 6 | 5 | 24 | 6 |
9 | 512 | 76 | 16 | 59 | 12 | 9 | 47 | 8 |
10 | 1.024 | 136 | 32 | 103 | 19 | 17 | 84 | 16 |
11 | 2.048 | 241 | 66 | 174 | 31 | 32 | 143 | 35 |
12 | 4.096 | 425 | 118 | 306 | 58 | 59 | 248 | 60 |
13 | 8.192 | 760 | 207 | 552 | 100 | 98 | 452 | 110 |
14 | 16.384 | 1.407 | 384 | 1.022 | 175 | 183 | 847 | 202 |
15 | 32.768 | 2.588 | 686 | 1.901 | 333 | 323 | 1.568 | 364 |
16 | 65.536 | 4.835 | 1.245 | 3.589 | 622 | 611 | 2.967 | 635 |
17 | 131.072 | 8.903 | 2.319 | 6.583 | 1.136 | 1.163 | 5.447 | 1.157 |
18 | 262.144 | 16.815 | 4.368 | 12.446 | 2.150 | 2.195 | 10.296 | 2.174 |
19 | 524.288 | 31.599 | 8.290 | 23.308 | 4.017 | 4.176 | 19.291 | 4.115 |
20 | 1.048.576 | 59.322 | 15.606 | 43.715 | 7.520 | 7.831 | 36.195 | 7.776 |
21 | 2.097.152 | 112.547 | 29.478 | 83.068 | 14.338 | 14.751 | 68.730 | 14.728 |
22 | 4.194.304 | 213.427 | 55.817 | 157.609 | 27.172 | 27.916 | 130.437 | 27.902 |
23 | 8.388.608 | 406.842 | 106.053 | 300.788 | 51.664 | 52.892 | 249.124 | 53.162 |
24 | 16.777.216 | 776.772 | 202.229 | 574.542 | 98.577 | 100.676 | 475.965 | 101.554 |
25 | 33.554.432 | 1.484.972 | 386.120 | 1.098.851 | 188.252 | 192.716 | 910.599 | 193.405 |
26 | 67.108.864 | 2.844.627 | 738.009 | 2.106.617 | 360.933 | 368.450 | 1.745.684 | 369.560 |
27 | 134.217.728 | 5.459.816 | 1.414.139 | 4.045.676 | 692.908 | 705.869 | 3.352.768 | 708.271 |
28 | 268.435.456 | 10.495.814 | 2.715.083 | 7.780.730 | 1.331.472 | 1.356.619 | 6.449.258 | 1.358.465 |
29 | 536.870.912 | 20.208.755 | 5.221.022 | 14.987.732 | 2.562.563 | 2.610.769 | 12.425.169 | 2.610.254 |
30 | 1.073.741.824 | 38.964.928 | 10.053.660 | 28.911.267 | 4.936.682 | 5.027.597 | 23.974.585 | 5.026.064 |
31 | 2.147.483.648 | 75.213.681 | 19.384.245 | 55.829.435 | 9.523.217 | 9.692.840 | 46.306.218 | 9.691.406 |
32 | 4.294.967.296 | 145.373.153 | 37.426.925 | 107.946.227 | 18.396.329 | 18.714.627 | 89.549.898 | 18.712.299 |
33 | 8.589.934.592 | 281.284.284 | 72.345.213 | 208.939.070 | 35.576.666 | 36.174.549 | 173.362.404 | 36.170.665 |
34 | 17.179.869.184 | 544.859.801 | 140.018.189 | 404.841.611 | 68.888.374 | 70.011.682 | 335.953.237 | 70.006.508 |
35 | 34.359.738.368 | 1.056.471.940 | 271.265.695 | 785.206.244 | 133.532.202 | 135.641.794 | 651.674.042 | 135.623.902 |
36 | 68.719.476.736 | 2.050.363.455 | 526.039.774 | 1.524.323.680 | 259.080.003 | 263.025.368 | 1.265.243.677 | 263.014.407 |
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 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 6 | 3 | 3 | 2 | 1 | 1 | 2 |
4 | 16 | 10 | 3 | 7 | 2 | 2 | 2 | 4 |
5 | 32 | 19 | 8 | 11 | 2 | 3 | 5 | 9 |
6 | 64 | 35 | 16 | 19 | 4 | 7 | 11 | 13 |
7 | 128 | 67 | 30 | 37 | 6 | 12 | 21 | 28 |
8 | 256 | 125 | 59 | 66 | 13 | 18 | 41 | 53 |
9 | 512 | 242 | 118 | 124 | 35 | 35 | 66 | 106 |
10 | 1.024 | 500 | 259 | 241 | 79 | 77 | 139 | 205 |
11 | 2.048 | 1.043 | 547 | 496 | 169 | 182 | 303 | 389 |
12 | 4.096 | 2.168 | 1.093 | 1.075 | 380 | 398 | 583 | 807 |
13 | 8.192 | 4.481 | 2.267 | 2.214 | 836 | 856 | 1.196 | 1.593 |
14 | 16.384 | 9.121 | 4.687 | 4.434 | 1.767 | 1.829 | 2.411 | 3.114 |
15 | 32.768 | 18.613 | 9.572 | 9.041 | 3.774 | 3.777 | 4.854 | 6.208 |
16 | 65.536 | 37.776 | 19.356 | 18.420 | 7.773 | 7.821 | 9.893 | 12.289 |
17 | 131.072 | 76.745 | 39.415 | 37.330 | 16.024 | 16.185 | 20.001 | 24.535 |
18 | 262.144 | 155.191 | 79.539 | 75.652 | 32.932 | 33.269 | 40.282 | 48.708 |
19 | 524.288 | 313.426 | 160.121 | 153.305 | 67.812 | 67.769 | 81.123 | 96.722 |
20 | 1.048.576 | 632.924 | 322.858 | 310.066 | 138.447 | 138.245 | 163.357 | 192.875 |
21 | 2.097.152 | 1.275.318 | 649.845 | 625.473 | 281.650 | 281.427 | 328.150 | 384.091 |
22 | 4.194.304 | 2.568.548 | 1.306.988 | 1.261.560 | 571.439 | 571.087 | 660.214 | 765.808 |
23 | 8.388.608 | 5.167.288 | 2.626.525 | 2.540.763 | 1.157.182 | 1.157.388 | 1.326.460 | 1.526.258 |
24 | 16.777.216 | 10.390.572 | 5.275.884 | 5.114.688 | 2.341.411 | 2.340.377 | 2.662.588 | 3.046.196 |
25 | 33.554.432 | 20.888.008 | 10.597.072 | 10.290.936 | 4.733.147 | 4.729.684 | 5.344.038 | 6.081.139 |
26 | 67.108.864 | 41.969.946 | 21.278.558 | 20.691.388 | 9.557.314 | 9.551.774 | 10.723.318 | 12.137.540 |
27 | 134.217.728 | 84.295.164 | 42.706.119 | 41.589.045 | 19.280.596 | 19.269.606 | 21.515.666 | 24.229.296 |
28 | 268.435.456 | 169.249.809 | 85.699.800 | 83.550.009 | 38.866.580 | 38.848.940 | 43.162.926 | 48.371.363 |
29 | 536.870.912 | 339.716.538 | 171.916.042 | 167.800.496 | 78.303.049 | 78.255.212 | 86.568.688 | 96.589.589 |
30 | 1.073.741.824 | 681.704.570 | 344.824.857 | 336.879.713 | 157.668.087 | 157.571.246 | 173.574.080 | 192.891.157 |
31 | 2.147.483.648 | 1.367.664.366 | 691.493.046 | 676.171.320 | 317.300.423 | 317.120.082 | 347.961.484 | 385.282.377 |
32 | 4.294.967.296 | 2.743.250.675 | 1.386.412.932 | 1.356.837.743 | 638.300.501 | 637.923.365 | 697.453.224 | 769.573.585 |
33 | 8.589.934.592 | 5.501.336.222 | 2.779.206.876 | 2.722.129.346 | 1.283.425.793 | 1.282.758.626 | 1.397.770.409 | 1.537.381.394 |
34 | 17.179.869.184 | 11.030.516.103 | 5.570.458.444 | 5.460.057.659 | 2.579.721.654 | 2.578.439.316 | 2.800.901.468 | 3.071.453.665 |
35 | 34.359.738.368 | 22.113.333.182 | 11.163.615.969 | 10.949.717.213 | 5.183.630.552 | 5.181.025.496 | 5.612.025.392 | 6.136.651.742 |
36 | 68.719.476.736 | 44.325.297.858 | 22.370.043.038 | 21.955.254.820 | 10.412.662.206 | 10.407.700.672 | 11.243.284.573 | 12.261.650.407 |