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-72x+47
f(0)=47
f(1)=3
f(2)=31
f(3)=5
f(4)=1
f(5)=1
f(6)=349
f(7)=17
f(8)=1
f(9)=13
f(10)=191
f(11)=1
f(12)=673
f(13)=1
f(14)=1
f(15)=101
f(16)=283
f(17)=37
f(18)=1
f(19)=1
f(20)=331
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=383
f(27)=73
f(28)=79
f(29)=1
f(30)=1213
f(31)=1
f(32)=137
f(33)=1
f(34)=83
f(35)=1
f(36)=1249
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
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)=103
f(79)=1
f(80)=229
f(81)=97
f(82)=1
f(83)=1
f(84)=211
f(85)=1
f(86)=139
f(87)=1
f(88)=1
f(89)=1
f(90)=1667
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=1
f(96)=2351
f(97)=1
f(98)=173
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-72x+47 could be written as f(y)= y^2-1249 with x=y+36
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-36
f'(x)>2x-73 with x > 35
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 | 6 | 3 | 3 | 0.600000 | 0.300000 | 0.300000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 22 | 10 | 12 | 0.220000 | 0.100000 | 0.120000 | 3.666667 | 3.333333 | 4.000000 |
3 | 1.000 | 508 | 89 | 419 | 0.508000 | 0.089000 | 0.419000 | 23.090910 | 8.900000 | 34.916668 |
4 | 10.000 | 5.946 | 682 | 5.264 | 0.594600 | 0.068200 | 0.526400 | 11.704724 | 7.662921 | 12.563246 |
5 | 100.000 | 61.992 | 5.152 | 56.840 | 0.619920 | 0.051520 | 0.568400 | 10.425833 | 7.554252 | 10.797873 |
6 | 1.000.000 | 633.492 | 41.364 | 592.128 | 0.633492 | 0.041364 | 0.592128 | 10.218931 | 8.028727 | 10.417453 |
7 | 10.000.000 | 6.424.610 | 346.862 | 6.077.748 | 0.642461 | 0.034686 | 0.607775 | 10.141581 | 8.385601 | 10.264247 |
8 | 100.000.000 | 64.901.710 | 2.986.194 | 61.915.516 | 0.649017 | 0.029862 | 0.619155 | 10.102047 | 8.609170 | 10.187246 |
9 | 1.000.000.000 | 654.033.012 | 26.207.166 | 627.825.846 | 0.654033 | 0.026207 | 0.627826 | 10.077285 | 8.776110 | 10.140040 |
10 | 10.000.000.000 | 6.580.366.742 | 233.563.014 | 6.346.803.728 | 0.658037 | 0.023356 | 0.634680 | 10.061215 | 8.912181 | 10.109179 |
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 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 5 | 3 | 2 | 0.625000 | 0.375000 | 0.250000 | 1.666667 | 1.500000 | 2.000000 |
4 | 16 | 9 | 5 | 4 | 0.562500 | 0.312500 | 0.250000 | 1.800000 | 1.666667 | 2.000000 |
5 | 32 | 16 | 7 | 9 | 0.500000 | 0.218750 | 0.281250 | 1.777778 | 1.400000 | 2.250000 |
6 | 64 | 18 | 8 | 10 | 0.281250 | 0.125000 | 0.156250 | 1.125000 | 1.142857 | 1.111111 |
7 | 128 | 34 | 13 | 21 | 0.265625 | 0.101562 | 0.164062 | 1.888889 | 1.625000 | 2.100000 |
8 | 256 | 98 | 26 | 72 | 0.382812 | 0.101562 | 0.281250 | 2.882353 | 2.000000 | 3.428571 |
9 | 512 | 237 | 47 | 190 | 0.462891 | 0.091797 | 0.371094 | 2.418367 | 1.807692 | 2.638889 |
10 | 1.024 | 523 | 91 | 432 | 0.510742 | 0.088867 | 0.421875 | 2.206751 | 1.936170 | 2.273684 |
11 | 2.048 | 1.125 | 170 | 955 | 0.549316 | 0.083008 | 0.466309 | 2.151052 | 1.868132 | 2.210648 |
12 | 4.096 | 2.338 | 325 | 2.013 | 0.570801 | 0.079346 | 0.491455 | 2.078222 | 1.911765 | 2.107853 |
13 | 8.192 | 4.839 | 575 | 4.264 | 0.590698 | 0.070190 | 0.520508 | 2.069718 | 1.769231 | 2.118232 |
14 | 16.384 | 9.842 | 1.045 | 8.797 | 0.600708 | 0.063782 | 0.536926 | 2.033891 | 1.817391 | 2.063086 |
15 | 32.768 | 20.012 | 1.931 | 18.081 | 0.610718 | 0.058929 | 0.551788 | 2.033327 | 1.847847 | 2.055360 |
16 | 65.536 | 40.429 | 3.558 | 36.871 | 0.616898 | 0.054291 | 0.562607 | 2.020238 | 1.842569 | 2.039212 |
17 | 131.072 | 81.534 | 6.569 | 74.965 | 0.622055 | 0.050117 | 0.571938 | 2.016721 | 1.846262 | 2.033170 |
18 | 262.144 | 164.145 | 12.280 | 151.865 | 0.626163 | 0.046844 | 0.579319 | 2.013209 | 1.869387 | 2.025812 |
19 | 524.288 | 330.532 | 23.027 | 307.505 | 0.630440 | 0.043921 | 0.586519 | 2.013659 | 1.875163 | 2.024858 |
20 | 1.048.576 | 664.480 | 43.230 | 621.250 | 0.633698 | 0.041227 | 0.592470 | 2.010335 | 1.877361 | 2.020292 |
21 | 2.097.152 | 1.335.728 | 81.765 | 1.253.963 | 0.636925 | 0.038989 | 0.597936 | 2.010185 | 1.891395 | 2.018451 |
22 | 4.194.304 | 2.682.181 | 155.041 | 2.527.140 | 0.639482 | 0.036965 | 0.602517 | 2.008029 | 1.896178 | 2.015323 |
23 | 8.388.608 | 5.384.874 | 294.432 | 5.090.442 | 0.641927 | 0.035099 | 0.606828 | 2.007648 | 1.899059 | 2.014309 |
24 | 16.777.216 | 10.807.307 | 561.799 | 10.245.508 | 0.644166 | 0.033486 | 0.610680 | 2.006975 | 1.908077 | 2.012695 |
25 | 33.554.432 | 21.681.173 | 1.072.844 | 20.608.329 | 0.646149 | 0.031973 | 0.614176 | 2.006159 | 1.909658 | 2.011450 |
26 | 67.108.864 | 43.485.461 | 2.053.948 | 41.431.513 | 0.647984 | 0.030606 | 0.617378 | 2.005678 | 1.914489 | 2.010426 |
27 | 134.217.728 | 87.205.433 | 3.938.886 | 83.266.547 | 0.649731 | 0.029347 | 0.620384 | 2.005393 | 1.917715 | 2.009739 |
28 | 268.435.456 | 174.836.181 | 7.564.041 | 167.272.140 | 0.651316 | 0.028178 | 0.623137 | 2.004877 | 1.920350 | 2.008876 |
29 | 536.870.912 | 350.465.918 | 14.552.111 | 335.913.807 | 0.652794 | 0.027105 | 0.625688 | 2.004539 | 1.923854 | 2.008187 |
30 | 1.073.741.824 | 702.416.581 | 28.033.257 | 674.383.324 | 0.654176 | 0.026108 | 0.628068 | 2.004236 | 1.926405 | 2.007608 |
31 | 2.147.483.648 | 1.407.592.471 | 54.093.178 | 1.353.499.293 | 0.655461 | 0.025189 | 0.630272 | 2.003928 | 1.929607 | 2.007018 |
32 | 4.294.967.296 | 2.820.363.049 | 104.487.193 | 2.715.875.856 | 0.656667 | 0.024328 | 0.632339 | 2.003679 | 1.931615 | 2.006559 |
33 | 8.589.934.592 | 5.650.432.154 | 202.082.351 | 5.448.349.803 | 0.657797 | 0.023525 | 0.634271 | 2.003441 | 1.934039 | 2.006111 |
34 | 17.179.869.184 | 11.319.150.212 | 391.259.397 | 10.927.890.815 | 0.658861 | 0.022774 | 0.636087 | 2.003236 | 1.936138 | 2.005725 |
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 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 0 | 1 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 1 | 1 | 0 | 1 | 1 | 1 |
4 | 16 | 5 | 2 | 2 | 1 | 1 | 2 | 1 |
5 | 32 | 7 | 4 | 2 | 2 | 1 | 3 | 1 |
6 | 64 | 8 | 5 | 2 | 3 | 1 | 3 | 1 |
7 | 128 | 13 | 7 | 5 | 3 | 3 | 3 | 4 |
8 | 256 | 26 | 12 | 13 | 3 | 7 | 6 | 10 |
9 | 512 | 47 | 21 | 25 | 6 | 15 | 10 | 16 |
10 | 1.024 | 91 | 40 | 50 | 14 | 30 | 15 | 32 |
11 | 2.048 | 170 | 70 | 99 | 20 | 53 | 31 | 66 |
12 | 4.096 | 325 | 129 | 195 | 38 | 112 | 55 | 120 |
13 | 8.192 | 575 | 218 | 356 | 75 | 205 | 86 | 209 |
14 | 16.384 | 1.045 | 386 | 658 | 142 | 361 | 147 | 395 |
15 | 32.768 | 1.931 | 685 | 1.245 | 272 | 676 | 263 | 720 |
16 | 65.536 | 3.558 | 1.270 | 2.287 | 492 | 1.267 | 470 | 1.329 |
17 | 131.072 | 6.569 | 2.321 | 4.247 | 904 | 2.367 | 849 | 2.449 |
18 | 262.144 | 12.280 | 4.295 | 7.984 | 1.678 | 4.445 | 1.580 | 4.577 |
19 | 524.288 | 23.027 | 8.043 | 14.983 | 3.095 | 8.357 | 3.043 | 8.532 |
20 | 1.048.576 | 43.230 | 15.050 | 28.179 | 5.799 | 15.831 | 5.676 | 15.924 |
21 | 2.097.152 | 81.765 | 28.503 | 53.261 | 10.880 | 30.028 | 10.760 | 30.097 |
22 | 4.194.304 | 155.041 | 53.934 | 101.106 | 20.486 | 57.079 | 20.369 | 57.107 |
23 | 8.388.608 | 294.432 | 102.141 | 192.290 | 38.785 | 108.440 | 38.604 | 108.603 |
24 | 16.777.216 | 561.799 | 194.433 | 367.365 | 73.771 | 207.328 | 73.435 | 207.265 |
25 | 33.554.432 | 1.072.844 | 370.769 | 702.074 | 140.582 | 396.370 | 140.410 | 395.482 |
26 | 67.108.864 | 2.053.948 | 708.723 | 1.345.224 | 267.774 | 759.885 | 267.706 | 758.583 |
27 | 134.217.728 | 3.938.886 | 1.357.349 | 2.581.536 | 512.600 | 1.457.363 | 512.512 | 1.456.411 |
28 | 268.435.456 | 7.564.041 | 2.603.727 | 4.960.313 | 982.413 | 2.799.908 | 982.633 | 2.799.087 |
29 | 536.870.912 | 14.552.111 | 5.002.087 | 9.550.023 | 1.887.645 | 5.387.675 | 1.888.488 | 5.388.303 |
30 | 1.073.741.824 | 28.033.257 | 9.628.056 | 18.405.200 | 3.632.622 | 10.383.703 | 3.632.919 | 10.384.013 |
31 | 2.147.483.648 | 54.093.178 | 18.558.471 | 35.534.706 | 7.000.323 | 20.041.414 | 7.001.908 | 20.049.533 |
32 | 4.294.967.296 | 104.487.193 | 35.813.837 | 68.673.355 | 13.508.287 | 38.730.316 | 13.511.964 | 38.736.626 |
33 | 8.589.934.592 | 202.082.351 | 69.200.449 | 132.881.901 | 26.100.291 | 74.937.543 | 26.099.647 | 74.944.870 |
34 | 17.179.869.184 | 391.259.397 | 133.863.793 | 257.395.603 | 50.480.486 | 145.150.888 | 50.479.997 | 145.148.026 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 2 | 1 | 1 | 1 | 0 | 0 | 1 |
4 | 16 | 4 | 2 | 2 | 1 | 1 | 0 | 2 |
5 | 32 | 9 | 5 | 4 | 2 | 2 | 1 | 4 |
6 | 64 | 10 | 5 | 5 | 2 | 3 | 1 | 4 |
7 | 128 | 21 | 10 | 11 | 5 | 6 | 3 | 7 |
8 | 256 | 72 | 33 | 39 | 24 | 17 | 12 | 19 |
9 | 512 | 190 | 104 | 86 | 50 | 47 | 52 | 41 |
10 | 1.024 | 432 | 223 | 209 | 116 | 108 | 115 | 93 |
11 | 2.048 | 955 | 489 | 466 | 270 | 214 | 245 | 226 |
12 | 4.096 | 2.013 | 1.016 | 997 | 549 | 458 | 540 | 466 |
13 | 8.192 | 4.264 | 2.138 | 2.126 | 1.123 | 1.019 | 1.136 | 986 |
14 | 16.384 | 8.797 | 4.393 | 4.404 | 2.273 | 2.101 | 2.334 | 2.089 |
15 | 32.768 | 18.081 | 9.114 | 8.967 | 4.680 | 4.306 | 4.817 | 4.278 |
16 | 65.536 | 36.871 | 18.526 | 18.345 | 9.669 | 8.749 | 9.750 | 8.703 |
17 | 131.072 | 74.965 | 37.842 | 37.123 | 19.575 | 17.867 | 19.679 | 17.844 |
18 | 262.144 | 151.865 | 76.663 | 75.202 | 39.411 | 36.423 | 39.718 | 36.313 |
19 | 524.288 | 307.505 | 155.087 | 152.418 | 79.540 | 73.976 | 80.015 | 73.974 |
20 | 1.048.576 | 621.250 | 313.154 | 308.096 | 160.668 | 149.635 | 160.850 | 150.097 |
21 | 2.097.152 | 1.253.963 | 631.696 | 622.267 | 323.868 | 302.593 | 323.854 | 303.648 |
22 | 4.194.304 | 2.527.140 | 1.272.189 | 1.254.951 | 650.951 | 611.230 | 651.890 | 613.069 |
23 | 8.388.608 | 5.090.442 | 2.562.866 | 2.527.576 | 1.309.545 | 1.234.827 | 1.310.008 | 1.236.062 |
24 | 16.777.216 | 10.245.508 | 5.157.103 | 5.088.405 | 2.632.653 | 2.490.801 | 2.631.278 | 2.490.776 |
25 | 33.554.432 | 20.608.329 | 10.367.930 | 10.240.399 | 5.288.245 | 5.016.834 | 5.288.704 | 5.014.546 |
26 | 67.108.864 | 41.431.513 | 20.834.794 | 20.596.719 | 10.619.970 | 10.100.546 | 10.614.145 | 10.096.852 |
27 | 134.217.728 | 83.266.547 | 41.862.104 | 41.404.443 | 21.318.621 | 20.322.615 | 21.309.328 | 20.315.983 |
28 | 268.435.456 | 167.272.140 | 84.073.743 | 83.198.397 | 42.776.079 | 40.868.608 | 42.772.780 | 40.854.673 |
29 | 536.870.912 | 335.913.807 | 168.803.413 | 167.110.394 | 85.826.133 | 82.144.198 | 85.812.599 | 82.130.877 |
30 | 1.073.741.824 | 674.383.324 | 338.815.374 | 335.567.950 | 172.139.198 | 165.068.809 | 172.118.606 | 165.056.711 |
31 | 2.147.483.648 | 1.353.499.293 | 679.898.515 | 673.600.778 | 345.197.671 | 331.558.335 | 345.177.303 | 331.565.984 |
32 | 4.294.967.296 | 2.715.875.856 | 1.364.030.469 | 1.351.845.387 | 692.134.204 | 665.811.738 | 692.107.250 | 665.822.664 |
33 | 8.589.934.592 | 5.448.349.803 | 2.735.948.652 | 2.712.401.151 | 1.387.550.668 | 1.336.610.929 | 1.387.546.407 | 1.336.641.799 |
34 | 17.179.869.184 | 10.927.890.815 | 5.486.673.566 | 5.441.217.249 | 2.781.220.245 | 2.682.705.812 | 2.781.233.125 | 2.682.731.633 |