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+138x-163
f(0)=163
f(1)=3
f(2)=13
f(3)=5
f(4)=1
f(5)=23
f(6)=701
f(7)=71
f(8)=67
f(9)=29
f(10)=439
f(11)=41
f(12)=1637
f(13)=1
f(14)=131
f(15)=1
f(16)=59
f(17)=103
f(18)=1
f(19)=47
f(20)=37
f(21)=397
f(22)=373
f(23)=1
f(24)=149
f(25)=1
f(26)=1367
f(27)=1
f(28)=1
f(29)=1
f(30)=4877
f(31)=1
f(32)=1759
f(33)=137
f(34)=379
f(35)=491
f(36)=6101
f(37)=263
f(38)=1
f(39)=337
f(40)=773
f(41)=1
f(42)=569
f(43)=127
f(44)=523
f(45)=1009
f(46)=2767
f(47)=79
f(48)=1753
f(49)=1
f(50)=3079
f(51)=1
f(52)=1
f(53)=83
f(54)=157
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=191
f(60)=11717
f(61)=499
f(62)=4079
f(63)=1
f(64)=1
f(65)=181
f(66)=283
f(67)=1
f(68)=1
f(69)=353
f(70)=4799
f(71)=1223
f(72)=14957
f(73)=1
f(74)=1
f(75)=1
f(76)=1789
f(77)=683
f(78)=1
f(79)=1
f(80)=443
f(81)=1
f(82)=101
f(83)=1
f(84)=3697
f(85)=1
f(86)=6367
f(87)=211
f(88)=1
f(89)=167
f(90)=20357
f(91)=1723
f(92)=2333
f(93)=1
f(94)=1
f(95)=1831
f(96)=769
f(97)=1
f(98)=1531
f(99)=233
b) Substitution of the polynom
The polynom f(x)=x^2+138x-163 could be written as f(y)= y^2-4924 with x=y-69
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+69
f'(x)>2x+137
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 | 3 | 6 | 0.900000 | 0.300000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 60 | 11 | 49 | 0.600000 | 0.110000 | 0.490000 | 6.666667 | 3.666667 | 8.166667 |
3 | 1.000 | 567 | 83 | 484 | 0.567000 | 0.083000 | 0.484000 | 9.450000 | 7.545455 | 9.877551 |
4 | 10.000 | 6.021 | 594 | 5.427 | 0.602100 | 0.059400 | 0.542700 | 10.619047 | 7.156627 | 11.212810 |
5 | 100.000 | 62.388 | 4.476 | 57.912 | 0.623880 | 0.044760 | 0.579120 | 10.361734 | 7.535354 | 10.671089 |
6 | 1.000.000 | 635.470 | 36.203 | 599.267 | 0.635470 | 0.036203 | 0.599267 | 10.185773 | 8.088248 | 10.347890 |
7 | 10.000.000 | 6.441.777 | 305.804 | 6.135.973 | 0.644178 | 0.030580 | 0.613597 | 10.137028 | 8.446924 | 10.239130 |
8 | 100.000.000 | 65.052.901 | 2.639.564 | 62.413.337 | 0.650529 | 0.026396 | 0.624133 | 10.098596 | 8.631555 | 10.171710 |
9 | 1.000.000.000 | 655.389.285 | 23.207.198 | 632.182.087 | 0.655389 | 0.023207 | 0.632182 | 10.074713 | 8.792057 | 10.128959 |
10 | 10.000.000.000 | 6.592.538.399 | 207.178.835 | 6.385.359.564 | 0.659254 | 0.020718 | 0.638536 | 10.058966 | 8.927352 | 10.100507 |
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 | 7 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 2.333333 | 1.500000 | 4.000000 |
4 | 16 | 13 | 4 | 9 | 0.812500 | 0.250000 | 0.562500 | 1.857143 | 1.333333 | 2.250000 |
5 | 32 | 21 | 6 | 15 | 0.656250 | 0.187500 | 0.468750 | 1.615385 | 1.500000 | 1.666667 |
6 | 64 | 40 | 9 | 31 | 0.625000 | 0.140625 | 0.484375 | 1.904762 | 1.500000 | 2.066667 |
7 | 128 | 77 | 15 | 62 | 0.601562 | 0.117188 | 0.484375 | 1.925000 | 1.666667 | 2.000000 |
8 | 256 | 142 | 28 | 114 | 0.554688 | 0.109375 | 0.445312 | 1.844156 | 1.866667 | 1.838710 |
9 | 512 | 286 | 48 | 238 | 0.558594 | 0.093750 | 0.464844 | 2.014085 | 1.714286 | 2.087719 |
10 | 1.024 | 582 | 86 | 496 | 0.568359 | 0.083984 | 0.484375 | 2.034965 | 1.791667 | 2.084034 |
11 | 2.048 | 1.189 | 150 | 1.039 | 0.580566 | 0.073242 | 0.507324 | 2.042955 | 1.744186 | 2.094758 |
12 | 4.096 | 2.410 | 275 | 2.135 | 0.588379 | 0.067139 | 0.521240 | 2.026913 | 1.833333 | 2.054860 |
13 | 8.192 | 4.905 | 503 | 4.402 | 0.598755 | 0.061401 | 0.537354 | 2.035270 | 1.829091 | 2.061827 |
14 | 16.384 | 9.977 | 907 | 9.070 | 0.608948 | 0.055359 | 0.553589 | 2.034047 | 1.803181 | 2.060427 |
15 | 32.768 | 20.160 | 1.656 | 18.504 | 0.615234 | 0.050537 | 0.564697 | 2.020648 | 1.825799 | 2.040132 |
16 | 65.536 | 40.670 | 3.090 | 37.580 | 0.620575 | 0.047150 | 0.573425 | 2.017361 | 1.865942 | 2.030912 |
17 | 131.072 | 81.955 | 5.695 | 76.260 | 0.625267 | 0.043449 | 0.581818 | 2.015122 | 1.843042 | 2.029271 |
18 | 262.144 | 164.886 | 10.656 | 154.230 | 0.628990 | 0.040649 | 0.588341 | 2.011909 | 1.871115 | 2.022423 |
19 | 524.288 | 331.655 | 20.137 | 311.518 | 0.632582 | 0.038408 | 0.594173 | 2.011420 | 1.889733 | 2.019828 |
20 | 1.048.576 | 666.639 | 37.813 | 628.826 | 0.635756 | 0.036061 | 0.599695 | 2.010037 | 1.877787 | 2.018586 |
21 | 2.097.152 | 1.339.513 | 71.590 | 1.267.923 | 0.638730 | 0.034137 | 0.604593 | 2.009353 | 1.893264 | 2.016334 |
22 | 4.194.304 | 2.689.938 | 136.221 | 2.553.717 | 0.641331 | 0.032478 | 0.608854 | 2.008146 | 1.902794 | 2.014095 |
23 | 8.388.608 | 5.398.800 | 259.564 | 5.139.236 | 0.643587 | 0.030942 | 0.612645 | 2.007035 | 1.905463 | 2.012453 |
24 | 16.777.216 | 10.834.385 | 495.107 | 10.339.278 | 0.645780 | 0.029511 | 0.616269 | 2.006814 | 1.907456 | 2.011832 |
25 | 33.554.432 | 21.735.531 | 946.952 | 20.788.579 | 0.647769 | 0.028221 | 0.619548 | 2.006162 | 1.912621 | 2.010641 |
26 | 67.108.864 | 43.589.143 | 1.814.535 | 41.774.608 | 0.649529 | 0.027039 | 0.622490 | 2.005433 | 1.916185 | 2.009498 |
27 | 134.217.728 | 87.404.937 | 3.481.513 | 83.923.424 | 0.651218 | 0.025939 | 0.625278 | 2.005200 | 1.918681 | 2.008958 |
28 | 268.435.456 | 175.223.326 | 6.687.937 | 168.535.389 | 0.652758 | 0.024915 | 0.627843 | 2.004730 | 1.920986 | 2.008204 |
29 | 536.870.912 | 351.212.293 | 12.875.760 | 338.336.533 | 0.654184 | 0.023983 | 0.630201 | 2.004369 | 1.925221 | 2.007510 |
30 | 1.073.741.824 | 703.864.287 | 24.826.129 | 679.038.158 | 0.655525 | 0.023121 | 0.632404 | 2.004099 | 1.928129 | 2.006990 |
31 | 2.147.483.648 | 1.410.399.799 | 47.927.179 | 1.362.472.620 | 0.656769 | 0.022318 | 0.634451 | 2.003795 | 1.930514 | 2.006474 |
32 | 4.294.967.296 | 2.825.797.946 | 92.629.499 | 2.733.168.447 | 0.657932 | 0.021567 | 0.636365 | 2.003544 | 1.932713 | 2.006036 |
33 | 8.589.934.592 | 5.660.972.620 | 179.231.429 | 5.481.741.191 | 0.659024 | 0.020865 | 0.638159 | 2.003318 | 1.934928 | 2.005636 |
34 | 17.179.869.184 | 11.339.584.279 | 347.167.553 | 10.992.416.726 | 0.660051 | 0.020208 | 0.639843 | 2.003116 | 1.936979 | 2.005278 |
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 | 1 | 0 | 0 | 2 | 0 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
4 | 16 | 4 | 1 | 2 | 0 | 2 | 2 | 0 |
5 | 32 | 6 | 2 | 3 | 0 | 2 | 4 | 0 |
6 | 64 | 9 | 3 | 5 | 1 | 2 | 6 | 0 |
7 | 128 | 15 | 5 | 9 | 2 | 2 | 11 | 0 |
8 | 256 | 28 | 7 | 20 | 4 | 2 | 22 | 0 |
9 | 512 | 48 | 11 | 36 | 10 | 2 | 36 | 0 |
10 | 1.024 | 86 | 22 | 63 | 20 | 2 | 64 | 0 |
11 | 2.048 | 150 | 35 | 114 | 36 | 2 | 112 | 0 |
12 | 4.096 | 275 | 67 | 207 | 75 | 2 | 198 | 0 |
13 | 8.192 | 503 | 131 | 371 | 132 | 2 | 369 | 0 |
14 | 16.384 | 907 | 250 | 656 | 235 | 2 | 670 | 0 |
15 | 32.768 | 1.656 | 453 | 1.202 | 422 | 2 | 1.232 | 0 |
16 | 65.536 | 3.090 | 827 | 2.262 | 793 | 2 | 2.295 | 0 |
17 | 131.072 | 5.695 | 1.501 | 4.193 | 1.474 | 2 | 4.219 | 0 |
18 | 262.144 | 10.656 | 2.800 | 7.855 | 2.753 | 2 | 7.901 | 0 |
19 | 524.288 | 20.137 | 5.324 | 14.812 | 5.217 | 2 | 14.918 | 0 |
20 | 1.048.576 | 37.813 | 9.900 | 27.912 | 9.757 | 2 | 28.054 | 0 |
21 | 2.097.152 | 71.590 | 18.743 | 52.846 | 18.454 | 2 | 53.134 | 0 |
22 | 4.194.304 | 136.221 | 35.618 | 100.602 | 35.178 | 2 | 101.041 | 0 |
23 | 8.388.608 | 259.564 | 67.958 | 191.605 | 66.877 | 2 | 192.685 | 0 |
24 | 16.777.216 | 495.107 | 129.294 | 365.812 | 127.328 | 2 | 367.777 | 0 |
25 | 33.554.432 | 946.952 | 246.503 | 700.448 | 243.753 | 2 | 703.197 | 0 |
26 | 67.108.864 | 1.814.535 | 471.433 | 1.343.101 | 465.722 | 2 | 1.348.811 | 0 |
27 | 134.217.728 | 3.481.513 | 902.347 | 2.579.165 | 891.853 | 2 | 2.589.658 | 0 |
28 | 268.435.456 | 6.687.937 | 1.730.033 | 4.957.903 | 1.712.129 | 2 | 4.975.806 | 0 |
29 | 536.870.912 | 12.875.760 | 3.325.155 | 9.550.604 | 3.292.485 | 2 | 9.583.273 | 0 |
30 | 1.073.741.824 | 24.826.129 | 6.402.841 | 18.423.287 | 6.343.680 | 2 | 18.482.447 | 0 |
31 | 2.147.483.648 | 47.927.179 | 12.347.524 | 35.579.654 | 12.239.228 | 2 | 35.687.949 | 0 |
32 | 4.294.967.296 | 92.629.499 | 23.841.762 | 68.787.736 | 23.638.463 | 2 | 68.991.034 | 0 |
33 | 8.589.934.592 | 179.231.429 | 46.093.649 | 133.137.779 | 45.714.248 | 2 | 133.517.179 | 0 |
34 | 17.179.869.184 | 347.167.553 | 89.212.671 | 257.954.881 | 88.499.675 | 2 | 258.667.876 | 0 |
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 | 1 | 0 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 1 | 0 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
4 | 16 | 9 | 3 | 6 | 1 | 3 | 2 | 3 |
5 | 32 | 15 | 6 | 9 | 1 | 3 | 4 | 7 |
6 | 64 | 31 | 15 | 16 | 5 | 7 | 6 | 13 |
7 | 128 | 62 | 31 | 31 | 11 | 18 | 10 | 23 |
8 | 256 | 114 | 54 | 60 | 23 | 31 | 20 | 40 |
9 | 512 | 238 | 123 | 115 | 51 | 65 | 42 | 80 |
10 | 1.024 | 496 | 253 | 243 | 119 | 135 | 89 | 153 |
11 | 2.048 | 1.039 | 526 | 513 | 245 | 277 | 205 | 312 |
12 | 4.096 | 2.135 | 1.109 | 1.026 | 496 | 591 | 423 | 625 |
13 | 8.192 | 4.402 | 2.266 | 2.136 | 1.014 | 1.215 | 896 | 1.277 |
14 | 16.384 | 9.070 | 4.618 | 4.452 | 2.124 | 2.423 | 1.944 | 2.579 |
15 | 32.768 | 18.504 | 9.396 | 9.108 | 4.368 | 4.915 | 3.986 | 5.235 |
16 | 65.536 | 37.580 | 19.228 | 18.352 | 8.943 | 9.862 | 8.182 | 10.593 |
17 | 131.072 | 76.260 | 38.964 | 37.296 | 18.243 | 19.877 | 16.802 | 21.338 |
18 | 262.144 | 154.230 | 78.653 | 75.577 | 36.837 | 40.115 | 34.311 | 42.967 |
19 | 524.288 | 311.518 | 158.409 | 153.109 | 74.482 | 80.848 | 70.180 | 86.008 |
20 | 1.048.576 | 628.826 | 319.058 | 309.768 | 151.059 | 162.714 | 142.937 | 172.116 |
21 | 2.097.152 | 1.267.923 | 642.596 | 625.327 | 305.132 | 327.127 | 290.099 | 345.565 |
22 | 4.194.304 | 2.553.717 | 1.293.871 | 1.259.846 | 617.150 | 657.570 | 586.705 | 692.292 |
23 | 8.388.608 | 5.139.236 | 2.602.323 | 2.536.913 | 1.245.246 | 1.319.181 | 1.187.587 | 1.387.222 |
24 | 16.777.216 | 10.339.278 | 5.230.556 | 5.108.722 | 2.511.197 | 2.648.645 | 2.399.399 | 2.780.037 |
25 | 33.554.432 | 20.788.579 | 10.510.497 | 10.278.082 | 5.056.033 | 5.318.638 | 4.844.299 | 5.569.609 |
26 | 67.108.864 | 41.774.608 | 21.109.083 | 20.665.525 | 10.173.417 | 10.679.207 | 9.764.866 | 11.157.118 |
27 | 134.217.728 | 83.923.424 | 42.390.337 | 41.533.087 | 20.461.409 | 21.430.838 | 19.680.379 | 22.350.798 |
28 | 268.435.456 | 168.535.389 | 85.098.858 | 83.436.531 | 41.144.706 | 42.991.810 | 39.638.037 | 44.760.836 |
29 | 536.870.912 | 338.336.533 | 170.773.907 | 167.562.626 | 82.690.127 | 86.224.566 | 79.778.506 | 89.643.334 |
30 | 1.073.741.824 | 679.038.158 | 342.635.183 | 336.402.975 | 166.134.268 | 172.910.082 | 160.482.707 | 179.511.101 |
31 | 2.147.483.648 | 1.362.472.620 | 687.263.794 | 675.208.826 | 333.633.772 | 346.668.918 | 322.745.662 | 359.424.268 |
32 | 4.294.967.296 | 2.733.168.447 | 1.378.214.509 | 1.354.953.938 | 669.831.696 | 694.936.889 | 648.784.137 | 719.615.725 |
33 | 8.589.934.592 | 5.481.741.191 | 2.763.442.887 | 2.718.298.304 | 1.344.441.179 | 1.392.893.501 | 1.303.696.736 | 1.440.709.775 |
34 | 17.179.869.184 | 10.992.416.726 | 5.539.903.671 | 5.452.513.055 | 2.697.807.180 | 2.791.478.167 | 2.618.994.096 | 2.884.137.283 |