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-13
f(0)=13
f(1)=3
f(2)=1
f(3)=1
f(4)=1
f(5)=1
f(6)=23
f(7)=1
f(8)=17
f(9)=1
f(10)=29
f(11)=1
f(12)=131
f(13)=1
f(14)=61
f(15)=53
f(16)=1
f(17)=1
f(18)=311
f(19)=1
f(20)=43
f(21)=107
f(22)=157
f(23)=1
f(24)=563
f(25)=1
f(26)=1
f(27)=179
f(28)=257
f(29)=1
f(30)=887
f(31)=79
f(32)=337
f(33)=269
f(34)=127
f(35)=101
f(36)=1283
f(37)=113
f(38)=1
f(39)=1
f(40)=1
f(41)=139
f(42)=103
f(43)=1
f(44)=641
f(45)=503
f(46)=701
f(47)=1
f(48)=1
f(49)=199
f(50)=829
f(51)=647
f(52)=1
f(53)=233
f(54)=2903
f(55)=251
f(56)=347
f(57)=809
f(58)=1117
f(59)=1
f(60)=211
f(61)=1
f(62)=1277
f(63)=1
f(64)=1361
f(65)=1
f(66)=1
f(67)=373
f(68)=1
f(69)=1187
f(70)=181
f(71)=419
f(72)=5171
f(73)=443
f(74)=607
f(75)=1
f(76)=1
f(77)=1
f(78)=467
f(79)=173
f(80)=2129
f(81)=1637
f(82)=2237
f(83)=191
f(84)=7043
f(85)=601
f(86)=1
f(87)=1889
f(88)=859
f(89)=659
f(90)=8087
f(91)=1
f(92)=313
f(93)=1
f(94)=1
f(95)=751
f(96)=9203
f(97)=1
f(98)=1
f(99)=2447
b) Substitution of the polynom
The polynom f(x)=x^2-13 could be written as f(y)= y^2-13 with x=y+0
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+0
f'(x)>2x-1 with x > 4
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 | 5 | 3 | 2 | 0.500000 | 0.300000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 24 | 40 | 0.640000 | 0.240000 | 0.640000 | 12.800000 | 8.000000 | 20.000000 |
3 | 1.000 | 675 | 148 | 527 | 0.675000 | 0.148000 | 0.675000 | 10.546875 | 6.166667 | 13.175000 |
4 | 10.000 | 6.826 | 1.063 | 5.763 | 0.682600 | 0.106300 | 0.682600 | 10.112593 | 7.182433 | 10.935484 |
5 | 100.000 | 68.591 | 8.023 | 60.568 | 0.685910 | 0.080230 | 0.685910 | 10.048491 | 7.547507 | 10.509804 |
6 | 1.000.000 | 686.783 | 65.524 | 621.259 | 0.686783 | 0.065524 | 0.686783 | 10.012728 | 8.167020 | 10.257215 |
7 | 10.000.000 | 6.875.551 | 549.103 | 6.326.448 | 0.687555 | 0.054910 | 0.687555 | 10.011242 | 8.380181 | 10.183270 |
8 | 100.000.000 | 68.801.133 | 4.746.807 | 64.054.326 | 0.688011 | 0.047468 | 0.688011 | 10.006636 | 8.644657 | 10.124848 |
9 | 1.000.000.000 | 688.418.526 | 41.800.087 | 646.618.439 | 0.688419 | 0.041800 | 0.688419 | 10.005918 | 8.805938 | 10.094844 |
10 | 10.000.000.000 | 6.887.796.115 | 373.338.620 | 6.514.457.495 | 0.688780 | 0.037334 | 0.688780 | 10.005246 | 8.931527 | 10.074655 |
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 | 2 | 2 | 0 | 1.000000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 2 | 2 | 0 | 0.500000 | 0.500000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 4 | 3 | 1 | 0.500000 | 0.375000 | 0.125000 | 2.000000 | 1.500000 | inf |
4 | 16 | 8 | 5 | 3 | 0.500000 | 0.312500 | 0.187500 | 2.000000 | 1.666667 | 3.000000 |
5 | 32 | 18 | 10 | 8 | 0.562500 | 0.312500 | 0.250000 | 2.250000 | 2.000000 | 2.666667 |
6 | 64 | 40 | 16 | 24 | 0.625000 | 0.250000 | 0.375000 | 2.222222 | 1.600000 | 3.000000 |
7 | 128 | 83 | 29 | 54 | 0.648438 | 0.226562 | 0.421875 | 2.075000 | 1.812500 | 2.250000 |
8 | 256 | 169 | 54 | 115 | 0.660156 | 0.210938 | 0.449219 | 2.036144 | 1.862069 | 2.129630 |
9 | 512 | 347 | 84 | 263 | 0.677734 | 0.164062 | 0.513672 | 2.053254 | 1.555556 | 2.286957 |
10 | 1.024 | 692 | 151 | 541 | 0.675781 | 0.147461 | 0.528320 | 1.994236 | 1.797619 | 2.057034 |
11 | 2.048 | 1.391 | 272 | 1.119 | 0.679199 | 0.132812 | 0.546387 | 2.010116 | 1.801324 | 2.068392 |
12 | 4.096 | 2.797 | 498 | 2.299 | 0.682861 | 0.121582 | 0.561279 | 2.010784 | 1.830882 | 2.054513 |
13 | 8.192 | 5.583 | 901 | 4.682 | 0.681519 | 0.109985 | 0.571533 | 1.996067 | 1.809237 | 2.036538 |
14 | 16.384 | 11.197 | 1.617 | 9.580 | 0.683411 | 0.098694 | 0.584717 | 2.005553 | 1.794673 | 2.046134 |
15 | 32.768 | 22.468 | 2.961 | 19.507 | 0.685669 | 0.090363 | 0.595306 | 2.006609 | 1.831169 | 2.036221 |
16 | 65.536 | 44.924 | 5.516 | 39.408 | 0.685486 | 0.084167 | 0.601318 | 1.999466 | 1.862884 | 2.020198 |
17 | 131.072 | 89.946 | 10.250 | 79.696 | 0.686234 | 0.078201 | 0.608032 | 2.002182 | 1.858231 | 2.022331 |
18 | 262.144 | 179.888 | 19.354 | 160.534 | 0.686218 | 0.073830 | 0.612389 | 1.999956 | 1.888195 | 2.014329 |
19 | 524.288 | 359.976 | 36.256 | 323.720 | 0.686600 | 0.069153 | 0.617447 | 2.001112 | 1.873308 | 2.016520 |
20 | 1.048.576 | 720.098 | 68.458 | 651.640 | 0.686739 | 0.065287 | 0.621452 | 2.000406 | 1.888184 | 2.012974 |
21 | 2.097.152 | 1.440.902 | 129.178 | 1.311.724 | 0.687076 | 0.061597 | 0.625479 | 2.000980 | 1.886967 | 2.012958 |
22 | 4.194.304 | 2.882.729 | 245.279 | 2.637.450 | 0.687296 | 0.058479 | 0.628817 | 2.000642 | 1.898768 | 2.010674 |
23 | 8.388.608 | 5.767.236 | 466.368 | 5.300.868 | 0.687508 | 0.055595 | 0.631913 | 2.000617 | 1.901378 | 2.009846 |
24 | 16.777.216 | 11.537.303 | 889.603 | 10.647.700 | 0.687677 | 0.053024 | 0.634652 | 2.000491 | 1.907513 | 2.008671 |
25 | 33.554.432 | 23.078.564 | 1.702.150 | 21.376.414 | 0.687795 | 0.050728 | 0.637067 | 2.000343 | 1.913382 | 2.007609 |
26 | 67.108.864 | 46.165.652 | 3.262.194 | 42.903.458 | 0.687922 | 0.048610 | 0.639311 | 2.000369 | 1.916514 | 2.007046 |
27 | 134.217.728 | 92.350.275 | 6.262.090 | 86.088.185 | 0.688063 | 0.046656 | 0.641407 | 2.000411 | 1.919595 | 2.006556 |
28 | 268.435.456 | 184.733.732 | 12.041.795 | 172.691.937 | 0.688187 | 0.044859 | 0.643328 | 2.000359 | 1.922967 | 2.005989 |
29 | 536.870.912 | 369.535.040 | 23.191.327 | 346.343.713 | 0.688313 | 0.043197 | 0.645115 | 2.000366 | 1.925903 | 2.005558 |
30 | 1.073.741.824 | 739.197.353 | 44.718.053 | 694.479.300 | 0.688431 | 0.041647 | 0.646784 | 2.000345 | 1.928223 | 2.005174 |
31 | 2.147.483.648 | 1.478.638.459 | 86.332.566 | 1.392.305.893 | 0.688545 | 0.040202 | 0.648343 | 2.000330 | 1.930598 | 2.004820 |
32 | 4.294.967.296 | 2.957.746.578 | 166.894.630 | 2.790.851.948 | 0.688654 | 0.038858 | 0.649796 | 2.000318 | 1.933159 | 2.004482 |
33 | 8.589.934.592 | 5.916.385.691 | 322.974.624 | 5.593.411.067 | 0.688758 | 0.037599 | 0.651159 | 2.000302 | 1.935201 | 2.004195 |
34 | 17.179.869.184 | 11.834.477.024 | 625.688.348 | 11.208.788.676 | 0.688857 | 0.036420 | 0.652437 | 2.000288 | 1.937268 | 2.003927 |
35 | 34.359.738.368 | 23.672.249.232 | 1.213.333.172 | 22.458.916.060 | 0.688953 | 0.035313 | 0.653641 | 2.000278 | 1.939197 | 2.003688 |
36 | 68.719.476.736 | 47.350.885.599 | 2.355.031.534 | 44.995.854.065 | 0.689046 | 0.034270 | 0.654776 | 2.000270 | 1.940960 | 2.003474 |
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 | 2 | 1 | 0 | 0 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 5 | 1 | 3 | 0 | 2 | 2 | 1 |
5 | 32 | 10 | 1 | 8 | 0 | 5 | 2 | 3 |
6 | 64 | 16 | 1 | 14 | 1 | 6 | 3 | 6 |
7 | 128 | 29 | 1 | 27 | 3 | 12 | 4 | 10 |
8 | 256 | 54 | 1 | 52 | 7 | 20 | 10 | 17 |
9 | 512 | 84 | 1 | 82 | 14 | 32 | 11 | 27 |
10 | 1.024 | 151 | 1 | 149 | 23 | 59 | 21 | 48 |
11 | 2.048 | 272 | 1 | 270 | 37 | 105 | 32 | 98 |
12 | 4.096 | 498 | 1 | 496 | 66 | 186 | 66 | 180 |
13 | 8.192 | 901 | 1 | 899 | 109 | 327 | 132 | 333 |
14 | 16.384 | 1.617 | 1 | 1.615 | 203 | 591 | 212 | 611 |
15 | 32.768 | 2.961 | 1 | 2.959 | 377 | 1.064 | 380 | 1.140 |
16 | 65.536 | 5.516 | 1 | 5.514 | 718 | 2.002 | 713 | 2.083 |
17 | 131.072 | 10.250 | 1 | 10.248 | 1.343 | 3.798 | 1.319 | 3.790 |
18 | 262.144 | 19.354 | 1 | 19.352 | 2.517 | 7.205 | 2.497 | 7.135 |
19 | 524.288 | 36.256 | 1 | 36.254 | 4.656 | 13.480 | 4.647 | 13.473 |
20 | 1.048.576 | 68.458 | 1 | 68.456 | 8.790 | 25.368 | 8.754 | 25.546 |
21 | 2.097.152 | 129.178 | 1 | 129.176 | 16.565 | 47.995 | 16.513 | 48.105 |
22 | 4.194.304 | 245.279 | 1 | 245.277 | 31.429 | 91.282 | 31.419 | 91.149 |
23 | 8.388.608 | 466.368 | 1 | 466.366 | 59.527 | 173.747 | 59.677 | 173.417 |
24 | 16.777.216 | 889.603 | 1 | 889.601 | 113.486 | 331.135 | 113.664 | 331.318 |
25 | 33.554.432 | 1.702.150 | 1 | 1.702.148 | 217.307 | 633.736 | 217.162 | 633.945 |
26 | 67.108.864 | 3.262.194 | 1 | 3.262.192 | 416.361 | 1.215.627 | 416.149 | 1.214.057 |
27 | 134.217.728 | 6.262.090 | 1 | 6.262.088 | 798.327 | 2.333.041 | 798.041 | 2.332.681 |
28 | 268.435.456 | 12.041.795 | 1 | 12.041.793 | 1.533.112 | 4.488.185 | 1.533.521 | 4.486.977 |
29 | 536.870.912 | 23.191.327 | 1 | 23.191.325 | 2.952.029 | 8.643.743 | 2.951.969 | 8.643.586 |
30 | 1.073.741.824 | 44.718.053 | 1 | 44.718.051 | 5.689.061 | 16.667.417 | 5.690.023 | 16.671.552 |
31 | 2.147.483.648 | 86.332.566 | 1 | 86.332.564 | 10.977.729 | 32.188.754 | 10.976.351 | 32.189.732 |
32 | 4.294.967.296 | 166.894.630 | 1 | 166.894.628 | 21.215.799 | 62.234.929 | 21.208.505 | 62.235.397 |
33 | 8.589.934.592 | 322.974.624 | 1 | 322.974.622 | 41.032.442 | 120.466.611 | 41.021.372 | 120.454.199 |
34 | 17.179.869.184 | 625.688.348 | 1 | 625.688.346 | 79.456.102 | 233.412.001 | 79.427.580 | 233.392.665 |
35 | 34.359.738.368 | 1.213.333.172 | 1 | 1.213.333.170 | 153.986.933 | 452.700.147 | 153.969.692 | 452.676.400 |
36 | 68.719.476.736 | 2.355.031.534 | 1 | 2.355.031.532 | 298.725.898 | 878.797.172 | 298.713.977 | 878.794.487 |
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 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 3 | 1 | 2 | 1 | 0 | 2 | 0 |
5 | 32 | 8 | 5 | 3 | 3 | 1 | 3 | 1 |
6 | 64 | 24 | 12 | 12 | 7 | 5 | 8 | 4 |
7 | 128 | 54 | 27 | 27 | 15 | 13 | 16 | 10 |
8 | 256 | 115 | 58 | 57 | 32 | 26 | 37 | 20 |
9 | 512 | 263 | 142 | 121 | 76 | 56 | 76 | 55 |
10 | 1.024 | 541 | 281 | 260 | 147 | 114 | 160 | 120 |
11 | 2.048 | 1.119 | 583 | 536 | 315 | 236 | 325 | 243 |
12 | 4.096 | 2.299 | 1.181 | 1.118 | 627 | 494 | 648 | 530 |
13 | 8.192 | 4.682 | 2.386 | 2.296 | 1.289 | 1.032 | 1.286 | 1.075 |
14 | 16.384 | 9.580 | 4.910 | 4.670 | 2.602 | 2.167 | 2.596 | 2.215 |
15 | 32.768 | 19.507 | 9.987 | 9.520 | 5.310 | 4.500 | 5.166 | 4.531 |
16 | 65.536 | 39.408 | 20.157 | 19.251 | 10.568 | 9.146 | 10.495 | 9.199 |
17 | 131.072 | 79.696 | 40.792 | 38.904 | 21.205 | 18.636 | 21.268 | 18.587 |
18 | 262.144 | 160.534 | 82.037 | 78.497 | 42.679 | 37.695 | 42.563 | 37.597 |
19 | 524.288 | 323.720 | 165.480 | 158.240 | 85.795 | 76.194 | 85.278 | 76.453 |
20 | 1.048.576 | 651.640 | 332.499 | 319.141 | 171.528 | 154.037 | 171.619 | 154.456 |
21 | 2.097.152 | 1.311.724 | 668.907 | 642.817 | 344.037 | 311.903 | 344.128 | 311.656 |
22 | 4.194.304 | 2.637.450 | 1.342.455 | 1.294.995 | 689.963 | 628.840 | 689.540 | 629.107 |
23 | 8.388.608 | 5.300.868 | 2.696.325 | 2.604.543 | 1.383.822 | 1.266.579 | 1.383.375 | 1.267.092 |
24 | 16.777.216 | 10.647.700 | 5.408.467 | 5.239.233 | 2.773.479 | 2.551.339 | 2.772.139 | 2.550.743 |
25 | 33.554.432 | 21.376.414 | 10.852.770 | 10.523.644 | 5.559.291 | 5.129.347 | 5.557.511 | 5.130.265 |
26 | 67.108.864 | 42.903.458 | 21.770.828 | 21.132.630 | 11.136.501 | 10.315.602 | 11.135.169 | 10.316.186 |
27 | 134.217.728 | 86.088.185 | 43.651.379 | 42.436.806 | 22.307.207 | 20.735.778 | 22.307.910 | 20.737.290 |
28 | 268.435.456 | 172.691.937 | 87.510.269 | 85.181.668 | 44.683.559 | 41.661.330 | 44.687.834 | 41.659.214 |
29 | 536.870.912 | 346.343.713 | 175.402.078 | 170.941.635 | 89.495.662 | 83.675.233 | 89.500.369 | 83.672.449 |
30 | 1.073.741.824 | 694.479.300 | 351.521.793 | 342.957.507 | 179.239.656 | 167.991.071 | 179.244.712 | 168.003.861 |
31 | 2.147.483.648 | 1.392.305.893 | 704.396.825 | 687.909.068 | 358.926.415 | 337.212.601 | 358.920.703 | 337.246.174 |
32 | 4.294.967.296 | 2.790.851.948 | 1.411.291.677 | 1.379.560.271 | 718.671.760 | 676.732.374 | 718.703.618 | 676.744.196 |
33 | 8.589.934.592 | 5.593.411.067 | 2.827.333.270 | 2.766.077.797 | 1.438.909.922 | 1.357.776.244 | 1.438.946.392 | 1.357.778.509 |
34 | 17.179.869.184 | 11.208.788.676 | 5.663.637.881 | 5.545.150.795 | 2.880.788.047 | 2.723.581.096 | 2.880.827.681 | 2.723.591.852 |
35 | 34.359.738.368 | 22.458.916.060 | 11.344.031.039 | 11.114.885.021 | 5.767.214.816 | 5.462.260.538 | 5.767.134.850 | 5.462.305.856 |
36 | 68.719.476.736 | 44.995.854.065 | 22.719.734.727 | 22.276.119.338 | 11.544.826.352 | 10.953.157.881 | 11.544.723.963 | 10.953.145.869 |