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+296x-89
f(0)=89
f(1)=13
f(2)=3
f(3)=101
f(4)=11
f(5)=59
f(6)=1723
f(7)=127
f(8)=71
f(9)=83
f(10)=2971
f(11)=137
f(12)=3607
f(13)=491
f(14)=109
f(15)=1
f(16)=4903
f(17)=1
f(18)=5563
f(19)=67
f(20)=31
f(21)=821
f(22)=6907
f(23)=151
f(24)=7591
f(25)=1
f(26)=251
f(27)=1
f(28)=691
f(29)=389
f(30)=881
f(31)=157
f(32)=3469
f(33)=673
f(34)=11131
f(35)=479
f(36)=11863
f(37)=139
f(38)=4201
f(39)=811
f(40)=79
f(41)=1
f(42)=14107
f(43)=1811
f(44)=4957
f(45)=1907
f(46)=15643
f(47)=167
f(48)=1493
f(49)=1051
f(50)=5737
f(51)=1
f(52)=1637
f(53)=1
f(54)=1447
f(55)=1201
f(56)=211
f(57)=313
f(58)=20443
f(59)=1
f(60)=239
f(61)=2711
f(62)=7369
f(63)=1
f(64)=1
f(65)=487
f(66)=1831
f(67)=233
f(68)=8221
f(69)=3137
f(70)=1
f(71)=541
f(72)=26407
f(73)=839
f(74)=827
f(75)=3467
f(76)=28183
f(77)=1193
f(78)=229
f(79)=1
f(80)=769
f(81)=173
f(82)=997
f(83)=1307
f(84)=1
f(85)=367
f(86)=163
f(87)=1
f(88)=33703
f(89)=1
f(90)=34651
f(91)=4391
f(92)=1
f(93)=347
f(94)=36571
f(95)=193
f(96)=3413
f(97)=2377
f(98)=12841
f(99)=4877
b) Substitution of the polynom
The polynom f(x)=x^2+296x-89 could be written as f(y)= y^2-21993 with x=y-148
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+148
f'(x)>2x+295
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 | 11 | 4 | 7 | 1.100000 | 0.400000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 82 | 20 | 62 | 0.820000 | 0.200000 | 0.820000 | 7.454545 | 5.000000 | 8.857142 |
3 | 1.000 | 679 | 123 | 556 | 0.679000 | 0.123000 | 0.679000 | 8.280488 | 6.150000 | 8.967742 |
4 | 10.000 | 6.645 | 881 | 5.764 | 0.664500 | 0.088100 | 0.664500 | 9.786450 | 7.162601 | 10.366906 |
5 | 100.000 | 66.857 | 6.953 | 59.904 | 0.668570 | 0.069530 | 0.668570 | 10.061249 | 7.892168 | 10.392783 |
6 | 1.000.000 | 673.212 | 57.125 | 616.087 | 0.673212 | 0.057125 | 0.673212 | 10.069431 | 8.215878 | 10.284572 |
7 | 10.000.000 | 6.764.390 | 481.946 | 6.282.444 | 0.676439 | 0.048195 | 0.676439 | 10.047935 | 8.436691 | 10.197332 |
8 | 100.000.000 | 67.848.148 | 4.175.104 | 63.673.044 | 0.678481 | 0.041751 | 0.678481 | 10.030194 | 8.663013 | 10.135076 |
9 | 1.000.000.000 | 680.108.836 | 36.845.613 | 643.263.223 | 0.680109 | 0.036846 | 0.680109 | 10.023986 | 8.825076 | 10.102599 |
10 | 10.000.000.000 | 6.813.998.373 | 329.753.900 | 6.484.244.473 | 0.681400 | 0.032975 | 0.681400 | 10.018982 | 8.949611 | 10.080235 |
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 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.500000 | 2.000000 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 1.777778 | 2.000000 | 1.666667 |
5 | 32 | 28 | 9 | 19 | 0.875000 | 0.281250 | 0.593750 | 1.750000 | 1.500000 | 1.900000 |
6 | 64 | 53 | 14 | 39 | 0.828125 | 0.218750 | 0.609375 | 1.892857 | 1.555556 | 2.052632 |
7 | 128 | 98 | 24 | 74 | 0.765625 | 0.187500 | 0.578125 | 1.849057 | 1.714286 | 1.897436 |
8 | 256 | 193 | 41 | 152 | 0.753906 | 0.160156 | 0.593750 | 1.969388 | 1.708333 | 2.054054 |
9 | 512 | 354 | 66 | 288 | 0.691406 | 0.128906 | 0.562500 | 1.834197 | 1.609756 | 1.894737 |
10 | 1.024 | 696 | 125 | 571 | 0.679688 | 0.122070 | 0.557617 | 1.966102 | 1.893939 | 1.982639 |
11 | 2.048 | 1.353 | 232 | 1.121 | 0.660645 | 0.113281 | 0.547363 | 1.943966 | 1.856000 | 1.963222 |
12 | 4.096 | 2.708 | 405 | 2.303 | 0.661133 | 0.098877 | 0.562256 | 2.001478 | 1.745690 | 2.054416 |
13 | 8.192 | 5.430 | 736 | 4.694 | 0.662842 | 0.089844 | 0.572998 | 2.005170 | 1.817284 | 2.038211 |
14 | 16.384 | 10.893 | 1.361 | 9.532 | 0.664856 | 0.083069 | 0.581787 | 2.006077 | 1.849185 | 2.030678 |
15 | 32.768 | 21.780 | 2.521 | 19.259 | 0.664673 | 0.076935 | 0.587738 | 1.999449 | 1.852314 | 2.020458 |
16 | 65.536 | 43.690 | 4.739 | 38.951 | 0.666656 | 0.072311 | 0.594345 | 2.005969 | 1.879810 | 2.022483 |
17 | 131.072 | 87.648 | 8.901 | 78.747 | 0.668701 | 0.067909 | 0.600792 | 2.006134 | 1.878244 | 2.021694 |
18 | 262.144 | 175.802 | 16.736 | 159.066 | 0.670631 | 0.063843 | 0.606789 | 2.005773 | 1.880238 | 2.019963 |
19 | 524.288 | 352.566 | 31.504 | 321.062 | 0.672466 | 0.060089 | 0.612377 | 2.005472 | 1.882409 | 2.018420 |
20 | 1.048.576 | 706.027 | 59.697 | 646.330 | 0.673320 | 0.056931 | 0.616388 | 2.002538 | 1.894902 | 2.013100 |
21 | 2.097.152 | 1.414.527 | 113.077 | 1.301.450 | 0.674499 | 0.053919 | 0.620580 | 2.003503 | 1.894182 | 2.013600 |
22 | 4.194.304 | 2.833.037 | 214.454 | 2.618.583 | 0.675449 | 0.051130 | 0.624319 | 2.002816 | 1.896531 | 2.012050 |
23 | 8.388.608 | 5.672.951 | 409.141 | 5.263.810 | 0.676268 | 0.048773 | 0.627495 | 2.002427 | 1.907826 | 2.010175 |
24 | 16.777.216 | 11.357.505 | 781.771 | 10.575.734 | 0.676960 | 0.046597 | 0.630363 | 2.002045 | 1.910762 | 2.009140 |
25 | 33.554.432 | 22.735.740 | 1.496.572 | 21.239.168 | 0.677578 | 0.044601 | 0.632977 | 2.001825 | 1.914335 | 2.008293 |
26 | 67.108.864 | 45.509.854 | 2.868.927 | 42.640.927 | 0.678150 | 0.042750 | 0.635399 | 2.001688 | 1.916999 | 2.007655 |
27 | 134.217.728 | 91.095.237 | 5.510.507 | 85.584.730 | 0.678712 | 0.041056 | 0.637656 | 2.001660 | 1.920755 | 2.007103 |
28 | 268.435.456 | 182.330.246 | 10.603.229 | 171.727.017 | 0.679233 | 0.039500 | 0.639733 | 2.001534 | 1.924184 | 2.006515 |
29 | 536.870.912 | 364.917.288 | 20.430.008 | 344.487.280 | 0.679711 | 0.038054 | 0.641658 | 2.001408 | 1.926772 | 2.006017 |
30 | 1.073.741.824 | 730.310.704 | 39.418.987 | 690.891.717 | 0.680155 | 0.036712 | 0.643443 | 2.001305 | 1.929465 | 2.005565 |
31 | 2.147.483.648 | 1.461.504.345 | 76.157.197 | 1.385.347.148 | 0.680566 | 0.035463 | 0.645103 | 2.001209 | 1.931993 | 2.005158 |
32 | 4.294.967.296 | 2.924.680.795 | 147.301.626 | 2.777.379.169 | 0.680955 | 0.034296 | 0.646659 | 2.001144 | 1.934179 | 2.004825 |
33 | 8.589.934.592 | 5.852.507.327 | 285.232.260 | 5.567.275.067 | 0.681322 | 0.033205 | 0.648116 | 2.001076 | 1.936382 | 2.004507 |
34 | 17.179.869.184 | 11.710.955.722 | 552.846.871 | 11.158.108.851 | 0.681667 | 0.032180 | 0.649487 | 2.001015 | 1.938234 | 2.004232 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 3 | 1 | 1 | 1 | 2 | 0 | 0 |
4 | 16 | 6 | 4 | 1 | 1 | 3 | 0 | 2 |
5 | 32 | 9 | 7 | 1 | 1 | 5 | 0 | 3 |
6 | 64 | 14 | 12 | 1 | 1 | 9 | 0 | 4 |
7 | 128 | 24 | 22 | 1 | 1 | 12 | 0 | 11 |
8 | 256 | 41 | 39 | 1 | 1 | 18 | 0 | 22 |
9 | 512 | 66 | 64 | 1 | 1 | 33 | 0 | 32 |
10 | 1.024 | 125 | 123 | 1 | 1 | 62 | 0 | 62 |
11 | 2.048 | 232 | 230 | 1 | 1 | 119 | 0 | 112 |
12 | 4.096 | 405 | 403 | 1 | 1 | 203 | 0 | 201 |
13 | 8.192 | 736 | 734 | 1 | 1 | 365 | 0 | 370 |
14 | 16.384 | 1.361 | 1.359 | 1 | 1 | 690 | 0 | 670 |
15 | 32.768 | 2.521 | 2.519 | 1 | 1 | 1.273 | 0 | 1.247 |
16 | 65.536 | 4.739 | 4.737 | 1 | 1 | 2.377 | 0 | 2.361 |
17 | 131.072 | 8.901 | 8.899 | 1 | 1 | 4.434 | 0 | 4.466 |
18 | 262.144 | 16.736 | 16.734 | 1 | 1 | 8.404 | 0 | 8.331 |
19 | 524.288 | 31.504 | 31.502 | 1 | 1 | 15.810 | 0 | 15.693 |
20 | 1.048.576 | 59.697 | 59.695 | 1 | 1 | 29.958 | 0 | 29.738 |
21 | 2.097.152 | 113.077 | 113.075 | 1 | 1 | 56.586 | 0 | 56.490 |
22 | 4.194.304 | 214.454 | 214.452 | 1 | 1 | 107.350 | 0 | 107.103 |
23 | 8.388.608 | 409.141 | 409.139 | 1 | 1 | 204.468 | 0 | 204.672 |
24 | 16.777.216 | 781.771 | 781.769 | 1 | 1 | 390.941 | 0 | 390.829 |
25 | 33.554.432 | 1.496.572 | 1.496.570 | 1 | 1 | 749.099 | 0 | 747.472 |
26 | 67.108.864 | 2.868.927 | 2.868.925 | 1 | 1 | 1.435.630 | 0 | 1.433.296 |
27 | 134.217.728 | 5.510.507 | 5.510.505 | 1 | 1 | 2.756.120 | 0 | 2.754.386 |
28 | 268.435.456 | 10.603.229 | 10.603.227 | 1 | 1 | 5.301.686 | 0 | 5.301.542 |
29 | 536.870.912 | 20.430.008 | 20.430.006 | 1 | 1 | 10.213.963 | 0 | 10.216.044 |
30 | 1.073.741.824 | 39.418.987 | 39.418.985 | 1 | 1 | 19.708.249 | 0 | 19.710.737 |
31 | 2.147.483.648 | 76.157.197 | 76.157.195 | 1 | 1 | 38.075.734 | 0 | 38.081.462 |
32 | 4.294.967.296 | 147.301.626 | 147.301.624 | 1 | 1 | 73.646.926 | 0 | 73.654.699 |
33 | 8.589.934.592 | 285.232.260 | 285.232.258 | 1 | 1 | 142.619.317 | 0 | 142.612.942 |
34 | 17.179.869.184 | 552.846.871 | 552.846.869 | 1 | 1 | 276.424.392 | 0 | 276.422.478 |
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 | 3 | 1 | 2 | 0 | 1 | 2 | 0 |
3 | 8 | 6 | 2 | 4 | 0 | 2 | 2 | 2 |
4 | 16 | 10 | 3 | 7 | 1 | 4 | 3 | 2 |
5 | 32 | 19 | 8 | 11 | 2 | 7 | 7 | 3 |
6 | 64 | 39 | 20 | 19 | 8 | 13 | 10 | 8 |
7 | 128 | 74 | 35 | 39 | 18 | 21 | 21 | 14 |
8 | 256 | 152 | 72 | 80 | 40 | 37 | 39 | 36 |
9 | 512 | 288 | 144 | 144 | 82 | 60 | 90 | 56 |
10 | 1.024 | 571 | 281 | 290 | 157 | 119 | 167 | 128 |
11 | 2.048 | 1.121 | 543 | 578 | 326 | 231 | 309 | 255 |
12 | 4.096 | 2.303 | 1.136 | 1.167 | 669 | 484 | 644 | 506 |
13 | 8.192 | 4.694 | 2.333 | 2.361 | 1.333 | 1.060 | 1.270 | 1.031 |
14 | 16.384 | 9.532 | 4.750 | 4.782 | 2.666 | 2.142 | 2.617 | 2.107 |
15 | 32.768 | 19.259 | 9.537 | 9.722 | 5.233 | 4.384 | 5.253 | 4.389 |
16 | 65.536 | 38.951 | 19.365 | 19.586 | 10.444 | 8.989 | 10.544 | 8.974 |
17 | 131.072 | 78.747 | 39.098 | 39.649 | 20.964 | 18.197 | 21.294 | 18.292 |
18 | 262.144 | 159.066 | 79.158 | 79.908 | 42.442 | 37.013 | 42.538 | 37.073 |
19 | 524.288 | 321.062 | 159.823 | 161.239 | 85.459 | 75.043 | 85.407 | 75.153 |
20 | 1.048.576 | 646.330 | 322.019 | 324.311 | 171.166 | 151.625 | 171.235 | 152.304 |
21 | 2.097.152 | 1.301.450 | 648.455 | 652.995 | 343.935 | 306.568 | 343.809 | 307.138 |
22 | 4.194.304 | 2.618.583 | 1.305.587 | 1.312.996 | 689.553 | 619.635 | 689.469 | 619.926 |
23 | 8.388.608 | 5.263.810 | 2.625.236 | 2.638.574 | 1.382.405 | 1.249.871 | 1.382.689 | 1.248.845 |
24 | 16.777.216 | 10.575.734 | 5.276.006 | 5.299.728 | 2.770.228 | 2.518.215 | 2.771.013 | 2.516.278 |
25 | 33.554.432 | 21.239.168 | 10.599.665 | 10.639.503 | 5.552.816 | 5.067.487 | 5.553.002 | 5.065.863 |
26 | 67.108.864 | 42.640.927 | 21.284.566 | 21.356.361 | 11.120.319 | 10.199.757 | 11.126.365 | 10.194.486 |
27 | 134.217.728 | 85.584.730 | 42.722.662 | 42.862.068 | 22.285.543 | 20.503.608 | 22.287.873 | 20.507.706 |
28 | 268.435.456 | 171.727.017 | 85.731.584 | 85.995.433 | 44.638.842 | 41.214.796 | 44.645.194 | 41.228.185 |
29 | 536.870.912 | 344.487.280 | 171.997.788 | 172.489.492 | 89.412.177 | 82.819.468 | 89.418.698 | 82.836.937 |
30 | 1.073.741.824 | 690.891.717 | 344.982.059 | 345.909.658 | 179.062.011 | 166.378.010 | 179.054.509 | 166.397.187 |
31 | 2.147.483.648 | 1.385.347.148 | 691.817.662 | 693.529.486 | 358.557.766 | 334.109.392 | 358.566.474 | 334.113.516 |
32 | 4.294.967.296 | 2.777.379.169 | 1.387.081.314 | 1.390.297.855 | 717.978.768 | 670.721.047 | 717.943.034 | 670.736.320 |
33 | 8.589.934.592 | 5.567.275.067 | 2.780.619.341 | 2.786.655.726 | 1.437.553.330 | 1.346.154.285 | 1.437.449.270 | 1.346.118.182 |
34 | 17.179.869.184 | 11.158.108.851 | 5.573.295.677 | 5.584.813.174 | 2.878.022.611 | 2.701.104.631 | 2.877.916.030 | 2.701.065.579 |