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+70x-3
f(0)=3
f(1)=17
f(2)=47
f(3)=1
f(4)=293
f(5)=31
f(6)=151
f(7)=67
f(8)=23
f(9)=59
f(10)=797
f(11)=37
f(12)=109
f(13)=269
f(14)=1
f(15)=53
f(16)=1373
f(17)=41
f(18)=1
f(19)=211
f(20)=599
f(21)=1
f(22)=43
f(23)=89
f(24)=751
f(25)=593
f(26)=277
f(27)=1
f(28)=2741
f(29)=239
f(30)=1
f(31)=1
f(32)=1087
f(33)=283
f(34)=3533
f(35)=1
f(36)=1
f(37)=1
f(38)=1367
f(39)=1
f(40)=4397
f(41)=379
f(42)=1567
f(43)=607
f(44)=557
f(45)=431
f(46)=5333
f(47)=229
f(48)=1
f(49)=1
f(50)=1999
f(51)=257
f(52)=373
f(53)=181
f(54)=97
f(55)=859
f(56)=2351
f(57)=1
f(58)=1
f(59)=317
f(60)=113
f(61)=1997
f(62)=101
f(63)=349
f(64)=8573
f(65)=1
f(66)=997
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=139
f(72)=3407
f(73)=2609
f(74)=1
f(75)=1
f(76)=11093
f(77)=1
f(78)=3847
f(79)=1471
f(80)=1
f(81)=1019
f(82)=733
f(83)=1
f(84)=479
f(85)=1
f(86)=263
f(87)=569
f(88)=13901
f(89)=131
f(90)=4799
f(91)=1831
f(92)=4967
f(93)=421
f(94)=15413
f(95)=653
f(96)=1
f(97)=4049
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+70x-3 could be written as f(y)= y^2-1228 with x=y-35
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+35
f'(x)>2x+69
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 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 66 | 24 | 42 | 0.660000 | 0.240000 | 0.420000 | 6.600000 | 4.800000 | 8.400000 |
3 | 1.000 | 620 | 129 | 491 | 0.620000 | 0.129000 | 0.491000 | 9.393939 | 5.375000 | 11.690476 |
4 | 10.000 | 6.472 | 953 | 5.519 | 0.647200 | 0.095300 | 0.551900 | 10.438709 | 7.387597 | 11.240326 |
5 | 100.000 | 65.745 | 7.435 | 58.310 | 0.657450 | 0.074350 | 0.583100 | 10.158375 | 7.801679 | 10.565320 |
6 | 1.000.000 | 663.289 | 60.536 | 602.753 | 0.663289 | 0.060536 | 0.602753 | 10.088813 | 8.142031 | 10.337044 |
7 | 10.000.000 | 6.676.836 | 508.843 | 6.167.993 | 0.667684 | 0.050884 | 0.616799 | 10.066255 | 8.405626 | 10.233036 |
8 | 100.000.000 | 67.088.386 | 4.388.066 | 62.700.320 | 0.670884 | 0.043881 | 0.627003 | 10.047931 | 8.623614 | 10.165433 |
9 | 1.000.000.000 | 673.349.980 | 38.603.049 | 634.746.931 | 0.673350 | 0.038603 | 0.634747 | 10.036759 | 8.797280 | 10.123504 |
10 | 10.000.000.000 | 6.753.181.496 | 344.607.411 | 6.408.574.085 | 0.675318 | 0.034461 | 0.640857 | 10.029230 | 8.926949 | 10.096266 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 1.333333 | 4.000000 |
4 | 16 | 15 | 7 | 8 | 0.937500 | 0.437500 | 0.500000 | 1.875000 | 1.750000 | 2.000000 |
5 | 32 | 25 | 10 | 15 | 0.781250 | 0.312500 | 0.468750 | 1.666667 | 1.428571 | 1.875000 |
6 | 64 | 46 | 17 | 29 | 0.718750 | 0.265625 | 0.453125 | 1.840000 | 1.700000 | 1.933333 |
7 | 128 | 82 | 26 | 56 | 0.640625 | 0.203125 | 0.437500 | 1.782609 | 1.529412 | 1.931034 |
8 | 256 | 162 | 43 | 119 | 0.632812 | 0.167969 | 0.464844 | 1.975610 | 1.653846 | 2.125000 |
9 | 512 | 319 | 74 | 245 | 0.623047 | 0.144531 | 0.478516 | 1.969136 | 1.720930 | 2.058824 |
10 | 1.024 | 639 | 131 | 508 | 0.624023 | 0.127930 | 0.496094 | 2.003135 | 1.770270 | 2.073469 |
11 | 2.048 | 1.296 | 236 | 1.060 | 0.632812 | 0.115234 | 0.517578 | 2.028169 | 1.801527 | 2.086614 |
12 | 4.096 | 2.623 | 434 | 2.189 | 0.640381 | 0.105957 | 0.534424 | 2.023920 | 1.838983 | 2.065094 |
13 | 8.192 | 5.284 | 800 | 4.484 | 0.645020 | 0.097656 | 0.547363 | 2.014487 | 1.843318 | 2.048424 |
14 | 16.384 | 10.657 | 1.443 | 9.214 | 0.650452 | 0.088074 | 0.562378 | 2.016843 | 1.803750 | 2.054862 |
15 | 32.768 | 21.448 | 2.691 | 18.757 | 0.654541 | 0.082123 | 0.572418 | 2.012574 | 1.864865 | 2.035707 |
16 | 65.536 | 43.024 | 5.058 | 37.966 | 0.656494 | 0.077179 | 0.579315 | 2.005968 | 1.879599 | 2.024098 |
17 | 131.072 | 86.323 | 9.518 | 76.805 | 0.658592 | 0.072617 | 0.585976 | 2.006392 | 1.881771 | 2.022994 |
18 | 262.144 | 173.054 | 17.843 | 155.211 | 0.660149 | 0.068066 | 0.592083 | 2.004726 | 1.874659 | 2.020845 |
19 | 524.288 | 347.057 | 33.552 | 313.505 | 0.661959 | 0.063995 | 0.597963 | 2.005484 | 1.880401 | 2.019863 |
20 | 1.048.576 | 695.714 | 63.207 | 632.507 | 0.663485 | 0.060279 | 0.603206 | 2.004610 | 1.883852 | 2.017534 |
21 | 2.097.152 | 1.394.450 | 119.648 | 1.274.802 | 0.664926 | 0.057053 | 0.607873 | 2.004344 | 1.892955 | 2.015475 |
22 | 4.194.304 | 2.794.320 | 227.020 | 2.567.300 | 0.666218 | 0.054126 | 0.612092 | 2.003887 | 1.897399 | 2.013881 |
23 | 8.388.608 | 5.598.316 | 432.084 | 5.166.232 | 0.667371 | 0.051508 | 0.615863 | 2.003463 | 1.903286 | 2.012321 |
24 | 16.777.216 | 11.214.855 | 823.579 | 10.391.276 | 0.668457 | 0.049089 | 0.619368 | 2.003255 | 1.906062 | 2.011384 |
25 | 33.554.432 | 22.464.154 | 1.574.347 | 20.889.807 | 0.669484 | 0.046919 | 0.622565 | 2.003071 | 1.911592 | 2.010322 |
26 | 67.108.864 | 44.989.310 | 3.016.862 | 41.972.448 | 0.670393 | 0.044955 | 0.625438 | 2.002716 | 1.916262 | 2.009231 |
27 | 134.217.728 | 90.091.515 | 5.788.839 | 84.302.676 | 0.671234 | 0.043130 | 0.628104 | 2.002509 | 1.918828 | 2.008524 |
28 | 268.435.456 | 180.393.880 | 11.127.721 | 169.266.159 | 0.672020 | 0.041454 | 0.630566 | 2.002341 | 1.922272 | 2.007839 |
29 | 536.870.912 | 361.174.324 | 21.421.437 | 339.752.887 | 0.672740 | 0.039901 | 0.632839 | 2.002143 | 1.925051 | 2.007211 |
30 | 1.073.741.824 | 723.073.934 | 41.296.657 | 681.777.277 | 0.673415 | 0.038461 | 0.634955 | 2.002008 | 1.927819 | 2.006686 |
31 | 2.147.483.648 | 1.447.514.501 | 79.714.837 | 1.367.799.664 | 0.674051 | 0.037120 | 0.636931 | 2.001890 | 1.930298 | 2.006227 |
32 | 4.294.967.296 | 2.897.573.849 | 154.072.681 | 2.743.501.168 | 0.674644 | 0.035873 | 0.638771 | 2.001758 | 1.932798 | 2.005777 |
33 | 8.589.934.592 | 5.799.927.588 | 298.133.890 | 5.501.793.698 | 0.675200 | 0.034707 | 0.640493 | 2.001650 | 1.935021 | 2.005392 |
34 | 17.179.869.184 | 11.608.900.013 | 577.479.093 | 11.031.420.920 | 0.675727 | 0.033614 | 0.642113 | 2.001559 | 1.936979 | 2.005059 |
35 | 34.359.738.368 | 23.234.809.698 | 1.119.690.490 | 22.115.119.208 | 0.676222 | 0.032587 | 0.643635 | 2.001465 | 1.938928 | 2.004739 |
36 | 68.719.476.736 | 46.501.773.366 | 2.173.072.994 | 44.328.700.372 | 0.676690 | 0.031622 | 0.645068 | 2.001384 | 1.940780 | 2.004452 |
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 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 1 | 2 | 1 | 0 |
4 | 16 | 7 | 1 | 5 | 1 | 2 | 4 | 0 |
5 | 32 | 10 | 2 | 7 | 2 | 3 | 5 | 0 |
6 | 64 | 17 | 4 | 12 | 2 | 4 | 10 | 1 |
7 | 128 | 26 | 7 | 18 | 4 | 5 | 14 | 3 |
8 | 256 | 43 | 13 | 29 | 7 | 8 | 22 | 6 |
9 | 512 | 74 | 24 | 49 | 11 | 14 | 38 | 11 |
10 | 1.024 | 131 | 41 | 89 | 17 | 25 | 72 | 17 |
11 | 2.048 | 236 | 69 | 166 | 30 | 38 | 136 | 32 |
12 | 4.096 | 434 | 116 | 317 | 53 | 63 | 264 | 54 |
13 | 8.192 | 800 | 222 | 577 | 107 | 116 | 470 | 107 |
14 | 16.384 | 1.443 | 376 | 1.066 | 181 | 190 | 885 | 187 |
15 | 32.768 | 2.691 | 724 | 1.966 | 347 | 363 | 1.619 | 362 |
16 | 65.536 | 5.058 | 1.352 | 3.705 | 648 | 670 | 3.057 | 683 |
17 | 131.072 | 9.518 | 2.542 | 6.975 | 1.235 | 1.280 | 5.740 | 1.263 |
18 | 262.144 | 17.843 | 4.702 | 13.140 | 2.278 | 2.354 | 10.862 | 2.349 |
19 | 524.288 | 33.552 | 8.833 | 24.718 | 4.254 | 4.425 | 20.464 | 4.409 |
20 | 1.048.576 | 63.207 | 16.514 | 46.692 | 8.080 | 8.295 | 38.612 | 8.220 |
21 | 2.097.152 | 119.648 | 31.240 | 88.407 | 15.303 | 15.640 | 73.104 | 15.601 |
22 | 4.194.304 | 227.020 | 59.238 | 167.781 | 29.028 | 29.615 | 138.753 | 29.624 |
23 | 8.388.608 | 432.084 | 112.597 | 319.486 | 54.969 | 56.383 | 264.517 | 56.215 |
24 | 16.777.216 | 823.579 | 214.416 | 609.162 | 104.568 | 107.336 | 504.594 | 107.081 |
25 | 33.554.432 | 1.574.347 | 409.262 | 1.165.084 | 199.993 | 204.652 | 965.091 | 204.611 |
26 | 67.108.864 | 3.016.862 | 783.276 | 2.233.585 | 383.122 | 391.782 | 1.850.463 | 391.495 |
27 | 134.217.728 | 5.788.839 | 1.499.969 | 4.288.869 | 734.233 | 750.835 | 3.554.636 | 749.135 |
28 | 268.435.456 | 11.127.721 | 2.879.642 | 8.248.078 | 1.410.560 | 1.440.853 | 6.837.518 | 1.438.790 |
29 | 536.870.912 | 21.421.437 | 5.534.507 | 15.886.929 | 2.713.773 | 2.767.819 | 13.173.156 | 2.766.689 |
30 | 1.073.741.824 | 41.296.657 | 10.655.826 | 30.640.830 | 5.230.540 | 5.328.251 | 25.410.290 | 5.327.576 |
31 | 2.147.483.648 | 79.714.837 | 20.545.479 | 59.169.357 | 10.091.514 | 10.272.202 | 49.077.843 | 10.273.278 |
32 | 4.294.967.296 | 154.072.681 | 39.670.140 | 114.402.540 | 19.496.032 | 19.835.253 | 94.906.508 | 19.834.888 |
33 | 8.589.934.592 | 298.133.890 | 76.682.517 | 221.451.372 | 37.709.394 | 38.342.726 | 183.741.978 | 38.339.792 |
34 | 17.179.869.184 | 577.479.093 | 148.395.604 | 429.083.488 | 73.013.522 | 74.203.675 | 356.069.966 | 74.191.930 |
35 | 34.359.738.368 | 1.119.690.490 | 287.491.494 | 832.198.995 | 141.525.090 | 143.753.243 | 690.673.905 | 143.738.252 |
36 | 68.719.476.736 | 2.173.072.994 | 557.497.983 | 1.615.575.010 | 274.592.120 | 278.754.088 | 1.340.982.890 | 278.743.896 |
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 | 0 | 1 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 0 | 0 | 0 | 4 |
4 | 16 | 8 | 4 | 4 | 0 | 1 | 3 | 4 |
5 | 32 | 15 | 7 | 8 | 2 | 1 | 4 | 8 |
6 | 64 | 29 | 15 | 14 | 3 | 3 | 10 | 13 |
7 | 128 | 56 | 26 | 30 | 5 | 8 | 17 | 26 |
8 | 256 | 119 | 62 | 57 | 16 | 22 | 30 | 51 |
9 | 512 | 245 | 129 | 116 | 34 | 42 | 65 | 104 |
10 | 1.024 | 508 | 267 | 241 | 82 | 92 | 133 | 201 |
11 | 2.048 | 1.060 | 545 | 515 | 187 | 203 | 271 | 399 |
12 | 4.096 | 2.189 | 1.108 | 1.081 | 431 | 430 | 545 | 783 |
13 | 8.192 | 4.484 | 2.258 | 2.226 | 918 | 899 | 1.134 | 1.533 |
14 | 16.384 | 9.214 | 4.628 | 4.586 | 1.924 | 1.963 | 2.281 | 3.046 |
15 | 32.768 | 18.757 | 9.444 | 9.313 | 3.958 | 4.053 | 4.663 | 6.083 |
16 | 65.536 | 37.966 | 19.084 | 18.882 | 8.207 | 8.257 | 9.437 | 12.065 |
17 | 131.072 | 76.805 | 38.694 | 38.111 | 16.814 | 16.744 | 19.173 | 24.074 |
18 | 262.144 | 155.211 | 78.043 | 77.168 | 34.394 | 34.257 | 38.918 | 47.642 |
19 | 524.288 | 313.505 | 157.860 | 155.645 | 70.348 | 69.949 | 78.334 | 94.874 |
20 | 1.048.576 | 632.507 | 318.346 | 314.161 | 142.664 | 142.483 | 158.248 | 189.112 |
21 | 2.097.152 | 1.274.802 | 641.756 | 633.046 | 289.587 | 289.376 | 318.616 | 377.223 |
22 | 4.194.304 | 2.567.300 | 1.291.511 | 1.275.789 | 587.444 | 585.772 | 640.354 | 753.730 |
23 | 8.388.608 | 5.166.232 | 2.598.800 | 2.567.432 | 1.187.920 | 1.185.542 | 1.288.358 | 1.504.412 |
24 | 16.777.216 | 10.391.276 | 5.228.642 | 5.162.634 | 2.399.277 | 2.396.640 | 2.592.600 | 3.002.759 |
25 | 33.554.432 | 20.889.807 | 10.506.755 | 10.383.052 | 4.844.343 | 4.838.218 | 5.212.290 | 5.994.956 |
26 | 67.108.864 | 41.972.448 | 21.107.457 | 20.864.991 | 9.770.994 | 9.759.436 | 10.470.954 | 11.971.064 |
27 | 134.217.728 | 84.302.676 | 42.379.421 | 41.923.255 | 19.685.687 | 19.672.685 | 21.032.336 | 23.911.968 |
28 | 268.435.456 | 169.266.159 | 85.068.014 | 84.198.145 | 39.644.403 | 39.611.935 | 42.240.240 | 47.769.581 |
29 | 536.870.912 | 339.752.887 | 170.731.125 | 169.021.762 | 79.792.848 | 79.737.410 | 84.790.671 | 95.431.958 |
30 | 1.073.741.824 | 681.777.277 | 342.538.949 | 339.238.328 | 160.523.483 | 160.422.546 | 170.149.574 | 190.681.674 |
31 | 2.147.483.648 | 1.367.799.664 | 687.064.497 | 680.735.167 | 322.793.195 | 322.620.532 | 341.371.342 | 381.014.595 |
32 | 4.294.967.296 | 2.743.501.168 | 1.377.843.279 | 1.365.657.889 | 648.867.283 | 648.506.756 | 684.728.676 | 761.398.453 |
33 | 8.589.934.592 | 5.501.793.698 | 2.762.667.305 | 2.739.126.393 | 1.303.899.018 | 1.303.114.242 | 1.373.209.826 | 1.521.570.612 |
34 | 17.179.869.184 | 11.031.420.920 | 5.538.468.189 | 5.492.952.731 | 2.619.280.463 | 2.617.766.946 | 2.753.453.271 | 3.040.920.240 |
35 | 34.359.738.368 | 22.115.119.208 | 11.101.667.913 | 11.013.451.295 | 5.260.069.175 | 5.257.197.108 | 5.520.219.638 | 6.077.633.287 |
36 | 68.719.476.736 | 44.328.700.372 | 22.249.934.428 | 22.078.765.944 | 10.560.819.326 | 10.555.337.634 | 11.065.253.757 | 12.147.289.655 |