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+4x-31
f(0)=31
f(1)=13
f(2)=19
f(3)=5
f(4)=1
f(5)=7
f(6)=29
f(7)=23
f(8)=1
f(9)=43
f(10)=109
f(11)=67
f(12)=1
f(13)=1
f(14)=17
f(15)=127
f(16)=1
f(17)=163
f(18)=73
f(19)=1
f(20)=449
f(21)=1
f(22)=541
f(23)=59
f(24)=641
f(25)=347
f(26)=107
f(27)=1
f(28)=173
f(29)=463
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=97
f(35)=1
f(36)=1409
f(37)=743
f(38)=313
f(39)=823
f(40)=1
f(41)=907
f(42)=1901
f(43)=199
f(44)=2081
f(45)=1087
f(46)=2269
f(47)=1
f(48)=1
f(49)=1283
f(50)=157
f(51)=1
f(52)=1
f(53)=1
f(54)=443
f(55)=1607
f(56)=3329
f(57)=1723
f(58)=1
f(59)=1
f(60)=293
f(61)=281
f(62)=131
f(63)=419
f(64)=149
f(65)=1
f(66)=353
f(67)=139
f(68)=1
f(69)=2503
f(70)=271
f(71)=2647
f(72)=5441
f(73)=1
f(74)=5741
f(75)=421
f(76)=263
f(77)=1
f(78)=1
f(79)=251
f(80)=6689
f(81)=1
f(82)=1
f(83)=719
f(84)=433
f(85)=3767
f(86)=593
f(87)=3943
f(88)=1613
f(89)=1
f(90)=8429
f(91)=1
f(92)=677
f(93)=1
f(94)=9181
f(95)=1
f(96)=1367
f(97)=257
f(98)=1993
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+4x-31 could be written as f(y)= y^2-35 with x=y-2
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+2
f'(x)>2x+3
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.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 18 | 49 | 0.670000 | 0.180000 | 0.670000 | 7.444445 | 4.500000 | 9.800000 |
3 | 1.000 | 691 | 121 | 570 | 0.691000 | 0.121000 | 0.691000 | 10.313433 | 6.722222 | 11.632653 |
4 | 10.000 | 6.962 | 849 | 6.113 | 0.696200 | 0.084900 | 0.696200 | 10.075253 | 7.016529 | 10.724562 |
5 | 100.000 | 69.698 | 6.451 | 63.247 | 0.696980 | 0.064510 | 0.696980 | 10.011204 | 7.598351 | 10.346312 |
6 | 1.000.000 | 696.254 | 52.382 | 643.872 | 0.696254 | 0.052382 | 0.696254 | 9.989584 | 8.119982 | 10.180277 |
7 | 10.000.000 | 6.955.700 | 443.051 | 6.512.649 | 0.695570 | 0.044305 | 0.695570 | 9.990176 | 8.458077 | 10.114820 |
8 | 100.000.000 | 69.507.404 | 3.839.086 | 65.668.318 | 0.695074 | 0.038391 | 0.695074 | 9.992870 | 8.665111 | 10.083197 |
9 | 1.000.000.000 | 694.724.830 | 33.857.833 | 660.866.997 | 0.694725 | 0.033858 | 0.694725 | 9.994975 | 8.819242 | 10.063711 |
10 | 10.000.000.000 | 6.944.647.370 | 303.022.519 | 6.641.624.851 | 0.694465 | 0.030302 | 0.694465 | 9.996256 | 8.949850 | 10.049867 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
4 | 16 | 11 | 4 | 7 | 0.687500 | 0.250000 | 0.437500 | 1.571429 | 1.333333 | 1.750000 |
5 | 32 | 21 | 7 | 14 | 0.656250 | 0.218750 | 0.437500 | 1.909091 | 1.750000 | 2.000000 |
6 | 64 | 43 | 12 | 31 | 0.671875 | 0.187500 | 0.484375 | 2.047619 | 1.714286 | 2.214286 |
7 | 128 | 87 | 21 | 66 | 0.679688 | 0.164062 | 0.515625 | 2.023256 | 1.750000 | 2.129032 |
8 | 256 | 175 | 37 | 138 | 0.683594 | 0.144531 | 0.539062 | 2.011494 | 1.761905 | 2.090909 |
9 | 512 | 353 | 71 | 282 | 0.689453 | 0.138672 | 0.550781 | 2.017143 | 1.918919 | 2.043478 |
10 | 1.024 | 712 | 122 | 590 | 0.695312 | 0.119141 | 0.576172 | 2.016997 | 1.718310 | 2.092199 |
11 | 2.048 | 1.436 | 226 | 1.210 | 0.701172 | 0.110352 | 0.590820 | 2.016854 | 1.852459 | 2.050848 |
12 | 4.096 | 2.852 | 396 | 2.456 | 0.696289 | 0.096680 | 0.599609 | 1.986072 | 1.752212 | 2.029752 |
13 | 8.192 | 5.682 | 708 | 4.974 | 0.693604 | 0.086426 | 0.607178 | 1.992286 | 1.787879 | 2.025244 |
14 | 16.384 | 11.419 | 1.301 | 10.118 | 0.696960 | 0.079407 | 0.617554 | 2.009680 | 1.837571 | 2.034178 |
15 | 32.768 | 22.805 | 2.382 | 20.423 | 0.695953 | 0.072693 | 0.623260 | 1.997110 | 1.830899 | 2.018482 |
16 | 65.536 | 45.673 | 4.425 | 41.248 | 0.696915 | 0.067520 | 0.629395 | 2.002763 | 1.857683 | 2.019684 |
17 | 131.072 | 91.316 | 8.217 | 83.099 | 0.696686 | 0.062691 | 0.633995 | 1.999343 | 1.856949 | 2.014619 |
18 | 262.144 | 182.659 | 15.478 | 167.181 | 0.696789 | 0.059044 | 0.637745 | 2.000296 | 1.883656 | 2.011829 |
19 | 524.288 | 365.200 | 28.934 | 336.266 | 0.696564 | 0.055187 | 0.641376 | 1.999354 | 1.869363 | 2.011389 |
20 | 1.048.576 | 730.023 | 54.787 | 675.236 | 0.696204 | 0.052249 | 0.643955 | 1.998968 | 1.893516 | 2.008041 |
21 | 2.097.152 | 1.459.480 | 103.946 | 1.355.534 | 0.695934 | 0.049565 | 0.646369 | 1.999225 | 1.897275 | 2.007497 |
22 | 4.194.304 | 2.918.411 | 197.299 | 2.721.112 | 0.695803 | 0.047040 | 0.648764 | 1.999624 | 1.898091 | 2.007410 |
23 | 8.388.608 | 5.835.445 | 376.020 | 5.459.425 | 0.695639 | 0.044825 | 0.650814 | 1.999528 | 1.905838 | 2.006321 |
24 | 16.777.216 | 11.667.586 | 718.493 | 10.949.093 | 0.695442 | 0.042826 | 0.652617 | 1.999434 | 1.910784 | 2.005540 |
25 | 33.554.432 | 23.329.728 | 1.374.230 | 21.955.498 | 0.695280 | 0.040955 | 0.654325 | 1.999533 | 1.912656 | 2.005234 |
26 | 67.108.864 | 46.649.530 | 2.637.169 | 44.012.361 | 0.695132 | 0.039297 | 0.655835 | 1.999574 | 1.919016 | 2.004617 |
27 | 134.217.728 | 93.284.482 | 5.065.218 | 88.219.264 | 0.695024 | 0.037739 | 0.657285 | 1.999688 | 1.920703 | 2.004420 |
28 | 268.435.456 | 186.538.916 | 9.743.547 | 176.795.369 | 0.694912 | 0.036298 | 0.658614 | 1.999678 | 1.923618 | 2.004045 |
29 | 536.870.912 | 373.021.117 | 18.771.758 | 354.249.359 | 0.694806 | 0.034965 | 0.659841 | 1.999696 | 1.926584 | 2.003725 |
30 | 1.073.741.824 | 745.947.795 | 36.222.232 | 709.725.563 | 0.694718 | 0.033735 | 0.660983 | 1.999747 | 1.929613 | 2.003463 |
31 | 2.147.483.648 | 1.491.701.905 | 69.984.619 | 1.421.717.286 | 0.694628 | 0.032589 | 0.662039 | 1.999740 | 1.932090 | 2.003193 |
32 | 4.294.967.296 | 2.983.088.046 | 135.361.140 | 2.847.726.906 | 0.694554 | 0.031516 | 0.663038 | 1.999788 | 1.934156 | 2.003019 |
33 | 8.589.934.592 | 5.965.531.109 | 262.108.280 | 5.703.422.829 | 0.694479 | 0.030513 | 0.663966 | 1.999784 | 1.936363 | 2.002799 |
34 | 17.179.869.184 | 11.929.970.704 | 508.040.552 | 11.421.930.152 | 0.694416 | 0.029572 | 0.664844 | 1.999817 | 1.938285 | 2.002645 |
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 | 2 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 4 | 3 | 1 | 0 | 1 | 2 | 1 |
5 | 32 | 7 | 4 | 3 | 2 | 1 | 3 | 1 |
6 | 64 | 12 | 5 | 7 | 5 | 1 | 5 | 1 |
7 | 128 | 21 | 7 | 14 | 8 | 1 | 11 | 1 |
8 | 256 | 37 | 14 | 23 | 16 | 1 | 19 | 1 |
9 | 512 | 71 | 24 | 47 | 32 | 1 | 37 | 1 |
10 | 1.024 | 122 | 39 | 83 | 58 | 1 | 62 | 1 |
11 | 2.048 | 226 | 80 | 146 | 111 | 1 | 113 | 1 |
12 | 4.096 | 396 | 135 | 261 | 196 | 1 | 198 | 1 |
13 | 8.192 | 708 | 236 | 472 | 341 | 1 | 365 | 1 |
14 | 16.384 | 1.301 | 426 | 875 | 632 | 1 | 667 | 1 |
15 | 32.768 | 2.382 | 795 | 1.587 | 1.184 | 1 | 1.196 | 1 |
16 | 65.536 | 4.425 | 1.496 | 2.929 | 2.203 | 1 | 2.220 | 1 |
17 | 131.072 | 8.217 | 2.751 | 5.466 | 4.110 | 1 | 4.105 | 1 |
18 | 262.144 | 15.478 | 5.159 | 10.319 | 7.700 | 1 | 7.776 | 1 |
19 | 524.288 | 28.934 | 9.654 | 19.280 | 14.430 | 1 | 14.502 | 1 |
20 | 1.048.576 | 54.787 | 18.185 | 36.602 | 27.386 | 1 | 27.399 | 1 |
21 | 2.097.152 | 103.946 | 34.689 | 69.257 | 51.968 | 1 | 51.976 | 1 |
22 | 4.194.304 | 197.299 | 65.800 | 131.499 | 98.658 | 1 | 98.639 | 1 |
23 | 8.388.608 | 376.020 | 125.249 | 250.771 | 187.924 | 1 | 188.094 | 1 |
24 | 16.777.216 | 718.493 | 239.536 | 478.957 | 359.011 | 1 | 359.480 | 1 |
25 | 33.554.432 | 1.374.230 | 458.127 | 916.103 | 687.041 | 1 | 687.187 | 1 |
26 | 67.108.864 | 2.637.169 | 878.762 | 1.758.407 | 1.318.631 | 1 | 1.318.536 | 1 |
27 | 134.217.728 | 5.065.218 | 1.688.767 | 3.376.451 | 2.532.472 | 1 | 2.532.744 | 1 |
28 | 268.435.456 | 9.743.547 | 3.247.685 | 6.495.862 | 4.871.939 | 1 | 4.871.606 | 1 |
29 | 536.870.912 | 18.771.758 | 6.257.308 | 12.514.450 | 9.386.391 | 1 | 9.385.365 | 1 |
30 | 1.073.741.824 | 36.222.232 | 12.073.086 | 24.149.146 | 18.112.360 | 1 | 18.109.870 | 1 |
31 | 2.147.483.648 | 69.984.619 | 23.326.102 | 46.658.517 | 34.993.438 | 1 | 34.991.179 | 1 |
32 | 4.294.967.296 | 135.361.140 | 45.114.603 | 90.246.537 | 67.680.617 | 1 | 67.680.521 | 1 |
33 | 8.589.934.592 | 262.108.280 | 87.370.926 | 174.737.354 | 131.053.294 | 1 | 131.054.984 | 1 |
34 | 17.179.869.184 | 508.040.552 | 169.345.911 | 338.694.641 | 254.015.249 | 1 | 254.025.301 | 1 |
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 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 0 | 2 | 2 |
4 | 16 | 7 | 5 | 2 | 0 | 2 | 2 | 3 |
5 | 32 | 14 | 8 | 6 | 1 | 6 | 3 | 4 |
6 | 64 | 31 | 16 | 15 | 4 | 12 | 6 | 9 |
7 | 128 | 66 | 32 | 34 | 11 | 19 | 11 | 25 |
8 | 256 | 138 | 70 | 68 | 25 | 46 | 22 | 45 |
9 | 512 | 282 | 145 | 137 | 53 | 90 | 56 | 83 |
10 | 1.024 | 590 | 301 | 289 | 115 | 179 | 118 | 178 |
11 | 2.048 | 1.210 | 624 | 586 | 246 | 366 | 248 | 350 |
12 | 4.096 | 2.456 | 1.237 | 1.219 | 508 | 722 | 498 | 728 |
13 | 8.192 | 4.974 | 2.583 | 2.391 | 1.046 | 1.430 | 1.060 | 1.438 |
14 | 16.384 | 10.118 | 5.276 | 4.842 | 2.148 | 2.848 | 2.213 | 2.909 |
15 | 32.768 | 20.423 | 10.655 | 9.768 | 4.427 | 5.698 | 4.502 | 5.796 |
16 | 65.536 | 41.248 | 21.375 | 19.873 | 9.128 | 11.419 | 9.162 | 11.539 |
17 | 131.072 | 83.099 | 43.016 | 40.083 | 18.564 | 22.890 | 18.665 | 22.980 |
18 | 262.144 | 167.181 | 86.178 | 81.003 | 37.636 | 45.846 | 37.870 | 45.829 |
19 | 524.288 | 336.266 | 173.228 | 163.038 | 76.472 | 91.424 | 76.780 | 91.590 |
20 | 1.048.576 | 675.236 | 347.098 | 328.138 | 154.792 | 182.971 | 154.404 | 183.069 |
21 | 2.097.152 | 1.355.534 | 695.398 | 660.136 | 312.707 | 365.794 | 311.719 | 365.314 |
22 | 4.194.304 | 2.721.112 | 1.394.340 | 1.326.772 | 629.602 | 731.825 | 629.173 | 730.512 |
23 | 8.388.608 | 5.459.425 | 2.794.061 | 2.665.364 | 1.267.433 | 1.462.099 | 1.268.578 | 1.461.315 |
24 | 16.777.216 | 10.949.093 | 5.596.833 | 5.352.260 | 2.552.131 | 2.922.544 | 2.553.980 | 2.920.438 |
25 | 33.554.432 | 21.955.498 | 11.211.483 | 10.744.015 | 5.136.509 | 5.840.957 | 5.138.477 | 5.839.555 |
26 | 67.108.864 | 44.012.361 | 22.454.606 | 21.557.755 | 10.329.125 | 11.678.984 | 10.330.860 | 11.673.392 |
27 | 134.217.728 | 88.219.264 | 44.967.880 | 43.251.384 | 20.762.967 | 23.351.791 | 20.762.407 | 23.342.099 |
28 | 268.435.456 | 176.795.369 | 90.045.036 | 86.750.333 | 41.710.525 | 46.690.023 | 41.716.179 | 46.678.642 |
29 | 536.870.912 | 354.249.359 | 180.311.191 | 173.938.168 | 83.774.034 | 93.352.721 | 83.779.341 | 93.343.263 |
30 | 1.073.741.824 | 709.725.563 | 360.997.327 | 348.728.236 | 168.201.087 | 186.657.372 | 168.214.670 | 186.652.434 |
31 | 2.147.483.648 | 1.421.717.286 | 722.707.789 | 699.009.497 | 337.615.210 | 373.233.916 | 337.638.246 | 373.229.914 |
32 | 4.294.967.296 | 2.847.726.906 | 1.446.778.085 | 1.400.948.821 | 677.512.964 | 746.372.047 | 677.518.728 | 746.323.167 |
33 | 8.589.934.592 | 5.703.422.829 | 2.896.055.050 | 2.807.367.779 | 1.359.254.226 | 1.492.469.500 | 1.359.274.138 | 1.492.424.965 |
34 | 17.179.869.184 | 11.421.930.152 | 5.796.889.097 | 5.625.041.055 | 2.726.387.947 | 2.984.584.045 | 2.726.485.973 | 2.984.472.187 |