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-78x+83
f(0)=83
f(1)=3
f(2)=23
f(3)=71
f(4)=1
f(5)=47
f(6)=349
f(7)=1
f(8)=53
f(9)=269
f(10)=199
f(11)=109
f(12)=709
f(13)=127
f(14)=271
f(15)=431
f(16)=101
f(17)=1
f(18)=997
f(19)=173
f(20)=359
f(21)=557
f(22)=383
f(23)=197
f(24)=1213
f(25)=1
f(26)=1
f(27)=647
f(28)=439
f(29)=223
f(30)=59
f(31)=229
f(32)=463
f(33)=701
f(34)=157
f(35)=79
f(36)=1429
f(37)=239
f(38)=479
f(39)=719
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)=1
f(79)=1
f(80)=1
f(81)=163
f(82)=137
f(83)=1
f(84)=587
f(85)=113
f(86)=257
f(87)=433
f(88)=107
f(89)=1
f(90)=1163
f(91)=211
f(92)=457
f(93)=739
f(94)=1
f(95)=283
f(96)=1811
f(97)=1
f(98)=227
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-78x+83 could be written as f(y)= y^2-1438 with x=y+39
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-39
f'(x)>2x-79 with x > 38
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 | 5 | 4 | 0.900000 | 0.500000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 46 | 20 | 26 | 0.460000 | 0.200000 | 0.460000 | 5.111111 | 4.000000 | 6.500000 |
3 | 1.000 | 682 | 172 | 510 | 0.682000 | 0.172000 | 0.682000 | 14.826087 | 8.600000 | 19.615385 |
4 | 10.000 | 7.224 | 1.275 | 5.949 | 0.722400 | 0.127500 | 0.722400 | 10.592376 | 7.412791 | 11.664706 |
5 | 100.000 | 71.895 | 9.798 | 62.097 | 0.718950 | 0.097980 | 0.718950 | 9.952243 | 7.684706 | 10.438225 |
6 | 1.000.000 | 715.044 | 79.296 | 635.748 | 0.715044 | 0.079296 | 0.715044 | 9.945671 | 8.093081 | 10.237983 |
7 | 10.000.000 | 7.116.393 | 668.138 | 6.448.255 | 0.711639 | 0.066814 | 0.711639 | 9.952385 | 8.425873 | 10.142784 |
8 | 100.000.000 | 70.912.488 | 5.785.009 | 65.127.479 | 0.709125 | 0.057850 | 0.709125 | 9.964667 | 8.658404 | 10.100017 |
9 | 1.000.000.000 | 707.170.973 | 50.992.742 | 656.178.231 | 0.707171 | 0.050993 | 0.707171 | 9.972445 | 8.814635 | 10.075290 |
10 | 10.000.000.000 | 7.056.350.773 | 455.850.709 | 6.600.500.064 | 0.705635 | 0.045585 | 0.705635 | 9.978281 | 8.939521 | 10.059005 |
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 | 4 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.750000 | 1.333333 | 3.000000 |
4 | 16 | 15 | 7 | 8 | 0.937500 | 0.437500 | 0.500000 | 2.142857 | 1.750000 | 2.666667 |
5 | 32 | 27 | 11 | 16 | 0.843750 | 0.343750 | 0.500000 | 1.800000 | 1.571429 | 2.000000 |
6 | 64 | 34 | 14 | 20 | 0.531250 | 0.218750 | 0.312500 | 1.259259 | 1.272727 | 1.250000 |
7 | 128 | 67 | 25 | 42 | 0.523438 | 0.195312 | 0.328125 | 1.970588 | 1.785714 | 2.100000 |
8 | 256 | 162 | 52 | 110 | 0.632812 | 0.203125 | 0.429688 | 2.417910 | 2.080000 | 2.619048 |
9 | 512 | 340 | 100 | 240 | 0.664062 | 0.195312 | 0.468750 | 2.098765 | 1.923077 | 2.181818 |
10 | 1.024 | 702 | 175 | 527 | 0.685547 | 0.170898 | 0.514648 | 2.064706 | 1.750000 | 2.195833 |
11 | 2.048 | 1.458 | 328 | 1.130 | 0.711914 | 0.160156 | 0.551758 | 2.076923 | 1.874286 | 2.144212 |
12 | 4.096 | 2.954 | 584 | 2.370 | 0.721191 | 0.142578 | 0.578613 | 2.026063 | 1.780488 | 2.097345 |
13 | 8.192 | 5.916 | 1.081 | 4.835 | 0.722168 | 0.131958 | 0.590210 | 2.002708 | 1.851027 | 2.040084 |
14 | 16.384 | 11.847 | 1.942 | 9.905 | 0.723083 | 0.118530 | 0.604553 | 2.002536 | 1.796485 | 2.048604 |
15 | 32.768 | 23.635 | 3.585 | 20.050 | 0.721283 | 0.109406 | 0.611877 | 1.995020 | 1.846035 | 2.024230 |
16 | 65.536 | 47.152 | 6.688 | 40.464 | 0.719482 | 0.102051 | 0.617432 | 1.995007 | 1.865551 | 2.018155 |
17 | 131.072 | 94.222 | 12.457 | 81.765 | 0.718857 | 0.095039 | 0.623817 | 1.998261 | 1.862590 | 2.020685 |
18 | 262.144 | 188.119 | 23.215 | 164.904 | 0.717617 | 0.088558 | 0.629059 | 1.996551 | 1.863611 | 2.016804 |
19 | 524.288 | 375.541 | 43.754 | 331.787 | 0.716288 | 0.083454 | 0.632833 | 1.996295 | 1.884730 | 2.012001 |
20 | 1.048.576 | 749.766 | 82.903 | 666.863 | 0.715033 | 0.079062 | 0.635970 | 1.996496 | 1.894753 | 2.009913 |
21 | 2.097.152 | 1.496.853 | 156.999 | 1.339.854 | 0.713755 | 0.074863 | 0.638892 | 1.996427 | 1.893767 | 2.009189 |
22 | 4.194.304 | 2.989.708 | 297.994 | 2.691.714 | 0.712802 | 0.071047 | 0.641755 | 1.997329 | 1.898063 | 2.008961 |
23 | 8.388.608 | 5.971.279 | 567.166 | 5.404.113 | 0.711832 | 0.067611 | 0.644220 | 1.997278 | 1.903280 | 2.007685 |
24 | 16.777.216 | 11.928.975 | 1.082.918 | 10.846.057 | 0.711022 | 0.064547 | 0.646475 | 1.997725 | 1.909349 | 2.007000 |
25 | 33.554.432 | 23.833.084 | 2.073.116 | 21.759.968 | 0.710281 | 0.061784 | 0.648498 | 1.997916 | 1.914379 | 2.006256 |
26 | 67.108.864 | 47.614.689 | 3.974.823 | 43.639.866 | 0.709514 | 0.059229 | 0.650285 | 1.997840 | 1.917318 | 2.005512 |
27 | 134.217.728 | 95.138.609 | 7.632.432 | 87.506.177 | 0.708838 | 0.056866 | 0.651972 | 1.998094 | 1.920194 | 2.005189 |
28 | 268.435.456 | 190.110.388 | 14.682.491 | 175.427.897 | 0.708216 | 0.054697 | 0.653520 | 1.998246 | 1.923698 | 2.004749 |
29 | 536.870.912 | 379.916.503 | 28.282.702 | 351.633.801 | 0.707650 | 0.052681 | 0.654969 | 1.998400 | 1.926288 | 2.004435 |
30 | 1.073.741.824 | 759.262.068 | 54.551.380 | 704.710.688 | 0.707118 | 0.050805 | 0.656313 | 1.998497 | 1.928789 | 2.004104 |
31 | 2.147.483.648 | 1.517.461.530 | 105.352.879 | 1.412.108.651 | 0.706623 | 0.049059 | 0.657564 | 1.998600 | 1.931260 | 2.003814 |
32 | 4.294.967.296 | 3.032.945.205 | 203.713.413 | 2.829.231.792 | 0.706163 | 0.047431 | 0.658732 | 1.998697 | 1.933629 | 2.003551 |
33 | 8.589.934.592 | 6.062.137.343 | 394.325.309 | 5.667.812.034 | 0.705726 | 0.045906 | 0.659820 | 1.998763 | 1.935687 | 2.003304 |
34 | 17.179.869.184 | 12.117.314.062 | 764.110.604 | 11.353.203.458 | 0.705321 | 0.044477 | 0.660843 | 1.998852 | 1.937767 | 2.003102 |
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 | 2 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 0 | 2 | 0 | 1 |
3 | 8 | 4 | 1 | 2 | 0 | 2 | 1 | 1 |
4 | 16 | 7 | 2 | 4 | 0 | 2 | 3 | 2 |
5 | 32 | 11 | 4 | 6 | 0 | 2 | 6 | 3 |
6 | 64 | 14 | 5 | 8 | 0 | 2 | 8 | 4 |
7 | 128 | 25 | 10 | 14 | 2 | 11 | 8 | 4 |
8 | 256 | 52 | 24 | 27 | 9 | 31 | 8 | 4 |
9 | 512 | 100 | 49 | 50 | 24 | 64 | 8 | 4 |
10 | 1.024 | 175 | 89 | 85 | 42 | 121 | 8 | 4 |
11 | 2.048 | 328 | 161 | 166 | 76 | 240 | 8 | 4 |
12 | 4.096 | 584 | 298 | 285 | 146 | 426 | 8 | 4 |
13 | 8.192 | 1.081 | 558 | 522 | 275 | 794 | 8 | 4 |
14 | 16.384 | 1.942 | 987 | 954 | 496 | 1.434 | 8 | 4 |
15 | 32.768 | 3.585 | 1.816 | 1.768 | 925 | 2.648 | 8 | 4 |
16 | 65.536 | 6.688 | 3.410 | 3.277 | 1.696 | 4.980 | 8 | 4 |
17 | 131.072 | 12.457 | 6.337 | 6.119 | 3.148 | 9.297 | 8 | 4 |
18 | 262.144 | 23.215 | 11.791 | 11.423 | 5.860 | 17.343 | 8 | 4 |
19 | 524.288 | 43.754 | 22.291 | 21.462 | 11.130 | 32.612 | 8 | 4 |
20 | 1.048.576 | 82.903 | 42.145 | 40.757 | 20.964 | 61.927 | 8 | 4 |
21 | 2.097.152 | 156.999 | 79.515 | 77.483 | 39.588 | 117.399 | 8 | 4 |
22 | 4.194.304 | 297.994 | 150.763 | 147.230 | 75.209 | 222.773 | 8 | 4 |
23 | 8.388.608 | 567.166 | 287.029 | 280.136 | 143.306 | 423.848 | 8 | 4 |
24 | 16.777.216 | 1.082.918 | 547.960 | 534.957 | 273.761 | 809.145 | 8 | 4 |
25 | 33.554.432 | 2.073.116 | 1.048.114 | 1.025.001 | 523.355 | 1.549.749 | 8 | 4 |
26 | 67.108.864 | 3.974.823 | 2.008.624 | 1.966.198 | 1.003.958 | 2.970.853 | 8 | 4 |
27 | 134.217.728 | 7.632.432 | 3.855.444 | 3.776.987 | 1.927.556 | 5.704.864 | 8 | 4 |
28 | 268.435.456 | 14.682.491 | 7.413.014 | 7.269.476 | 3.706.838 | 10.975.641 | 8 | 4 |
29 | 536.870.912 | 28.282.702 | 14.272.087 | 14.010.614 | 7.134.680 | 21.148.010 | 8 | 4 |
30 | 1.073.741.824 | 54.551.380 | 27.516.609 | 27.034.770 | 13.755.982 | 40.795.386 | 8 | 4 |
31 | 2.147.483.648 | 105.352.879 | 53.126.087 | 52.226.791 | 26.560.326 | 78.792.541 | 8 | 4 |
32 | 4.294.967.296 | 203.713.413 | 102.702.225 | 101.011.187 | 51.350.691 | 152.362.710 | 8 | 4 |
33 | 8.589.934.592 | 394.325.309 | 198.744.874 | 195.580.434 | 99.369.084 | 294.956.213 | 8 | 4 |
34 | 17.179.869.184 | 764.110.604 | 385.019.268 | 379.091.335 | 192.508.128 | 571.602.464 | 8 | 4 |
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 | 0 | 1 | 0 | 0 | 0 | 1 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
3 | 8 | 3 | 0 | 3 | 0 | 0 | 1 | 2 |
4 | 16 | 8 | 4 | 4 | 0 | 0 | 3 | 5 |
5 | 32 | 16 | 8 | 8 | 0 | 0 | 6 | 10 |
6 | 64 | 20 | 10 | 10 | 0 | 0 | 7 | 13 |
7 | 128 | 42 | 23 | 19 | 13 | 9 | 7 | 13 |
8 | 256 | 110 | 56 | 54 | 50 | 35 | 11 | 14 |
9 | 512 | 240 | 124 | 116 | 118 | 74 | 21 | 27 |
10 | 1.024 | 527 | 259 | 268 | 246 | 160 | 58 | 63 |
11 | 2.048 | 1.130 | 565 | 565 | 492 | 315 | 170 | 153 |
12 | 4.096 | 2.370 | 1.165 | 1.205 | 949 | 656 | 391 | 374 |
13 | 8.192 | 4.835 | 2.412 | 2.423 | 1.864 | 1.343 | 823 | 805 |
14 | 16.384 | 9.905 | 4.959 | 4.946 | 3.647 | 2.709 | 1.760 | 1.789 |
15 | 32.768 | 20.050 | 10.074 | 9.976 | 7.211 | 5.468 | 3.706 | 3.665 |
16 | 65.536 | 40.464 | 20.238 | 20.226 | 14.265 | 10.827 | 7.641 | 7.731 |
17 | 131.072 | 81.765 | 40.851 | 40.914 | 27.998 | 21.910 | 15.905 | 15.952 |
18 | 262.144 | 164.904 | 82.377 | 82.527 | 55.518 | 43.750 | 32.728 | 32.908 |
19 | 524.288 | 331.787 | 165.781 | 166.006 | 109.716 | 87.700 | 67.131 | 67.240 |
20 | 1.048.576 | 666.863 | 333.253 | 333.610 | 217.717 | 175.777 | 136.783 | 136.586 |
21 | 2.097.152 | 1.339.854 | 669.821 | 670.033 | 431.764 | 352.555 | 277.840 | 277.695 |
22 | 4.194.304 | 2.691.714 | 1.345.152 | 1.346.562 | 857.408 | 705.321 | 564.282 | 564.703 |
23 | 8.388.608 | 5.404.113 | 2.700.712 | 2.703.401 | 1.701.518 | 1.412.213 | 1.144.942 | 1.145.440 |
24 | 16.777.216 | 10.846.057 | 5.422.625 | 5.423.432 | 3.379.196 | 2.829.325 | 2.317.943 | 2.319.593 |
25 | 33.554.432 | 21.759.968 | 10.876.529 | 10.883.439 | 6.715.350 | 5.667.645 | 4.686.499 | 4.690.474 |
26 | 67.108.864 | 43.639.866 | 21.816.306 | 21.823.560 | 13.356.443 | 11.347.544 | 9.464.295 | 9.471.584 |
27 | 134.217.728 | 87.506.177 | 43.746.399 | 43.759.778 | 26.577.569 | 22.716.979 | 19.104.629 | 19.107.000 |
28 | 268.435.456 | 175.427.897 | 87.694.976 | 87.732.921 | 52.897.572 | 45.473.791 | 38.526.955 | 38.529.579 |
29 | 536.870.912 | 351.633.801 | 175.785.459 | 175.848.342 | 105.306.628 | 91.025.252 | 77.638.180 | 77.663.741 |
30 | 1.073.741.824 | 704.710.688 | 352.290.977 | 352.419.711 | 209.724.998 | 182.190.982 | 156.366.235 | 156.428.473 |
31 | 2.147.483.648 | 1.412.108.651 | 705.935.424 | 706.173.227 | 417.814.881 | 364.615.908 | 314.782.282 | 314.895.580 |
32 | 4.294.967.296 | 2.829.231.792 | 1.414.369.751 | 1.414.862.041 | 832.572.307 | 729.737.779 | 633.351.818 | 633.569.888 |
33 | 8.589.934.592 | 5.667.812.034 | 2.833.484.046 | 2.834.327.988 | 1.659.387.640 | 1.460.373.504 | 1.273.834.345 | 1.274.216.545 |
34 | 17.179.869.184 | 11.353.203.458 | 5.675.838.383 | 5.677.365.075 | 3.307.955.834 | 2.922.410.098 | 2.561.041.655 | 2.561.795.871 |