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+35x-17
f(0)=17
f(1)=19
f(2)=3
f(3)=97
f(4)=139
f(5)=61
f(6)=229
f(7)=277
f(8)=109
f(9)=379
f(10)=433
f(11)=163
f(12)=547
f(13)=607
f(14)=223
f(15)=733
f(16)=47
f(17)=1
f(18)=937
f(19)=1009
f(20)=1
f(21)=1
f(22)=1237
f(23)=439
f(24)=1399
f(25)=1483
f(26)=523
f(27)=1657
f(28)=1747
f(29)=613
f(30)=1933
f(31)=2029
f(32)=709
f(33)=131
f(34)=137
f(35)=811
f(36)=2539
f(37)=2647
f(38)=919
f(39)=151
f(40)=157
f(41)=1033
f(42)=3217
f(43)=71
f(44)=1153
f(45)=3583
f(46)=3709
f(47)=1279
f(48)=3967
f(49)=4099
f(50)=83
f(51)=257
f(52)=4507
f(53)=1549
f(54)=4789
f(55)=4933
f(56)=1693
f(57)=5227
f(58)=283
f(59)=1
f(60)=5683
f(61)=5839
f(62)=1999
f(63)=1
f(64)=89
f(65)=2161
f(66)=1
f(67)=401
f(68)=1
f(69)=7159
f(70)=7333
f(71)=2503
f(72)=7687
f(73)=7867
f(74)=2683
f(75)=8233
f(76)=8419
f(77)=1
f(78)=463
f(79)=101
f(80)=3061
f(81)=113
f(82)=1
f(83)=3259
f(84)=587
f(85)=599
f(86)=3463
f(87)=10597
f(88)=107
f(89)=3673
f(90)=239
f(91)=1
f(92)=3889
f(93)=11887
f(94)=12109
f(95)=4111
f(96)=661
f(97)=673
f(98)=4339
f(99)=13249
b) Substitution of the polynom
The polynom f(x)=x^2+35x-17 could be written as f(y)= y^2-323.25 with x=y-17.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+17.5
f'(x)>2x+34
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 | 11 | 9 | 2 | 1.100000 | 0.900000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 84 | 44 | 40 | 0.840000 | 0.440000 | 0.840000 | 7.636364 | 4.888889 | 20.000000 |
3 | 1.000 | 799 | 298 | 501 | 0.799000 | 0.298000 | 0.799000 | 9.511905 | 6.772727 | 12.525000 |
4 | 10.000 | 7.645 | 2.139 | 5.506 | 0.764500 | 0.213900 | 0.764500 | 9.568211 | 7.177852 | 10.990020 |
5 | 100.000 | 74.945 | 16.662 | 58.283 | 0.749450 | 0.166620 | 0.749450 | 9.803140 | 7.789621 | 10.585361 |
6 | 1.000.000 | 739.715 | 136.171 | 603.544 | 0.739715 | 0.136171 | 0.739715 | 9.870105 | 8.172548 | 10.355404 |
7 | 10.000.000 | 7.329.806 | 1.151.065 | 6.178.741 | 0.732981 | 0.115107 | 0.732981 | 9.908959 | 8.453085 | 10.237432 |
8 | 100.000.000 | 72.781.741 | 9.977.073 | 62.804.668 | 0.727817 | 0.099771 | 0.727817 | 9.929560 | 8.667688 | 10.164639 |
9 | 1.000.000.000 | 723.783.566 | 88.058.518 | 635.725.048 | 0.723784 | 0.088059 | 0.723784 | 9.944575 | 8.826088 | 10.122258 |
10 | 10.000.000.000 | 7.205.909.547 | 788.073.222 | 6.417.836.325 | 0.720591 | 0.078807 | 0.720591 | 9.955890 | 8.949426 | 10.095303 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 7 | 2 | 1.125000 | 0.875000 | 0.250000 | 1.800000 | 1.400000 | inf |
4 | 16 | 17 | 12 | 5 | 1.062500 | 0.750000 | 0.312500 | 1.888889 | 1.714286 | 2.500000 |
5 | 32 | 30 | 21 | 9 | 0.937500 | 0.656250 | 0.281250 | 1.764706 | 1.750000 | 1.800000 |
6 | 64 | 57 | 34 | 23 | 0.890625 | 0.531250 | 0.359375 | 1.900000 | 1.619048 | 2.555556 |
7 | 128 | 109 | 56 | 53 | 0.851562 | 0.437500 | 0.414062 | 1.912281 | 1.647059 | 2.304348 |
8 | 256 | 208 | 100 | 108 | 0.812500 | 0.390625 | 0.421875 | 1.908257 | 1.785714 | 2.037736 |
9 | 512 | 411 | 173 | 238 | 0.802734 | 0.337891 | 0.464844 | 1.975962 | 1.730000 | 2.203704 |
10 | 1.024 | 820 | 307 | 513 | 0.800781 | 0.299805 | 0.500977 | 1.995134 | 1.774567 | 2.155462 |
11 | 2.048 | 1.602 | 542 | 1.060 | 0.782227 | 0.264648 | 0.517578 | 1.953659 | 1.765472 | 2.066277 |
12 | 4.096 | 3.183 | 974 | 2.209 | 0.777100 | 0.237793 | 0.539307 | 1.986891 | 1.797048 | 2.083962 |
13 | 8.192 | 6.297 | 1.775 | 4.522 | 0.768677 | 0.216675 | 0.552002 | 1.978322 | 1.822382 | 2.047080 |
14 | 16.384 | 12.464 | 3.299 | 9.165 | 0.760742 | 0.201355 | 0.559387 | 1.979355 | 1.858592 | 2.026758 |
15 | 32.768 | 24.788 | 6.115 | 18.673 | 0.756470 | 0.186615 | 0.569855 | 1.988768 | 1.853592 | 2.037425 |
16 | 65.536 | 49.301 | 11.350 | 37.951 | 0.752274 | 0.173187 | 0.579086 | 1.988906 | 1.856092 | 2.032400 |
17 | 131.072 | 98.033 | 21.324 | 76.709 | 0.747932 | 0.162689 | 0.585243 | 1.988459 | 1.878767 | 2.021264 |
18 | 262.144 | 195.319 | 40.032 | 155.287 | 0.745083 | 0.152710 | 0.592373 | 1.992380 | 1.877321 | 2.024365 |
19 | 524.288 | 388.915 | 75.294 | 313.621 | 0.741796 | 0.143612 | 0.598185 | 1.991179 | 1.880845 | 2.019622 |
20 | 1.048.576 | 775.470 | 142.326 | 633.144 | 0.739546 | 0.135733 | 0.603813 | 1.993932 | 1.890270 | 2.018819 |
21 | 2.097.152 | 1.546.194 | 269.666 | 1.276.528 | 0.737283 | 0.128587 | 0.608696 | 1.993880 | 1.894706 | 2.016173 |
22 | 4.194.304 | 3.084.042 | 512.494 | 2.571.548 | 0.735293 | 0.122188 | 0.613105 | 1.994602 | 1.900477 | 2.014486 |
23 | 8.388.608 | 6.152.263 | 977.528 | 5.174.735 | 0.733407 | 0.116530 | 0.616876 | 1.994870 | 1.907394 | 2.012304 |
24 | 16.777.216 | 12.276.033 | 1.865.577 | 10.410.456 | 0.731709 | 0.111197 | 0.620512 | 1.995369 | 1.908464 | 2.011785 |
25 | 33.554.432 | 24.498.053 | 3.572.357 | 20.925.696 | 0.730099 | 0.106465 | 0.623634 | 1.995600 | 1.914881 | 2.010065 |
26 | 67.108.864 | 48.895.520 | 6.853.934 | 42.041.586 | 0.728600 | 0.102132 | 0.626468 | 1.995894 | 1.918603 | 2.009089 |
27 | 134.217.728 | 97.606.331 | 13.169.466 | 84.436.865 | 0.727224 | 0.098120 | 0.629104 | 1.996222 | 1.921446 | 2.008413 |
28 | 268.435.456 | 194.873.457 | 25.338.957 | 169.534.500 | 0.725960 | 0.094395 | 0.631565 | 1.996525 | 1.924069 | 2.007826 |
29 | 536.870.912 | 389.111.529 | 48.825.532 | 340.285.997 | 0.724777 | 0.090945 | 0.633832 | 1.996740 | 1.926896 | 2.007179 |
30 | 1.073.741.824 | 777.040.499 | 94.209.185 | 682.831.314 | 0.723675 | 0.087739 | 0.635936 | 1.996961 | 1.929507 | 2.006639 |
31 | 2.147.483.648 | 1.551.872.227 | 182.004.509 | 1.369.867.718 | 0.722647 | 0.084752 | 0.637894 | 1.997157 | 1.931919 | 2.006158 |
32 | 4.294.967.296 | 3.099.605.866 | 352.033.930 | 2.747.571.936 | 0.721683 | 0.081964 | 0.639719 | 1.997333 | 1.934204 | 2.005721 |
33 | 8.589.934.592 | 6.191.465.407 | 681.675.801 | 5.509.789.606 | 0.720781 | 0.079358 | 0.641424 | 1.997501 | 1.936392 | 2.005330 |
34 | 17.179.869.184 | 12.368.365.308 | 1.321.320.687 | 11.047.044.621 | 0.719934 | 0.076911 | 0.643023 | 1.997648 | 1.938342 | 2.004985 |
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 | 1 | 1 | 2 | 1 | 0 | 0 |
2 | 4 | 5 | 3 | 1 | 3 | 2 | 0 | 0 |
3 | 8 | 7 | 5 | 1 | 3 | 2 | 2 | 0 |
4 | 16 | 12 | 10 | 1 | 4 | 4 | 3 | 1 |
5 | 32 | 21 | 19 | 1 | 7 | 6 | 6 | 2 |
6 | 64 | 34 | 32 | 1 | 8 | 11 | 9 | 6 |
7 | 128 | 56 | 54 | 1 | 12 | 17 | 15 | 12 |
8 | 256 | 100 | 98 | 1 | 23 | 29 | 27 | 21 |
9 | 512 | 173 | 171 | 1 | 41 | 47 | 45 | 40 |
10 | 1.024 | 307 | 305 | 1 | 75 | 80 | 80 | 72 |
11 | 2.048 | 542 | 540 | 1 | 131 | 136 | 147 | 128 |
12 | 4.096 | 974 | 972 | 1 | 235 | 255 | 248 | 236 |
13 | 8.192 | 1.775 | 1.773 | 1 | 442 | 445 | 455 | 433 |
14 | 16.384 | 3.299 | 3.297 | 1 | 835 | 805 | 850 | 809 |
15 | 32.768 | 6.115 | 6.113 | 1 | 1.541 | 1.500 | 1.535 | 1.539 |
16 | 65.536 | 11.350 | 11.348 | 1 | 2.810 | 2.859 | 2.819 | 2.862 |
17 | 131.072 | 21.324 | 21.322 | 1 | 5.302 | 5.330 | 5.304 | 5.388 |
18 | 262.144 | 40.032 | 40.030 | 1 | 9.997 | 10.009 | 9.937 | 10.089 |
19 | 524.288 | 75.294 | 75.292 | 1 | 18.786 | 18.742 | 18.839 | 18.927 |
20 | 1.048.576 | 142.326 | 142.324 | 1 | 35.602 | 35.636 | 35.625 | 35.463 |
21 | 2.097.152 | 269.666 | 269.664 | 1 | 67.313 | 67.218 | 67.764 | 67.371 |
22 | 4.194.304 | 512.494 | 512.492 | 1 | 128.096 | 127.815 | 128.418 | 128.165 |
23 | 8.388.608 | 977.528 | 977.526 | 1 | 243.946 | 244.500 | 244.660 | 244.422 |
24 | 16.777.216 | 1.865.577 | 1.865.575 | 1 | 465.936 | 466.714 | 466.632 | 466.295 |
25 | 33.554.432 | 3.572.357 | 3.572.355 | 1 | 892.843 | 893.182 | 892.572 | 893.760 |
26 | 67.108.864 | 6.853.934 | 6.853.932 | 1 | 1.713.914 | 1.713.961 | 1.712.166 | 1.713.893 |
27 | 134.217.728 | 13.169.466 | 13.169.464 | 1 | 3.293.113 | 3.292.636 | 3.291.662 | 3.292.055 |
28 | 268.435.456 | 25.338.957 | 25.338.955 | 1 | 6.333.647 | 6.334.989 | 6.336.175 | 6.334.146 |
29 | 536.870.912 | 48.825.532 | 48.825.530 | 1 | 12.204.669 | 12.208.175 | 12.206.552 | 12.206.136 |
30 | 1.073.741.824 | 94.209.185 | 94.209.183 | 1 | 23.552.503 | 23.550.621 | 23.552.967 | 23.553.094 |
31 | 2.147.483.648 | 182.004.509 | 182.004.507 | 1 | 45.502.064 | 45.496.923 | 45.506.453 | 45.499.069 |
32 | 4.294.967.296 | 352.033.930 | 352.033.928 | 1 | 88.010.708 | 88.007.772 | 88.007.047 | 88.008.403 |
33 | 8.589.934.592 | 681.675.801 | 681.675.799 | 1 | 170.420.613 | 170.419.177 | 170.413.318 | 170.422.693 |
34 | 17.179.869.184 | 1.321.320.687 | 1.321.320.685 | 1 | 330.330.103 | 330.321.767 | 330.330.144 | 330.338.673 |
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 | 2 | 2 | 0 | 0 | 0 | 2 | 0 |
4 | 16 | 5 | 4 | 1 | 0 | 1 | 2 | 2 |
5 | 32 | 9 | 8 | 1 | 0 | 2 | 4 | 3 |
6 | 64 | 23 | 19 | 4 | 4 | 5 | 7 | 7 |
7 | 128 | 53 | 41 | 12 | 11 | 13 | 15 | 14 |
8 | 256 | 108 | 75 | 33 | 23 | 28 | 32 | 25 |
9 | 512 | 238 | 154 | 84 | 56 | 58 | 64 | 60 |
10 | 1.024 | 513 | 301 | 212 | 125 | 134 | 137 | 117 |
11 | 2.048 | 1.060 | 616 | 444 | 259 | 268 | 269 | 264 |
12 | 4.096 | 2.209 | 1.234 | 975 | 532 | 543 | 566 | 568 |
13 | 8.192 | 4.522 | 2.505 | 2.017 | 1.092 | 1.111 | 1.137 | 1.182 |
14 | 16.384 | 9.165 | 5.061 | 4.104 | 2.259 | 2.286 | 2.286 | 2.334 |
15 | 32.768 | 18.673 | 10.226 | 8.447 | 4.635 | 4.673 | 4.645 | 4.720 |
16 | 65.536 | 37.951 | 20.609 | 17.342 | 9.468 | 9.517 | 9.504 | 9.462 |
17 | 131.072 | 76.709 | 41.390 | 35.319 | 19.204 | 19.273 | 19.168 | 19.064 |
18 | 262.144 | 155.287 | 83.457 | 71.830 | 38.884 | 38.809 | 38.816 | 38.778 |
19 | 524.288 | 313.621 | 167.591 | 146.030 | 78.394 | 78.421 | 78.434 | 78.372 |
20 | 1.048.576 | 633.144 | 336.959 | 296.185 | 158.523 | 158.090 | 158.247 | 158.284 |
21 | 2.097.152 | 1.276.528 | 677.710 | 598.818 | 319.421 | 319.114 | 319.120 | 318.873 |
22 | 4.194.304 | 2.571.548 | 1.360.798 | 1.210.750 | 642.630 | 642.523 | 643.043 | 643.352 |
23 | 8.388.608 | 5.174.735 | 2.730.455 | 2.444.280 | 1.293.504 | 1.293.248 | 1.294.131 | 1.293.852 |
24 | 16.777.216 | 10.410.456 | 5.479.846 | 4.930.610 | 2.601.018 | 2.603.344 | 2.602.637 | 2.603.457 |
25 | 33.554.432 | 20.925.696 | 10.991.384 | 9.934.312 | 5.230.561 | 5.230.076 | 5.232.208 | 5.232.851 |
26 | 67.108.864 | 42.041.586 | 22.036.633 | 20.004.953 | 10.509.612 | 10.507.029 | 10.511.782 | 10.513.163 |
27 | 134.217.728 | 84.436.865 | 44.174.902 | 40.261.963 | 21.108.073 | 21.106.120 | 21.110.414 | 21.112.258 |
28 | 268.435.456 | 169.534.500 | 88.531.377 | 81.003.123 | 42.382.770 | 42.379.175 | 42.390.309 | 42.382.246 |
29 | 536.870.912 | 340.285.997 | 177.419.233 | 162.866.764 | 85.070.152 | 85.069.665 | 85.078.364 | 85.067.816 |
30 | 1.073.741.824 | 682.831.314 | 355.477.680 | 327.353.634 | 170.721.128 | 170.705.833 | 170.711.300 | 170.693.053 |
31 | 2.147.483.648 | 1.369.867.718 | 712.144.393 | 657.723.325 | 342.478.947 | 342.470.567 | 342.470.461 | 342.447.743 |
32 | 4.294.967.296 | 2.747.571.936 | 1.426.489.303 | 1.321.082.633 | 686.892.624 | 686.907.885 | 686.899.078 | 686.872.349 |
33 | 8.589.934.592 | 5.509.789.606 | 2.857.057.669 | 2.652.731.937 | 1.377.404.504 | 1.377.473.599 | 1.377.469.648 | 1.377.441.855 |
34 | 17.179.869.184 | 11.047.044.621 | 5.721.734.950 | 5.325.309.671 | 2.761.737.244 | 2.761.752.860 | 2.761.756.984 | 2.761.797.533 |