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+60x-13
f(0)=13
f(1)=3
f(2)=37
f(3)=11
f(4)=1
f(5)=1
f(6)=383
f(7)=19
f(8)=59
f(9)=1
f(10)=229
f(11)=1
f(12)=23
f(13)=1
f(14)=31
f(15)=139
f(16)=401
f(17)=1
f(18)=107
f(19)=1
f(20)=1
f(21)=211
f(22)=199
f(23)=79
f(24)=2003
f(25)=1
f(26)=1
f(27)=73
f(28)=43
f(29)=1
f(30)=2687
f(31)=1
f(32)=977
f(33)=191
f(34)=1061
f(35)=1
f(36)=313
f(37)=149
f(38)=1237
f(39)=1
f(40)=443
f(41)=1
f(42)=4271
f(43)=1
f(44)=1
f(45)=1
f(46)=1621
f(47)=1
f(48)=5171
f(49)=1
f(50)=1
f(51)=353
f(52)=1
f(53)=83
f(54)=6143
f(55)=263
f(56)=2161
f(57)=1
f(58)=1
f(59)=1
f(60)=7187
f(61)=307
f(62)=839
f(63)=967
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=2897
f(69)=101
f(70)=233
f(71)=1
f(72)=9491
f(73)=1
f(74)=3301
f(75)=1
f(76)=1
f(77)=439
f(78)=827
f(79)=457
f(80)=113
f(81)=1
f(82)=3877
f(83)=1
f(84)=281
f(85)=1
f(86)=1
f(87)=1597
f(88)=4337
f(89)=1
f(90)=13487
f(91)=1
f(92)=4657
f(93)=1777
f(94)=1607
f(95)=613
f(96)=1151
f(97)=317
f(98)=1
f(99)=983
b) Substitution of the polynom
The polynom f(x)=x^2+60x-13 could be written as f(y)= y^2-913 with x=y-30
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+30
f'(x)>2x+59
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 | 8 | 2 | 6 | 0.800000 | 0.200000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 56 | 10 | 46 | 0.560000 | 0.100000 | 0.560000 | 7.000000 | 5.000000 | 7.666667 |
3 | 1.000 | 596 | 57 | 539 | 0.596000 | 0.057000 | 0.596000 | 10.642858 | 5.700000 | 11.717391 |
4 | 10.000 | 6.192 | 425 | 5.767 | 0.619200 | 0.042500 | 0.619200 | 10.389262 | 7.456141 | 10.699444 |
5 | 100.000 | 63.640 | 3.381 | 60.259 | 0.636400 | 0.033810 | 0.636400 | 10.277778 | 7.955294 | 10.448934 |
6 | 1.000.000 | 646.333 | 27.262 | 619.071 | 0.646333 | 0.027262 | 0.646333 | 10.156081 | 8.063294 | 10.273502 |
7 | 10.000.000 | 6.533.020 | 229.808 | 6.303.212 | 0.653302 | 0.022981 | 0.653302 | 10.107823 | 8.429609 | 10.181727 |
8 | 100.000.000 | 65.840.135 | 1.992.098 | 63.848.037 | 0.658401 | 0.019921 | 0.658401 | 10.078055 | 8.668532 | 10.129444 |
9 | 1.000.000.000 | 662.320.168 | 17.582.197 | 644.737.971 | 0.662320 | 0.017582 | 0.662320 | 10.059521 | 8.825970 | 10.098008 |
10 | 10.000.000.000 | 6.654.524.713 | 157.330.135 | 6.497.194.578 | 0.665452 | 0.015733 | 0.665452 | 10.047293 | 8.948264 | 10.077264 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 1 | 3 | 1.000000 | 0.250000 | 0.750000 | 1.333333 | 1.000000 | 1.500000 |
3 | 8 | 7 | 2 | 5 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 2.000000 | 1.666667 |
4 | 16 | 11 | 2 | 9 | 0.687500 | 0.125000 | 0.562500 | 1.571429 | 1.000000 | 1.800000 |
5 | 32 | 19 | 4 | 15 | 0.593750 | 0.125000 | 0.468750 | 1.727273 | 2.000000 | 1.666667 |
6 | 64 | 37 | 8 | 29 | 0.578125 | 0.125000 | 0.453125 | 1.947368 | 2.000000 | 1.933333 |
7 | 128 | 72 | 12 | 60 | 0.562500 | 0.093750 | 0.468750 | 1.945946 | 1.500000 | 2.068965 |
8 | 256 | 146 | 20 | 126 | 0.570312 | 0.078125 | 0.492188 | 2.027778 | 1.666667 | 2.100000 |
9 | 512 | 298 | 36 | 262 | 0.582031 | 0.070312 | 0.511719 | 2.041096 | 1.800000 | 2.079365 |
10 | 1.024 | 611 | 58 | 553 | 0.596680 | 0.056641 | 0.540039 | 2.050336 | 1.611111 | 2.110687 |
11 | 2.048 | 1.236 | 103 | 1.133 | 0.603516 | 0.050293 | 0.553223 | 2.022913 | 1.775862 | 2.048825 |
12 | 4.096 | 2.507 | 189 | 2.318 | 0.612061 | 0.046143 | 0.565918 | 2.028317 | 1.834951 | 2.045896 |
13 | 8.192 | 5.053 | 350 | 4.703 | 0.616821 | 0.042725 | 0.574097 | 2.015556 | 1.851852 | 2.028904 |
14 | 16.384 | 10.208 | 677 | 9.531 | 0.623047 | 0.041321 | 0.581726 | 2.020186 | 1.934286 | 2.026579 |
15 | 32.768 | 20.614 | 1.240 | 19.374 | 0.629089 | 0.037842 | 0.591248 | 2.019397 | 1.831610 | 2.032735 |
16 | 65.536 | 41.530 | 2.283 | 39.247 | 0.633698 | 0.034836 | 0.598862 | 2.014650 | 1.841129 | 2.025756 |
17 | 131.072 | 83.625 | 4.237 | 79.388 | 0.638008 | 0.032326 | 0.605682 | 2.013605 | 1.855891 | 2.022779 |
18 | 262.144 | 168.088 | 8.020 | 160.068 | 0.641205 | 0.030594 | 0.610611 | 2.010021 | 1.892849 | 2.016274 |
19 | 524.288 | 337.599 | 15.105 | 322.494 | 0.643919 | 0.028811 | 0.615108 | 2.008466 | 1.883416 | 2.014731 |
20 | 1.048.576 | 677.800 | 28.481 | 649.319 | 0.646400 | 0.027162 | 0.619239 | 2.007707 | 1.885535 | 2.013430 |
21 | 2.097.152 | 1.360.818 | 53.692 | 1.307.126 | 0.648889 | 0.025602 | 0.623286 | 2.007699 | 1.885187 | 2.013072 |
22 | 4.194.304 | 2.730.019 | 102.127 | 2.627.892 | 0.650887 | 0.024349 | 0.626538 | 2.006160 | 1.902090 | 2.010435 |
23 | 8.388.608 | 5.476.594 | 195.141 | 5.281.453 | 0.652861 | 0.023263 | 0.629598 | 2.006064 | 1.910768 | 2.009768 |
24 | 16.777.216 | 10.982.076 | 372.652 | 10.609.424 | 0.654583 | 0.022212 | 0.632371 | 2.005275 | 1.909655 | 2.008808 |
25 | 33.554.432 | 22.016.434 | 713.325 | 21.303.109 | 0.656141 | 0.021259 | 0.634882 | 2.004761 | 1.914185 | 2.007942 |
26 | 67.108.864 | 44.132.096 | 1.368.349 | 42.763.747 | 0.657619 | 0.020390 | 0.637230 | 2.004507 | 1.918269 | 2.007395 |
27 | 134.217.728 | 88.442.869 | 2.629.325 | 85.813.544 | 0.658951 | 0.019590 | 0.639361 | 2.004049 | 1.921531 | 2.006689 |
28 | 268.435.456 | 177.217.710 | 5.060.032 | 172.157.678 | 0.660187 | 0.018850 | 0.641337 | 2.003753 | 1.924460 | 2.006183 |
29 | 536.870.912 | 355.056.816 | 9.748.737 | 345.308.079 | 0.661345 | 0.018158 | 0.643186 | 2.003506 | 1.926616 | 2.005766 |
30 | 1.073.741.824 | 711.278.263 | 18.809.688 | 692.468.575 | 0.662430 | 0.017518 | 0.644912 | 2.003280 | 1.929449 | 2.005364 |
31 | 2.147.483.648 | 1.424.720.950 | 36.339.334 | 1.388.381.616 | 0.663437 | 0.016922 | 0.646516 | 2.003043 | 1.931948 | 2.004974 |
32 | 4.294.967.296 | 2.853.492.983 | 70.292.996 | 2.783.199.987 | 0.664381 | 0.016366 | 0.648014 | 2.002844 | 1.934350 | 2.004636 |
33 | 8.589.934.592 | 5.714.600.445 | 136.092.798 | 5.578.507.647 | 0.665267 | 0.015843 | 0.649424 | 2.002668 | 1.936079 | 2.004350 |
34 | 17.179.869.184 | 11.443.459.562 | 263.788.281 | 11.179.671.281 | 0.666097 | 0.015354 | 0.650743 | 2.002495 | 1.938297 | 2.004061 |
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 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
4 | 16 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
5 | 32 | 4 | 1 | 3 | 0 | 1 | 1 | 2 |
6 | 64 | 8 | 1 | 7 | 0 | 3 | 1 | 4 |
7 | 128 | 12 | 1 | 11 | 0 | 6 | 1 | 5 |
8 | 256 | 20 | 1 | 19 | 0 | 10 | 1 | 9 |
9 | 512 | 36 | 1 | 35 | 0 | 17 | 1 | 18 |
10 | 1.024 | 58 | 1 | 57 | 0 | 28 | 1 | 29 |
11 | 2.048 | 103 | 1 | 102 | 0 | 51 | 1 | 51 |
12 | 4.096 | 189 | 1 | 188 | 0 | 88 | 1 | 100 |
13 | 8.192 | 350 | 1 | 349 | 0 | 165 | 1 | 184 |
14 | 16.384 | 677 | 1 | 676 | 0 | 336 | 1 | 340 |
15 | 32.768 | 1.240 | 1 | 1.239 | 0 | 611 | 1 | 628 |
16 | 65.536 | 2.283 | 1 | 2.282 | 0 | 1.127 | 1 | 1.155 |
17 | 131.072 | 4.237 | 1 | 4.236 | 0 | 2.078 | 1 | 2.158 |
18 | 262.144 | 8.020 | 1 | 8.019 | 0 | 4.003 | 1 | 4.016 |
19 | 524.288 | 15.105 | 1 | 15.104 | 0 | 7.523 | 1 | 7.581 |
20 | 1.048.576 | 28.481 | 1 | 28.480 | 0 | 14.153 | 1 | 14.327 |
21 | 2.097.152 | 53.692 | 1 | 53.691 | 0 | 26.832 | 1 | 26.859 |
22 | 4.194.304 | 102.127 | 1 | 102.126 | 0 | 51.044 | 1 | 51.082 |
23 | 8.388.608 | 195.141 | 1 | 195.140 | 0 | 97.689 | 1 | 97.451 |
24 | 16.777.216 | 372.652 | 1 | 372.651 | 0 | 186.327 | 1 | 186.324 |
25 | 33.554.432 | 713.325 | 1 | 713.324 | 0 | 356.654 | 1 | 356.670 |
26 | 67.108.864 | 1.368.349 | 1 | 1.368.348 | 0 | 684.322 | 1 | 684.026 |
27 | 134.217.728 | 2.629.325 | 1 | 2.629.324 | 0 | 1.315.090 | 1 | 1.314.234 |
28 | 268.435.456 | 5.060.032 | 1 | 5.060.031 | 0 | 2.529.958 | 1 | 2.530.073 |
29 | 536.870.912 | 9.748.737 | 1 | 9.748.736 | 0 | 4.873.308 | 1 | 4.875.428 |
30 | 1.073.741.824 | 18.809.688 | 1 | 18.809.687 | 0 | 9.405.161 | 1 | 9.404.526 |
31 | 2.147.483.648 | 36.339.334 | 1 | 36.339.333 | 0 | 18.169.636 | 1 | 18.169.697 |
32 | 4.294.967.296 | 70.292.996 | 1 | 70.292.995 | 0 | 35.147.045 | 1 | 35.145.950 |
33 | 8.589.934.592 | 136.092.798 | 1 | 136.092.797 | 0 | 68.042.910 | 1 | 68.049.887 |
34 | 17.179.869.184 | 263.788.281 | 1 | 263.788.280 | 0 | 131.880.594 | 1 | 131.907.686 |
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 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
3 | 8 | 5 | 2 | 2 | 0 | 4 | 1 | 0 |
4 | 16 | 9 | 5 | 3 | 1 | 5 | 2 | 1 |
5 | 32 | 15 | 9 | 5 | 3 | 7 | 2 | 3 |
6 | 64 | 29 | 15 | 12 | 6 | 10 | 6 | 7 |
7 | 128 | 60 | 30 | 28 | 15 | 15 | 18 | 12 |
8 | 256 | 126 | 66 | 58 | 31 | 29 | 33 | 33 |
9 | 512 | 262 | 133 | 127 | 76 | 55 | 73 | 58 |
10 | 1.024 | 553 | 279 | 272 | 156 | 120 | 162 | 115 |
11 | 2.048 | 1.133 | 578 | 553 | 304 | 264 | 323 | 242 |
12 | 4.096 | 2.318 | 1.163 | 1.153 | 625 | 535 | 642 | 516 |
13 | 8.192 | 4.703 | 2.379 | 2.322 | 1.296 | 1.080 | 1.254 | 1.073 |
14 | 16.384 | 9.531 | 4.825 | 4.704 | 2.580 | 2.180 | 2.579 | 2.192 |
15 | 32.768 | 19.374 | 9.853 | 9.519 | 5.229 | 4.480 | 5.186 | 4.479 |
16 | 65.536 | 39.247 | 19.896 | 19.349 | 10.449 | 9.215 | 10.427 | 9.156 |
17 | 131.072 | 79.388 | 40.232 | 39.154 | 20.799 | 18.831 | 20.955 | 18.803 |
18 | 262.144 | 160.068 | 81.076 | 78.990 | 41.726 | 38.206 | 42.101 | 38.035 |
19 | 524.288 | 322.494 | 162.813 | 159.679 | 84.338 | 76.778 | 84.442 | 76.936 |
20 | 1.048.576 | 649.319 | 327.767 | 321.550 | 169.209 | 155.439 | 169.614 | 155.057 |
21 | 2.097.152 | 1.307.126 | 659.272 | 647.852 | 339.885 | 313.850 | 340.626 | 312.765 |
22 | 4.194.304 | 2.627.892 | 1.324.373 | 1.303.517 | 682.403 | 631.718 | 682.742 | 631.029 |
23 | 8.388.608 | 5.281.453 | 2.661.263 | 2.620.188 | 1.368.527 | 1.271.129 | 1.370.449 | 1.271.348 |
24 | 16.777.216 | 10.609.424 | 5.344.116 | 5.265.306 | 2.746.319 | 2.557.941 | 2.747.745 | 2.557.419 |
25 | 33.554.432 | 21.303.109 | 10.726.837 | 10.576.270 | 5.504.710 | 5.144.317 | 5.508.400 | 5.145.682 |
26 | 67.108.864 | 42.763.747 | 21.524.881 | 21.238.864 | 11.035.847 | 10.342.678 | 11.039.729 | 10.345.493 |
27 | 134.217.728 | 85.813.544 | 43.183.661 | 42.629.881 | 22.118.618 | 20.784.011 | 22.122.444 | 20.788.471 |
28 | 268.435.456 | 172.157.678 | 86.613.675 | 85.544.001 | 44.321.758 | 41.750.715 | 44.325.836 | 41.759.369 |
29 | 536.870.912 | 345.308.079 | 173.671.164 | 171.636.913 | 88.792.495 | 83.846.260 | 88.808.008 | 83.861.316 |
30 | 1.073.741.824 | 692.468.575 | 348.208.588 | 344.259.985 | 177.880.628 | 168.337.261 | 177.901.046 | 168.349.640 |
31 | 2.147.483.648 | 1.388.381.616 | 698.014.299 | 690.367.315 | 356.300.472 | 337.866.215 | 356.331.436 | 337.883.493 |
32 | 4.294.967.296 | 2.783.199.987 | 1.398.958.084 | 1.384.241.901 | 713.601.145 | 677.956.050 | 713.665.273 | 677.977.519 |
33 | 8.589.934.592 | 5.578.507.647 | 2.803.468.910 | 2.775.038.735 | 1.429.130.777 | 1.360.111.344 | 1.429.146.282 | 1.360.119.244 |
34 | 17.179.869.184 | 11.179.671.281 | 5.617.303.484 | 5.562.367.795 | 2.861.822.010 | 2.727.986.018 | 2.861.810.505 | 2.728.052.748 |