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-40x-73
f(0)=73
f(1)=7
f(2)=149
f(3)=23
f(4)=31
f(5)=1
f(6)=277
f(7)=19
f(8)=47
f(9)=11
f(10)=373
f(11)=1
f(12)=409
f(13)=53
f(14)=1
f(15)=1
f(16)=457
f(17)=29
f(18)=67
f(19)=59
f(20)=43
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=103
f(45)=1
f(46)=1
f(47)=1
f(48)=311
f(49)=1
f(50)=61
f(51)=1
f(52)=1
f(53)=1
f(54)=683
f(55)=1
f(56)=823
f(57)=1
f(58)=971
f(59)=131
f(60)=1
f(61)=151
f(62)=1291
f(63)=1
f(64)=1
f(65)=97
f(66)=1
f(67)=1
f(68)=1831
f(69)=241
f(70)=2027
f(71)=1
f(72)=1
f(73)=1
f(74)=349
f(75)=1
f(76)=2663
f(77)=347
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=3371
f(83)=1
f(84)=3623
f(85)=1
f(86)=353
f(87)=251
f(88)=593
f(89)=1
f(90)=233
f(91)=571
f(92)=673
f(93)=607
f(94)=5003
f(95)=1
f(96)=5303
f(97)=1
f(98)=181
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-40x-73 could be written as f(y)= y^2-473 with x=y+20
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-20
f'(x)>2x-41 with x > 22
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 | 10 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 42 | 20 | 22 | 0.420000 | 0.200000 | 0.420000 | 4.200000 | 5.000000 | 3.666667 |
3 | 1.000 | 602 | 143 | 459 | 0.602000 | 0.143000 | 0.602000 | 14.333333 | 7.150000 | 20.863636 |
4 | 10.000 | 6.510 | 1.002 | 5.508 | 0.651000 | 0.100200 | 0.651000 | 10.813953 | 7.006993 | 12.000000 |
5 | 100.000 | 66.312 | 7.729 | 58.583 | 0.663120 | 0.077290 | 0.663120 | 10.186175 | 7.713573 | 10.635984 |
6 | 1.000.000 | 668.785 | 63.416 | 605.369 | 0.668785 | 0.063416 | 0.668785 | 10.085429 | 8.204943 | 10.333527 |
7 | 10.000.000 | 6.722.909 | 533.030 | 6.189.879 | 0.672291 | 0.053303 | 0.672291 | 10.052422 | 8.405293 | 10.224969 |
8 | 100.000.000 | 67.488.145 | 4.623.696 | 62.864.449 | 0.674881 | 0.046237 | 0.674881 | 10.038533 | 8.674363 | 10.156006 |
9 | 1.000.000.000 | 676.893.411 | 40.800.102 | 636.093.309 | 0.676893 | 0.040800 | 0.676893 | 10.029813 | 8.824132 | 10.118490 |
10 | 10.000.000.000 | 6.785.069.762 | 365.125.049 | 6.419.944.713 | 0.678507 | 0.036513 | 0.678507 | 10.023837 | 8.949121 | 10.092772 |
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 | 8 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.500000 | 1.666667 |
4 | 16 | 13 | 6 | 7 | 0.812500 | 0.375000 | 0.437500 | 1.625000 | 2.000000 | 1.400000 |
5 | 32 | 16 | 6 | 10 | 0.500000 | 0.187500 | 0.312500 | 1.230769 | 1.000000 | 1.428571 |
6 | 64 | 24 | 12 | 12 | 0.375000 | 0.187500 | 0.187500 | 1.500000 | 2.000000 | 1.200000 |
7 | 128 | 58 | 23 | 35 | 0.453125 | 0.179688 | 0.273438 | 2.416667 | 1.916667 | 2.916667 |
8 | 256 | 137 | 42 | 95 | 0.535156 | 0.164062 | 0.371094 | 2.362069 | 1.826087 | 2.714286 |
9 | 512 | 295 | 81 | 214 | 0.576172 | 0.158203 | 0.417969 | 2.153285 | 1.928571 | 2.252632 |
10 | 1.024 | 618 | 146 | 472 | 0.603516 | 0.142578 | 0.460938 | 2.094915 | 1.802469 | 2.205607 |
11 | 2.048 | 1.294 | 260 | 1.034 | 0.631836 | 0.126953 | 0.504883 | 2.093851 | 1.780822 | 2.190678 |
12 | 4.096 | 2.642 | 462 | 2.180 | 0.645020 | 0.112793 | 0.532227 | 2.041731 | 1.776923 | 2.108317 |
13 | 8.192 | 5.334 | 837 | 4.497 | 0.651123 | 0.102173 | 0.548950 | 2.018925 | 1.811688 | 2.062844 |
14 | 16.384 | 10.745 | 1.541 | 9.204 | 0.655823 | 0.094055 | 0.561768 | 2.014436 | 1.841099 | 2.046698 |
15 | 32.768 | 21.587 | 2.849 | 18.738 | 0.658783 | 0.086945 | 0.571838 | 2.009027 | 1.848799 | 2.035854 |
16 | 65.536 | 43.356 | 5.282 | 38.074 | 0.661560 | 0.080597 | 0.580963 | 2.008431 | 1.853984 | 2.031914 |
17 | 131.072 | 87.042 | 9.892 | 77.150 | 0.664078 | 0.075470 | 0.588608 | 2.007612 | 1.872775 | 2.026317 |
18 | 262.144 | 174.555 | 18.488 | 156.067 | 0.665874 | 0.070526 | 0.595348 | 2.005411 | 1.868985 | 2.022903 |
19 | 524.288 | 349.989 | 35.006 | 314.983 | 0.667551 | 0.066769 | 0.600782 | 2.005036 | 1.893444 | 2.018255 |
20 | 1.048.576 | 701.450 | 66.207 | 635.243 | 0.668955 | 0.063140 | 0.605815 | 2.004206 | 1.891304 | 2.016753 |
21 | 2.097.152 | 1.405.217 | 125.048 | 1.280.169 | 0.670060 | 0.059628 | 0.610432 | 2.003303 | 1.888743 | 2.015243 |
22 | 4.194.304 | 2.815.210 | 237.005 | 2.578.205 | 0.671198 | 0.056506 | 0.614692 | 2.003399 | 1.895312 | 2.013957 |
23 | 8.388.608 | 5.638.188 | 452.253 | 5.185.935 | 0.672124 | 0.053913 | 0.618212 | 2.002759 | 1.908200 | 2.011452 |
24 | 16.777.216 | 11.289.612 | 865.100 | 10.424.512 | 0.672913 | 0.051564 | 0.621349 | 2.002347 | 1.912867 | 2.010151 |
25 | 33.554.432 | 22.607.592 | 1.655.820 | 20.951.772 | 0.673759 | 0.049347 | 0.624411 | 2.002513 | 1.914021 | 2.009856 |
26 | 67.108.864 | 45.263.442 | 3.175.656 | 42.087.786 | 0.674478 | 0.047321 | 0.627157 | 2.002135 | 1.917875 | 2.008794 |
27 | 134.217.728 | 90.619.783 | 6.101.395 | 84.518.388 | 0.675170 | 0.045459 | 0.629711 | 2.002053 | 1.921302 | 2.008145 |
28 | 268.435.456 | 181.409.847 | 11.740.524 | 169.669.323 | 0.675804 | 0.043737 | 0.632068 | 2.001879 | 1.924236 | 2.007484 |
29 | 536.870.912 | 363.137.467 | 22.623.625 | 340.513.842 | 0.676396 | 0.042140 | 0.634256 | 2.001752 | 1.926969 | 2.006926 |
30 | 1.073.741.824 | 726.866.881 | 43.650.596 | 683.216.285 | 0.676948 | 0.040653 | 0.636295 | 2.001630 | 1.929425 | 2.006427 |
31 | 2.147.483.648 | 1.454.851.740 | 84.321.794 | 1.370.529.946 | 0.677468 | 0.039265 | 0.638203 | 2.001538 | 1.931744 | 2.005997 |
32 | 4.294.967.296 | 2.911.783.432 | 163.108.879 | 2.748.674.553 | 0.677952 | 0.037977 | 0.639976 | 2.001430 | 1.934362 | 2.005556 |
33 | 8.589.934.592 | 5.827.499.761 | 315.837.650 | 5.511.662.111 | 0.678410 | 0.036768 | 0.641642 | 2.001351 | 1.936361 | 2.005207 |
34 | 17.179.869.184 | 11.662.399.805 | 612.172.027 | 11.050.227.778 | 0.678841 | 0.035633 | 0.643208 | 2.001270 | 1.938249 | 2.004881 |
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 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
3 | 8 | 3 | 2 | 1 | 1 | 0 | 2 | 0 |
4 | 16 | 6 | 5 | 1 | 3 | 0 | 3 | 0 |
5 | 32 | 6 | 5 | 1 | 3 | 0 | 3 | 0 |
6 | 64 | 12 | 8 | 4 | 3 | 3 | 3 | 3 |
7 | 128 | 23 | 10 | 13 | 3 | 8 | 3 | 9 |
8 | 256 | 42 | 19 | 23 | 3 | 18 | 3 | 18 |
9 | 512 | 81 | 32 | 49 | 3 | 34 | 3 | 41 |
10 | 1.024 | 146 | 57 | 89 | 3 | 70 | 3 | 70 |
11 | 2.048 | 260 | 98 | 162 | 3 | 123 | 3 | 131 |
12 | 4.096 | 462 | 165 | 297 | 3 | 231 | 3 | 225 |
13 | 8.192 | 837 | 293 | 544 | 3 | 410 | 3 | 421 |
14 | 16.384 | 1.541 | 533 | 1.008 | 3 | 768 | 3 | 767 |
15 | 32.768 | 2.849 | 981 | 1.868 | 3 | 1.415 | 3 | 1.428 |
16 | 65.536 | 5.282 | 1.788 | 3.494 | 3 | 2.610 | 3 | 2.666 |
17 | 131.072 | 9.892 | 3.350 | 6.542 | 3 | 4.922 | 3 | 4.964 |
18 | 262.144 | 18.488 | 6.207 | 12.281 | 3 | 9.273 | 3 | 9.209 |
19 | 524.288 | 35.006 | 11.724 | 23.282 | 3 | 17.432 | 3 | 17.568 |
20 | 1.048.576 | 66.207 | 22.027 | 44.180 | 3 | 33.161 | 3 | 33.040 |
21 | 2.097.152 | 125.048 | 41.573 | 83.475 | 3 | 62.505 | 3 | 62.537 |
22 | 4.194.304 | 237.005 | 79.026 | 157.979 | 3 | 118.446 | 3 | 118.553 |
23 | 8.388.608 | 452.253 | 150.753 | 301.500 | 3 | 226.007 | 3 | 226.240 |
24 | 16.777.216 | 865.100 | 288.656 | 576.444 | 3 | 432.332 | 3 | 432.762 |
25 | 33.554.432 | 1.655.820 | 552.128 | 1.103.692 | 3 | 828.144 | 3 | 827.670 |
26 | 67.108.864 | 3.175.656 | 1.059.092 | 2.116.564 | 3 | 1.587.692 | 3 | 1.587.958 |
27 | 134.217.728 | 6.101.395 | 2.034.433 | 4.066.962 | 3 | 3.049.750 | 3 | 3.051.639 |
28 | 268.435.456 | 11.740.524 | 3.913.742 | 7.826.782 | 3 | 5.868.654 | 3 | 5.871.864 |
29 | 536.870.912 | 22.623.625 | 7.540.954 | 15.082.671 | 3 | 11.309.301 | 3 | 11.314.318 |
30 | 1.073.741.824 | 43.650.596 | 14.549.729 | 29.100.867 | 3 | 21.822.605 | 3 | 21.827.985 |
31 | 2.147.483.648 | 84.321.794 | 28.106.336 | 56.215.458 | 3 | 42.155.373 | 3 | 42.166.415 |
32 | 4.294.967.296 | 163.108.879 | 54.365.736 | 108.743.143 | 3 | 81.551.491 | 3 | 81.557.382 |
33 | 8.589.934.592 | 315.837.650 | 105.275.975 | 210.561.675 | 3 | 157.917.820 | 3 | 157.919.824 |
34 | 17.179.869.184 | 612.172.027 | 204.064.421 | 408.107.606 | 3 | 306.087.201 | 3 | 306.084.820 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 0 | 0 | 3 |
3 | 8 | 5 | 3 | 2 | 0 | 1 | 0 | 4 |
4 | 16 | 7 | 3 | 4 | 0 | 2 | 1 | 4 |
5 | 32 | 10 | 5 | 5 | 0 | 5 | 1 | 4 |
6 | 64 | 12 | 6 | 6 | 0 | 6 | 1 | 5 |
7 | 128 | 35 | 17 | 18 | 9 | 11 | 6 | 9 |
8 | 256 | 95 | 45 | 50 | 29 | 21 | 23 | 22 |
9 | 512 | 214 | 100 | 114 | 64 | 44 | 63 | 43 |
10 | 1.024 | 472 | 224 | 248 | 133 | 111 | 133 | 95 |
11 | 2.048 | 1.034 | 515 | 519 | 292 | 227 | 293 | 222 |
12 | 4.096 | 2.180 | 1.093 | 1.087 | 605 | 492 | 604 | 479 |
13 | 8.192 | 4.497 | 2.251 | 2.246 | 1.229 | 1.007 | 1.256 | 1.005 |
14 | 16.384 | 9.204 | 4.600 | 4.604 | 2.530 | 2.074 | 2.510 | 2.090 |
15 | 32.768 | 18.738 | 9.362 | 9.376 | 5.041 | 4.276 | 5.083 | 4.338 |
16 | 65.536 | 38.074 | 19.008 | 19.066 | 10.185 | 8.778 | 10.299 | 8.812 |
17 | 131.072 | 77.150 | 38.660 | 38.490 | 20.663 | 17.963 | 20.576 | 17.948 |
18 | 262.144 | 156.067 | 78.635 | 77.432 | 41.464 | 36.700 | 41.474 | 36.429 |
19 | 524.288 | 314.983 | 158.503 | 156.480 | 83.129 | 74.078 | 83.645 | 74.131 |
20 | 1.048.576 | 635.243 | 319.465 | 315.778 | 167.370 | 150.113 | 167.681 | 150.079 |
21 | 2.097.152 | 1.280.169 | 643.403 | 636.766 | 337.059 | 303.115 | 336.556 | 303.439 |
22 | 4.194.304 | 2.578.205 | 1.294.735 | 1.283.470 | 676.830 | 612.267 | 676.053 | 613.055 |
23 | 8.388.608 | 5.185.935 | 2.603.738 | 2.582.197 | 1.356.959 | 1.235.673 | 1.356.271 | 1.237.032 |
24 | 16.777.216 | 10.424.512 | 5.233.921 | 5.190.591 | 2.719.422 | 2.492.397 | 2.719.562 | 2.493.131 |
25 | 33.554.432 | 20.951.772 | 10.517.550 | 10.434.222 | 5.454.167 | 5.022.157 | 5.454.893 | 5.020.555 |
26 | 67.108.864 | 42.087.786 | 21.126.809 | 20.960.977 | 10.936.694 | 10.108.292 | 10.936.047 | 10.106.753 |
27 | 134.217.728 | 84.518.388 | 42.415.589 | 42.102.799 | 21.923.506 | 20.337.658 | 21.921.246 | 20.335.978 |
28 | 268.435.456 | 169.669.323 | 85.137.248 | 84.532.075 | 43.942.509 | 40.898.078 | 43.934.826 | 40.893.910 |
29 | 536.870.912 | 340.513.842 | 170.830.674 | 169.683.168 | 88.061.556 | 82.200.973 | 88.054.114 | 82.197.199 |
30 | 1.073.741.824 | 683.216.285 | 342.699.969 | 340.516.316 | 176.460.574 | 165.160.422 | 176.446.491 | 165.148.798 |
31 | 2.147.483.648 | 1.370.529.946 | 687.371.996 | 683.157.950 | 353.508.599 | 331.762.927 | 353.519.557 | 331.738.863 |
32 | 4.294.967.296 | 2.748.674.553 | 1.378.408.649 | 1.370.265.904 | 708.177.350 | 666.145.891 | 708.224.971 | 666.126.341 |
33 | 8.589.934.592 | 5.511.662.111 | 2.763.711.854 | 2.747.950.257 | 1.418.572.964 | 1.337.232.563 | 1.418.621.899 | 1.337.234.685 |
34 | 17.179.869.184 | 11.050.227.778 | 5.540.358.803 | 5.509.868.975 | 2.841.306.152 | 2.683.769.061 | 2.841.397.513 | 2.683.755.052 |