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-47x+5
f(0)=5
f(1)=41
f(2)=17
f(3)=127
f(4)=167
f(5)=1
f(6)=241
f(7)=11
f(8)=307
f(9)=337
f(10)=73
f(11)=23
f(12)=83
f(13)=19
f(14)=457
f(15)=1
f(16)=491
f(17)=101
f(18)=47
f(19)=31
f(20)=107
f(21)=541
f(22)=109
f(23)=547
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
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)=53
f(49)=103
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=383
f(55)=89
f(56)=509
f(57)=1
f(58)=643
f(59)=1
f(60)=157
f(61)=859
f(62)=1
f(63)=1013
f(64)=1093
f(65)=1
f(66)=1259
f(67)=269
f(68)=1433
f(69)=1523
f(70)=1
f(71)=1709
f(72)=1
f(73)=173
f(74)=2003
f(75)=421
f(76)=1
f(77)=463
f(78)=2423
f(79)=149
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=283
f(85)=647
f(86)=3359
f(87)=1
f(88)=3613
f(89)=197
f(90)=1
f(91)=211
f(92)=829
f(93)=4283
f(94)=4423
f(95)=1
f(96)=277
f(97)=971
f(98)=5003
f(99)=5153
b) Substitution of the polynom
The polynom f(x)=x^2-47x+5 could be written as f(y)= y^2-547.25 with x=y+23.5
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-23.5
f'(x)>2x-48 with x > 23
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 | 10 | 8 | 2 | 1.000000 | 0.800000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 52 | 31 | 21 | 0.520000 | 0.310000 | 0.520000 | 5.200000 | 3.875000 | 10.500000 |
3 | 1.000 | 665 | 220 | 445 | 0.665000 | 0.220000 | 0.665000 | 12.788462 | 7.096774 | 21.190475 |
4 | 10.000 | 6.953 | 1.512 | 5.441 | 0.695300 | 0.151200 | 0.695300 | 10.455639 | 6.872727 | 12.226966 |
5 | 100.000 | 69.965 | 11.709 | 58.256 | 0.699650 | 0.117090 | 0.699650 | 10.062563 | 7.744048 | 10.706856 |
6 | 1.000.000 | 699.002 | 94.596 | 604.406 | 0.699002 | 0.094596 | 0.699002 | 9.990738 | 8.078914 | 10.375000 |
7 | 10.000.000 | 6.979.222 | 799.328 | 6.179.894 | 0.697922 | 0.079933 | 0.697922 | 9.984552 | 8.449913 | 10.224740 |
8 | 100.000.000 | 69.729.421 | 6.925.571 | 62.803.850 | 0.697294 | 0.069256 | 0.697294 | 9.991002 | 8.664242 | 10.162609 |
9 | 1.000.000.000 | 696.730.113 | 61.130.951 | 635.599.162 | 0.696730 | 0.061131 | 0.696730 | 9.991910 | 8.826846 | 10.120386 |
10 | 10.000.000.000 | 6.962.954.360 | 547.064.800 | 6.415.889.560 | 0.696295 | 0.054706 | 0.696295 | 9.993761 | 8.949064 | 10.094238 |
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 | 5 | 4 | 1 | 1.250000 | 1.000000 | 0.250000 | 1.666667 | 2.000000 | 1.000000 |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.750000 | 1.000000 |
4 | 16 | 14 | 10 | 4 | 0.875000 | 0.625000 | 0.250000 | 1.750000 | 1.428571 | 4.000000 |
5 | 32 | 20 | 12 | 8 | 0.625000 | 0.375000 | 0.250000 | 1.428571 | 1.200000 | 2.000000 |
6 | 64 | 28 | 19 | 9 | 0.437500 | 0.296875 | 0.140625 | 1.400000 | 1.583333 | 1.125000 |
7 | 128 | 70 | 37 | 33 | 0.546875 | 0.289062 | 0.257812 | 2.500000 | 1.947368 | 3.666667 |
8 | 256 | 157 | 62 | 95 | 0.613281 | 0.242188 | 0.371094 | 2.242857 | 1.675676 | 2.878788 |
9 | 512 | 335 | 122 | 213 | 0.654297 | 0.238281 | 0.416016 | 2.133758 | 1.967742 | 2.242105 |
10 | 1.024 | 677 | 223 | 454 | 0.661133 | 0.217773 | 0.443359 | 2.020895 | 1.827869 | 2.131455 |
11 | 2.048 | 1.396 | 386 | 1.010 | 0.681641 | 0.188477 | 0.493164 | 2.062038 | 1.730942 | 2.224670 |
12 | 4.096 | 2.814 | 703 | 2.111 | 0.687012 | 0.171631 | 0.515381 | 2.015759 | 1.821244 | 2.090099 |
13 | 8.192 | 5.686 | 1.271 | 4.415 | 0.694092 | 0.155151 | 0.538940 | 2.020611 | 1.807966 | 2.091426 |
14 | 16.384 | 11.429 | 2.316 | 9.113 | 0.697571 | 0.141357 | 0.556213 | 2.010025 | 1.822187 | 2.064100 |
15 | 32.768 | 22.929 | 4.299 | 18.630 | 0.699738 | 0.131195 | 0.568542 | 2.006212 | 1.856218 | 2.044332 |
16 | 65.536 | 45.833 | 7.987 | 37.846 | 0.699356 | 0.121872 | 0.577484 | 1.998910 | 1.857874 | 2.031455 |
17 | 131.072 | 91.719 | 14.887 | 76.832 | 0.699760 | 0.113579 | 0.586182 | 2.001156 | 1.863904 | 2.030122 |
18 | 262.144 | 183.391 | 27.835 | 155.556 | 0.699581 | 0.106182 | 0.593399 | 1.999488 | 1.869752 | 2.024625 |
19 | 524.288 | 366.730 | 52.098 | 314.632 | 0.699482 | 0.099369 | 0.600113 | 1.999716 | 1.871672 | 2.022629 |
20 | 1.048.576 | 732.911 | 98.807 | 634.104 | 0.698958 | 0.094230 | 0.604729 | 1.998503 | 1.896560 | 2.015383 |
21 | 2.097.152 | 1.465.311 | 187.011 | 1.278.300 | 0.698715 | 0.089174 | 0.609541 | 1.999303 | 1.892690 | 2.015915 |
22 | 4.194.304 | 2.929.018 | 355.607 | 2.573.411 | 0.698332 | 0.084783 | 0.613549 | 1.998905 | 1.901530 | 2.013151 |
23 | 8.388.608 | 5.855.713 | 678.226 | 5.177.487 | 0.698055 | 0.080851 | 0.617205 | 1.999207 | 1.907235 | 2.011916 |
24 | 16.777.216 | 11.707.809 | 1.295.454 | 10.412.355 | 0.697840 | 0.077215 | 0.620625 | 1.999382 | 1.910062 | 2.011083 |
25 | 33.554.432 | 23.406.616 | 2.481.179 | 20.925.437 | 0.697572 | 0.073945 | 0.623627 | 1.999231 | 1.915297 | 2.009674 |
26 | 67.108.864 | 46.802.219 | 4.758.056 | 42.044.163 | 0.697407 | 0.070901 | 0.626507 | 1.999529 | 1.917659 | 2.009237 |
27 | 134.217.728 | 93.577.592 | 9.139.538 | 84.438.054 | 0.697207 | 0.068095 | 0.629113 | 1.999426 | 1.920856 | 2.008318 |
28 | 268.435.456 | 187.106.136 | 17.585.363 | 169.520.773 | 0.697025 | 0.065511 | 0.631514 | 1.999476 | 1.924098 | 2.007635 |
29 | 536.870.912 | 374.129.124 | 33.891.032 | 340.238.092 | 0.696870 | 0.063127 | 0.633743 | 1.999555 | 1.927230 | 2.007058 |
30 | 1.073.741.824 | 748.091.505 | 65.399.541 | 682.691.964 | 0.696715 | 0.060908 | 0.635806 | 1.999554 | 1.929700 | 2.006512 |
31 | 2.147.483.648 | 1.495.877.407 | 126.355.604 | 1.369.521.803 | 0.696572 | 0.058839 | 0.637733 | 1.999591 | 1.932056 | 2.006061 |
32 | 4.294.967.296 | 2.991.204.114 | 244.389.520 | 2.746.814.594 | 0.696444 | 0.056901 | 0.639543 | 1.999632 | 1.934141 | 2.005674 |
33 | 8.589.934.592 | 5.981.360.777 | 473.202.218 | 5.508.158.559 | 0.696322 | 0.055088 | 0.641234 | 1.999650 | 1.936262 | 2.005289 |
34 | 17.179.869.184 | 11.960.825.508 | 917.214.339 | 11.043.611.169 | 0.696212 | 0.053389 | 0.642823 | 1.999683 | 1.938314 | 2.004955 |
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 | 0 | 1 | 0 |
2 | 4 | 4 | 1 | 3 | 1 | 0 | 1 | 2 |
3 | 8 | 7 | 3 | 4 | 2 | 2 | 1 | 2 |
4 | 16 | 10 | 5 | 5 | 4 | 3 | 1 | 2 |
5 | 32 | 12 | 7 | 5 | 4 | 4 | 2 | 2 |
6 | 64 | 19 | 11 | 8 | 4 | 6 | 5 | 4 |
7 | 128 | 37 | 14 | 23 | 8 | 13 | 9 | 7 |
8 | 256 | 62 | 24 | 38 | 13 | 19 | 18 | 12 |
9 | 512 | 122 | 41 | 81 | 28 | 34 | 33 | 27 |
10 | 1.024 | 223 | 72 | 151 | 54 | 61 | 60 | 48 |
11 | 2.048 | 386 | 130 | 256 | 98 | 99 | 96 | 93 |
12 | 4.096 | 703 | 245 | 458 | 169 | 182 | 179 | 173 |
13 | 8.192 | 1.271 | 437 | 834 | 315 | 317 | 336 | 303 |
14 | 16.384 | 2.316 | 801 | 1.515 | 570 | 579 | 610 | 557 |
15 | 32.768 | 4.299 | 1.455 | 2.844 | 1.089 | 1.068 | 1.097 | 1.045 |
16 | 65.536 | 7.987 | 2.674 | 5.313 | 1.979 | 1.996 | 2.045 | 1.967 |
17 | 131.072 | 14.887 | 5.006 | 9.881 | 3.731 | 3.692 | 3.769 | 3.695 |
18 | 262.144 | 27.835 | 9.346 | 18.489 | 6.984 | 6.871 | 6.990 | 6.990 |
19 | 524.288 | 52.098 | 17.328 | 34.770 | 12.980 | 12.934 | 13.072 | 13.112 |
20 | 1.048.576 | 98.807 | 32.885 | 65.922 | 24.613 | 24.646 | 24.810 | 24.738 |
21 | 2.097.152 | 187.011 | 62.467 | 124.544 | 46.746 | 46.719 | 46.867 | 46.679 |
22 | 4.194.304 | 355.607 | 118.567 | 237.040 | 88.965 | 88.890 | 88.969 | 88.783 |
23 | 8.388.608 | 678.226 | 226.081 | 452.145 | 169.635 | 169.324 | 169.968 | 169.299 |
24 | 16.777.216 | 1.295.454 | 431.734 | 863.720 | 324.045 | 323.831 | 323.879 | 323.699 |
25 | 33.554.432 | 2.481.179 | 826.290 | 1.654.889 | 620.635 | 619.999 | 620.275 | 620.270 |
26 | 67.108.864 | 4.758.056 | 1.584.719 | 3.173.337 | 1.189.906 | 1.189.015 | 1.189.843 | 1.189.292 |
27 | 134.217.728 | 9.139.538 | 3.045.446 | 6.094.092 | 2.285.633 | 2.284.579 | 2.285.091 | 2.284.235 |
28 | 268.435.456 | 17.585.363 | 5.861.706 | 11.723.657 | 4.396.728 | 4.396.995 | 4.397.527 | 4.394.113 |
29 | 536.870.912 | 33.891.032 | 11.298.422 | 22.592.610 | 8.474.736 | 8.474.565 | 8.472.799 | 8.468.932 |
30 | 1.073.741.824 | 65.399.541 | 21.799.665 | 43.599.876 | 16.352.866 | 16.351.997 | 16.349.221 | 16.345.457 |
31 | 2.147.483.648 | 126.355.604 | 42.120.170 | 84.235.434 | 31.592.765 | 31.586.529 | 31.588.850 | 31.587.460 |
32 | 4.294.967.296 | 244.389.520 | 81.457.514 | 162.932.006 | 61.105.500 | 61.094.023 | 61.091.311 | 61.098.686 |
33 | 8.589.934.592 | 473.202.218 | 157.734.514 | 315.467.704 | 118.297.959 | 118.303.695 | 118.296.468 | 118.304.096 |
34 | 17.179.869.184 | 917.214.339 | 305.735.523 | 611.478.816 | 229.304.189 | 229.320.633 | 229.292.477 | 229.297.040 |
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 | 1 | 0 | 0 | 0 |
2 | 4 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 4 | 1 | 3 | 2 | 1 | 0 | 1 |
5 | 32 | 8 | 2 | 6 | 2 | 2 | 2 | 2 |
6 | 64 | 9 | 3 | 6 | 2 | 2 | 3 | 2 |
7 | 128 | 33 | 17 | 16 | 7 | 8 | 11 | 7 |
8 | 256 | 95 | 51 | 44 | 20 | 27 | 25 | 23 |
9 | 512 | 213 | 116 | 97 | 45 | 57 | 51 | 60 |
10 | 1.024 | 454 | 248 | 206 | 102 | 117 | 116 | 119 |
11 | 2.048 | 1.010 | 540 | 470 | 248 | 259 | 253 | 250 |
12 | 4.096 | 2.111 | 1.119 | 992 | 519 | 532 | 537 | 523 |
13 | 8.192 | 4.415 | 2.339 | 2.076 | 1.095 | 1.129 | 1.117 | 1.074 |
14 | 16.384 | 9.113 | 4.810 | 4.303 | 2.260 | 2.319 | 2.294 | 2.240 |
15 | 32.768 | 18.630 | 9.765 | 8.865 | 4.626 | 4.708 | 4.676 | 4.620 |
16 | 65.536 | 37.846 | 19.758 | 18.088 | 9.399 | 9.455 | 9.476 | 9.516 |
17 | 131.072 | 76.832 | 39.913 | 36.919 | 19.242 | 19.072 | 19.280 | 19.238 |
18 | 262.144 | 155.556 | 80.509 | 75.047 | 38.796 | 38.711 | 39.121 | 38.928 |
19 | 524.288 | 314.632 | 162.578 | 152.054 | 78.801 | 78.332 | 78.992 | 78.507 |
20 | 1.048.576 | 634.104 | 327.360 | 306.744 | 158.465 | 158.601 | 158.682 | 158.356 |
21 | 2.097.152 | 1.278.300 | 658.033 | 620.267 | 319.052 | 320.189 | 319.706 | 319.353 |
22 | 4.194.304 | 2.573.411 | 1.322.341 | 1.251.070 | 643.030 | 643.868 | 643.346 | 643.167 |
23 | 8.388.608 | 5.177.487 | 2.657.361 | 2.520.126 | 1.294.445 | 1.295.710 | 1.293.725 | 1.293.607 |
24 | 16.777.216 | 10.412.355 | 5.337.518 | 5.074.837 | 2.602.138 | 2.603.892 | 2.602.882 | 2.603.443 |
25 | 33.554.432 | 20.925.437 | 10.713.928 | 10.211.509 | 5.228.921 | 5.233.882 | 5.231.068 | 5.231.566 |
26 | 67.108.864 | 42.044.163 | 21.503.545 | 20.540.618 | 10.503.887 | 10.512.446 | 10.511.939 | 10.515.891 |
27 | 134.217.728 | 84.438.054 | 43.137.723 | 41.300.331 | 21.102.267 | 21.113.174 | 21.107.820 | 21.114.793 |
28 | 268.435.456 | 169.520.773 | 86.529.863 | 82.990.910 | 42.376.612 | 42.382.095 | 42.373.776 | 42.388.290 |
29 | 536.870.912 | 340.238.092 | 173.513.658 | 166.724.434 | 85.057.389 | 85.066.970 | 85.049.784 | 85.063.949 |
30 | 1.073.741.824 | 682.691.964 | 347.888.485 | 334.803.479 | 170.662.582 | 170.674.100 | 170.668.574 | 170.686.708 |
31 | 2.147.483.648 | 1.369.521.803 | 697.392.819 | 672.128.984 | 342.369.674 | 342.382.467 | 342.383.949 | 342.385.713 |
32 | 4.294.967.296 | 2.746.814.594 | 1.397.822.545 | 1.348.992.049 | 686.706.843 | 686.688.919 | 686.689.266 | 686.729.566 |
33 | 8.589.934.592 | 5.508.158.559 | 2.801.318.723 | 2.706.839.836 | 1.377.066.657 | 1.377.007.240 | 1.377.010.678 | 1.377.073.984 |
34 | 17.179.869.184 | 11.043.611.169 | 5.613.317.404 | 5.430.293.765 | 2.760.953.701 | 2.760.827.816 | 2.760.867.443 | 2.760.962.209 |