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+120x-137
f(0)=137
f(1)=1
f(2)=107
f(3)=29
f(4)=359
f(5)=61
f(6)=619
f(7)=47
f(8)=887
f(9)=1
f(10)=1163
f(11)=163
f(12)=1447
f(13)=199
f(14)=37
f(15)=59
f(16)=2039
f(17)=1
f(18)=2347
f(19)=313
f(20)=2663
f(21)=353
f(22)=103
f(23)=197
f(24)=3319
f(25)=109
f(26)=3659
f(27)=479
f(28)=4007
f(29)=523
f(30)=4363
f(31)=71
f(32)=1
f(33)=307
f(34)=5099
f(35)=661
f(36)=5479
f(37)=709
f(38)=5867
f(39)=379
f(40)=6263
f(41)=101
f(42)=113
f(43)=859
f(44)=7079
f(45)=911
f(46)=7499
f(47)=241
f(48)=7927
f(49)=509
f(50)=8363
f(51)=1
f(52)=8807
f(53)=1129
f(54)=1
f(55)=593
f(56)=9719
f(57)=311
f(58)=167
f(59)=1303
f(60)=10663
f(61)=1
f(62)=157
f(63)=89
f(64)=1
f(65)=743
f(66)=1
f(67)=1549
f(68)=12647
f(69)=1613
f(70)=13163
f(71)=839
f(72)=13687
f(73)=1
f(74)=1
f(75)=1811
f(76)=14759
f(77)=1879
f(78)=15307
f(79)=487
f(80)=547
f(81)=1009
f(82)=16427
f(83)=2089
f(84)=191
f(85)=2161
f(86)=17579
f(87)=1117
f(88)=491
f(89)=577
f(90)=647
f(91)=2383
f(92)=181
f(93)=2459
f(94)=19979
f(95)=317
f(96)=20599
f(97)=1307
f(98)=21227
f(99)=2693
b) Substitution of the polynom
The polynom f(x)=x^2+120x-137 could be written as f(y)= y^2-3737 with x=y-60
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+60
f'(x)>2x+119
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 | 9 | 6 | 3 | 0.900000 | 0.600000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 88 | 37 | 51 | 0.880000 | 0.370000 | 0.880000 | 9.777778 | 6.166667 | 17.000000 |
3 | 1.000 | 770 | 250 | 520 | 0.770000 | 0.250000 | 0.770000 | 8.750000 | 6.756757 | 10.196078 |
4 | 10.000 | 7.358 | 1.873 | 5.485 | 0.735800 | 0.187300 | 0.735800 | 9.555844 | 7.492000 | 10.548077 |
5 | 100.000 | 72.413 | 14.804 | 57.609 | 0.724130 | 0.148040 | 0.724130 | 9.841397 | 7.903897 | 10.503008 |
6 | 1.000.000 | 719.007 | 119.963 | 599.044 | 0.719007 | 0.119963 | 0.719007 | 9.929253 | 8.103418 | 10.398445 |
7 | 10.000.000 | 7.152.162 | 1.013.431 | 6.138.731 | 0.715216 | 0.101343 | 0.715216 | 9.947277 | 8.447863 | 10.247546 |
8 | 100.000.000 | 71.225.045 | 8.782.365 | 62.442.680 | 0.712250 | 0.087824 | 0.712250 | 9.958534 | 8.665973 | 10.171920 |
9 | 1.000.000.000 | 709.986.369 | 77.486.879 | 632.499.490 | 0.709986 | 0.077487 | 0.709986 | 9.968212 | 8.823009 | 10.129282 |
10 | 10.000.000.000 | 7.081.884.477 | 693.496.507 | 6.388.387.970 | 0.708188 | 0.069350 | 0.708188 | 9.974677 | 8.949857 | 10.100225 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 2.000000 | 1.500000 | inf |
3 | 8 | 8 | 5 | 3 | 1.000000 | 0.625000 | 0.375000 | 2.000000 | 1.666667 | 3.000000 |
4 | 16 | 15 | 9 | 6 | 0.937500 | 0.562500 | 0.375000 | 1.875000 | 1.800000 | 2.000000 |
5 | 32 | 29 | 15 | 14 | 0.906250 | 0.468750 | 0.437500 | 1.933333 | 1.666667 | 2.333333 |
6 | 64 | 56 | 26 | 30 | 0.875000 | 0.406250 | 0.468750 | 1.931034 | 1.733333 | 2.142857 |
7 | 128 | 110 | 49 | 61 | 0.859375 | 0.382812 | 0.476562 | 1.964286 | 1.884615 | 2.033333 |
8 | 256 | 205 | 80 | 125 | 0.800781 | 0.312500 | 0.488281 | 1.863636 | 1.632653 | 2.049180 |
9 | 512 | 400 | 140 | 260 | 0.781250 | 0.273438 | 0.507812 | 1.951220 | 1.750000 | 2.080000 |
10 | 1.024 | 789 | 255 | 534 | 0.770508 | 0.249023 | 0.521484 | 1.972500 | 1.821429 | 2.053846 |
11 | 2.048 | 1.540 | 475 | 1.065 | 0.751953 | 0.231934 | 0.520020 | 1.951838 | 1.862745 | 1.994382 |
12 | 4.096 | 3.035 | 865 | 2.170 | 0.740967 | 0.211182 | 0.529785 | 1.970779 | 1.821053 | 2.037559 |
13 | 8.192 | 6.024 | 1.566 | 4.458 | 0.735352 | 0.191162 | 0.544189 | 1.984843 | 1.810405 | 2.054378 |
14 | 16.384 | 12.022 | 2.882 | 9.140 | 0.733765 | 0.175903 | 0.557861 | 1.995684 | 1.840358 | 2.050247 |
15 | 32.768 | 23.916 | 5.412 | 18.504 | 0.729858 | 0.165161 | 0.564697 | 1.989353 | 1.877863 | 2.024508 |
16 | 65.536 | 47.573 | 10.150 | 37.423 | 0.725906 | 0.154877 | 0.571030 | 1.989170 | 1.875462 | 2.022428 |
17 | 131.072 | 94.822 | 18.854 | 75.968 | 0.723434 | 0.143845 | 0.579590 | 1.993189 | 1.857537 | 2.029982 |
18 | 262.144 | 189.228 | 35.321 | 153.907 | 0.721848 | 0.134739 | 0.587109 | 1.995613 | 1.873396 | 2.025945 |
19 | 524.288 | 377.606 | 66.379 | 311.227 | 0.720226 | 0.126608 | 0.593618 | 1.995508 | 1.879307 | 2.022176 |
20 | 1.048.576 | 753.834 | 125.282 | 628.552 | 0.718912 | 0.119478 | 0.599434 | 1.996351 | 1.887374 | 2.019593 |
21 | 2.097.152 | 1.505.209 | 237.120 | 1.268.089 | 0.717740 | 0.113068 | 0.604672 | 1.996738 | 1.892690 | 2.017477 |
22 | 4.194.304 | 3.005.629 | 451.016 | 2.554.613 | 0.716598 | 0.107531 | 0.609067 | 1.996818 | 1.902058 | 2.014538 |
23 | 8.388.608 | 6.001.955 | 859.829 | 5.142.126 | 0.715489 | 0.102500 | 0.612989 | 1.996905 | 1.906427 | 2.012879 |
24 | 16.777.216 | 11.986.662 | 1.643.657 | 10.343.005 | 0.714461 | 0.097970 | 0.616491 | 1.997126 | 1.911609 | 2.011426 |
25 | 33.554.432 | 23.942.557 | 3.145.560 | 20.796.997 | 0.713544 | 0.093745 | 0.619799 | 1.997433 | 1.913757 | 2.010731 |
26 | 67.108.864 | 47.828.763 | 6.032.081 | 41.796.682 | 0.712704 | 0.089885 | 0.622819 | 1.997647 | 1.917649 | 2.009746 |
27 | 134.217.728 | 95.553.431 | 11.588.341 | 83.965.090 | 0.711929 | 0.086340 | 0.625589 | 1.997824 | 1.921118 | 2.008894 |
28 | 268.435.456 | 190.912.420 | 22.299.531 | 168.612.889 | 0.711204 | 0.083072 | 0.628132 | 1.997965 | 1.924308 | 2.008131 |
29 | 536.870.912 | 381.471.421 | 42.965.744 | 338.505.677 | 0.710546 | 0.080030 | 0.630516 | 1.998149 | 1.926755 | 2.007591 |
30 | 1.073.741.824 | 762.277.519 | 82.901.022 | 679.376.497 | 0.709926 | 0.077208 | 0.632719 | 1.998256 | 1.929468 | 2.006987 |
31 | 2.147.483.648 | 1.523.299.996 | 160.167.287 | 1.363.132.709 | 0.709342 | 0.074584 | 0.634758 | 1.998354 | 1.932030 | 2.006447 |
32 | 4.294.967.296 | 3.044.275.215 | 309.797.336 | 2.734.477.879 | 0.708801 | 0.072130 | 0.636670 | 1.998474 | 1.934211 | 2.006025 |
33 | 8.589.934.592 | 6.084.208.987 | 599.871.827 | 5.484.337.160 | 0.708295 | 0.069834 | 0.638461 | 1.998574 | 1.936336 | 2.005625 |
34 | 17.179.869.184 | 12.160.256.358 | 1.162.719.459 | 10.997.536.899 | 0.707820 | 0.067679 | 0.640141 | 1.998658 | 1.938280 | 2.005263 |
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 | 2 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 3 | 1 | 1 | 0 | 1 |
3 | 8 | 5 | 1 | 4 | 1 | 2 | 0 | 2 |
4 | 16 | 9 | 2 | 7 | 1 | 4 | 0 | 4 |
5 | 32 | 15 | 5 | 10 | 1 | 7 | 0 | 7 |
6 | 64 | 26 | 8 | 18 | 1 | 11 | 0 | 14 |
7 | 128 | 49 | 14 | 35 | 1 | 23 | 0 | 25 |
8 | 256 | 80 | 24 | 56 | 1 | 40 | 0 | 39 |
9 | 512 | 140 | 51 | 89 | 1 | 72 | 0 | 67 |
10 | 1.024 | 255 | 80 | 175 | 1 | 129 | 0 | 125 |
11 | 2.048 | 475 | 154 | 321 | 1 | 240 | 0 | 234 |
12 | 4.096 | 865 | 287 | 578 | 1 | 432 | 0 | 432 |
13 | 8.192 | 1.566 | 519 | 1.047 | 1 | 793 | 0 | 772 |
14 | 16.384 | 2.882 | 965 | 1.917 | 1 | 1.459 | 0 | 1.422 |
15 | 32.768 | 5.412 | 1.811 | 3.601 | 1 | 2.723 | 0 | 2.688 |
16 | 65.536 | 10.150 | 3.373 | 6.777 | 1 | 5.074 | 0 | 5.075 |
17 | 131.072 | 18.854 | 6.273 | 12.581 | 1 | 9.414 | 0 | 9.439 |
18 | 262.144 | 35.321 | 11.794 | 23.527 | 1 | 17.698 | 0 | 17.622 |
19 | 524.288 | 66.379 | 22.091 | 44.288 | 1 | 33.261 | 0 | 33.117 |
20 | 1.048.576 | 125.282 | 41.781 | 83.501 | 1 | 62.746 | 0 | 62.535 |
21 | 2.097.152 | 237.120 | 78.962 | 158.158 | 1 | 118.746 | 0 | 118.373 |
22 | 4.194.304 | 451.016 | 150.437 | 300.579 | 1 | 225.543 | 0 | 225.472 |
23 | 8.388.608 | 859.829 | 286.884 | 572.945 | 1 | 430.088 | 0 | 429.740 |
24 | 16.777.216 | 1.643.657 | 547.518 | 1.096.139 | 1 | 821.595 | 0 | 822.061 |
25 | 33.554.432 | 3.145.560 | 1.047.937 | 2.097.623 | 1 | 1.572.993 | 0 | 1.572.566 |
26 | 67.108.864 | 6.032.081 | 2.009.676 | 4.022.405 | 1 | 3.016.317 | 0 | 3.015.763 |
27 | 134.217.728 | 11.588.341 | 3.861.570 | 7.726.771 | 1 | 5.794.635 | 0 | 5.793.705 |
28 | 268.435.456 | 22.299.531 | 7.431.318 | 14.868.213 | 1 | 11.149.240 | 0 | 11.150.290 |
29 | 536.870.912 | 42.965.744 | 14.319.668 | 28.646.076 | 1 | 21.485.614 | 0 | 21.480.129 |
30 | 1.073.741.824 | 82.901.022 | 27.637.288 | 55.263.734 | 1 | 41.454.733 | 0 | 41.446.288 |
31 | 2.147.483.648 | 160.167.287 | 53.396.980 | 106.770.307 | 1 | 80.086.140 | 0 | 80.081.146 |
32 | 4.294.967.296 | 309.797.336 | 103.271.767 | 206.525.569 | 1 | 154.906.366 | 0 | 154.890.969 |
33 | 8.589.934.592 | 599.871.827 | 199.962.227 | 399.909.600 | 1 | 299.926.606 | 0 | 299.945.220 |
34 | 17.179.869.184 | 1.162.719.459 | 387.579.271 | 775.140.188 | 1 | 581.349.069 | 0 | 581.370.389 |
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 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 3 | 1 | 2 | 0 | 0 | 2 | 1 |
4 | 16 | 6 | 3 | 3 | 0 | 2 | 2 | 2 |
5 | 32 | 14 | 7 | 7 | 2 | 3 | 4 | 5 |
6 | 64 | 30 | 16 | 14 | 6 | 6 | 9 | 9 |
7 | 128 | 61 | 30 | 31 | 13 | 14 | 16 | 18 |
8 | 256 | 125 | 68 | 57 | 31 | 30 | 31 | 33 |
9 | 512 | 260 | 136 | 124 | 63 | 69 | 61 | 67 |
10 | 1.024 | 534 | 287 | 247 | 123 | 148 | 126 | 137 |
11 | 2.048 | 1.065 | 568 | 497 | 255 | 289 | 254 | 267 |
12 | 4.096 | 2.170 | 1.163 | 1.007 | 516 | 565 | 533 | 556 |
13 | 8.192 | 4.458 | 2.373 | 2.085 | 1.069 | 1.162 | 1.092 | 1.135 |
14 | 16.384 | 9.140 | 4.829 | 4.311 | 2.208 | 2.327 | 2.280 | 2.325 |
15 | 32.768 | 18.504 | 9.718 | 8.786 | 4.520 | 4.680 | 4.567 | 4.737 |
16 | 65.536 | 37.423 | 19.426 | 17.997 | 9.191 | 9.493 | 9.255 | 9.484 |
17 | 131.072 | 75.968 | 39.345 | 36.623 | 18.697 | 19.316 | 18.804 | 19.151 |
18 | 262.144 | 153.907 | 79.358 | 74.549 | 38.112 | 38.945 | 38.103 | 38.747 |
19 | 524.288 | 311.227 | 160.215 | 151.012 | 76.969 | 78.565 | 77.266 | 78.427 |
20 | 1.048.576 | 628.552 | 323.804 | 304.748 | 155.376 | 158.388 | 155.822 | 158.966 |
21 | 2.097.152 | 1.268.089 | 652.163 | 615.926 | 313.859 | 319.570 | 314.264 | 320.396 |
22 | 4.194.304 | 2.554.613 | 1.310.221 | 1.244.392 | 631.938 | 644.118 | 633.468 | 645.089 |
23 | 8.388.608 | 5.142.126 | 2.633.530 | 2.508.596 | 1.272.984 | 1.296.371 | 1.275.475 | 1.297.296 |
24 | 16.777.216 | 10.343.005 | 5.290.982 | 5.052.023 | 2.562.387 | 2.607.316 | 2.564.553 | 2.608.749 |
25 | 33.554.432 | 20.796.997 | 10.626.533 | 10.170.464 | 5.156.221 | 5.240.539 | 5.157.487 | 5.242.750 |
26 | 67.108.864 | 41.796.682 | 21.335.921 | 20.460.761 | 10.368.633 | 10.529.498 | 10.369.374 | 10.529.177 |
27 | 134.217.728 | 83.965.090 | 42.817.251 | 41.147.839 | 20.839.040 | 21.142.802 | 20.839.528 | 21.143.720 |
28 | 268.435.456 | 168.612.889 | 85.913.328 | 82.699.561 | 41.860.784 | 42.447.014 | 41.863.625 | 42.441.466 |
29 | 536.870.912 | 338.505.677 | 172.356.770 | 166.148.907 | 84.067.759 | 85.191.081 | 84.070.653 | 85.176.184 |
30 | 1.073.741.824 | 679.376.497 | 345.683.714 | 333.692.783 | 168.774.607 | 170.915.623 | 168.778.247 | 170.908.020 |
31 | 2.147.483.648 | 1.363.132.709 | 693.147.226 | 669.985.483 | 338.724.166 | 342.842.022 | 338.722.228 | 342.844.293 |
32 | 4.294.967.296 | 2.734.477.879 | 1.389.596.015 | 1.344.881.864 | 679.648.598 | 687.597.429 | 679.649.817 | 687.582.035 |
33 | 8.589.934.592 | 5.484.337.160 | 2.785.393.746 | 2.698.943.414 | 1.363.402.486 | 1.378.800.553 | 1.363.376.734 | 1.378.757.387 |
34 | 17.179.869.184 | 10.997.536.899 | 5.582.416.162 | 5.415.120.737 | 2.734.447.102 | 2.764.335.676 | 2.734.454.994 | 2.764.299.127 |