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-5
f(0)=5
f(1)=1
f(2)=1
f(3)=1
f(4)=11
f(5)=1
f(6)=31
f(7)=1
f(8)=59
f(9)=19
f(10)=1
f(11)=29
f(12)=139
f(13)=41
f(14)=191
f(15)=1
f(16)=251
f(17)=71
f(18)=1
f(19)=89
f(20)=79
f(21)=109
f(22)=479
f(23)=131
f(24)=571
f(25)=1
f(26)=61
f(27)=181
f(28)=1
f(29)=1
f(30)=179
f(31)=239
f(32)=1019
f(33)=271
f(34)=1151
f(35)=1
f(36)=1291
f(37)=1
f(38)=1439
f(39)=379
f(40)=1
f(41)=419
f(42)=1759
f(43)=461
f(44)=1931
f(45)=101
f(46)=2111
f(47)=1
f(48)=1
f(49)=599
f(50)=499
f(51)=1
f(52)=2699
f(53)=701
f(54)=1
f(55)=151
f(56)=1
f(57)=811
f(58)=3359
f(59)=1
f(60)=719
f(61)=929
f(62)=349
f(63)=991
f(64)=4091
f(65)=211
f(66)=229
f(67)=1
f(68)=149
f(69)=1
f(70)=1
f(71)=1259
f(72)=5179
f(73)=1
f(74)=5471
f(75)=281
f(76)=199
f(77)=1481
f(78)=6079
f(79)=1559
f(80)=1279
f(81)=1
f(82)=6719
f(83)=1721
f(84)=641
f(85)=1
f(86)=389
f(87)=1
f(88)=1
f(89)=1979
f(90)=1619
f(91)=2069
f(92)=769
f(93)=2161
f(94)=8831
f(95)=1
f(96)=1
f(97)=2351
f(98)=331
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-5 could be written as f(y)= y^2-5 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 > 2
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 | 5 | 0 | 0.500000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 70 | 50 | 20 | 0.700000 | 0.500000 | 0.700000 | 14.000000 | 10.000000 | inf |
3 | 1.000 | 721 | 328 | 393 | 0.721000 | 0.328000 | 0.721000 | 10.300000 | 6.560000 | 19.650000 |
4 | 10.000 | 7.173 | 2.272 | 4.901 | 0.717300 | 0.227200 | 0.717300 | 9.948683 | 6.926829 | 12.470737 |
5 | 100.000 | 71.126 | 17.712 | 53.414 | 0.711260 | 0.177120 | 0.711260 | 9.915795 | 7.795774 | 10.898592 |
6 | 1.000.000 | 707.827 | 143.540 | 564.287 | 0.707827 | 0.143540 | 0.707827 | 9.951734 | 8.104110 | 10.564403 |
7 | 10.000.000 | 7.053.002 | 1.207.691 | 5.845.311 | 0.705300 | 0.120769 | 0.705300 | 9.964302 | 8.413620 | 10.358755 |
8 | 100.000.000 | 70.352.853 | 10.431.319 | 59.921.534 | 0.703529 | 0.104313 | 0.703529 | 9.974881 | 8.637407 | 10.251214 |
9 | 1.000.000.000 | 702.187.799 | 91.820.600 | 610.367.199 | 0.702188 | 0.091821 | 0.702188 | 9.980942 | 8.802396 | 10.186107 |
10 | 10.000.000.000 | 7.011.511.538 | 820.089.019 | 6.191.422.519 | 0.701151 | 0.082009 | 0.701151 | 9.985237 | 8.931427 | 10.143767 |
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 | 1 | 1 | 0 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 2 | 2 | 0 | 0.500000 | 0.500000 | 0.000000 | 2.000000 | 2.000000 | -nan |
3 | 8 | 4 | 4 | 0 | 0.500000 | 0.500000 | 0.000000 | 2.000000 | 2.000000 | -nan |
4 | 16 | 10 | 10 | 0 | 0.625000 | 0.625000 | 0.000000 | 2.500000 | 2.500000 | -nan |
5 | 32 | 22 | 19 | 3 | 0.687500 | 0.593750 | 0.093750 | 2.200000 | 1.900000 | inf |
6 | 64 | 45 | 37 | 8 | 0.703125 | 0.578125 | 0.125000 | 2.045455 | 1.947368 | 2.666667 |
7 | 128 | 92 | 61 | 31 | 0.718750 | 0.476562 | 0.242188 | 2.044445 | 1.648649 | 3.875000 |
8 | 256 | 185 | 103 | 82 | 0.722656 | 0.402344 | 0.320312 | 2.010870 | 1.688525 | 2.645161 |
9 | 512 | 370 | 189 | 181 | 0.722656 | 0.369141 | 0.353516 | 2.000000 | 1.834951 | 2.207317 |
10 | 1.024 | 740 | 339 | 401 | 0.722656 | 0.331055 | 0.391602 | 2.000000 | 1.793651 | 2.215470 |
11 | 2.048 | 1.467 | 607 | 860 | 0.716309 | 0.296387 | 0.419922 | 1.982432 | 1.790560 | 2.144638 |
12 | 4.096 | 2.935 | 1.065 | 1.870 | 0.716553 | 0.260010 | 0.456543 | 2.000682 | 1.754530 | 2.174419 |
13 | 8.192 | 5.872 | 1.918 | 3.954 | 0.716797 | 0.234131 | 0.482666 | 2.000681 | 1.800939 | 2.114439 |
14 | 16.384 | 11.708 | 3.560 | 8.148 | 0.714600 | 0.217285 | 0.497314 | 1.993869 | 1.856100 | 2.060698 |
15 | 32.768 | 23.375 | 6.510 | 16.865 | 0.713348 | 0.198669 | 0.514679 | 1.996498 | 1.828652 | 2.069833 |
16 | 65.536 | 46.666 | 12.090 | 34.576 | 0.712067 | 0.184479 | 0.527588 | 1.996406 | 1.857143 | 2.050163 |
17 | 131.072 | 93.175 | 22.563 | 70.612 | 0.710869 | 0.172142 | 0.538727 | 1.996636 | 1.866253 | 2.042226 |
18 | 262.144 | 186.001 | 42.310 | 143.691 | 0.709538 | 0.161400 | 0.548138 | 1.996254 | 1.875194 | 2.034937 |
19 | 524.288 | 371.555 | 79.465 | 292.090 | 0.708685 | 0.151567 | 0.557117 | 1.997597 | 1.878161 | 2.032765 |
20 | 1.048.576 | 742.020 | 149.920 | 592.100 | 0.707645 | 0.142975 | 0.564671 | 1.997066 | 1.886617 | 2.027115 |
21 | 2.097.152 | 1.482.615 | 283.614 | 1.199.001 | 0.706966 | 0.135238 | 0.571728 | 1.998080 | 1.891769 | 2.024997 |
22 | 4.194.304 | 2.961.929 | 538.205 | 2.423.724 | 0.706179 | 0.128318 | 0.577861 | 1.997774 | 1.897667 | 2.021453 |
23 | 8.388.608 | 5.918.689 | 1.025.190 | 4.893.499 | 0.705563 | 0.122212 | 0.583351 | 1.998255 | 1.904832 | 2.019000 |
24 | 16.777.216 | 11.825.983 | 1.956.538 | 9.869.445 | 0.704884 | 0.116619 | 0.588265 | 1.998075 | 1.908464 | 2.016848 |
25 | 33.554.432 | 23.632.596 | 3.742.329 | 19.890.267 | 0.704306 | 0.111530 | 0.592776 | 1.998362 | 1.912730 | 2.015338 |
26 | 67.108.864 | 47.230.009 | 7.168.687 | 40.061.322 | 0.703782 | 0.106822 | 0.596960 | 1.998511 | 1.915568 | 2.014117 |
27 | 134.217.728 | 94.400.157 | 13.762.398 | 80.637.759 | 0.703336 | 0.102538 | 0.600798 | 1.998733 | 1.919793 | 2.012858 |
28 | 268.435.456 | 188.686.637 | 26.458.304 | 162.228.333 | 0.702913 | 0.098565 | 0.604348 | 1.998796 | 1.922507 | 2.011816 |
29 | 536.870.912 | 377.159.363 | 50.943.386 | 326.215.977 | 0.702514 | 0.094889 | 0.607625 | 1.998866 | 1.925421 | 2.010844 |
30 | 1.073.741.824 | 753.930.434 | 98.226.781 | 655.703.653 | 0.702152 | 0.091481 | 0.610672 | 1.998971 | 1.928156 | 2.010029 |
31 | 2.147.483.648 | 1.507.145.912 | 189.637.949 | 1.317.507.963 | 0.701819 | 0.088307 | 0.613512 | 1.999052 | 1.930614 | 2.009304 |
32 | 4.294.967.296 | 3.012.937.517 | 366.592.849 | 2.646.344.668 | 0.701504 | 0.085354 | 0.616150 | 1.999101 | 1.933120 | 2.008599 |
33 | 8.589.934.592 | 6.023.372.344 | 709.449.015 | 5.313.923.329 | 0.701213 | 0.082591 | 0.618622 | 1.999169 | 1.935251 | 2.008024 |
34 | 17.179.869.184 | 12.042.058.596 | 1.374.424.261 | 10.667.634.335 | 0.700940 | 0.080002 | 0.620938 | 1.999222 | 1.937312 | 2.007487 |
35 | 34.359.738.368 | 24.075.312.890 | 2.665.326.171 | 21.409.986.719 | 0.700684 | 0.077571 | 0.623113 | 1.999269 | 1.939231 | 2.007004 |
36 | 68.719.476.736 | 48.134.227.543 | 5.173.440.606 | 42.960.786.937 | 0.700445 | 0.075283 | 0.625162 | 1.999319 | 1.941016 | 2.006577 |
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 | 0 | 1 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 0 | 2 | 0 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 3 | 0 | 2 | 1 | 1 |
4 | 16 | 10 | 3 | 7 | 1 | 5 | 2 | 2 |
5 | 32 | 19 | 6 | 13 | 2 | 8 | 4 | 5 |
6 | 64 | 37 | 12 | 25 | 3 | 15 | 6 | 13 |
7 | 128 | 61 | 17 | 44 | 7 | 22 | 9 | 23 |
8 | 256 | 103 | 35 | 68 | 13 | 40 | 15 | 35 |
9 | 512 | 189 | 63 | 126 | 27 | 75 | 23 | 64 |
10 | 1.024 | 339 | 112 | 227 | 46 | 122 | 47 | 124 |
11 | 2.048 | 607 | 199 | 408 | 81 | 230 | 82 | 214 |
12 | 4.096 | 1.065 | 361 | 704 | 137 | 406 | 141 | 381 |
13 | 8.192 | 1.918 | 647 | 1.271 | 242 | 726 | 262 | 688 |
14 | 16.384 | 3.560 | 1.200 | 2.360 | 456 | 1.328 | 470 | 1.306 |
15 | 32.768 | 6.510 | 2.156 | 4.354 | 830 | 2.433 | 866 | 2.381 |
16 | 65.536 | 12.090 | 3.984 | 8.106 | 1.553 | 4.513 | 1.598 | 4.426 |
17 | 131.072 | 22.563 | 7.459 | 15.104 | 2.877 | 8.424 | 2.974 | 8.288 |
18 | 262.144 | 42.310 | 14.029 | 28.281 | 5.426 | 15.792 | 5.484 | 15.608 |
19 | 524.288 | 79.465 | 26.428 | 53.037 | 10.136 | 29.527 | 10.304 | 29.498 |
20 | 1.048.576 | 149.920 | 50.022 | 99.898 | 19.141 | 55.611 | 19.500 | 55.668 |
21 | 2.097.152 | 283.614 | 94.620 | 188.994 | 36.383 | 105.368 | 36.674 | 105.189 |
22 | 4.194.304 | 538.205 | 179.852 | 358.353 | 68.835 | 200.090 | 69.448 | 199.832 |
23 | 8.388.608 | 1.025.190 | 341.834 | 683.356 | 130.979 | 381.222 | 131.539 | 381.450 |
24 | 16.777.216 | 1.956.538 | 652.522 | 1.304.016 | 249.797 | 728.217 | 250.439 | 728.085 |
25 | 33.554.432 | 3.742.329 | 1.248.531 | 2.493.798 | 477.375 | 1.393.606 | 478.067 | 1.393.281 |
26 | 67.108.864 | 7.168.687 | 2.391.197 | 4.777.490 | 914.341 | 2.669.023 | 915.224 | 2.670.099 |
27 | 134.217.728 | 13.762.398 | 4.589.940 | 9.172.458 | 1.754.726 | 5.125.204 | 1.755.578 | 5.126.890 |
28 | 268.435.456 | 26.458.304 | 8.823.562 | 17.634.742 | 3.370.977 | 9.855.631 | 3.373.649 | 9.858.047 |
29 | 536.870.912 | 50.943.386 | 16.982.138 | 33.961.248 | 6.486.066 | 18.982.011 | 6.489.172 | 18.986.137 |
30 | 1.073.741.824 | 98.226.781 | 32.748.112 | 65.478.669 | 12.496.473 | 36.611.494 | 12.502.981 | 36.615.833 |
31 | 2.147.483.648 | 189.637.949 | 63.219.125 | 126.418.824 | 24.112.275 | 70.699.629 | 24.117.613 | 70.708.432 |
32 | 4.294.967.296 | 366.592.849 | 122.204.946 | 244.387.903 | 46.590.812 | 136.700.230 | 46.592.773 | 136.709.034 |
33 | 8.589.934.592 | 709.449.015 | 236.484.817 | 472.964.198 | 90.117.543 | 264.596.925 | 90.114.904 | 264.619.643 |
34 | 17.179.869.184 | 1.374.424.261 | 458.152.758 | 916.271.503 | 174.495.473 | 512.693.013 | 174.499.432 | 512.736.343 |
35 | 34.359.738.368 | 2.665.326.171 | 888.452.044 | 1.776.874.127 | 338.235.895 | 994.402.463 | 338.228.666 | 994.459.147 |
36 | 68.719.476.736 | 5.173.440.606 | 1.724.471.045 | 3.448.969.561 | 656.210.924 | 1.930.453.881 | 656.210.016 | 1.930.565.785 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
6 | 64 | 8 | 5 | 3 | 0 | 2 | 3 | 3 |
7 | 128 | 31 | 16 | 15 | 8 | 5 | 10 | 8 |
8 | 256 | 82 | 43 | 39 | 24 | 18 | 20 | 20 |
9 | 512 | 181 | 104 | 77 | 45 | 44 | 50 | 42 |
10 | 1.024 | 401 | 225 | 176 | 102 | 105 | 101 | 93 |
11 | 2.048 | 860 | 464 | 396 | 216 | 211 | 233 | 200 |
12 | 4.096 | 1.870 | 1.003 | 867 | 473 | 441 | 499 | 457 |
13 | 8.192 | 3.954 | 2.089 | 1.865 | 1.009 | 947 | 1.038 | 960 |
14 | 16.384 | 8.148 | 4.314 | 3.834 | 2.043 | 1.993 | 2.094 | 2.018 |
15 | 32.768 | 16.865 | 8.902 | 7.963 | 4.251 | 4.119 | 4.342 | 4.153 |
16 | 65.536 | 34.576 | 18.142 | 16.434 | 8.793 | 8.399 | 8.835 | 8.549 |
17 | 131.072 | 70.612 | 36.935 | 33.677 | 17.932 | 17.170 | 18.029 | 17.481 |
18 | 262.144 | 143.691 | 74.699 | 68.992 | 36.413 | 35.210 | 36.656 | 35.412 |
19 | 524.288 | 292.090 | 151.602 | 140.488 | 74.121 | 71.637 | 74.381 | 71.951 |
20 | 1.048.576 | 592.100 | 306.449 | 285.651 | 150.111 | 145.626 | 150.465 | 145.898 |
21 | 2.097.152 | 1.199.001 | 619.372 | 579.629 | 303.838 | 295.230 | 304.473 | 295.460 |
22 | 4.194.304 | 2.423.724 | 1.248.574 | 1.175.150 | 613.380 | 597.242 | 614.484 | 598.618 |
23 | 8.388.608 | 4.893.499 | 2.516.315 | 2.377.184 | 1.238.894 | 1.206.145 | 1.239.323 | 1.209.137 |
24 | 16.777.216 | 9.869.445 | 5.066.594 | 4.802.851 | 2.495.904 | 2.438.206 | 2.494.758 | 2.440.577 |
25 | 33.554.432 | 19.890.267 | 10.197.664 | 9.692.603 | 5.024.125 | 4.922.136 | 5.024.900 | 4.919.106 |
26 | 67.108.864 | 40.061.322 | 20.516.411 | 19.544.911 | 10.115.906 | 9.918.106 | 10.114.356 | 9.912.954 |
27 | 134.217.728 | 80.637.759 | 41.247.720 | 39.390.039 | 20.350.109 | 19.972.069 | 20.348.628 | 19.966.953 |
28 | 268.435.456 | 162.228.333 | 82.892.600 | 79.335.733 | 40.924.019 | 40.193.337 | 40.919.218 | 40.191.759 |
29 | 536.870.912 | 326.215.977 | 166.524.083 | 159.691.894 | 82.254.757 | 80.856.355 | 82.245.725 | 80.859.140 |
30 | 1.073.741.824 | 655.703.653 | 334.442.736 | 321.260.917 | 165.258.649 | 162.596.485 | 165.256.839 | 162.591.680 |
31 | 2.147.483.648 | 1.317.507.963 | 671.441.218 | 646.066.745 | 331.922.809 | 326.824.791 | 331.942.042 | 326.818.321 |
32 | 4.294.967.296 | 2.646.344.668 | 1.347.678.164 | 1.298.666.504 | 666.485.801 | 656.671.166 | 666.524.702 | 656.662.999 |
33 | 8.589.934.592 | 5.313.923.329 | 2.704.307.001 | 2.609.616.328 | 1.337.935.895 | 1.318.990.193 | 1.338.018.234 | 1.318.979.007 |
34 | 17.179.869.184 | 10.667.634.335 | 5.425.418.908 | 5.242.215.427 | 2.685.128.290 | 2.648.586.662 | 2.685.295.665 | 2.648.623.718 |
35 | 34.359.738.368 | 21.409.986.719 | 10.882.391.813 | 10.527.594.906 | 5.387.799.364 | 5.317.185.693 | 5.387.898.354 | 5.317.103.308 |
36 | 68.719.476.736 | 42.960.786.937 | 21.824.258.824 | 21.136.528.113 | 10.808.450.762 | 10.671.903.578 | 10.808.621.186 | 10.671.811.411 |