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+4x-139
f(0)=139
f(1)=67
f(2)=127
f(3)=59
f(4)=107
f(5)=47
f(6)=79
f(7)=31
f(8)=43
f(9)=11
f(10)=1
f(11)=13
f(12)=53
f(13)=41
f(14)=113
f(15)=73
f(16)=181
f(17)=109
f(18)=257
f(19)=149
f(20)=1
f(21)=193
f(22)=433
f(23)=241
f(24)=1
f(25)=293
f(26)=641
f(27)=349
f(28)=757
f(29)=409
f(30)=881
f(31)=1
f(32)=1013
f(33)=541
f(34)=1153
f(35)=613
f(36)=1301
f(37)=1
f(38)=1
f(39)=769
f(40)=1621
f(41)=853
f(42)=163
f(43)=941
f(44)=1973
f(45)=1033
f(46)=2161
f(47)=1129
f(48)=2357
f(49)=1229
f(50)=197
f(51)=1
f(52)=1
f(53)=131
f(54)=1
f(55)=1553
f(56)=3221
f(57)=1669
f(58)=3457
f(59)=1789
f(60)=3701
f(61)=1913
f(62)=1
f(63)=157
f(64)=383
f(65)=1
f(66)=4481
f(67)=2309
f(68)=71
f(69)=1
f(70)=1
f(71)=2593
f(72)=5333
f(73)=2741
f(74)=1
f(75)=263
f(76)=457
f(77)=3049
f(78)=6257
f(79)=3209
f(80)=6581
f(81)=3373
f(82)=223
f(83)=3541
f(84)=7253
f(85)=1
f(86)=691
f(87)=3889
f(88)=1
f(89)=313
f(90)=1
f(91)=4253
f(92)=8693
f(93)=4441
f(94)=211
f(95)=1
f(96)=9461
f(97)=439
f(98)=9857
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+4x-139 could be written as f(y)= y^2-143 with x=y-2
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+2
f'(x)>2x+3
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 | 10 | 5 | 5 | 1.000000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 81 | 31 | 50 | 0.810000 | 0.310000 | 0.810000 | 8.100000 | 6.200000 | 10.000000 |
3 | 1.000 | 756 | 196 | 560 | 0.756000 | 0.196000 | 0.756000 | 9.333333 | 6.322581 | 11.200000 |
4 | 10.000 | 7.424 | 1.403 | 6.021 | 0.742400 | 0.140300 | 0.742400 | 9.820106 | 7.158163 | 10.751785 |
5 | 100.000 | 73.150 | 10.947 | 62.203 | 0.731500 | 0.109470 | 0.731500 | 9.853179 | 7.802566 | 10.331008 |
6 | 1.000.000 | 725.521 | 89.101 | 636.420 | 0.725521 | 0.089101 | 0.725521 | 9.918263 | 8.139308 | 10.231339 |
7 | 10.000.000 | 7.207.275 | 753.941 | 6.453.334 | 0.720728 | 0.075394 | 0.720728 | 9.933930 | 8.461645 | 10.140056 |
8 | 100.000.000 | 71.702.175 | 6.530.743 | 65.171.432 | 0.717022 | 0.065307 | 0.717022 | 9.948584 | 8.662141 | 10.098878 |
9 | 1.000.000.000 | 714.201.355 | 57.614.962 | 656.586.393 | 0.714201 | 0.057615 | 0.714201 | 9.960665 | 8.822114 | 10.074758 |
10 | 10.000.000.000 | 7.119.912.947 | 515.564.202 | 6.604.348.745 | 0.711991 | 0.051556 | 0.711991 | 9.969056 | 8.948443 | 10.058614 |
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 | 9 | 5 | 4 | 1.125000 | 0.625000 | 0.500000 | 1.800000 | 1.666667 | 2.000000 |
4 | 16 | 16 | 8 | 8 | 1.000000 | 0.500000 | 0.500000 | 1.777778 | 1.600000 | 2.000000 |
5 | 32 | 29 | 14 | 15 | 0.906250 | 0.437500 | 0.468750 | 1.812500 | 1.750000 | 1.875000 |
6 | 64 | 55 | 23 | 32 | 0.859375 | 0.359375 | 0.500000 | 1.896552 | 1.642857 | 2.133333 |
7 | 128 | 103 | 39 | 64 | 0.804688 | 0.304688 | 0.500000 | 1.872727 | 1.695652 | 2.000000 |
8 | 256 | 200 | 68 | 132 | 0.781250 | 0.265625 | 0.515625 | 1.941748 | 1.743590 | 2.062500 |
9 | 512 | 398 | 116 | 282 | 0.777344 | 0.226562 | 0.550781 | 1.990000 | 1.705882 | 2.136364 |
10 | 1.024 | 776 | 200 | 576 | 0.757812 | 0.195312 | 0.562500 | 1.949749 | 1.724138 | 2.042553 |
11 | 2.048 | 1.539 | 360 | 1.179 | 0.751465 | 0.175781 | 0.575684 | 1.983247 | 1.800000 | 2.046875 |
12 | 4.096 | 3.055 | 648 | 2.407 | 0.745850 | 0.158203 | 0.587646 | 1.985055 | 1.800000 | 2.041561 |
13 | 8.192 | 6.085 | 1.176 | 4.909 | 0.742798 | 0.143555 | 0.599243 | 1.991817 | 1.814815 | 2.039468 |
14 | 16.384 | 12.099 | 2.170 | 9.929 | 0.738464 | 0.132446 | 0.606018 | 1.988332 | 1.845238 | 2.022612 |
15 | 32.768 | 24.069 | 4.050 | 20.019 | 0.734528 | 0.123596 | 0.610931 | 1.989338 | 1.866359 | 2.016215 |
16 | 65.536 | 48.016 | 7.520 | 40.496 | 0.732666 | 0.114746 | 0.617920 | 1.994931 | 1.856790 | 2.022878 |
17 | 131.072 | 95.832 | 14.004 | 81.828 | 0.731140 | 0.106842 | 0.624298 | 1.995835 | 1.862234 | 2.020644 |
18 | 262.144 | 191.120 | 26.174 | 164.946 | 0.729065 | 0.099846 | 0.629219 | 1.994323 | 1.869037 | 2.015765 |
19 | 524.288 | 381.130 | 49.344 | 331.786 | 0.726948 | 0.094116 | 0.632832 | 1.994192 | 1.885230 | 2.011482 |
20 | 1.048.576 | 760.529 | 93.094 | 667.435 | 0.725297 | 0.088781 | 0.636516 | 1.995458 | 1.886633 | 2.011643 |
21 | 2.097.152 | 1.518.161 | 176.582 | 1.341.579 | 0.723916 | 0.084201 | 0.639715 | 1.996191 | 1.896814 | 2.010052 |
22 | 4.194.304 | 3.030.572 | 335.360 | 2.695.212 | 0.722545 | 0.079956 | 0.642589 | 1.996212 | 1.899174 | 2.008985 |
23 | 8.388.608 | 6.049.414 | 639.964 | 5.409.450 | 0.721146 | 0.076290 | 0.644857 | 1.996129 | 1.908290 | 2.007059 |
24 | 16.777.216 | 12.076.136 | 1.222.352 | 10.853.784 | 0.719794 | 0.072858 | 0.646936 | 1.996249 | 1.910032 | 2.006449 |
25 | 33.554.432 | 24.112.891 | 2.340.663 | 21.772.228 | 0.718620 | 0.069757 | 0.648863 | 1.996739 | 1.914885 | 2.005957 |
26 | 67.108.864 | 48.156.517 | 4.486.561 | 43.669.956 | 0.717588 | 0.066855 | 0.650733 | 1.997127 | 1.916791 | 2.005764 |
27 | 134.217.728 | 96.182.082 | 8.616.132 | 87.565.950 | 0.716612 | 0.064195 | 0.652417 | 1.997281 | 1.920431 | 2.005176 |
28 | 268.435.456 | 192.125.334 | 16.580.096 | 175.545.238 | 0.715723 | 0.061766 | 0.653957 | 1.997517 | 1.924309 | 2.004720 |
29 | 536.870.912 | 383.801.333 | 31.948.842 | 351.852.491 | 0.714886 | 0.059509 | 0.655376 | 1.997661 | 1.926939 | 2.004341 |
30 | 1.073.741.824 | 766.789.312 | 61.639.922 | 705.149.390 | 0.714128 | 0.057407 | 0.656722 | 1.997881 | 1.929332 | 2.004105 |
31 | 2.147.483.648 | 1.532.052.441 | 119.077.063 | 1.412.975.378 | 0.713418 | 0.055450 | 0.657968 | 1.998010 | 1.931817 | 2.003796 |
32 | 4.294.967.296 | 3.061.236.042 | 230.319.406 | 2.830.916.636 | 0.712750 | 0.053625 | 0.659124 | 1.998127 | 1.934205 | 2.003515 |
33 | 8.589.934.592 | 6.117.093.784 | 445.964.779 | 5.671.129.005 | 0.712123 | 0.051917 | 0.660206 | 1.998243 | 1.936288 | 2.003284 |
34 | 17.179.869.184 | 12.224.060.228 | 864.422.705 | 11.359.637.523 | 0.711534 | 0.050316 | 0.661218 | 1.998344 | 1.938321 | 2.003065 |
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 | 2 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 2 | 0 | 1 |
3 | 8 | 5 | 4 | 1 | 0 | 3 | 0 | 2 |
4 | 16 | 8 | 5 | 3 | 1 | 3 | 2 | 2 |
5 | 32 | 14 | 7 | 7 | 5 | 3 | 4 | 2 |
6 | 64 | 23 | 11 | 12 | 8 | 3 | 10 | 2 |
7 | 128 | 39 | 13 | 26 | 14 | 3 | 20 | 2 |
8 | 256 | 68 | 21 | 47 | 32 | 3 | 31 | 2 |
9 | 512 | 116 | 35 | 81 | 57 | 3 | 54 | 2 |
10 | 1.024 | 200 | 66 | 134 | 95 | 3 | 100 | 2 |
11 | 2.048 | 360 | 110 | 250 | 174 | 3 | 181 | 2 |
12 | 4.096 | 648 | 201 | 447 | 327 | 3 | 316 | 2 |
13 | 8.192 | 1.176 | 379 | 797 | 592 | 3 | 579 | 2 |
14 | 16.384 | 2.170 | 704 | 1.466 | 1.101 | 3 | 1.064 | 2 |
15 | 32.768 | 4.050 | 1.317 | 2.733 | 2.004 | 3 | 2.041 | 2 |
16 | 65.536 | 7.520 | 2.456 | 5.064 | 3.757 | 3 | 3.758 | 2 |
17 | 131.072 | 14.004 | 4.603 | 9.401 | 6.980 | 3 | 7.019 | 2 |
18 | 262.144 | 26.174 | 8.653 | 17.521 | 13.100 | 3 | 13.069 | 2 |
19 | 524.288 | 49.344 | 16.386 | 32.958 | 24.752 | 3 | 24.587 | 2 |
20 | 1.048.576 | 93.094 | 31.009 | 62.085 | 46.569 | 3 | 46.520 | 2 |
21 | 2.097.152 | 176.582 | 58.858 | 117.724 | 88.302 | 3 | 88.275 | 2 |
22 | 4.194.304 | 335.360 | 111.748 | 223.612 | 167.529 | 3 | 167.826 | 2 |
23 | 8.388.608 | 639.964 | 213.350 | 426.614 | 319.869 | 3 | 320.090 | 2 |
24 | 16.777.216 | 1.222.352 | 407.600 | 814.752 | 610.895 | 3 | 611.452 | 2 |
25 | 33.554.432 | 2.340.663 | 779.970 | 1.560.693 | 1.170.618 | 3 | 1.170.040 | 2 |
26 | 67.108.864 | 4.486.561 | 1.494.934 | 2.991.627 | 2.242.861 | 3 | 2.243.695 | 2 |
27 | 134.217.728 | 8.616.132 | 2.870.946 | 5.745.186 | 4.308.333 | 3 | 4.307.794 | 2 |
28 | 268.435.456 | 16.580.096 | 5.526.459 | 11.053.637 | 8.290.449 | 3 | 8.289.642 | 2 |
29 | 536.870.912 | 31.948.842 | 10.650.071 | 21.298.771 | 15.974.414 | 3 | 15.974.423 | 2 |
30 | 1.073.741.824 | 61.639.922 | 20.547.176 | 41.092.746 | 30.821.228 | 3 | 30.818.689 | 2 |
31 | 2.147.483.648 | 119.077.063 | 39.690.463 | 79.386.600 | 59.541.573 | 3 | 59.535.485 | 2 |
32 | 4.294.967.296 | 230.319.406 | 76.771.508 | 153.547.898 | 115.165.955 | 3 | 115.153.446 | 2 |
33 | 8.589.934.592 | 445.964.779 | 148.654.582 | 297.310.197 | 222.991.543 | 3 | 222.973.231 | 2 |
34 | 17.179.869.184 | 864.422.705 | 288.136.646 | 576.286.059 | 432.219.152 | 3 | 432.203.548 | 2 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 0 | 2 | 0 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 2 | 0 | 2 |
4 | 16 | 8 | 4 | 4 | 2 | 3 | 1 | 2 |
5 | 32 | 15 | 9 | 6 | 5 | 3 | 5 | 2 |
6 | 64 | 32 | 19 | 13 | 10 | 5 | 14 | 3 |
7 | 128 | 64 | 38 | 26 | 24 | 9 | 24 | 7 |
8 | 256 | 132 | 77 | 55 | 45 | 23 | 44 | 20 |
9 | 512 | 282 | 156 | 126 | 92 | 57 | 83 | 50 |
10 | 1.024 | 576 | 314 | 262 | 175 | 113 | 176 | 112 |
11 | 2.048 | 1.179 | 640 | 539 | 343 | 244 | 354 | 238 |
12 | 4.096 | 2.407 | 1.326 | 1.081 | 692 | 502 | 694 | 519 |
13 | 8.192 | 4.909 | 2.657 | 2.252 | 1.375 | 1.058 | 1.411 | 1.065 |
14 | 16.384 | 9.929 | 5.328 | 4.601 | 2.784 | 2.199 | 2.781 | 2.165 |
15 | 32.768 | 20.019 | 10.701 | 9.318 | 5.622 | 4.433 | 5.611 | 4.353 |
16 | 65.536 | 40.496 | 21.513 | 18.983 | 11.229 | 9.040 | 11.236 | 8.991 |
17 | 131.072 | 81.828 | 43.363 | 38.465 | 22.535 | 18.433 | 22.557 | 18.303 |
18 | 262.144 | 164.946 | 86.976 | 77.970 | 45.187 | 37.262 | 45.345 | 37.152 |
19 | 524.288 | 331.786 | 174.545 | 157.241 | 90.673 | 75.203 | 90.583 | 75.327 |
20 | 1.048.576 | 667.435 | 349.794 | 317.641 | 181.224 | 152.370 | 181.547 | 152.294 |
21 | 2.097.152 | 1.341.579 | 700.648 | 640.931 | 362.703 | 308.150 | 363.057 | 307.669 |
22 | 4.194.304 | 2.695.212 | 1.404.579 | 1.290.633 | 725.451 | 621.219 | 726.968 | 621.574 |
23 | 8.388.608 | 5.409.450 | 2.812.620 | 2.596.830 | 1.452.338 | 1.251.905 | 1.453.630 | 1.251.577 |
24 | 16.777.216 | 10.853.784 | 5.633.905 | 5.219.879 | 2.906.463 | 2.519.980 | 2.906.552 | 2.520.789 |
25 | 33.554.432 | 21.772.228 | 11.282.044 | 10.490.184 | 5.813.740 | 5.072.165 | 5.813.037 | 5.073.286 |
26 | 67.108.864 | 43.669.956 | 22.597.669 | 21.072.287 | 11.629.500 | 10.204.500 | 11.627.840 | 10.208.116 |
27 | 134.217.728 | 87.565.950 | 45.241.445 | 42.324.505 | 23.260.254 | 20.523.480 | 23.260.613 | 20.521.603 |
28 | 268.435.456 | 175.545.238 | 90.573.205 | 84.972.033 | 46.521.564 | 41.243.674 | 46.532.324 | 41.247.676 |
29 | 536.870.912 | 351.852.491 | 181.330.633 | 170.521.858 | 93.052.942 | 82.868.259 | 93.070.368 | 82.860.922 |
30 | 1.073.741.824 | 705.149.390 | 363.017.852 | 342.131.538 | 186.122.714 | 166.454.478 | 186.148.421 | 166.423.777 |
31 | 2.147.483.648 | 1.412.975.378 | 726.683.429 | 686.291.949 | 372.290.940 | 334.207.926 | 372.309.525 | 334.166.987 |
32 | 4.294.967.296 | 2.830.916.636 | 1.454.495.227 | 1.376.421.409 | 744.621.289 | 670.859.735 | 744.653.990 | 670.781.622 |
33 | 8.589.934.592 | 5.671.129.005 | 2.911.092.374 | 2.760.036.631 | 1.489.326.448 | 1.346.270.202 | 1.489.329.116 | 1.346.203.239 |
34 | 17.179.869.184 | 11.359.637.523 | 5.826.163.781 | 5.533.473.742 | 2.978.752.180 | 2.701.081.169 | 2.978.739.351 | 2.701.064.823 |