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-149
f(0)=149
f(1)=5
f(2)=71
f(3)=23
f(4)=13
f(5)=1
f(6)=107
f(7)=41
f(8)=19
f(9)=113
f(10)=1031
f(11)=29
f(12)=1291
f(13)=89
f(14)=1559
f(15)=53
f(16)=367
f(17)=1
f(18)=163
f(19)=283
f(20)=2411
f(21)=1
f(22)=2711
f(23)=179
f(24)=3019
f(25)=397
f(26)=1
f(27)=1
f(28)=3659
f(29)=239
f(30)=307
f(31)=1
f(32)=61
f(33)=563
f(34)=4679
f(35)=607
f(36)=1
f(37)=1
f(38)=5399
f(39)=349
f(40)=199
f(41)=1
f(42)=6151
f(43)=1
f(44)=503
f(45)=421
f(46)=73
f(47)=223
f(48)=1
f(49)=1
f(50)=337
f(51)=1
f(52)=8171
f(53)=131
f(54)=8599
f(55)=1
f(56)=139
f(57)=1
f(58)=9479
f(59)=1213
f(60)=9931
f(61)=127
f(62)=10391
f(63)=83
f(64)=10859
f(65)=1
f(66)=2267
f(67)=1447
f(68)=1
f(69)=1
f(70)=947
f(71)=157
f(72)=557
f(73)=1
f(74)=701
f(75)=1697
f(76)=2767
f(77)=881
f(78)=173
f(79)=457
f(80)=14891
f(81)=379
f(82)=1187
f(83)=151
f(84)=1
f(85)=1
f(86)=3307
f(87)=1051
f(88)=17099
f(89)=1
f(90)=431
f(91)=449
f(92)=18251
f(93)=1
f(94)=18839
f(95)=1
f(96)=1
f(97)=2467
f(98)=691
f(99)=2543
b) Substitution of the polynom
The polynom f(x)=x^2+108x-149 could be written as f(y)= y^2-3065 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+107
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 71 | 22 | 49 | 0.710000 | 0.220000 | 0.710000 | 7.100000 | 7.333333 | 7.000000 |
3 | 1.000 | 638 | 138 | 500 | 0.638000 | 0.138000 | 0.638000 | 8.985915 | 6.272727 | 10.204082 |
4 | 10.000 | 6.537 | 1.008 | 5.529 | 0.653700 | 0.100800 | 0.653700 | 10.246081 | 7.304348 | 11.058000 |
5 | 100.000 | 66.303 | 8.019 | 58.284 | 0.663030 | 0.080190 | 0.663030 | 10.142726 | 7.955357 | 10.541509 |
6 | 1.000.000 | 668.249 | 65.586 | 602.663 | 0.668249 | 0.065586 | 0.668249 | 10.078714 | 8.178825 | 10.340111 |
7 | 10.000.000 | 6.717.797 | 553.024 | 6.164.773 | 0.671780 | 0.055302 | 0.671780 | 10.052835 | 8.432043 | 10.229221 |
8 | 100.000.000 | 67.447.184 | 4.802.942 | 62.644.242 | 0.674472 | 0.048029 | 0.674472 | 10.040074 | 8.684871 | 10.161646 |
9 | 1.000.000.000 | 676.570.969 | 42.376.546 | 634.194.423 | 0.676571 | 0.042377 | 0.676571 | 10.031122 | 8.823039 | 10.123747 |
10 | 10.000.000.000 | 6.782.351.791 | 379.222.316 | 6.403.129.475 | 0.678235 | 0.037922 | 0.678235 | 10.024598 | 8.948873 | 10.096477 |
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 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 1.000000 | 2.000000 |
4 | 16 | 16 | 5 | 11 | 1.000000 | 0.312500 | 0.687500 | 2.000000 | 2.500000 | 1.833333 |
5 | 32 | 26 | 9 | 17 | 0.812500 | 0.281250 | 0.531250 | 1.625000 | 1.800000 | 1.545455 |
6 | 64 | 47 | 18 | 29 | 0.734375 | 0.281250 | 0.453125 | 1.807692 | 2.000000 | 1.705882 |
7 | 128 | 88 | 26 | 62 | 0.687500 | 0.203125 | 0.484375 | 1.872340 | 1.444444 | 2.137931 |
8 | 256 | 165 | 41 | 124 | 0.644531 | 0.160156 | 0.484375 | 1.875000 | 1.576923 | 2.000000 |
9 | 512 | 325 | 73 | 252 | 0.634766 | 0.142578 | 0.492188 | 1.969697 | 1.780488 | 2.032258 |
10 | 1.024 | 655 | 139 | 516 | 0.639648 | 0.135742 | 0.503906 | 2.015385 | 1.904110 | 2.047619 |
11 | 2.048 | 1.323 | 256 | 1.067 | 0.645996 | 0.125000 | 0.520996 | 2.019847 | 1.841727 | 2.067829 |
12 | 4.096 | 2.648 | 467 | 2.181 | 0.646484 | 0.114014 | 0.532471 | 2.001512 | 1.824219 | 2.044049 |
13 | 8.192 | 5.341 | 845 | 4.496 | 0.651978 | 0.103149 | 0.548828 | 2.016994 | 1.809422 | 2.061440 |
14 | 16.384 | 10.752 | 1.564 | 9.188 | 0.656250 | 0.095459 | 0.560791 | 2.013106 | 1.850888 | 2.043594 |
15 | 32.768 | 21.569 | 2.933 | 18.636 | 0.658234 | 0.089508 | 0.568726 | 2.006045 | 1.875320 | 2.028298 |
16 | 65.536 | 43.363 | 5.504 | 37.859 | 0.661667 | 0.083984 | 0.577682 | 2.010432 | 1.876577 | 2.031498 |
17 | 131.072 | 87.010 | 10.210 | 76.800 | 0.663834 | 0.077896 | 0.585938 | 2.006549 | 1.855015 | 2.028580 |
18 | 262.144 | 174.413 | 19.130 | 155.283 | 0.665333 | 0.072975 | 0.592358 | 2.004517 | 1.873653 | 2.021914 |
19 | 524.288 | 349.619 | 36.181 | 313.438 | 0.666845 | 0.069010 | 0.597836 | 2.004547 | 1.891322 | 2.018495 |
20 | 1.048.576 | 700.889 | 68.456 | 632.433 | 0.668420 | 0.065285 | 0.603135 | 2.004722 | 1.892043 | 2.017729 |
21 | 2.097.152 | 1.404.022 | 129.803 | 1.274.219 | 0.669490 | 0.061895 | 0.607595 | 2.003202 | 1.896152 | 2.014789 |
22 | 4.194.304 | 2.812.522 | 246.261 | 2.566.261 | 0.670557 | 0.058713 | 0.611844 | 2.003189 | 1.897190 | 2.013987 |
23 | 8.388.608 | 5.632.979 | 469.694 | 5.163.285 | 0.671503 | 0.055992 | 0.615512 | 2.002821 | 1.907302 | 2.011987 |
24 | 16.777.216 | 11.282.044 | 897.091 | 10.384.953 | 0.672462 | 0.053471 | 0.618991 | 2.002856 | 1.909948 | 2.011307 |
25 | 33.554.432 | 22.592.522 | 1.720.117 | 20.872.405 | 0.673310 | 0.051263 | 0.622046 | 2.002520 | 1.917439 | 2.009870 |
26 | 67.108.864 | 45.236.174 | 3.299.001 | 41.937.173 | 0.674072 | 0.049159 | 0.624913 | 2.002263 | 1.917893 | 2.009216 |
27 | 134.217.728 | 90.565.075 | 6.338.026 | 84.227.049 | 0.674762 | 0.047222 | 0.627540 | 2.002050 | 1.921196 | 2.008410 |
28 | 268.435.456 | 181.311.914 | 12.193.679 | 169.118.235 | 0.675440 | 0.045425 | 0.630015 | 2.002007 | 1.923892 | 2.007885 |
29 | 536.870.912 | 362.955.583 | 23.498.466 | 339.457.117 | 0.676057 | 0.043769 | 0.632288 | 2.001830 | 1.927102 | 2.007218 |
30 | 1.073.741.824 | 726.525.807 | 45.337.977 | 681.187.830 | 0.676630 | 0.042224 | 0.634406 | 2.001693 | 1.929402 | 2.006698 |
31 | 2.147.483.648 | 1.454.193.959 | 87.586.983 | 1.366.606.976 | 0.677162 | 0.040786 | 0.636376 | 2.001572 | 1.931868 | 2.006212 |
32 | 4.294.967.296 | 2.910.550.872 | 169.408.783 | 2.741.142.089 | 0.677665 | 0.039444 | 0.638222 | 2.001487 | 1.934178 | 2.005801 |
33 | 8.589.934.592 | 5.825.138.581 | 328.025.923 | 5.497.112.658 | 0.678135 | 0.038187 | 0.639948 | 2.001387 | 1.936298 | 2.005410 |
34 | 17.179.869.184 | 11.657.916.318 | 635.789.434 | 11.022.126.884 | 0.678580 | 0.037008 | 0.641572 | 2.001311 | 1.938229 | 2.005076 |
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 | 0 | 0 | 1 | 1 |
2 | 4 | 2 | 0 | 2 | 0 | 0 | 1 | 1 |
3 | 8 | 2 | 0 | 2 | 0 | 0 | 1 | 1 |
4 | 16 | 5 | 1 | 4 | 0 | 1 | 1 | 3 |
5 | 32 | 9 | 2 | 7 | 0 | 4 | 1 | 4 |
6 | 64 | 18 | 5 | 13 | 0 | 7 | 1 | 10 |
7 | 128 | 26 | 6 | 20 | 0 | 13 | 1 | 12 |
8 | 256 | 41 | 11 | 30 | 0 | 20 | 1 | 20 |
9 | 512 | 73 | 26 | 47 | 0 | 39 | 1 | 33 |
10 | 1.024 | 139 | 49 | 90 | 0 | 72 | 1 | 66 |
11 | 2.048 | 256 | 84 | 172 | 0 | 134 | 1 | 121 |
12 | 4.096 | 467 | 154 | 313 | 0 | 236 | 1 | 230 |
13 | 8.192 | 845 | 274 | 571 | 0 | 428 | 1 | 416 |
14 | 16.384 | 1.564 | 515 | 1.049 | 0 | 791 | 1 | 772 |
15 | 32.768 | 2.933 | 989 | 1.944 | 0 | 1.482 | 1 | 1.450 |
16 | 65.536 | 5.504 | 1.855 | 3.649 | 0 | 2.762 | 1 | 2.741 |
17 | 131.072 | 10.210 | 3.405 | 6.805 | 0 | 5.122 | 1 | 5.087 |
18 | 262.144 | 19.130 | 6.352 | 12.778 | 0 | 9.605 | 1 | 9.524 |
19 | 524.288 | 36.181 | 12.035 | 24.146 | 0 | 18.147 | 1 | 18.033 |
20 | 1.048.576 | 68.456 | 22.872 | 45.584 | 0 | 34.239 | 1 | 34.216 |
21 | 2.097.152 | 129.803 | 43.295 | 86.508 | 0 | 64.808 | 1 | 64.994 |
22 | 4.194.304 | 246.261 | 82.036 | 164.225 | 0 | 123.060 | 1 | 123.200 |
23 | 8.388.608 | 469.694 | 156.611 | 313.083 | 0 | 234.731 | 1 | 234.962 |
24 | 16.777.216 | 897.091 | 299.058 | 598.033 | 0 | 448.488 | 1 | 448.602 |
25 | 33.554.432 | 1.720.117 | 574.138 | 1.145.979 | 0 | 860.303 | 1 | 859.813 |
26 | 67.108.864 | 3.299.001 | 1.100.407 | 2.198.594 | 0 | 1.649.386 | 1 | 1.649.614 |
27 | 134.217.728 | 6.338.026 | 2.113.094 | 4.224.932 | 0 | 3.169.384 | 1 | 3.168.641 |
28 | 268.435.456 | 12.193.679 | 4.063.691 | 8.129.988 | 0 | 6.096.489 | 1 | 6.097.189 |
29 | 536.870.912 | 23.498.466 | 7.832.626 | 15.665.840 | 0 | 11.748.679 | 1 | 11.749.786 |
30 | 1.073.741.824 | 45.337.977 | 15.111.925 | 30.226.052 | 0 | 22.667.348 | 1 | 22.670.628 |
31 | 2.147.483.648 | 87.586.983 | 29.193.548 | 58.393.435 | 0 | 43.793.434 | 1 | 43.793.548 |
32 | 4.294.967.296 | 169.408.783 | 56.469.056 | 112.939.727 | 0 | 84.701.537 | 1 | 84.707.245 |
33 | 8.589.934.592 | 328.025.923 | 109.332.003 | 218.693.920 | 0 | 164.017.709 | 1 | 164.008.213 |
34 | 17.179.869.184 | 635.789.434 | 211.918.540 | 423.870.894 | 0 | 317.900.860 | 1 | 317.888.573 |
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 | 1 | 0 |
2 | 4 | 3 | 1 | 2 | 0 | 0 | 2 | 1 |
3 | 8 | 6 | 2 | 4 | 1 | 2 | 2 | 1 |
4 | 16 | 11 | 3 | 8 | 3 | 2 | 4 | 2 |
5 | 32 | 17 | 7 | 10 | 3 | 6 | 5 | 3 |
6 | 64 | 29 | 16 | 13 | 4 | 9 | 8 | 8 |
7 | 128 | 62 | 32 | 30 | 13 | 21 | 13 | 15 |
8 | 256 | 124 | 71 | 53 | 24 | 34 | 28 | 38 |
9 | 512 | 252 | 133 | 119 | 49 | 71 | 58 | 74 |
10 | 1.024 | 516 | 267 | 249 | 110 | 143 | 111 | 152 |
11 | 2.048 | 1.067 | 554 | 513 | 243 | 297 | 234 | 293 |
12 | 4.096 | 2.181 | 1.126 | 1.055 | 508 | 586 | 484 | 603 |
13 | 8.192 | 4.496 | 2.301 | 2.195 | 1.049 | 1.238 | 1.004 | 1.205 |
14 | 16.384 | 9.188 | 4.691 | 4.497 | 2.161 | 2.480 | 2.100 | 2.447 |
15 | 32.768 | 18.636 | 9.517 | 9.119 | 4.420 | 4.999 | 4.331 | 4.886 |
16 | 65.536 | 37.859 | 19.351 | 18.508 | 8.928 | 10.037 | 8.882 | 10.012 |
17 | 131.072 | 76.800 | 39.283 | 37.517 | 18.064 | 20.173 | 18.292 | 20.271 |
18 | 262.144 | 155.283 | 79.290 | 75.993 | 36.722 | 40.801 | 37.029 | 40.731 |
19 | 524.288 | 313.438 | 159.861 | 153.577 | 74.558 | 81.925 | 74.931 | 82.024 |
20 | 1.048.576 | 632.433 | 321.908 | 310.525 | 151.637 | 164.932 | 151.100 | 164.764 |
21 | 2.097.152 | 1.274.219 | 647.002 | 627.217 | 306.538 | 330.940 | 305.800 | 330.941 |
22 | 4.194.304 | 2.566.261 | 1.303.749 | 1.262.512 | 618.000 | 665.256 | 617.649 | 665.356 |
23 | 8.388.608 | 5.163.285 | 2.621.610 | 2.541.675 | 1.244.972 | 1.336.149 | 1.245.525 | 1.336.639 |
24 | 16.777.216 | 10.384.953 | 5.269.198 | 5.115.755 | 2.508.457 | 2.681.951 | 2.511.105 | 2.683.440 |
25 | 33.554.432 | 20.872.405 | 10.579.842 | 10.292.563 | 5.050.117 | 5.382.681 | 5.055.309 | 5.384.298 |
26 | 67.108.864 | 41.937.173 | 21.246.702 | 20.690.471 | 10.168.460 | 10.798.641 | 10.170.082 | 10.799.990 |
27 | 134.217.728 | 84.227.049 | 42.655.378 | 41.571.671 | 20.449.234 | 21.660.952 | 20.452.905 | 21.663.958 |
28 | 268.435.456 | 169.118.235 | 85.598.047 | 83.520.188 | 41.116.462 | 43.440.279 | 41.118.378 | 43.443.116 |
29 | 536.870.912 | 339.457.117 | 171.716.592 | 167.740.525 | 82.635.560 | 87.096.863 | 82.632.352 | 87.092.342 |
30 | 1.073.741.824 | 681.187.830 | 344.408.111 | 336.779.719 | 166.008.202 | 174.593.082 | 166.001.558 | 174.584.988 |
31 | 2.147.483.648 | 1.366.606.976 | 690.703.446 | 675.903.530 | 333.348.177 | 349.954.255 | 333.369.481 | 349.935.063 |
32 | 4.294.967.296 | 2.741.142.089 | 1.384.884.848 | 1.356.257.241 | 669.255.017 | 701.319.710 | 669.270.455 | 701.296.907 |
33 | 8.589.934.592 | 5.497.112.658 | 2.776.276.179 | 2.720.836.479 | 1.343.298.657 | 1.405.243.397 | 1.343.321.950 | 1.405.248.654 |
34 | 17.179.869.184 | 11.022.126.884 | 5.564.648.455 | 5.457.478.429 | 2.695.556.206 | 2.815.530.646 | 2.695.543.695 | 2.815.496.337 |