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-108x+13
f(0)=13
f(1)=47
f(2)=199
f(3)=151
f(4)=31
f(5)=251
f(6)=599
f(7)=347
f(8)=787
f(9)=439
f(10)=967
f(11)=17
f(12)=67
f(13)=1
f(14)=1303
f(15)=691
f(16)=1459
f(17)=59
f(18)=1607
f(19)=839
f(20)=1747
f(21)=907
f(22)=1879
f(23)=971
f(24)=2003
f(25)=1031
f(26)=163
f(27)=1087
f(28)=131
f(29)=1
f(30)=179
f(31)=1187
f(32)=41
f(33)=1231
f(34)=2503
f(35)=1
f(36)=2579
f(37)=1307
f(38)=2647
f(39)=103
f(40)=2707
f(41)=1367
f(42)=89
f(43)=107
f(44)=2803
f(45)=83
f(46)=167
f(47)=1427
f(48)=61
f(49)=1439
f(50)=2887
f(51)=1447
f(52)=223
f(53)=1451
f(54)=2903
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=1
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-108x+13 could be written as f(y)= y^2-2903 with x=y+54
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-54
f'(x)>2x-109 with x > 54
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 | 10 | 1 | 1.100000 | 1.000000 | 0.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 48 | 37 | 11 | 0.480000 | 0.370000 | 0.110000 | 4.363636 | 3.700000 | 11.000000 |
3 | 1.000 | 729 | 409 | 320 | 0.729000 | 0.409000 | 0.320000 | 15.187500 | 11.054054 | 29.090910 |
4 | 10.000 | 7.512 | 2.927 | 4.585 | 0.751200 | 0.292700 | 0.458500 | 10.304526 | 7.156479 | 14.328125 |
5 | 100.000 | 74.297 | 22.888 | 51.409 | 0.742970 | 0.228880 | 0.514090 | 9.890442 | 7.819611 | 11.212432 |
6 | 1.000.000 | 734.284 | 187.059 | 547.225 | 0.734284 | 0.187059 | 0.547225 | 9.883091 | 8.172798 | 10.644537 |
7 | 10.000.000 | 7.282.282 | 1.574.057 | 5.708.225 | 0.728228 | 0.157406 | 0.570822 | 9.917528 | 8.414762 | 10.431221 |
8 | 100.000.000 | 72.364.373 | 13.611.799 | 58.752.574 | 0.723644 | 0.136118 | 0.587526 | 9.937047 | 8.647590 | 10.292618 |
9 | 1.000.000.000 | 720.082.023 | 119.974.065 | 600.107.958 | 0.720082 | 0.119974 | 0.600108 | 9.950781 | 8.813975 | 10.214156 |
10 | 10.000.000.000 | 7.172.605.210 | 1.072.533.728 | 6.100.071.482 | 0.717261 | 0.107253 | 0.610007 | 9.960817 | 8.939713 | 10.164956 |
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 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 1.333333 | inf |
3 | 8 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 2.000000 | 1.000000 |
4 | 16 | 15 | 13 | 2 | 0.937500 | 0.812500 | 0.125000 | 1.666667 | 1.625000 | 2.000000 |
5 | 32 | 29 | 23 | 6 | 0.906250 | 0.718750 | 0.187500 | 1.933333 | 1.769231 | 3.000000 |
6 | 64 | 48 | 37 | 11 | 0.750000 | 0.578125 | 0.171875 | 1.655172 | 1.608696 | 1.833333 |
7 | 128 | 61 | 50 | 11 | 0.476562 | 0.390625 | 0.085938 | 1.270833 | 1.351351 | 1.000000 |
8 | 256 | 152 | 110 | 42 | 0.593750 | 0.429688 | 0.164062 | 2.491803 | 2.200000 | 3.818182 |
9 | 512 | 346 | 224 | 122 | 0.675781 | 0.437500 | 0.238281 | 2.276316 | 2.036364 | 2.904762 |
10 | 1.024 | 750 | 415 | 335 | 0.732422 | 0.405273 | 0.327148 | 2.167630 | 1.852679 | 2.745902 |
11 | 2.048 | 1.532 | 736 | 796 | 0.748047 | 0.359375 | 0.388672 | 2.042667 | 1.773494 | 2.376119 |
12 | 4.096 | 3.083 | 1.358 | 1.725 | 0.752686 | 0.331543 | 0.421143 | 2.012402 | 1.845109 | 2.167085 |
13 | 8.192 | 6.153 | 2.458 | 3.695 | 0.751099 | 0.300049 | 0.451050 | 1.995783 | 1.810015 | 2.142029 |
14 | 16.384 | 12.312 | 4.521 | 7.791 | 0.751465 | 0.275940 | 0.475525 | 2.000975 | 1.839300 | 2.108525 |
15 | 32.768 | 24.497 | 8.363 | 16.134 | 0.747589 | 0.255219 | 0.492371 | 1.989685 | 1.849812 | 2.070851 |
16 | 65.536 | 48.793 | 15.624 | 33.169 | 0.744522 | 0.238403 | 0.506119 | 1.991795 | 1.868229 | 2.055845 |
17 | 131.072 | 97.178 | 29.385 | 67.793 | 0.741409 | 0.224190 | 0.517220 | 1.991638 | 1.880760 | 2.043866 |
18 | 262.144 | 193.762 | 55.061 | 138.701 | 0.739143 | 0.210041 | 0.529102 | 1.993888 | 1.873779 | 2.045949 |
19 | 524.288 | 386.172 | 103.335 | 282.837 | 0.736565 | 0.197096 | 0.539469 | 1.993022 | 1.876737 | 2.039185 |
20 | 1.048.576 | 769.864 | 195.330 | 574.534 | 0.734200 | 0.186281 | 0.547918 | 1.993578 | 1.890260 | 2.031326 |
21 | 2.097.152 | 1.535.607 | 369.660 | 1.165.947 | 0.732234 | 0.176268 | 0.555967 | 1.994647 | 1.892490 | 2.029379 |
22 | 4.194.304 | 3.062.826 | 702.013 | 2.360.813 | 0.730235 | 0.167373 | 0.562862 | 1.994538 | 1.899078 | 2.024803 |
23 | 8.388.608 | 6.112.522 | 1.336.176 | 4.776.346 | 0.728669 | 0.159285 | 0.569385 | 1.995713 | 1.903349 | 2.023178 |
24 | 16.777.216 | 12.198.900 | 2.550.391 | 9.648.509 | 0.727111 | 0.152015 | 0.575096 | 1.995723 | 1.908724 | 2.020061 |
25 | 33.554.432 | 24.350.619 | 4.878.904 | 19.471.715 | 0.725705 | 0.145403 | 0.580302 | 1.996132 | 1.913002 | 2.018106 |
26 | 67.108.864 | 48.611.314 | 9.352.110 | 39.259.204 | 0.724365 | 0.139357 | 0.585008 | 1.996307 | 1.916847 | 2.016217 |
27 | 134.217.728 | 97.056.545 | 17.960.310 | 79.096.235 | 0.723128 | 0.133815 | 0.589313 | 1.996583 | 1.920455 | 2.014718 |
28 | 268.435.456 | 193.810.081 | 34.544.373 | 159.265.708 | 0.721999 | 0.128688 | 0.593311 | 1.996878 | 1.923373 | 2.013569 |
29 | 536.870.912 | 387.060.986 | 66.540.292 | 320.520.694 | 0.720957 | 0.123941 | 0.597016 | 1.997115 | 1.926227 | 2.012490 |
30 | 1.073.741.824 | 773.076.010 | 128.351.550 | 644.724.460 | 0.719983 | 0.119537 | 0.600446 | 1.997298 | 1.928930 | 2.011491 |
31 | 2.147.483.648 | 1.544.213.063 | 247.877.113 | 1.296.335.950 | 0.719080 | 0.115427 | 0.603653 | 1.997492 | 1.931236 | 2.010682 |
32 | 4.294.967.296 | 3.084.777.703 | 479.290.134 | 2.605.487.569 | 0.718231 | 0.111593 | 0.606637 | 1.997637 | 1.933580 | 2.009886 |
33 | 8.589.934.592 | 6.162.665.708 | 927.780.586 | 5.234.885.122 | 0.717429 | 0.108008 | 0.609421 | 1.997766 | 1.935739 | 2.009177 |
34 | 17.179.869.184 | 12.312.460.344 | 1.797.863.134 | 10.514.597.210 | 0.716680 | 0.104649 | 0.612030 | 1.997911 | 1.937811 | 2.008563 |
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 | 0 | 1 | 2 |
2 | 4 | 4 | 3 | 1 | 0 | 0 | 1 | 3 |
3 | 8 | 8 | 4 | 4 | 0 | 3 | 1 | 4 |
4 | 16 | 13 | 9 | 4 | 0 | 5 | 1 | 7 |
5 | 32 | 23 | 13 | 10 | 0 | 10 | 1 | 12 |
6 | 64 | 37 | 20 | 17 | 0 | 16 | 1 | 20 |
7 | 128 | 50 | 26 | 24 | 6 | 16 | 8 | 20 |
8 | 256 | 110 | 61 | 49 | 38 | 16 | 36 | 20 |
9 | 512 | 224 | 116 | 108 | 96 | 16 | 92 | 20 |
10 | 1.024 | 415 | 210 | 205 | 185 | 16 | 194 | 20 |
11 | 2.048 | 736 | 367 | 369 | 338 | 16 | 362 | 20 |
12 | 4.096 | 1.358 | 677 | 681 | 652 | 16 | 670 | 20 |
13 | 8.192 | 2.458 | 1.236 | 1.222 | 1.230 | 16 | 1.192 | 20 |
14 | 16.384 | 4.521 | 2.254 | 2.267 | 2.273 | 16 | 2.212 | 20 |
15 | 32.768 | 8.363 | 4.174 | 4.189 | 4.177 | 16 | 4.150 | 20 |
16 | 65.536 | 15.624 | 7.828 | 7.796 | 7.831 | 16 | 7.757 | 20 |
17 | 131.072 | 29.385 | 14.756 | 14.629 | 14.706 | 16 | 14.643 | 20 |
18 | 262.144 | 55.061 | 27.706 | 27.355 | 27.466 | 16 | 27.559 | 20 |
19 | 524.288 | 103.335 | 52.011 | 51.324 | 51.543 | 16 | 51.756 | 20 |
20 | 1.048.576 | 195.330 | 97.948 | 97.382 | 97.716 | 16 | 97.578 | 20 |
21 | 2.097.152 | 369.660 | 185.581 | 184.079 | 184.866 | 16 | 184.758 | 20 |
22 | 4.194.304 | 702.013 | 352.449 | 349.564 | 350.783 | 16 | 351.194 | 20 |
23 | 8.388.608 | 1.336.176 | 671.023 | 665.153 | 667.513 | 16 | 668.627 | 20 |
24 | 16.777.216 | 2.550.391 | 1.279.944 | 1.270.447 | 1.274.742 | 16 | 1.275.613 | 20 |
25 | 33.554.432 | 4.878.904 | 2.448.772 | 2.430.132 | 2.439.151 | 16 | 2.439.717 | 20 |
26 | 67.108.864 | 9.352.110 | 4.692.782 | 4.659.328 | 4.676.081 | 16 | 4.675.993 | 20 |
27 | 134.217.728 | 17.960.310 | 9.010.375 | 8.949.935 | 8.980.661 | 16 | 8.979.613 | 20 |
28 | 268.435.456 | 34.544.373 | 17.325.767 | 17.218.606 | 17.272.667 | 16 | 17.271.670 | 20 |
29 | 536.870.912 | 66.540.292 | 33.369.026 | 33.171.266 | 33.270.854 | 16 | 33.269.402 | 20 |
30 | 1.073.741.824 | 128.351.550 | 64.370.111 | 63.981.439 | 64.178.831 | 16 | 64.172.683 | 20 |
31 | 2.147.483.648 | 247.877.113 | 124.299.401 | 123.577.712 | 123.940.220 | 16 | 123.936.857 | 20 |
32 | 4.294.967.296 | 479.290.134 | 240.314.995 | 238.975.139 | 239.647.623 | 16 | 239.642.475 | 20 |
33 | 8.589.934.592 | 927.780.586 | 465.128.134 | 462.652.452 | 463.888.143 | 16 | 463.892.407 | 20 |
34 | 17.179.869.184 | 1.797.863.134 | 901.257.488 | 896.605.646 | 898.948.665 | 16 | 898.914.433 | 20 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
4 | 16 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
5 | 32 | 6 | 3 | 3 | 0 | 5 | 0 | 1 |
6 | 64 | 11 | 5 | 6 | 1 | 6 | 0 | 4 |
7 | 128 | 11 | 5 | 6 | 1 | 6 | 0 | 4 |
8 | 256 | 42 | 22 | 20 | 11 | 10 | 16 | 5 |
9 | 512 | 122 | 62 | 60 | 41 | 24 | 41 | 16 |
10 | 1.024 | 335 | 165 | 170 | 99 | 73 | 99 | 64 |
11 | 2.048 | 796 | 393 | 403 | 226 | 174 | 227 | 169 |
12 | 4.096 | 1.725 | 862 | 863 | 478 | 375 | 486 | 386 |
13 | 8.192 | 3.695 | 1.832 | 1.863 | 974 | 829 | 1.037 | 855 |
14 | 16.384 | 7.791 | 3.887 | 3.904 | 2.089 | 1.782 | 2.093 | 1.827 |
15 | 32.768 | 16.134 | 8.073 | 8.061 | 4.250 | 3.777 | 4.250 | 3.857 |
16 | 65.536 | 33.169 | 16.525 | 16.644 | 8.601 | 7.884 | 8.709 | 7.975 |
17 | 131.072 | 67.793 | 33.743 | 34.050 | 17.593 | 16.130 | 17.753 | 16.317 |
18 | 262.144 | 138.701 | 69.229 | 69.472 | 36.155 | 33.063 | 36.059 | 33.424 |
19 | 524.288 | 282.837 | 141.125 | 141.712 | 73.610 | 67.814 | 73.422 | 67.991 |
20 | 1.048.576 | 574.534 | 286.755 | 287.779 | 149.153 | 138.240 | 148.884 | 138.257 |
21 | 2.097.152 | 1.165.947 | 582.520 | 583.427 | 301.796 | 281.362 | 301.451 | 281.338 |
22 | 4.194.304 | 2.360.813 | 1.179.464 | 1.181.349 | 609.616 | 571.143 | 609.206 | 570.848 |
23 | 8.388.608 | 4.776.346 | 2.387.475 | 2.388.871 | 1.230.887 | 1.157.474 | 1.230.526 | 1.157.459 |
24 | 16.777.216 | 9.648.509 | 4.823.039 | 4.825.470 | 2.482.397 | 2.341.879 | 2.481.045 | 2.343.188 |
25 | 33.554.432 | 19.471.715 | 9.732.927 | 9.738.788 | 5.002.703 | 4.736.171 | 5.000.949 | 4.731.892 |
26 | 67.108.864 | 39.259.204 | 19.625.921 | 19.633.283 | 10.071.098 | 9.557.359 | 10.073.555 | 9.557.192 |
27 | 134.217.728 | 79.096.235 | 39.548.068 | 39.548.167 | 20.270.698 | 19.278.177 | 20.270.752 | 19.276.608 |
28 | 268.435.456 | 159.265.708 | 79.624.163 | 79.641.545 | 40.768.844 | 38.853.530 | 40.775.604 | 38.867.730 |
29 | 536.870.912 | 320.520.694 | 160.251.874 | 160.268.820 | 81.969.168 | 78.275.469 | 81.983.778 | 78.292.279 |
30 | 1.073.741.824 | 644.724.460 | 322.352.088 | 322.372.372 | 164.735.750 | 157.598.711 | 164.767.790 | 157.622.209 |
31 | 2.147.483.648 | 1.296.335.950 | 648.169.930 | 648.166.020 | 330.975.712 | 317.169.545 | 331.002.022 | 317.188.671 |
32 | 4.294.967.296 | 2.605.487.569 | 1.302.749.579 | 1.302.737.990 | 664.749.033 | 637.967.000 | 664.744.424 | 638.027.112 |
33 | 8.589.934.592 | 5.234.885.122 | 2.617.470.592 | 2.617.414.530 | 1.334.655.375 | 1.282.745.577 | 1.334.649.778 | 1.282.834.392 |
34 | 17.179.869.184 | 10.514.597.210 | 5.257.373.970 | 5.257.223.240 | 2.678.967.309 | 2.578.319.635 | 2.678.923.696 | 2.578.386.570 |