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+3x-23
f(0)=23
f(1)=19
f(2)=13
f(3)=5
f(4)=1
f(5)=17
f(6)=31
f(7)=47
f(8)=1
f(9)=1
f(10)=107
f(11)=131
f(12)=157
f(13)=37
f(14)=43
f(15)=1
f(16)=281
f(17)=317
f(18)=71
f(19)=79
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=677
f(26)=1
f(27)=787
f(28)=1
f(29)=181
f(30)=967
f(31)=1031
f(32)=1097
f(33)=233
f(34)=1
f(35)=1307
f(36)=1381
f(37)=1
f(38)=307
f(39)=1
f(40)=1697
f(41)=137
f(42)=1867
f(43)=1
f(44)=409
f(45)=2137
f(46)=97
f(47)=179
f(48)=1
f(49)=101
f(50)=1
f(51)=2731
f(52)=2837
f(53)=1
f(54)=1
f(55)=3167
f(56)=193
f(57)=1
f(58)=1
f(59)=727
f(60)=1
f(61)=3881
f(62)=4007
f(63)=827
f(64)=853
f(65)=4397
f(66)=197
f(67)=359
f(68)=1
f(69)=1
f(70)=5087
f(71)=5231
f(72)=283
f(73)=1
f(74)=227
f(75)=5827
f(76)=5981
f(77)=1
f(78)=1259
f(79)=1291
f(80)=509
f(81)=6781
f(82)=6947
f(83)=1423
f(84)=1
f(85)=7457
f(86)=587
f(87)=211
f(88)=1597
f(89)=1
f(90)=491
f(91)=449
f(92)=379
f(93)=1
f(94)=1
f(95)=251
f(96)=499
f(97)=9677
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+3x-23 could be written as f(y)= y^2-25.25 with x=y-1.5
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+1.5
f'(x)>2x+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 | 7 | 7 | 0 | 0.700000 | 0.700000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 68 | 36 | 32 | 0.680000 | 0.360000 | 0.320000 | 9.714286 | 5.142857 | inf |
3 | 1.000 | 709 | 207 | 502 | 0.709000 | 0.207000 | 0.502000 | 10.426471 | 5.750000 | 15.687500 |
4 | 10.000 | 7.087 | 1.493 | 5.594 | 0.708700 | 0.149300 | 0.559400 | 9.995769 | 7.212560 | 11.143426 |
5 | 100.000 | 70.698 | 11.516 | 59.182 | 0.706980 | 0.115160 | 0.591820 | 9.975730 | 7.713329 | 10.579550 |
6 | 1.000.000 | 704.622 | 94.228 | 610.394 | 0.704622 | 0.094228 | 0.610394 | 9.966647 | 8.182355 | 10.313846 |
7 | 10.000.000 | 7.027.775 | 794.378 | 6.233.397 | 0.702778 | 0.079438 | 0.623340 | 9.973823 | 8.430382 | 10.212088 |
8 | 100.000.000 | 70.135.477 | 6.882.086 | 63.253.391 | 0.701355 | 0.068821 | 0.632534 | 9.979756 | 8.663490 | 10.147499 |
9 | 1.000.000.000 | 700.304.705 | 60.717.232 | 639.587.473 | 0.700305 | 0.060717 | 0.639587 | 9.985027 | 8.822504 | 10.111512 |
10 | 10.000.000.000 | 6.994.787.892 | 543.358.095 | 6.451.429.797 | 0.699479 | 0.054336 | 0.645143 | 9.988206 | 8.948993 | 10.086862 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 3 | 0 | 0.750000 | 0.750000 | 0.000000 | 1.000000 | 1.000000 | -nan |
3 | 8 | 6 | 6 | 0 | 0.750000 | 0.750000 | 0.000000 | 2.000000 | 2.000000 | -nan |
4 | 16 | 12 | 10 | 2 | 0.750000 | 0.625000 | 0.125000 | 2.000000 | 1.666667 | inf |
5 | 32 | 21 | 16 | 5 | 0.656250 | 0.500000 | 0.156250 | 1.750000 | 1.600000 | 2.500000 |
6 | 64 | 42 | 27 | 15 | 0.656250 | 0.421875 | 0.234375 | 2.000000 | 1.687500 | 3.000000 |
7 | 128 | 89 | 43 | 46 | 0.695312 | 0.335938 | 0.359375 | 2.119048 | 1.592593 | 3.066667 |
8 | 256 | 180 | 70 | 110 | 0.703125 | 0.273438 | 0.429688 | 2.022472 | 1.627907 | 2.391304 |
9 | 512 | 366 | 126 | 240 | 0.714844 | 0.246094 | 0.468750 | 2.033333 | 1.800000 | 2.181818 |
10 | 1.024 | 727 | 211 | 516 | 0.709961 | 0.206055 | 0.503906 | 1.986339 | 1.674603 | 2.150000 |
11 | 2.048 | 1.464 | 384 | 1.080 | 0.714844 | 0.187500 | 0.527344 | 2.013755 | 1.819905 | 2.093023 |
12 | 4.096 | 2.917 | 686 | 2.231 | 0.712158 | 0.167480 | 0.544678 | 1.992486 | 1.786458 | 2.065741 |
13 | 8.192 | 5.811 | 1.244 | 4.567 | 0.709351 | 0.151855 | 0.557495 | 1.992115 | 1.813411 | 2.047064 |
14 | 16.384 | 11.600 | 2.285 | 9.315 | 0.708008 | 0.139465 | 0.568542 | 1.996214 | 1.836817 | 2.039632 |
15 | 32.768 | 23.217 | 4.238 | 18.979 | 0.708527 | 0.129333 | 0.579193 | 2.001466 | 1.854705 | 2.037467 |
16 | 65.536 | 46.335 | 7.897 | 38.438 | 0.707016 | 0.120499 | 0.586517 | 1.995736 | 1.863379 | 2.025291 |
17 | 131.072 | 92.630 | 14.747 | 77.883 | 0.706711 | 0.112511 | 0.594200 | 1.999137 | 1.867418 | 2.026198 |
18 | 262.144 | 185.169 | 27.732 | 157.437 | 0.706364 | 0.105789 | 0.600574 | 1.999018 | 1.880518 | 2.021455 |
19 | 524.288 | 369.784 | 52.065 | 317.719 | 0.705307 | 0.099306 | 0.606001 | 1.997008 | 1.877434 | 2.018071 |
20 | 1.048.576 | 738.856 | 98.413 | 640.443 | 0.704628 | 0.093854 | 0.610774 | 1.998075 | 1.890195 | 2.015753 |
21 | 2.097.152 | 1.476.375 | 186.154 | 1.290.221 | 0.703990 | 0.088765 | 0.615225 | 1.998190 | 1.891559 | 2.014576 |
22 | 4.194.304 | 2.950.088 | 353.923 | 2.596.165 | 0.703356 | 0.084382 | 0.618974 | 1.998197 | 1.901238 | 2.012186 |
23 | 8.388.608 | 5.896.321 | 674.116 | 5.222.205 | 0.702896 | 0.080361 | 0.622535 | 1.998693 | 1.904697 | 2.011507 |
24 | 16.777.216 | 11.784.125 | 1.288.595 | 10.495.530 | 0.702389 | 0.076806 | 0.625582 | 1.998556 | 1.911533 | 2.009789 |
25 | 33.554.432 | 23.553.441 | 2.466.837 | 21.086.604 | 0.701947 | 0.073517 | 0.628430 | 1.998743 | 1.914362 | 2.009103 |
26 | 67.108.864 | 47.082.437 | 4.727.373 | 42.355.064 | 0.701583 | 0.070443 | 0.631140 | 1.998962 | 1.916370 | 2.008624 |
27 | 134.217.728 | 94.115.195 | 9.081.137 | 85.034.058 | 0.701213 | 0.067660 | 0.633553 | 1.998945 | 1.920969 | 2.007648 |
28 | 268.435.456 | 188.139.967 | 17.469.025 | 170.670.942 | 0.700876 | 0.065077 | 0.635799 | 1.999039 | 1.923660 | 2.007089 |
29 | 536.870.912 | 376.111.774 | 33.666.448 | 342.445.326 | 0.700563 | 0.062709 | 0.637854 | 1.999106 | 1.927208 | 2.006465 |
30 | 1.073.741.824 | 751.914.145 | 64.959.380 | 686.954.765 | 0.700275 | 0.060498 | 0.639776 | 1.999177 | 1.929499 | 2.006028 |
31 | 2.147.483.648 | 1.503.255.144 | 125.501.557 | 1.377.753.587 | 0.700008 | 0.058441 | 0.641567 | 1.999238 | 1.932001 | 2.005596 |
32 | 4.294.967.296 | 3.005.432.931 | 242.739.115 | 2.762.693.816 | 0.699757 | 0.056517 | 0.643240 | 1.999283 | 1.934152 | 2.005216 |
33 | 8.589.934.592 | 6.008.878.563 | 470.003.885 | 5.538.874.678 | 0.699526 | 0.054716 | 0.644810 | 1.999339 | 1.936251 | 2.004882 |
34 | 17.179.869.184 | 12.014.108.476 | 910.981.606 | 11.103.126.870 | 0.699313 | 0.053026 | 0.646287 | 1.999393 | 1.938243 | 2.004582 |
35 | 34.359.738.368 | 24.021.323.350 | 1.767.388.620 | 22.253.934.730 | 0.699113 | 0.051438 | 0.647675 | 1.999426 | 1.940093 | 2.004294 |
36 | 68.719.476.736 | 48.029.684.208 | 3.432.041.673 | 44.597.642.535 | 0.698924 | 0.049943 | 0.648981 | 1.999460 | 1.941872 | 2.004034 |
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 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
2 | 4 | 3 | 2 | 1 | 0 | 1 | 1 | 1 |
3 | 8 | 6 | 3 | 3 | 1 | 1 | 1 | 3 |
4 | 16 | 10 | 4 | 6 | 2 | 3 | 2 | 3 |
5 | 32 | 16 | 6 | 10 | 3 | 4 | 4 | 5 |
6 | 64 | 27 | 10 | 17 | 6 | 7 | 7 | 7 |
7 | 128 | 43 | 16 | 27 | 8 | 10 | 13 | 12 |
8 | 256 | 70 | 24 | 46 | 17 | 15 | 22 | 16 |
9 | 512 | 126 | 42 | 84 | 30 | 30 | 35 | 31 |
10 | 1.024 | 211 | 72 | 139 | 48 | 54 | 58 | 51 |
11 | 2.048 | 384 | 130 | 254 | 83 | 101 | 100 | 100 |
12 | 4.096 | 686 | 231 | 455 | 164 | 176 | 179 | 167 |
13 | 8.192 | 1.244 | 427 | 817 | 314 | 316 | 315 | 299 |
14 | 16.384 | 2.285 | 768 | 1.517 | 590 | 571 | 569 | 555 |
15 | 32.768 | 4.238 | 1.427 | 2.811 | 1.085 | 1.058 | 1.048 | 1.047 |
16 | 65.536 | 7.897 | 2.638 | 5.259 | 2.002 | 1.981 | 1.957 | 1.957 |
17 | 131.072 | 14.747 | 4.930 | 9.817 | 3.685 | 3.677 | 3.726 | 3.659 |
18 | 262.144 | 27.732 | 9.224 | 18.508 | 6.942 | 6.903 | 6.958 | 6.929 |
19 | 524.288 | 52.065 | 17.401 | 34.664 | 13.050 | 12.960 | 13.034 | 13.021 |
20 | 1.048.576 | 98.413 | 32.941 | 65.472 | 24.661 | 24.483 | 24.709 | 24.560 |
21 | 2.097.152 | 186.154 | 62.046 | 124.108 | 46.623 | 46.464 | 46.706 | 46.361 |
22 | 4.194.304 | 353.923 | 118.076 | 235.847 | 88.466 | 88.417 | 88.871 | 88.169 |
23 | 8.388.608 | 674.116 | 224.786 | 449.330 | 168.529 | 168.426 | 168.955 | 168.206 |
24 | 16.777.216 | 1.288.595 | 429.602 | 858.993 | 322.292 | 322.065 | 322.669 | 321.569 |
25 | 33.554.432 | 2.466.837 | 822.754 | 1.644.083 | 617.152 | 616.836 | 616.896 | 615.953 |
26 | 67.108.864 | 4.727.373 | 1.576.037 | 3.151.336 | 1.182.826 | 1.181.836 | 1.181.355 | 1.181.356 |
27 | 134.217.728 | 9.081.137 | 3.027.750 | 6.053.387 | 2.271.717 | 2.270.764 | 2.269.102 | 2.269.554 |
28 | 268.435.456 | 17.469.025 | 5.823.064 | 11.645.961 | 4.367.886 | 4.370.275 | 4.365.473 | 4.365.391 |
29 | 536.870.912 | 33.666.448 | 11.222.902 | 22.443.546 | 8.417.137 | 8.417.623 | 8.415.176 | 8.416.512 |
30 | 1.073.741.824 | 64.959.380 | 21.651.324 | 43.308.056 | 16.240.154 | 16.238.814 | 16.241.017 | 16.239.395 |
31 | 2.147.483.648 | 125.501.557 | 41.829.688 | 83.671.869 | 31.378.072 | 31.374.193 | 31.378.259 | 31.371.033 |
32 | 4.294.967.296 | 242.739.115 | 80.911.309 | 161.827.806 | 60.687.958 | 60.681.988 | 60.690.012 | 60.679.157 |
33 | 8.589.934.592 | 470.003.885 | 156.663.259 | 313.340.626 | 117.496.596 | 117.500.336 | 117.506.970 | 117.499.983 |
34 | 17.179.869.184 | 910.981.606 | 303.665.073 | 607.316.533 | 227.746.802 | 227.739.630 | 227.753.152 | 227.742.022 |
35 | 34.359.738.368 | 1.767.388.620 | 589.129.355 | 1.178.259.265 | 441.843.240 | 441.834.049 | 441.866.898 | 441.844.433 |
36 | 68.719.476.736 | 3.432.041.673 | 1.143.999.301 | 2.288.042.372 | 858.006.499 | 858.011.074 | 858.024.526 | 857.999.574 |
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 | 2 | 2 | 0 | 0 | 1 | 1 | 0 |
5 | 32 | 5 | 4 | 1 | 0 | 1 | 2 | 2 |
6 | 64 | 15 | 10 | 5 | 5 | 4 | 3 | 3 |
7 | 128 | 46 | 25 | 21 | 8 | 18 | 10 | 10 |
8 | 256 | 110 | 54 | 56 | 23 | 31 | 26 | 30 |
9 | 512 | 240 | 122 | 118 | 55 | 58 | 67 | 60 |
10 | 1.024 | 516 | 266 | 250 | 122 | 127 | 138 | 129 |
11 | 2.048 | 1.080 | 563 | 517 | 260 | 286 | 284 | 250 |
12 | 4.096 | 2.231 | 1.156 | 1.075 | 554 | 569 | 568 | 540 |
13 | 8.192 | 4.567 | 2.353 | 2.214 | 1.095 | 1.185 | 1.145 | 1.142 |
14 | 16.384 | 9.315 | 4.792 | 4.523 | 2.295 | 2.335 | 2.328 | 2.357 |
15 | 32.768 | 18.979 | 9.702 | 9.277 | 4.677 | 4.778 | 4.723 | 4.801 |
16 | 65.536 | 38.438 | 19.670 | 18.768 | 9.498 | 9.653 | 9.663 | 9.624 |
17 | 131.072 | 77.883 | 39.852 | 38.031 | 19.316 | 19.509 | 19.672 | 19.386 |
18 | 262.144 | 157.437 | 80.414 | 77.023 | 39.180 | 39.483 | 39.538 | 39.236 |
19 | 524.288 | 317.719 | 161.984 | 155.735 | 79.335 | 79.533 | 79.610 | 79.241 |
20 | 1.048.576 | 640.443 | 326.179 | 314.264 | 160.041 | 160.098 | 160.277 | 160.027 |
21 | 2.097.152 | 1.290.221 | 657.021 | 633.200 | 322.900 | 322.713 | 322.503 | 322.105 |
22 | 4.194.304 | 2.596.165 | 1.321.076 | 1.275.089 | 649.175 | 648.995 | 649.024 | 648.971 |
23 | 8.388.608 | 5.222.205 | 2.654.513 | 2.567.692 | 1.306.353 | 1.304.953 | 1.305.103 | 1.305.796 |
24 | 16.777.216 | 10.495.530 | 5.333.779 | 5.161.751 | 2.623.427 | 2.623.372 | 2.624.228 | 2.624.503 |
25 | 33.554.432 | 21.086.604 | 10.704.949 | 10.381.655 | 5.271.344 | 5.271.583 | 5.270.722 | 5.272.955 |
26 | 67.108.864 | 42.355.064 | 21.485.960 | 20.869.104 | 10.589.359 | 10.587.840 | 10.585.413 | 10.592.452 |
27 | 134.217.728 | 85.034.058 | 43.104.936 | 41.929.122 | 21.259.296 | 21.260.963 | 21.252.906 | 21.260.893 |
28 | 268.435.456 | 170.670.942 | 86.463.430 | 84.207.512 | 42.667.030 | 42.672.470 | 42.660.915 | 42.670.527 |
29 | 536.870.912 | 342.445.326 | 173.396.923 | 169.048.403 | 85.612.497 | 85.617.098 | 85.599.908 | 85.615.823 |
30 | 1.073.741.824 | 686.954.765 | 347.681.567 | 339.273.198 | 171.737.120 | 171.753.542 | 171.725.508 | 171.738.595 |
31 | 2.147.483.648 | 1.377.753.587 | 696.973.355 | 680.780.232 | 344.449.292 | 344.460.640 | 344.412.430 | 344.431.225 |
32 | 4.294.967.296 | 2.762.693.816 | 1.396.984.756 | 1.365.709.060 | 690.684.003 | 690.693.603 | 690.645.477 | 690.670.733 |
33 | 8.589.934.592 | 5.538.874.678 | 2.799.653.275 | 2.739.221.403 | 1.384.731.279 | 1.384.738.431 | 1.384.681.869 | 1.384.723.099 |
34 | 17.179.869.184 | 11.103.126.870 | 5.610.041.749 | 5.493.085.121 | 2.775.766.222 | 2.775.867.196 | 2.775.710.836 | 2.775.782.616 |
35 | 34.359.738.368 | 22.253.934.730 | 11.240.344.224 | 11.013.590.506 | 5.563.500.390 | 5.563.560.241 | 5.563.410.552 | 5.563.463.547 |
36 | 68.719.476.736 | 44.597.642.535 | 22.518.833.910 | 22.078.808.625 | 11.149.519.252 | 11.149.423.210 | 11.149.350.477 | 11.149.349.596 |