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-68x+5
f(0)=5
f(1)=31
f(2)=127
f(3)=19
f(4)=251
f(5)=1
f(6)=367
f(7)=211
f(8)=1
f(9)=263
f(10)=23
f(11)=311
f(12)=29
f(13)=71
f(14)=751
f(15)=79
f(16)=827
f(17)=431
f(18)=179
f(19)=463
f(20)=191
f(21)=491
f(22)=53
f(23)=103
f(24)=1051
f(25)=107
f(26)=1087
f(27)=1
f(28)=223
f(29)=563
f(30)=227
f(31)=571
f(32)=37
f(33)=1
f(34)=1151
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)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=109
f(72)=293
f(73)=1
f(74)=449
f(75)=1
f(76)=613
f(77)=349
f(78)=157
f(79)=1
f(80)=193
f(81)=1
f(82)=1153
f(83)=1
f(84)=1
f(85)=1
f(86)=1553
f(87)=829
f(88)=353
f(89)=937
f(90)=397
f(91)=1049
f(92)=2213
f(93)=233
f(94)=1
f(95)=257
f(96)=2693
f(97)=1409
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-68x+5 could be written as f(y)= y^2-1151 with x=y+34
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-34
f'(x)>2x-69 with x > 34
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 | 49 | 30 | 19 | 0.490000 | 0.300000 | 0.190000 | 5.444445 | 4.285714 | 9.500000 |
3 | 1.000 | 669 | 251 | 418 | 0.669000 | 0.251000 | 0.418000 | 13.653061 | 8.366667 | 22.000000 |
4 | 10.000 | 6.978 | 1.796 | 5.182 | 0.697800 | 0.179600 | 0.518200 | 10.430493 | 7.155378 | 12.397129 |
5 | 100.000 | 70.229 | 14.124 | 56.105 | 0.702290 | 0.141240 | 0.561050 | 10.064345 | 7.864142 | 10.826900 |
6 | 1.000.000 | 701.821 | 114.887 | 586.934 | 0.701821 | 0.114887 | 0.586934 | 9.993321 | 8.134169 | 10.461349 |
7 | 10.000.000 | 7.003.095 | 970.395 | 6.032.700 | 0.700310 | 0.097039 | 0.603270 | 9.978463 | 8.446517 | 10.278328 |
8 | 100.000.000 | 69.924.396 | 8.398.212 | 61.526.184 | 0.699244 | 0.083982 | 0.615262 | 9.984785 | 8.654427 | 10.198781 |
9 | 1.000.000.000 | 698.436.958 | 74.026.117 | 624.410.841 | 0.698437 | 0.074026 | 0.624411 | 9.988458 | 8.814509 | 10.148701 |
10 | 10.000.000.000 | 6.978.234.711 | 661.848.230 | 6.316.386.481 | 0.697823 | 0.066185 | 0.631639 | 9.991217 | 8.940740 | 10.115754 |
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 | 7 | 6 | 1 | 0.875000 | 0.750000 | 0.125000 | 1.400000 | 1.500000 | 1.000000 |
4 | 16 | 15 | 10 | 5 | 0.937500 | 0.625000 | 0.312500 | 2.142857 | 1.666667 | 5.000000 |
5 | 32 | 29 | 17 | 12 | 0.906250 | 0.531250 | 0.375000 | 1.933333 | 1.700000 | 2.400000 |
6 | 64 | 30 | 18 | 12 | 0.468750 | 0.281250 | 0.187500 | 1.034483 | 1.058824 | 1.000000 |
7 | 128 | 65 | 39 | 26 | 0.507812 | 0.304688 | 0.203125 | 2.166667 | 2.166667 | 2.166667 |
8 | 256 | 156 | 76 | 80 | 0.609375 | 0.296875 | 0.312500 | 2.400000 | 1.948718 | 3.076923 |
9 | 512 | 322 | 143 | 179 | 0.628906 | 0.279297 | 0.349609 | 2.064103 | 1.881579 | 2.237500 |
10 | 1.024 | 683 | 257 | 426 | 0.666992 | 0.250977 | 0.416016 | 2.121118 | 1.797203 | 2.379888 |
11 | 2.048 | 1.399 | 470 | 929 | 0.683105 | 0.229492 | 0.453613 | 2.048316 | 1.828794 | 2.180751 |
12 | 4.096 | 2.835 | 837 | 1.998 | 0.692139 | 0.204346 | 0.487793 | 2.026448 | 1.780851 | 2.150700 |
13 | 8.192 | 5.721 | 1.537 | 4.184 | 0.698364 | 0.187622 | 0.510742 | 2.017989 | 1.836320 | 2.094094 |
14 | 16.384 | 11.489 | 2.779 | 8.710 | 0.701233 | 0.169617 | 0.531616 | 2.008215 | 1.808068 | 2.081740 |
15 | 32.768 | 23.029 | 5.137 | 17.892 | 0.702789 | 0.156769 | 0.546021 | 2.004439 | 1.848507 | 2.054191 |
16 | 65.536 | 46.019 | 9.641 | 36.378 | 0.702194 | 0.147110 | 0.555084 | 1.998307 | 1.876776 | 2.033199 |
17 | 131.072 | 92.052 | 18.058 | 73.994 | 0.702301 | 0.137772 | 0.564529 | 2.000304 | 1.873042 | 2.034032 |
18 | 262.144 | 184.069 | 33.725 | 150.344 | 0.702168 | 0.128651 | 0.573517 | 1.999620 | 1.867593 | 2.031840 |
19 | 524.288 | 368.197 | 63.477 | 304.720 | 0.702280 | 0.121073 | 0.581207 | 2.000320 | 1.882194 | 2.026819 |
20 | 1.048.576 | 735.824 | 119.997 | 615.827 | 0.701736 | 0.114438 | 0.587298 | 1.998452 | 1.890401 | 2.020960 |
21 | 2.097.152 | 1.470.666 | 227.320 | 1.243.346 | 0.701268 | 0.108395 | 0.592874 | 1.998665 | 1.894381 | 2.018986 |
22 | 4.194.304 | 2.938.986 | 432.248 | 2.506.738 | 0.700709 | 0.103056 | 0.597653 | 1.998405 | 1.901496 | 2.016123 |
23 | 8.388.608 | 5.875.405 | 823.576 | 5.051.829 | 0.700403 | 0.098178 | 0.602225 | 1.999127 | 1.905332 | 2.015300 |
24 | 16.777.216 | 11.745.442 | 1.572.850 | 10.172.592 | 0.700083 | 0.093749 | 0.606334 | 1.999086 | 1.909781 | 2.013645 |
25 | 33.554.432 | 23.479.649 | 3.010.345 | 20.469.304 | 0.699748 | 0.089715 | 0.610033 | 1.999043 | 1.913943 | 2.012201 |
26 | 67.108.864 | 46.936.018 | 5.770.280 | 41.165.738 | 0.699401 | 0.085984 | 0.613417 | 1.999009 | 1.916817 | 2.011096 |
27 | 134.217.728 | 93.835.763 | 11.079.928 | 82.755.835 | 0.699131 | 0.082552 | 0.616579 | 1.999227 | 1.920172 | 2.010309 |
28 | 268.435.456 | 187.598.211 | 21.314.310 | 166.283.901 | 0.698858 | 0.079402 | 0.619456 | 1.999219 | 1.923687 | 2.009331 |
29 | 536.870.912 | 375.074.183 | 41.054.255 | 334.019.928 | 0.698630 | 0.076470 | 0.622161 | 1.999348 | 1.926136 | 2.008733 |
30 | 1.073.741.824 | 749.920.876 | 79.196.604 | 670.724.272 | 0.698418 | 0.073758 | 0.624661 | 1.999394 | 1.929072 | 2.008037 |
31 | 2.147.483.648 | 1.499.408.203 | 152.948.503 | 1.346.459.700 | 0.698216 | 0.071222 | 0.626994 | 1.999422 | 1.931251 | 2.007471 |
32 | 4.294.967.296 | 2.998.021.600 | 295.763.623 | 2.702.257.977 | 0.698031 | 0.068863 | 0.629168 | 1.999470 | 1.933746 | 2.006936 |
33 | 8.589.934.592 | 5.994.559.093 | 572.512.398 | 5.422.046.695 | 0.697859 | 0.066649 | 0.631209 | 1.999505 | 1.935709 | 2.006488 |
34 | 17.179.869.184 | 11.986.395.933 | 1.109.432.239 | 10.876.963.694 | 0.697700 | 0.064577 | 0.633123 | 1.999546 | 1.937831 | 2.006062 |
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 | 0 | 1 | 2 |
2 | 4 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
3 | 8 | 6 | 4 | 2 | 0 | 2 | 1 | 3 |
4 | 16 | 10 | 5 | 5 | 0 | 3 | 1 | 6 |
5 | 32 | 17 | 9 | 8 | 0 | 7 | 1 | 9 |
6 | 64 | 18 | 9 | 9 | 0 | 7 | 1 | 10 |
7 | 128 | 39 | 20 | 19 | 8 | 7 | 14 | 10 |
8 | 256 | 76 | 38 | 38 | 28 | 7 | 31 | 10 |
9 | 512 | 143 | 65 | 78 | 56 | 7 | 70 | 10 |
10 | 1.024 | 257 | 128 | 129 | 111 | 7 | 129 | 10 |
11 | 2.048 | 470 | 238 | 232 | 215 | 7 | 238 | 10 |
12 | 4.096 | 837 | 421 | 416 | 410 | 7 | 410 | 10 |
13 | 8.192 | 1.537 | 766 | 771 | 763 | 7 | 757 | 10 |
14 | 16.384 | 2.779 | 1.392 | 1.387 | 1.375 | 7 | 1.387 | 10 |
15 | 32.768 | 5.137 | 2.559 | 2.578 | 2.599 | 7 | 2.521 | 10 |
16 | 65.536 | 9.641 | 4.830 | 4.811 | 4.868 | 7 | 4.756 | 10 |
17 | 131.072 | 18.058 | 9.086 | 8.972 | 9.058 | 7 | 8.983 | 10 |
18 | 262.144 | 33.725 | 17.001 | 16.724 | 16.963 | 7 | 16.745 | 10 |
19 | 524.288 | 63.477 | 31.908 | 31.569 | 31.862 | 7 | 31.598 | 10 |
20 | 1.048.576 | 119.997 | 60.203 | 59.794 | 60.204 | 7 | 59.776 | 10 |
21 | 2.097.152 | 227.320 | 114.342 | 112.978 | 113.843 | 7 | 113.460 | 10 |
22 | 4.194.304 | 432.248 | 217.172 | 215.076 | 216.198 | 7 | 216.033 | 10 |
23 | 8.388.608 | 823.576 | 413.639 | 409.937 | 412.157 | 7 | 411.402 | 10 |
24 | 16.777.216 | 1.572.850 | 790.119 | 782.731 | 786.074 | 7 | 786.759 | 10 |
25 | 33.554.432 | 3.010.345 | 1.511.128 | 1.499.217 | 1.504.594 | 7 | 1.505.734 | 10 |
26 | 67.108.864 | 5.770.280 | 2.895.166 | 2.875.114 | 2.884.185 | 7 | 2.886.078 | 10 |
27 | 134.217.728 | 11.079.928 | 5.559.285 | 5.520.643 | 5.539.483 | 7 | 5.540.428 | 10 |
28 | 268.435.456 | 21.314.310 | 10.693.948 | 10.620.362 | 10.656.237 | 7 | 10.658.056 | 10 |
29 | 536.870.912 | 41.054.255 | 20.594.955 | 20.459.300 | 20.525.993 | 7 | 20.528.245 | 10 |
30 | 1.073.741.824 | 79.196.604 | 39.727.629 | 39.468.975 | 39.597.708 | 7 | 39.598.879 | 10 |
31 | 2.147.483.648 | 152.948.503 | 76.704.089 | 76.244.414 | 76.476.422 | 7 | 76.472.064 | 10 |
32 | 4.294.967.296 | 295.763.623 | 148.302.860 | 147.460.763 | 147.890.470 | 7 | 147.873.136 | 10 |
33 | 8.589.934.592 | 572.512.398 | 287.030.623 | 285.481.775 | 286.267.067 | 7 | 286.245.314 | 10 |
34 | 17.179.869.184 | 1.109.432.239 | 556.160.360 | 553.271.879 | 554.730.578 | 7 | 554.701.644 | 10 |
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 | 1 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 5 | 2 | 3 | 0 | 1 | 1 | 3 |
5 | 32 | 12 | 4 | 8 | 0 | 4 | 2 | 6 |
6 | 64 | 12 | 4 | 8 | 0 | 4 | 2 | 6 |
7 | 128 | 26 | 9 | 17 | 6 | 5 | 9 | 6 |
8 | 256 | 80 | 34 | 46 | 26 | 10 | 27 | 17 |
9 | 512 | 179 | 84 | 95 | 54 | 23 | 69 | 33 |
10 | 1.024 | 426 | 207 | 219 | 125 | 80 | 142 | 79 |
11 | 2.048 | 929 | 458 | 471 | 269 | 185 | 286 | 189 |
12 | 4.096 | 1.998 | 989 | 1.009 | 547 | 433 | 587 | 431 |
13 | 8.192 | 4.184 | 2.059 | 2.125 | 1.109 | 935 | 1.198 | 942 |
14 | 16.384 | 8.710 | 4.301 | 4.409 | 2.355 | 1.975 | 2.433 | 1.947 |
15 | 32.768 | 17.892 | 8.877 | 9.015 | 4.840 | 4.109 | 4.878 | 4.065 |
16 | 65.536 | 36.378 | 18.085 | 18.293 | 9.812 | 8.376 | 9.888 | 8.302 |
17 | 131.072 | 73.994 | 36.762 | 37.232 | 19.871 | 17.112 | 20.004 | 17.007 |
18 | 262.144 | 150.344 | 74.736 | 75.608 | 40.344 | 34.925 | 40.289 | 34.786 |
19 | 524.288 | 304.720 | 152.013 | 152.707 | 81.322 | 71.000 | 81.304 | 71.094 |
20 | 1.048.576 | 615.827 | 307.655 | 308.172 | 163.546 | 144.401 | 163.425 | 144.455 |
21 | 2.097.152 | 1.243.346 | 620.834 | 622.512 | 329.364 | 292.869 | 328.952 | 292.161 |
22 | 4.194.304 | 2.506.738 | 1.252.403 | 1.254.335 | 661.437 | 592.683 | 661.433 | 591.185 |
23 | 8.388.608 | 5.051.829 | 2.523.214 | 2.528.615 | 1.329.841 | 1.197.429 | 1.328.860 | 1.195.699 |
24 | 16.777.216 | 10.172.592 | 5.083.995 | 5.088.597 | 2.670.538 | 2.416.650 | 2.669.645 | 2.415.759 |
25 | 33.554.432 | 20.469.304 | 10.231.376 | 10.237.928 | 5.362.003 | 4.873.208 | 5.362.150 | 4.871.943 |
26 | 67.108.864 | 41.165.738 | 20.578.841 | 20.586.897 | 10.760.730 | 9.822.110 | 10.763.190 | 9.819.708 |
27 | 134.217.728 | 82.755.835 | 41.376.869 | 41.378.966 | 21.588.888 | 19.793.378 | 21.589.546 | 19.784.023 |
28 | 268.435.456 | 166.283.901 | 83.129.923 | 83.153.978 | 43.298.049 | 39.846.588 | 43.307.365 | 39.831.899 |
29 | 536.870.912 | 334.019.928 | 166.989.372 | 167.030.556 | 86.845.628 | 80.167.589 | 86.852.822 | 80.153.889 |
30 | 1.073.741.824 | 670.724.272 | 335.324.178 | 335.400.094 | 174.128.627 | 161.233.431 | 174.149.467 | 161.212.747 |
31 | 2.147.483.648 | 1.346.459.700 | 673.156.360 | 673.303.340 | 349.074.514 | 324.147.501 | 349.105.555 | 324.132.130 |
32 | 4.294.967.296 | 2.702.257.977 | 1.350.973.026 | 1.351.284.951 | 699.703.002 | 651.435.053 | 699.717.201 | 651.402.721 |
33 | 8.589.934.592 | 5.422.046.695 | 2.710.692.964 | 2.711.353.731 | 1.402.266.591 | 1.308.767.709 | 1.402.287.462 | 1.308.724.933 |
34 | 17.179.869.184 | 10.876.963.694 | 5.437.809.867 | 5.439.153.827 | 2.809.916.289 | 2.628.605.537 | 2.809.910.335 | 2.628.531.533 |