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+20x-31
f(0)=31
f(1)=5
f(2)=13
f(3)=19
f(4)=1
f(5)=47
f(6)=1
f(7)=79
f(8)=193
f(9)=23
f(10)=269
f(11)=1
f(12)=353
f(13)=199
f(14)=89
f(15)=1
f(16)=109
f(17)=1
f(18)=653
f(19)=71
f(20)=769
f(21)=83
f(22)=1
f(23)=479
f(24)=41
f(25)=547
f(26)=233
f(27)=619
f(28)=101
f(29)=139
f(30)=113
f(31)=1
f(32)=1
f(33)=859
f(34)=1
f(35)=947
f(36)=397
f(37)=1039
f(38)=53
f(39)=227
f(40)=103
f(41)=1
f(42)=1
f(43)=1
f(44)=557
f(45)=1447
f(46)=601
f(47)=1559
f(48)=61
f(49)=67
f(50)=3469
f(51)=359
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=2179
f(58)=4493
f(59)=463
f(60)=251
f(61)=491
f(62)=163
f(63)=1
f(64)=1069
f(65)=1
f(66)=1129
f(67)=223
f(68)=5953
f(69)=1
f(70)=6269
f(71)=643
f(72)=347
f(73)=1
f(74)=277
f(75)=3547
f(76)=1453
f(77)=3719
f(78)=331
f(79)=1
f(80)=613
f(81)=1
f(82)=641
f(83)=4259
f(84)=1741
f(85)=4447
f(86)=1
f(87)=4639
f(88)=9473
f(89)=967
f(90)=1
f(91)=1
f(92)=10273
f(93)=1
f(94)=2137
f(95)=419
f(96)=2221
f(97)=5659
f(98)=607
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+20x-31 could be written as f(y)= y^2-131 with x=y-10
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+10
f'(x)>2x+19
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 | 8 | 1 | 0.900000 | 0.800000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 69 | 34 | 35 | 0.690000 | 0.340000 | 0.350000 | 7.666667 | 4.250000 | 35.000000 |
3 | 1.000 | 680 | 226 | 454 | 0.680000 | 0.226000 | 0.454000 | 9.855072 | 6.647059 | 12.971429 |
4 | 10.000 | 6.883 | 1.589 | 5.294 | 0.688300 | 0.158900 | 0.529400 | 10.122059 | 7.030973 | 11.660793 |
5 | 100.000 | 69.040 | 12.198 | 56.842 | 0.690400 | 0.121980 | 0.568420 | 10.030510 | 7.676526 | 10.737061 |
6 | 1.000.000 | 690.759 | 98.388 | 592.371 | 0.690759 | 0.098388 | 0.592371 | 10.005199 | 8.065912 | 10.421361 |
7 | 10.000.000 | 6.909.316 | 831.075 | 6.078.241 | 0.690932 | 0.083108 | 0.607824 | 10.002499 | 8.446915 | 10.260869 |
8 | 100.000.000 | 69.103.303 | 7.192.687 | 61.910.616 | 0.691033 | 0.071927 | 0.619106 | 10.001468 | 8.654678 | 10.185614 |
9 | 1.000.000.000 | 691.160.450 | 63.394.532 | 627.765.918 | 0.691160 | 0.063395 | 0.627766 | 10.001843 | 8.813748 | 10.139874 |
10 | 10.000.000.000 | 6.912.874.064 | 566.756.496 | 6.346.117.568 | 0.691287 | 0.056676 | 0.634612 | 10.001837 | 8.940147 | 10.109052 |
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 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.750000 | 1.750000 | -nan |
4 | 16 | 13 | 10 | 3 | 0.812500 | 0.625000 | 0.187500 | 1.857143 | 1.428571 | inf |
5 | 32 | 24 | 15 | 9 | 0.750000 | 0.468750 | 0.281250 | 1.846154 | 1.500000 | 3.000000 |
6 | 64 | 43 | 23 | 20 | 0.671875 | 0.359375 | 0.312500 | 1.791667 | 1.533333 | 2.222222 |
7 | 128 | 86 | 44 | 42 | 0.671875 | 0.343750 | 0.328125 | 2.000000 | 1.913043 | 2.100000 |
8 | 256 | 167 | 73 | 94 | 0.652344 | 0.285156 | 0.367188 | 1.941860 | 1.659091 | 2.238095 |
9 | 512 | 347 | 133 | 214 | 0.677734 | 0.259766 | 0.417969 | 2.077844 | 1.821918 | 2.276596 |
10 | 1.024 | 695 | 230 | 465 | 0.678711 | 0.224609 | 0.454102 | 2.002882 | 1.729323 | 2.172897 |
11 | 2.048 | 1.397 | 397 | 1.000 | 0.682129 | 0.193848 | 0.488281 | 2.010072 | 1.726087 | 2.150538 |
12 | 4.096 | 2.825 | 710 | 2.115 | 0.689697 | 0.173340 | 0.516357 | 2.022190 | 1.788413 | 2.115000 |
13 | 8.192 | 5.654 | 1.325 | 4.329 | 0.690186 | 0.161743 | 0.528442 | 2.001416 | 1.866197 | 2.046808 |
14 | 16.384 | 11.279 | 2.432 | 8.847 | 0.688416 | 0.148438 | 0.539978 | 1.994871 | 1.835472 | 2.043659 |
15 | 32.768 | 22.618 | 4.456 | 18.162 | 0.690247 | 0.135986 | 0.554260 | 2.005320 | 1.832237 | 2.052899 |
16 | 65.536 | 45.306 | 8.313 | 36.993 | 0.691315 | 0.126846 | 0.564468 | 2.003095 | 1.865574 | 2.036835 |
17 | 131.072 | 90.516 | 15.509 | 75.007 | 0.690582 | 0.118324 | 0.572258 | 1.997881 | 1.865632 | 2.027600 |
18 | 262.144 | 181.036 | 28.893 | 152.143 | 0.690598 | 0.110218 | 0.580379 | 2.000044 | 1.862983 | 2.028384 |
19 | 524.288 | 362.094 | 54.439 | 307.655 | 0.690639 | 0.103834 | 0.586805 | 2.000122 | 1.884159 | 2.022144 |
20 | 1.048.576 | 724.307 | 102.730 | 621.577 | 0.690753 | 0.097971 | 0.592782 | 2.000329 | 1.887066 | 2.020370 |
21 | 2.097.152 | 1.448.794 | 194.756 | 1.254.038 | 0.690839 | 0.092867 | 0.597972 | 2.000248 | 1.895805 | 2.017510 |
22 | 4.194.304 | 2.897.763 | 370.201 | 2.527.562 | 0.690881 | 0.088263 | 0.602618 | 2.000121 | 1.900845 | 2.015539 |
23 | 8.388.608 | 5.795.464 | 705.744 | 5.089.720 | 0.690873 | 0.084131 | 0.606742 | 1.999979 | 1.906381 | 2.013688 |
24 | 16.777.216 | 11.593.021 | 1.347.103 | 10.245.918 | 0.690998 | 0.080294 | 0.610704 | 2.000361 | 1.908770 | 2.013061 |
25 | 33.554.432 | 23.187.191 | 2.577.816 | 20.609.375 | 0.691032 | 0.076825 | 0.614207 | 2.000099 | 1.913600 | 2.011472 |
26 | 67.108.864 | 46.372.486 | 4.942.172 | 41.430.314 | 0.691004 | 0.073644 | 0.617360 | 1.999918 | 1.917193 | 2.010265 |
27 | 134.217.728 | 92.753.197 | 9.491.368 | 83.261.829 | 0.691065 | 0.070716 | 0.620349 | 2.000177 | 1.920485 | 2.009684 |
28 | 268.435.456 | 185.511.425 | 18.256.266 | 167.255.159 | 0.691084 | 0.068010 | 0.623074 | 2.000054 | 1.923460 | 2.008785 |
29 | 536.870.912 | 371.046.664 | 35.164.553 | 335.882.111 | 0.691128 | 0.065499 | 0.625629 | 2.000128 | 1.926163 | 2.008202 |
30 | 1.073.741.824 | 742.133.232 | 67.822.957 | 674.310.275 | 0.691165 | 0.063165 | 0.628000 | 2.000108 | 1.928731 | 2.007580 |
31 | 2.147.483.648 | 1.484.356.587 | 130.980.127 | 1.353.376.460 | 0.691207 | 0.060992 | 0.630215 | 2.000121 | 1.931206 | 2.007053 |
32 | 4.294.967.296 | 2.968.868.789 | 253.271.168 | 2.715.597.621 | 0.691244 | 0.058969 | 0.632274 | 2.000105 | 1.933661 | 2.006535 |
33 | 8.589.934.592 | 5.938.056.120 | 490.262.347 | 5.447.793.773 | 0.691281 | 0.057074 | 0.634207 | 2.000107 | 1.935721 | 2.006112 |
34 | 17.179.869.184 | 11.876.688.358 | 950.034.867 | 10.926.653.491 | 0.691314 | 0.055299 | 0.636015 | 2.000097 | 1.937809 | 2.005702 |
35 | 34.359.738.368 | 23.754.558.480 | 1.842.750.748 | 21.911.807.732 | 0.691349 | 0.053631 | 0.637718 | 2.000100 | 1.939666 | 2.005354 |
36 | 68.719.476.736 | 47.511.397.693 | 3.577.656.037 | 43.933.741.656 | 0.691382 | 0.052062 | 0.639320 | 2.000096 | 1.941476 | 2.005026 |
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 | 2 | 1 |
2 | 4 | 4 | 3 | 1 | 0 | 1 | 2 | 1 |
3 | 8 | 7 | 5 | 2 | 1 | 1 | 2 | 3 |
4 | 16 | 10 | 6 | 4 | 2 | 1 | 3 | 4 |
5 | 32 | 15 | 9 | 6 | 3 | 3 | 4 | 5 |
6 | 64 | 23 | 14 | 9 | 3 | 6 | 6 | 8 |
7 | 128 | 44 | 25 | 19 | 9 | 13 | 10 | 12 |
8 | 256 | 73 | 38 | 35 | 15 | 21 | 19 | 18 |
9 | 512 | 133 | 68 | 65 | 29 | 38 | 34 | 32 |
10 | 1.024 | 230 | 115 | 115 | 62 | 63 | 49 | 56 |
11 | 2.048 | 397 | 194 | 203 | 101 | 99 | 99 | 98 |
12 | 4.096 | 710 | 355 | 355 | 171 | 179 | 179 | 181 |
13 | 8.192 | 1.325 | 668 | 657 | 320 | 329 | 335 | 341 |
14 | 16.384 | 2.432 | 1.217 | 1.215 | 598 | 603 | 603 | 628 |
15 | 32.768 | 4.456 | 2.233 | 2.223 | 1.076 | 1.116 | 1.107 | 1.157 |
16 | 65.536 | 8.313 | 4.149 | 4.164 | 2.041 | 2.077 | 2.054 | 2.141 |
17 | 131.072 | 15.509 | 7.777 | 7.732 | 3.778 | 3.913 | 3.833 | 3.985 |
18 | 262.144 | 28.893 | 14.547 | 14.346 | 7.123 | 7.337 | 7.043 | 7.390 |
19 | 524.288 | 54.439 | 27.344 | 27.095 | 13.434 | 13.839 | 13.340 | 13.826 |
20 | 1.048.576 | 102.730 | 51.613 | 51.117 | 25.287 | 26.013 | 25.325 | 26.105 |
21 | 2.097.152 | 194.756 | 97.808 | 96.948 | 47.985 | 49.354 | 48.046 | 49.371 |
22 | 4.194.304 | 370.201 | 186.053 | 184.148 | 91.246 | 93.728 | 91.403 | 93.824 |
23 | 8.388.608 | 705.744 | 354.726 | 351.018 | 174.416 | 178.505 | 174.234 | 178.589 |
24 | 16.777.216 | 1.347.103 | 676.568 | 670.535 | 333.070 | 340.691 | 332.817 | 340.525 |
25 | 33.554.432 | 2.577.816 | 1.293.838 | 1.283.978 | 637.598 | 650.934 | 637.586 | 651.698 |
26 | 67.108.864 | 4.942.172 | 2.480.138 | 2.462.034 | 1.222.968 | 1.247.311 | 1.222.727 | 1.249.166 |
27 | 134.217.728 | 9.491.368 | 4.761.267 | 4.730.101 | 2.349.787 | 2.394.405 | 2.348.959 | 2.398.217 |
28 | 268.435.456 | 18.256.266 | 9.156.850 | 9.099.416 | 4.521.640 | 4.604.540 | 4.520.569 | 4.609.517 |
29 | 536.870.912 | 35.164.553 | 17.635.342 | 17.529.211 | 8.712.247 | 8.870.461 | 8.709.866 | 8.871.979 |
30 | 1.073.741.824 | 67.822.957 | 34.009.733 | 33.813.224 | 16.805.144 | 17.106.206 | 16.808.124 | 17.103.483 |
31 | 2.147.483.648 | 130.980.127 | 65.675.612 | 65.304.515 | 32.462.919 | 33.028.051 | 32.467.736 | 33.021.421 |
32 | 4.294.967.296 | 253.271.168 | 126.987.263 | 126.283.905 | 62.792.197 | 63.843.102 | 62.795.219 | 63.840.650 |
33 | 8.589.934.592 | 490.262.347 | 245.780.907 | 244.481.440 | 121.587.334 | 123.551.307 | 121.582.272 | 123.541.434 |
34 | 17.179.869.184 | 950.034.867 | 476.248.716 | 473.786.151 | 235.657.754 | 239.364.744 | 235.662.303 | 239.350.066 |
35 | 34.359.738.368 | 1.842.750.748 | 923.692.199 | 919.058.549 | 457.206.133 | 464.174.591 | 457.225.287 | 464.144.737 |
36 | 68.719.476.736 | 3.577.656.037 | 1.793.220.467 | 1.784.435.570 | 887.863.097 | 900.992.388 | 887.849.340 | 900.951.212 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 0 | 1 | 1 |
5 | 32 | 9 | 2 | 7 | 3 | 2 | 2 | 2 |
6 | 64 | 20 | 8 | 12 | 4 | 6 | 5 | 5 |
7 | 128 | 42 | 25 | 17 | 10 | 11 | 12 | 9 |
8 | 256 | 94 | 51 | 43 | 24 | 25 | 22 | 23 |
9 | 512 | 214 | 102 | 112 | 58 | 54 | 55 | 47 |
10 | 1.024 | 465 | 226 | 239 | 122 | 129 | 108 | 106 |
11 | 2.048 | 1.000 | 481 | 519 | 244 | 270 | 241 | 245 |
12 | 4.096 | 2.115 | 1.039 | 1.076 | 530 | 537 | 523 | 525 |
13 | 8.192 | 4.329 | 2.145 | 2.184 | 1.070 | 1.099 | 1.076 | 1.084 |
14 | 16.384 | 8.847 | 4.396 | 4.451 | 2.244 | 2.176 | 2.213 | 2.214 |
15 | 32.768 | 18.162 | 8.976 | 9.186 | 4.614 | 4.462 | 4.524 | 4.562 |
16 | 65.536 | 36.993 | 18.438 | 18.555 | 9.258 | 9.131 | 9.273 | 9.331 |
17 | 131.072 | 75.007 | 37.392 | 37.615 | 18.639 | 18.740 | 18.823 | 18.805 |
18 | 262.144 | 152.143 | 75.857 | 76.286 | 37.819 | 38.042 | 38.337 | 37.945 |
19 | 524.288 | 307.655 | 153.649 | 154.006 | 76.647 | 76.900 | 77.170 | 76.938 |
20 | 1.048.576 | 621.577 | 310.810 | 310.767 | 154.662 | 155.508 | 155.805 | 155.602 |
21 | 2.097.152 | 1.254.038 | 626.638 | 627.400 | 312.603 | 313.730 | 313.441 | 314.264 |
22 | 4.194.304 | 2.527.562 | 1.263.005 | 1.264.557 | 630.588 | 632.896 | 631.278 | 632.800 |
23 | 8.388.608 | 5.089.720 | 2.543.739 | 2.545.981 | 1.270.503 | 1.273.097 | 1.271.786 | 1.274.334 |
24 | 16.777.216 | 10.245.918 | 5.122.639 | 5.123.279 | 2.559.223 | 2.562.055 | 2.560.515 | 2.564.125 |
25 | 33.554.432 | 20.609.375 | 10.303.280 | 10.306.095 | 5.148.642 | 5.154.019 | 5.150.520 | 5.156.194 |
26 | 67.108.864 | 41.430.314 | 20.711.547 | 20.718.767 | 10.352.550 | 10.359.610 | 10.350.131 | 10.368.023 |
27 | 134.217.728 | 83.261.829 | 41.624.162 | 41.637.667 | 20.805.366 | 20.820.658 | 20.802.190 | 20.833.615 |
28 | 268.435.456 | 167.255.159 | 83.618.309 | 83.636.850 | 41.793.671 | 41.837.137 | 41.788.038 | 41.836.313 |
29 | 536.870.912 | 335.882.111 | 167.925.977 | 167.956.134 | 83.937.668 | 84.012.745 | 83.926.985 | 84.004.713 |
30 | 1.073.741.824 | 674.310.275 | 337.121.208 | 337.189.067 | 168.501.614 | 168.656.731 | 168.506.626 | 168.645.304 |
31 | 2.147.483.648 | 1.353.376.460 | 676.620.125 | 676.756.335 | 338.206.063 | 338.478.252 | 338.230.314 | 338.461.831 |
32 | 4.294.967.296 | 2.715.597.621 | 1.357.708.971 | 1.357.888.650 | 678.665.300 | 679.141.783 | 678.664.774 | 679.125.764 |
33 | 8.589.934.592 | 5.447.793.773 | 2.723.689.360 | 2.724.104.413 | 1.361.491.689 | 1.362.406.166 | 1.361.472.989 | 1.362.422.929 |
34 | 17.179.869.184 | 10.926.653.491 | 5.462.894.434 | 5.463.759.057 | 2.730.783.506 | 2.732.528.669 | 2.730.781.255 | 2.732.560.061 |
35 | 34.359.738.368 | 21.911.807.732 | 10.955.113.058 | 10.956.694.674 | 5.476.337.011 | 5.479.575.784 | 5.476.290.288 | 5.479.604.649 |
36 | 68.719.476.736 | 43.933.741.656 | 21.965.390.713 | 21.968.350.943 | 10.980.341.975 | 10.986.519.014 | 10.980.415.111 | 10.986.465.556 |