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-17
f(0)=17
f(1)=1
f(2)=13
f(3)=1
f(4)=1
f(5)=1
f(6)=19
f(7)=1
f(8)=47
f(9)=1
f(10)=83
f(11)=1
f(12)=127
f(13)=1
f(14)=179
f(15)=1
f(16)=239
f(17)=1
f(18)=307
f(19)=43
f(20)=383
f(21)=53
f(22)=467
f(23)=1
f(24)=1
f(25)=1
f(26)=659
f(27)=89
f(28)=59
f(29)=103
f(30)=883
f(31)=1
f(32)=1
f(33)=67
f(34)=1
f(35)=151
f(36)=1279
f(37)=1
f(38)=1427
f(39)=1
f(40)=1583
f(41)=1
f(42)=1747
f(43)=229
f(44)=101
f(45)=251
f(46)=2099
f(47)=137
f(48)=2287
f(49)=149
f(50)=191
f(51)=1
f(52)=2687
f(53)=349
f(54)=223
f(55)=1
f(56)=3119
f(57)=1
f(58)=3347
f(59)=433
f(60)=3583
f(61)=463
f(62)=1
f(63)=1
f(64)=4079
f(65)=263
f(66)=4339
f(67)=1
f(68)=271
f(69)=593
f(70)=257
f(71)=157
f(72)=5167
f(73)=1
f(74)=1
f(75)=701
f(76)=443
f(77)=739
f(78)=6067
f(79)=389
f(80)=491
f(81)=409
f(82)=353
f(83)=859
f(84)=7039
f(85)=1
f(86)=1
f(87)=1
f(88)=7727
f(89)=1
f(90)=1
f(91)=1033
f(92)=8447
f(93)=1
f(94)=8819
f(95)=563
f(96)=9199
f(97)=587
f(98)=9587
f(99)=1223
b) Substitution of the polynom
The polynom f(x)=x^2-17 could be written as f(y)= y^2-17 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 | 5 | 0 | 0.500000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 67 | 58 | 9 | 0.670000 | 0.580000 | 0.670000 | 13.400000 | 11.600000 | inf |
3 | 1.000 | 700 | 447 | 253 | 0.700000 | 0.447000 | 0.700000 | 10.447762 | 7.706897 | 28.111111 |
4 | 10.000 | 7.014 | 3.226 | 3.788 | 0.701400 | 0.322600 | 0.701400 | 10.020000 | 7.217002 | 14.972332 |
5 | 100.000 | 70.160 | 24.424 | 45.736 | 0.701600 | 0.244240 | 0.701600 | 10.002851 | 7.570986 | 12.073917 |
6 | 1.000.000 | 699.710 | 197.556 | 502.154 | 0.699710 | 0.197556 | 0.699710 | 9.973062 | 8.088601 | 10.979403 |
7 | 10.000.000 | 6.985.445 | 1.650.704 | 5.334.741 | 0.698545 | 0.165070 | 0.698545 | 9.983343 | 8.355626 | 10.623715 |
8 | 100.000.000 | 69.765.034 | 14.202.141 | 55.562.893 | 0.697650 | 0.142021 | 0.697650 | 9.987200 | 8.603687 | 10.415294 |
9 | 1.000.000.000 | 697.003.610 | 124.645.820 | 572.357.790 | 0.697004 | 0.124646 | 0.697004 | 9.990729 | 8.776551 | 10.301080 |
10 | 10.000.000.000 | 6.965.138.183 | 1.110.745.529 | 5.854.392.654 | 0.696514 | 0.111075 | 0.696514 | 9.992973 | 8.911213 | 10.228555 |
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 | 4 | 0 | 0.500000 | 0.500000 | 0.000000 | 2.000000 | 2.000000 | -nan |
4 | 16 | 8 | 8 | 0 | 0.500000 | 0.500000 | 0.000000 | 2.000000 | 2.000000 | -nan |
5 | 32 | 18 | 17 | 1 | 0.562500 | 0.531250 | 0.031250 | 2.250000 | 2.125000 | inf |
6 | 64 | 41 | 37 | 4 | 0.640625 | 0.578125 | 0.062500 | 2.277778 | 2.176471 | 4.000000 |
7 | 128 | 88 | 74 | 14 | 0.687500 | 0.578125 | 0.109375 | 2.146342 | 2.000000 | 3.500000 |
8 | 256 | 173 | 140 | 33 | 0.675781 | 0.546875 | 0.128906 | 1.965909 | 1.891892 | 2.357143 |
9 | 512 | 354 | 248 | 106 | 0.691406 | 0.484375 | 0.207031 | 2.046243 | 1.771429 | 3.212121 |
10 | 1.024 | 717 | 457 | 260 | 0.700195 | 0.446289 | 0.253906 | 2.025424 | 1.842742 | 2.452830 |
11 | 2.048 | 1.431 | 834 | 597 | 0.698730 | 0.407227 | 0.291504 | 1.995816 | 1.824945 | 2.296154 |
12 | 4.096 | 2.876 | 1.504 | 1.372 | 0.702148 | 0.367188 | 0.334961 | 2.009783 | 1.803357 | 2.298157 |
13 | 8.192 | 5.749 | 2.723 | 3.026 | 0.701782 | 0.332397 | 0.369385 | 1.998957 | 1.810505 | 2.205539 |
14 | 16.384 | 11.506 | 4.948 | 6.558 | 0.702271 | 0.302002 | 0.400269 | 2.001392 | 1.817114 | 2.167217 |
15 | 32.768 | 23.017 | 9.114 | 13.903 | 0.702423 | 0.278137 | 0.424286 | 2.000435 | 1.841956 | 2.120006 |
16 | 65.536 | 45.980 | 16.750 | 29.230 | 0.701599 | 0.255585 | 0.446014 | 1.997654 | 1.837832 | 2.102424 |
17 | 131.072 | 91.906 | 31.202 | 60.704 | 0.701187 | 0.238052 | 0.463135 | 1.998826 | 1.862806 | 2.076771 |
18 | 262.144 | 183.638 | 58.228 | 125.410 | 0.700523 | 0.222122 | 0.478401 | 1.998107 | 1.866162 | 2.065927 |
19 | 524.288 | 367.113 | 109.324 | 257.789 | 0.700212 | 0.208519 | 0.491693 | 1.999112 | 1.877516 | 2.055570 |
20 | 1.048.576 | 733.630 | 206.238 | 527.392 | 0.699644 | 0.196684 | 0.502960 | 1.998376 | 1.886484 | 2.045828 |
21 | 2.097.152 | 1.466.280 | 389.744 | 1.076.536 | 0.699177 | 0.185844 | 0.513332 | 1.998664 | 1.889778 | 2.041245 |
22 | 4.194.304 | 2.931.368 | 737.834 | 2.193.534 | 0.698893 | 0.175913 | 0.522979 | 1.999187 | 1.893125 | 2.037585 |
23 | 8.388.608 | 5.860.349 | 1.402.433 | 4.457.916 | 0.698608 | 0.167183 | 0.531425 | 1.999186 | 1.900743 | 2.032299 |
24 | 16.777.216 | 11.715.744 | 2.670.324 | 9.045.420 | 0.698313 | 0.159164 | 0.539149 | 1.999155 | 1.904065 | 2.029069 |
25 | 33.554.432 | 23.421.794 | 5.103.021 | 18.318.773 | 0.698024 | 0.152082 | 0.545942 | 1.999173 | 1.911012 | 2.025199 |
26 | 67.108.864 | 46.828.217 | 9.767.792 | 37.060.425 | 0.697795 | 0.145551 | 0.552243 | 1.999344 | 1.914119 | 2.023084 |
27 | 134.217.728 | 93.625.807 | 18.727.743 | 74.898.064 | 0.697567 | 0.139533 | 0.558034 | 1.999346 | 1.917296 | 2.020972 |
28 | 268.435.456 | 187.192.043 | 35.973.768 | 151.218.275 | 0.697345 | 0.134013 | 0.563332 | 1.999364 | 1.920881 | 2.018988 |
29 | 536.870.912 | 374.284.033 | 69.204.231 | 305.079.802 | 0.697158 | 0.128903 | 0.568255 | 1.999465 | 1.923742 | 2.017480 |
30 | 1.073.741.824 | 748.382.479 | 133.334.763 | 615.047.716 | 0.696985 | 0.124178 | 0.572808 | 1.999504 | 1.926685 | 2.016022 |
31 | 2.147.483.648 | 1.496.414.986 | 257.250.728 | 1.239.164.258 | 0.696823 | 0.119792 | 0.577031 | 1.999532 | 1.929360 | 2.014745 |
32 | 4.294.967.296 | 2.992.207.777 | 496.918.525 | 2.495.289.252 | 0.696678 | 0.115698 | 0.580980 | 1.999584 | 1.931651 | 2.013687 |
33 | 8.589.934.592 | 5.983.254.983 | 961.023.218 | 5.022.231.765 | 0.696543 | 0.111878 | 0.584665 | 1.999612 | 1.933965 | 2.012685 |
34 | 17.179.869.184 | 11.964.313.610 | 1.860.706.633 | 10.103.606.977 | 0.696415 | 0.108307 | 0.588107 | 1.999633 | 1.936172 | 2.011776 |
35 | 34.359.738.368 | 23.924.632.733 | 3.606.282.820 | 20.318.349.913 | 0.696298 | 0.104957 | 0.591342 | 1.999666 | 1.938125 | 2.010999 |
36 | 68.719.476.736 | 47.841.729.387 | 6.996.135.127 | 40.845.594.260 | 0.696189 | 0.101807 | 0.594382 | 1.999685 | 1.939985 | 2.010281 |
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 | 1 | 1 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 8 | 3 | 5 | 1 | 3 | 1 | 3 |
5 | 32 | 17 | 7 | 10 | 2 | 8 | 2 | 5 |
6 | 64 | 37 | 17 | 20 | 4 | 14 | 5 | 14 |
7 | 128 | 74 | 35 | 39 | 10 | 28 | 11 | 25 |
8 | 256 | 140 | 61 | 79 | 17 | 56 | 18 | 49 |
9 | 512 | 248 | 119 | 129 | 32 | 92 | 34 | 90 |
10 | 1.024 | 457 | 214 | 243 | 56 | 163 | 66 | 172 |
11 | 2.048 | 834 | 378 | 456 | 105 | 294 | 117 | 318 |
12 | 4.096 | 1.504 | 685 | 819 | 197 | 541 | 215 | 551 |
13 | 8.192 | 2.723 | 1.235 | 1.488 | 353 | 968 | 381 | 1.021 |
14 | 16.384 | 4.948 | 2.223 | 2.725 | 663 | 1.787 | 681 | 1.817 |
15 | 32.768 | 9.114 | 4.096 | 5.018 | 1.221 | 3.332 | 1.221 | 3.340 |
16 | 65.536 | 16.750 | 7.578 | 9.172 | 2.235 | 6.136 | 2.257 | 6.122 |
17 | 131.072 | 31.202 | 14.086 | 17.116 | 4.147 | 11.503 | 4.207 | 11.345 |
18 | 262.144 | 58.228 | 26.319 | 31.909 | 7.732 | 21.420 | 7.771 | 21.305 |
19 | 524.288 | 109.324 | 49.343 | 59.981 | 14.483 | 40.086 | 14.535 | 40.220 |
20 | 1.048.576 | 206.238 | 92.899 | 113.339 | 27.189 | 75.804 | 27.293 | 75.952 |
21 | 2.097.152 | 389.744 | 175.315 | 214.429 | 51.355 | 143.352 | 51.424 | 143.613 |
22 | 4.194.304 | 737.834 | 331.515 | 406.319 | 96.961 | 271.681 | 97.083 | 272.109 |
23 | 8.388.608 | 1.402.433 | 629.470 | 772.963 | 183.668 | 517.045 | 184.085 | 517.635 |
24 | 16.777.216 | 2.670.324 | 1.197.926 | 1.472.398 | 349.035 | 984.882 | 349.842 | 986.565 |
25 | 33.554.432 | 5.103.021 | 2.287.863 | 2.815.158 | 666.345 | 1.883.837 | 667.116 | 1.885.723 |
26 | 67.108.864 | 9.767.792 | 4.380.048 | 5.387.744 | 1.272.980 | 3.609.253 | 1.275.028 | 3.610.531 |
27 | 134.217.728 | 18.727.743 | 8.394.186 | 10.333.557 | 2.437.387 | 6.924.807 | 2.437.923 | 6.927.626 |
28 | 268.435.456 | 35.973.768 | 16.119.169 | 19.854.599 | 4.676.641 | 13.312.075 | 4.672.598 | 13.312.454 |
29 | 536.870.912 | 69.204.231 | 31.002.062 | 38.202.169 | 8.981.874 | 25.624.827 | 8.978.384 | 25.619.146 |
30 | 1.073.741.824 | 133.334.763 | 59.712.141 | 73.622.622 | 17.280.592 | 49.392.439 | 17.276.626 | 49.385.106 |
31 | 2.147.483.648 | 257.250.728 | 115.170.982 | 142.079.746 | 33.301.119 | 95.334.568 | 33.296.517 | 95.318.524 |
32 | 4.294.967.296 | 496.918.525 | 222.411.684 | 274.506.841 | 64.247.843 | 184.215.217 | 64.242.981 | 184.212.484 |
33 | 8.589.934.592 | 961.023.218 | 430.028.315 | 530.994.903 | 124.127.882 | 356.397.952 | 124.111.233 | 356.386.151 |
34 | 17.179.869.184 | 1.860.706.633 | 832.433.954 | 1.028.272.679 | 240.063.841 | 690.291.526 | 240.049.676 | 690.301.590 |
35 | 34.359.738.368 | 3.606.282.820 | 1.613.049.420 | 1.993.233.400 | 464.820.100 | 1.338.342.305 | 464.827.702 | 1.338.292.713 |
36 | 68.719.476.736 | 6.996.135.127 | 3.128.678.663 | 3.867.456.464 | 900.914.401 | 2.597.156.039 | 900.930.172 | 2.597.134.515 |
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 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
6 | 64 | 4 | 1 | 3 | 0 | 1 | 1 | 2 |
7 | 128 | 14 | 4 | 10 | 3 | 4 | 3 | 4 |
8 | 256 | 33 | 14 | 19 | 5 | 9 | 8 | 11 |
9 | 512 | 106 | 48 | 58 | 21 | 27 | 29 | 29 |
10 | 1.024 | 260 | 116 | 144 | 65 | 59 | 68 | 68 |
11 | 2.048 | 597 | 293 | 304 | 140 | 144 | 162 | 151 |
12 | 4.096 | 1.372 | 673 | 699 | 343 | 322 | 361 | 346 |
13 | 8.192 | 3.026 | 1.469 | 1.557 | 768 | 743 | 791 | 724 |
14 | 16.384 | 6.558 | 3.224 | 3.334 | 1.678 | 1.635 | 1.662 | 1.583 |
15 | 32.768 | 13.903 | 6.885 | 7.018 | 3.497 | 3.446 | 3.544 | 3.416 |
16 | 65.536 | 29.230 | 14.541 | 14.689 | 7.333 | 7.235 | 7.443 | 7.219 |
17 | 131.072 | 60.704 | 30.238 | 30.466 | 15.209 | 15.034 | 15.460 | 15.001 |
18 | 262.144 | 125.410 | 62.491 | 62.919 | 31.470 | 31.063 | 31.820 | 31.057 |
19 | 524.288 | 257.789 | 128.719 | 129.070 | 64.694 | 63.922 | 65.240 | 63.933 |
20 | 1.048.576 | 527.392 | 262.971 | 264.421 | 132.486 | 130.928 | 133.006 | 130.972 |
21 | 2.097.152 | 1.076.536 | 536.781 | 539.755 | 271.013 | 267.797 | 270.754 | 266.972 |
22 | 4.194.304 | 2.193.534 | 1.093.105 | 1.100.429 | 551.699 | 546.071 | 550.966 | 544.798 |
23 | 8.388.608 | 4.457.916 | 2.222.215 | 2.235.701 | 1.119.534 | 1.110.088 | 1.120.019 | 1.108.275 |
24 | 16.777.216 | 9.045.420 | 4.508.769 | 4.536.651 | 2.271.585 | 2.252.456 | 2.271.893 | 2.249.486 |
25 | 33.554.432 | 18.318.773 | 9.131.300 | 9.187.473 | 4.599.292 | 4.560.130 | 4.601.132 | 4.558.219 |
26 | 67.108.864 | 37.060.425 | 18.475.833 | 18.584.592 | 9.302.535 | 9.227.475 | 9.305.593 | 9.224.822 |
27 | 134.217.728 | 74.898.064 | 37.349.062 | 37.549.002 | 18.797.944 | 18.647.452 | 18.800.428 | 18.652.240 |
28 | 268.435.456 | 151.218.275 | 75.420.936 | 75.797.339 | 37.945.733 | 37.659.038 | 37.948.134 | 37.665.370 |
29 | 536.870.912 | 305.079.802 | 152.160.811 | 152.918.991 | 76.538.788 | 75.992.351 | 76.542.278 | 76.006.385 |
30 | 1.073.741.824 | 615.047.716 | 306.787.614 | 308.260.102 | 154.281.407 | 153.235.924 | 154.283.664 | 153.246.721 |
31 | 2.147.483.648 | 1.239.164.258 | 618.160.652 | 621.003.606 | 310.790.003 | 308.788.517 | 310.799.903 | 308.785.835 |
32 | 4.294.967.296 | 2.495.289.252 | 1.244.882.536 | 1.250.406.716 | 625.723.075 | 621.918.238 | 625.751.848 | 621.896.091 |
33 | 8.589.934.592 | 5.022.231.765 | 2.505.712.829 | 2.516.518.936 | 1.259.216.093 | 1.251.893.441 | 1.259.267.655 | 1.251.854.576 |
34 | 17.179.869.184 | 10.103.606.977 | 5.041.320.238 | 5.062.286.739 | 2.532.885.050 | 2.518.923.641 | 2.532.952.510 | 2.518.845.776 |
35 | 34.359.738.368 | 20.318.349.913 | 10.138.845.089 | 10.179.504.824 | 5.093.037.199 | 5.066.147.120 | 5.093.172.097 | 5.065.993.497 |
36 | 68.719.476.736 | 40.845.594.260 | 20.383.350.421 | 20.462.243.839 | 10.237.335.031 | 10.185.435.683 | 10.237.495.090 | 10.185.328.456 |