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-52x+79
f(0)=79
f(1)=7
f(2)=3
f(3)=17
f(4)=113
f(5)=13
f(6)=197
f(7)=59
f(8)=1
f(9)=11
f(10)=31
f(11)=1
f(12)=401
f(13)=107
f(14)=151
f(15)=1
f(16)=71
f(17)=43
f(18)=41
f(19)=137
f(20)=1
f(21)=1
f(22)=83
f(23)=1
f(24)=593
f(25)=149
f(26)=199
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)=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)=61
f(56)=101
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=157
f(62)=233
f(63)=193
f(64)=1
f(65)=1
f(66)=1
f(67)=271
f(68)=389
f(69)=313
f(70)=103
f(71)=1
f(72)=1
f(73)=1
f(74)=569
f(75)=1
f(76)=173
f(77)=167
f(78)=1
f(79)=1
f(80)=773
f(81)=607
f(82)=2539
f(83)=1
f(84)=2767
f(85)=1
f(86)=1
f(87)=1
f(88)=191
f(89)=281
f(90)=3499
f(91)=907
f(92)=179
f(93)=139
f(94)=4027
f(95)=347
f(96)=331
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-52x+79 could be written as f(y)= y^2-597 with x=y+26
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-26
f'(x)>2x-53 with x > 24
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 | 40 | 10 | 30 | 0.400000 | 0.100000 | 0.400000 | 4.444445 | 2.500000 | 6.000000 |
3 | 1.000 | 590 | 77 | 513 | 0.590000 | 0.077000 | 0.590000 | 14.750000 | 7.700000 | 17.100000 |
4 | 10.000 | 6.437 | 556 | 5.881 | 0.643700 | 0.055600 | 0.643700 | 10.910170 | 7.220779 | 11.463938 |
5 | 100.000 | 65.683 | 4.259 | 61.424 | 0.656830 | 0.042590 | 0.656830 | 10.203977 | 7.660072 | 10.444482 |
6 | 1.000.000 | 663.605 | 34.819 | 628.786 | 0.663605 | 0.034819 | 0.663605 | 10.103147 | 8.175393 | 10.236813 |
7 | 10.000.000 | 6.677.031 | 293.868 | 6.383.163 | 0.667703 | 0.029387 | 0.667703 | 10.061755 | 8.439875 | 10.151567 |
8 | 100.000.000 | 67.088.605 | 2.542.996 | 64.545.609 | 0.670886 | 0.025430 | 0.670886 | 10.047670 | 8.653531 | 10.111854 |
9 | 1.000.000.000 | 673.358.160 | 22.451.950 | 650.906.210 | 0.673358 | 0.022452 | 0.673358 | 10.036848 | 8.828937 | 10.084439 |
10 | 10.000.000.000 | 6.753.251.192 | 200.969.813 | 6.552.281.379 | 0.675325 | 0.020097 | 0.675325 | 10.029212 | 8.951107 | 10.066399 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 13 | 5 | 8 | 0.812500 | 0.312500 | 0.500000 | 1.625000 | 1.250000 | 2.000000 |
5 | 32 | 20 | 6 | 14 | 0.625000 | 0.187500 | 0.437500 | 1.538462 | 1.200000 | 1.750000 |
6 | 64 | 23 | 6 | 17 | 0.359375 | 0.093750 | 0.265625 | 1.150000 | 1.000000 | 1.214286 |
7 | 128 | 54 | 14 | 40 | 0.421875 | 0.109375 | 0.312500 | 2.347826 | 2.333333 | 2.352941 |
8 | 256 | 127 | 25 | 102 | 0.496094 | 0.097656 | 0.398438 | 2.351852 | 1.785714 | 2.550000 |
9 | 512 | 282 | 45 | 237 | 0.550781 | 0.087891 | 0.462891 | 2.220472 | 1.800000 | 2.323529 |
10 | 1.024 | 606 | 77 | 529 | 0.591797 | 0.075195 | 0.516602 | 2.148936 | 1.711111 | 2.232068 |
11 | 2.048 | 1.266 | 144 | 1.122 | 0.618164 | 0.070312 | 0.547852 | 2.089109 | 1.870130 | 2.120983 |
12 | 4.096 | 2.582 | 264 | 2.318 | 0.630371 | 0.064453 | 0.565918 | 2.039495 | 1.833333 | 2.065954 |
13 | 8.192 | 5.248 | 469 | 4.779 | 0.640625 | 0.057251 | 0.583374 | 2.032533 | 1.776515 | 2.061691 |
14 | 16.384 | 10.626 | 850 | 9.776 | 0.648560 | 0.051880 | 0.596680 | 2.024771 | 1.812367 | 2.045616 |
15 | 32.768 | 21.355 | 1.566 | 19.789 | 0.651703 | 0.047791 | 0.603912 | 2.009693 | 1.842353 | 2.024243 |
16 | 65.536 | 42.923 | 2.905 | 40.018 | 0.654953 | 0.044327 | 0.610626 | 2.009974 | 1.855045 | 2.022235 |
17 | 131.072 | 86.236 | 5.407 | 80.829 | 0.657928 | 0.041252 | 0.616676 | 2.009086 | 1.861274 | 2.019816 |
18 | 262.144 | 172.911 | 10.192 | 162.719 | 0.659603 | 0.038879 | 0.620724 | 2.005091 | 1.884964 | 2.013126 |
19 | 524.288 | 347.043 | 19.252 | 327.791 | 0.661932 | 0.036720 | 0.625212 | 2.007061 | 1.888932 | 2.014461 |
20 | 1.048.576 | 695.934 | 36.412 | 659.522 | 0.663694 | 0.034725 | 0.628969 | 2.005325 | 1.891336 | 2.012020 |
21 | 2.097.152 | 1.394.714 | 68.862 | 1.325.852 | 0.665051 | 0.032836 | 0.632215 | 2.004089 | 1.891190 | 2.010323 |
22 | 4.194.304 | 2.794.459 | 130.761 | 2.663.698 | 0.666251 | 0.031176 | 0.635075 | 2.003607 | 1.898885 | 2.009046 |
23 | 8.388.608 | 5.598.712 | 249.532 | 5.349.180 | 0.667418 | 0.029747 | 0.637672 | 2.003505 | 1.908306 | 2.008178 |
24 | 16.777.216 | 11.215.877 | 475.856 | 10.740.021 | 0.668518 | 0.028363 | 0.640155 | 2.003296 | 1.906994 | 2.007788 |
25 | 33.554.432 | 22.464.107 | 910.847 | 21.553.260 | 0.669483 | 0.027145 | 0.642337 | 2.002885 | 1.914123 | 2.006817 |
26 | 67.108.864 | 44.989.515 | 1.746.465 | 43.243.050 | 0.670396 | 0.026024 | 0.644372 | 2.002729 | 1.917408 | 2.006335 |
27 | 134.217.728 | 90.092.720 | 3.356.663 | 86.736.057 | 0.671243 | 0.025009 | 0.646234 | 2.002527 | 1.921975 | 2.005780 |
28 | 268.435.456 | 180.394.838 | 6.458.770 | 173.936.068 | 0.672023 | 0.024061 | 0.647962 | 2.002324 | 1.924164 | 2.005349 |
29 | 536.870.912 | 361.181.714 | 12.447.418 | 348.734.296 | 0.672753 | 0.023185 | 0.649568 | 2.002173 | 1.927212 | 2.004957 |
30 | 1.073.741.824 | 723.083.929 | 24.021.273 | 699.062.656 | 0.673424 | 0.022372 | 0.651053 | 2.001995 | 1.929820 | 2.004571 |
31 | 2.147.483.648 | 1.447.531.046 | 46.410.219 | 1.401.120.827 | 0.674059 | 0.021611 | 0.652448 | 2.001885 | 1.932047 | 2.004285 |
32 | 4.294.967.296 | 2.897.612.125 | 89.770.969 | 2.807.841.156 | 0.674653 | 0.020901 | 0.653751 | 2.001762 | 1.934293 | 2.003997 |
33 | 8.589.934.592 | 5.799.985.526 | 173.831.174 | 5.626.154.352 | 0.675207 | 0.020237 | 0.654971 | 2.001643 | 1.936385 | 2.003730 |
34 | 17.179.869.184 | 11.608.958.178 | 336.933.505 | 11.272.024.673 | 0.675730 | 0.019612 | 0.656118 | 2.001549 | 1.938280 | 2.003504 |
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 | 0 | 0 | 0 | 1 | 1 |
2 | 4 | 3 | 1 | 1 | 1 | 0 | 1 | 1 |
3 | 8 | 4 | 1 | 2 | 1 | 0 | 2 | 1 |
4 | 16 | 5 | 1 | 3 | 2 | 0 | 2 | 1 |
5 | 32 | 6 | 1 | 4 | 3 | 0 | 2 | 1 |
6 | 64 | 6 | 1 | 4 | 3 | 0 | 2 | 1 |
7 | 128 | 14 | 9 | 4 | 3 | 6 | 2 | 3 |
8 | 256 | 25 | 20 | 4 | 3 | 10 | 2 | 10 |
9 | 512 | 45 | 40 | 4 | 3 | 20 | 2 | 20 |
10 | 1.024 | 77 | 72 | 4 | 3 | 34 | 2 | 38 |
11 | 2.048 | 144 | 139 | 4 | 3 | 64 | 2 | 75 |
12 | 4.096 | 264 | 259 | 4 | 3 | 115 | 2 | 144 |
13 | 8.192 | 469 | 464 | 4 | 3 | 219 | 2 | 245 |
14 | 16.384 | 850 | 845 | 4 | 3 | 410 | 2 | 435 |
15 | 32.768 | 1.566 | 1.561 | 4 | 3 | 764 | 2 | 797 |
16 | 65.536 | 2.905 | 2.900 | 4 | 3 | 1.430 | 2 | 1.470 |
17 | 131.072 | 5.407 | 5.402 | 4 | 3 | 2.721 | 2 | 2.681 |
18 | 262.144 | 10.192 | 10.187 | 4 | 3 | 5.155 | 2 | 5.032 |
19 | 524.288 | 19.252 | 19.247 | 4 | 3 | 9.711 | 2 | 9.536 |
20 | 1.048.576 | 36.412 | 36.407 | 4 | 3 | 18.271 | 2 | 18.136 |
21 | 2.097.152 | 68.862 | 68.857 | 4 | 3 | 34.402 | 2 | 34.455 |
22 | 4.194.304 | 130.761 | 130.756 | 4 | 3 | 65.447 | 2 | 65.309 |
23 | 8.388.608 | 249.532 | 249.527 | 4 | 3 | 124.661 | 2 | 124.866 |
24 | 16.777.216 | 475.856 | 475.851 | 4 | 3 | 238.093 | 2 | 237.758 |
25 | 33.554.432 | 910.847 | 910.842 | 4 | 3 | 455.931 | 2 | 454.911 |
26 | 67.108.864 | 1.746.465 | 1.746.460 | 4 | 3 | 873.840 | 2 | 872.620 |
27 | 134.217.728 | 3.356.663 | 3.356.658 | 4 | 3 | 1.678.579 | 2 | 1.678.079 |
28 | 268.435.456 | 6.458.770 | 6.458.765 | 4 | 3 | 3.229.708 | 2 | 3.229.057 |
29 | 536.870.912 | 12.447.418 | 12.447.413 | 4 | 3 | 6.222.902 | 2 | 6.224.511 |
30 | 1.073.741.824 | 24.021.273 | 24.021.268 | 4 | 3 | 12.011.165 | 2 | 12.010.103 |
31 | 2.147.483.648 | 46.410.219 | 46.410.214 | 4 | 3 | 23.202.891 | 2 | 23.207.323 |
32 | 4.294.967.296 | 89.770.969 | 89.770.964 | 4 | 3 | 44.882.737 | 2 | 44.888.227 |
33 | 8.589.934.592 | 173.831.174 | 173.831.169 | 4 | 3 | 86.913.552 | 2 | 86.917.617 |
34 | 17.179.869.184 | 336.933.505 | 336.933.500 | 4 | 3 | 168.465.950 | 2 | 168.467.550 |
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 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 8 | 4 | 4 | 1 | 2 | 1 | 4 |
5 | 32 | 14 | 6 | 8 | 3 | 4 | 2 | 5 |
6 | 64 | 17 | 8 | 9 | 5 | 4 | 3 | 5 |
7 | 128 | 40 | 19 | 21 | 10 | 11 | 9 | 10 |
8 | 256 | 102 | 55 | 47 | 25 | 26 | 26 | 25 |
9 | 512 | 237 | 123 | 114 | 59 | 52 | 71 | 55 |
10 | 1.024 | 529 | 278 | 251 | 132 | 127 | 160 | 110 |
11 | 2.048 | 1.122 | 557 | 565 | 299 | 254 | 326 | 243 |
12 | 4.096 | 2.318 | 1.158 | 1.160 | 602 | 537 | 653 | 526 |
13 | 8.192 | 4.779 | 2.417 | 2.362 | 1.234 | 1.125 | 1.297 | 1.123 |
14 | 16.384 | 9.776 | 4.888 | 4.888 | 2.557 | 2.301 | 2.607 | 2.311 |
15 | 32.768 | 19.789 | 9.960 | 9.829 | 5.159 | 4.675 | 5.274 | 4.681 |
16 | 65.536 | 40.018 | 20.183 | 19.835 | 10.455 | 9.467 | 10.560 | 9.536 |
17 | 131.072 | 80.829 | 40.657 | 40.172 | 21.116 | 19.257 | 21.268 | 19.188 |
18 | 262.144 | 162.719 | 81.689 | 81.030 | 42.426 | 38.922 | 42.577 | 38.794 |
19 | 524.288 | 327.791 | 164.694 | 163.097 | 85.238 | 78.731 | 85.064 | 78.758 |
20 | 1.048.576 | 659.522 | 331.602 | 327.920 | 170.896 | 158.591 | 171.019 | 159.016 |
21 | 2.097.152 | 1.325.852 | 666.990 | 658.862 | 342.978 | 320.284 | 343.020 | 319.570 |
22 | 4.194.304 | 2.663.698 | 1.338.975 | 1.324.723 | 687.950 | 643.724 | 688.341 | 643.683 |
23 | 8.388.608 | 5.349.180 | 2.688.713 | 2.660.467 | 1.379.098 | 1.294.319 | 1.379.423 | 1.296.340 |
24 | 16.777.216 | 10.740.021 | 5.397.036 | 5.342.985 | 2.763.308 | 2.602.993 | 2.765.767 | 2.607.953 |
25 | 33.554.432 | 21.553.260 | 10.831.671 | 10.721.589 | 5.539.763 | 5.232.829 | 5.544.042 | 5.236.626 |
26 | 67.108.864 | 43.243.050 | 21.725.910 | 21.517.140 | 11.104.550 | 10.513.619 | 11.107.871 | 10.517.010 |
27 | 134.217.728 | 86.736.057 | 43.566.342 | 43.169.715 | 22.248.885 | 21.113.744 | 22.254.508 | 21.118.920 |
28 | 268.435.456 | 173.936.068 | 87.362.285 | 86.573.783 | 44.572.026 | 42.388.424 | 44.574.483 | 42.401.135 |
29 | 536.870.912 | 348.734.296 | 175.126.628 | 173.607.668 | 89.281.800 | 85.079.115 | 89.287.940 | 85.085.441 |
30 | 1.073.741.824 | 699.062.656 | 351.033.301 | 348.029.355 | 178.809.234 | 170.717.235 | 178.822.102 | 170.714.085 |
31 | 2.147.483.648 | 1.401.120.827 | 703.474.727 | 697.646.100 | 358.086.324 | 342.453.246 | 358.109.235 | 342.472.022 |
32 | 4.294.967.296 | 2.807.841.156 | 1.409.539.348 | 1.398.301.808 | 717.065.207 | 686.842.078 | 717.068.988 | 686.864.883 |
33 | 8.589.934.592 | 5.626.154.352 | 2.823.972.257 | 2.802.182.095 | 1.435.780.160 | 1.377.311.620 | 1.435.793.349 | 1.377.269.223 |
34 | 17.179.869.184 | 11.272.024.673 | 5.657.232.642 | 5.614.792.031 | 2.874.660.910 | 2.761.353.657 | 2.874.690.472 | 2.761.319.634 |