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+68x-151
f(0)=151
f(1)=41
f(2)=11
f(3)=31
f(4)=137
f(5)=107
f(6)=293
f(7)=17
f(8)=457
f(9)=271
f(10)=37
f(11)=359
f(12)=809
f(13)=1
f(14)=997
f(15)=547
f(16)=1193
f(17)=647
f(18)=127
f(19)=751
f(20)=1609
f(21)=859
f(22)=59
f(23)=971
f(24)=1
f(25)=1087
f(26)=2293
f(27)=71
f(28)=43
f(29)=1
f(30)=2789
f(31)=1459
f(32)=3049
f(33)=1
f(34)=1
f(35)=157
f(36)=3593
f(37)=1867
f(38)=3877
f(39)=2011
f(40)=379
f(41)=1
f(42)=109
f(43)=2311
f(44)=281
f(45)=2467
f(46)=463
f(47)=1
f(48)=5417
f(49)=2791
f(50)=5749
f(51)=269
f(52)=6089
f(53)=101
f(54)=1
f(55)=3307
f(56)=6793
f(57)=317
f(58)=421
f(59)=3671
f(60)=7529
f(61)=227
f(62)=719
f(63)=4051
f(64)=8297
f(65)=1
f(66)=8693
f(67)=4447
f(68)=827
f(69)=4651
f(70)=257
f(71)=113
f(72)=9929
f(73)=461
f(74)=10357
f(75)=311
f(76)=251
f(77)=5507
f(78)=661
f(79)=521
f(80)=11689
f(81)=1
f(82)=12149
f(83)=1
f(84)=1
f(85)=6427
f(86)=13093
f(87)=1
f(88)=13577
f(89)=6911
f(90)=1279
f(91)=7159
f(92)=857
f(93)=7411
f(94)=15077
f(95)=1
f(96)=503
f(97)=7927
f(98)=1
f(99)=8191
b) Substitution of the polynom
The polynom f(x)=x^2+68x-151 could be written as f(y)= y^2-1307 with x=y-34
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+34
f'(x)>2x+67
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 | 9 | 2 | 1.100000 | 0.900000 | 0.200000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 83 | 58 | 25 | 0.830000 | 0.580000 | 0.250000 | 7.545455 | 6.444445 | 12.500000 |
3 | 1.000 | 773 | 380 | 393 | 0.773000 | 0.380000 | 0.393000 | 9.313253 | 6.551724 | 15.720000 |
4 | 10.000 | 7.442 | 2.742 | 4.700 | 0.744200 | 0.274200 | 0.470000 | 9.627425 | 7.215789 | 11.959288 |
5 | 100.000 | 73.358 | 21.218 | 52.140 | 0.733580 | 0.212180 | 0.521400 | 9.857296 | 7.738147 | 11.093617 |
6 | 1.000.000 | 726.443 | 173.568 | 552.875 | 0.726443 | 0.173568 | 0.552875 | 9.902710 | 8.180224 | 10.603663 |
7 | 10.000.000 | 7.212.966 | 1.466.516 | 5.746.450 | 0.721297 | 0.146652 | 0.574645 | 9.929156 | 8.449230 | 10.393760 |
8 | 100.000.000 | 71.766.026 | 12.677.329 | 59.088.697 | 0.717660 | 0.126773 | 0.590887 | 9.949586 | 8.644522 | 10.282643 |
9 | 1.000.000.000 | 714.796.348 | 111.716.000 | 603.080.348 | 0.714796 | 0.111716 | 0.603080 | 9.960094 | 8.812266 | 10.206357 |
10 | 10.000.000.000 | 7.125.062.360 | 998.792.427 | 6.126.269.933 | 0.712506 | 0.099879 | 0.612627 | 9.967961 | 8.940460 | 10.158298 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 8 | 1 | 1.125000 | 1.000000 | 0.125000 | 1.800000 | 1.600000 | inf |
4 | 16 | 16 | 14 | 2 | 1.000000 | 0.875000 | 0.125000 | 1.777778 | 1.750000 | 2.000000 |
5 | 32 | 29 | 24 | 5 | 0.906250 | 0.750000 | 0.156250 | 1.812500 | 1.714286 | 2.500000 |
6 | 64 | 55 | 40 | 15 | 0.859375 | 0.625000 | 0.234375 | 1.896552 | 1.666667 | 3.000000 |
7 | 128 | 106 | 69 | 37 | 0.828125 | 0.539062 | 0.289062 | 1.927273 | 1.725000 | 2.466667 |
8 | 256 | 207 | 128 | 79 | 0.808594 | 0.500000 | 0.308594 | 1.952830 | 1.855072 | 2.135135 |
9 | 512 | 406 | 225 | 181 | 0.792969 | 0.439453 | 0.353516 | 1.961353 | 1.757812 | 2.291139 |
10 | 1.024 | 793 | 386 | 407 | 0.774414 | 0.376953 | 0.397461 | 1.953202 | 1.715556 | 2.248619 |
11 | 2.048 | 1.560 | 702 | 858 | 0.761719 | 0.342773 | 0.418945 | 1.967213 | 1.818653 | 2.108108 |
12 | 4.096 | 3.068 | 1.270 | 1.798 | 0.749023 | 0.310059 | 0.438965 | 1.966667 | 1.809117 | 2.095571 |
13 | 8.192 | 6.112 | 2.293 | 3.819 | 0.746094 | 0.279907 | 0.466187 | 1.992177 | 1.805512 | 2.124027 |
14 | 16.384 | 12.165 | 4.235 | 7.930 | 0.742493 | 0.258484 | 0.484009 | 1.990347 | 1.846925 | 2.076460 |
15 | 32.768 | 24.210 | 7.847 | 16.363 | 0.738831 | 0.239471 | 0.499359 | 1.990136 | 1.852893 | 2.063430 |
16 | 65.536 | 48.220 | 14.491 | 33.729 | 0.735779 | 0.221115 | 0.514664 | 1.991739 | 1.846693 | 2.061297 |
17 | 131.072 | 96.027 | 27.139 | 68.888 | 0.732628 | 0.207054 | 0.525574 | 1.991435 | 1.872818 | 2.042397 |
18 | 262.144 | 191.435 | 51.001 | 140.434 | 0.730267 | 0.194553 | 0.535713 | 1.993554 | 1.879251 | 2.038584 |
19 | 524.288 | 381.572 | 95.995 | 285.577 | 0.727791 | 0.183096 | 0.544695 | 1.993220 | 1.882218 | 2.033532 |
20 | 1.048.576 | 761.546 | 181.378 | 580.168 | 0.726267 | 0.172976 | 0.553291 | 1.995812 | 1.889453 | 2.031564 |
21 | 2.097.152 | 1.519.469 | 344.026 | 1.175.443 | 0.724539 | 0.164044 | 0.560495 | 1.995243 | 1.896735 | 2.026039 |
22 | 4.194.304 | 3.032.527 | 653.678 | 2.378.849 | 0.723011 | 0.155849 | 0.567162 | 1.995781 | 1.900083 | 2.023789 |
23 | 8.388.608 | 6.053.454 | 1.245.245 | 4.808.209 | 0.721628 | 0.148445 | 0.573183 | 1.996175 | 1.904982 | 2.021233 |
24 | 16.777.216 | 12.086.843 | 2.375.766 | 9.711.077 | 0.720432 | 0.141607 | 0.578825 | 1.996685 | 1.907870 | 2.019687 |
25 | 33.554.432 | 24.134.559 | 4.544.426 | 19.590.133 | 0.719266 | 0.135434 | 0.583831 | 1.996763 | 1.912826 | 2.017298 |
26 | 67.108.864 | 48.199.536 | 8.713.560 | 39.485.976 | 0.718229 | 0.129842 | 0.588387 | 1.997117 | 1.917417 | 2.015605 |
27 | 134.217.728 | 96.266.374 | 16.727.736 | 79.538.638 | 0.717240 | 0.124631 | 0.592609 | 1.997247 | 1.919736 | 2.014352 |
28 | 268.435.456 | 192.294.113 | 32.170.445 | 160.123.668 | 0.716351 | 0.119844 | 0.596507 | 1.997521 | 1.923180 | 2.013156 |
29 | 536.870.912 | 384.133.356 | 61.969.103 | 322.164.253 | 0.715504 | 0.115426 | 0.600078 | 1.997634 | 1.926274 | 2.011971 |
30 | 1.073.741.824 | 767.419.417 | 119.518.125 | 647.901.292 | 0.714715 | 0.111310 | 0.603405 | 1.997794 | 1.928673 | 2.011090 |
31 | 2.147.483.648 | 1.533.253.868 | 230.825.223 | 1.302.428.645 | 0.713977 | 0.107486 | 0.606491 | 1.997935 | 1.931299 | 2.010227 |
32 | 4.294.967.296 | 3.063.544.445 | 446.322.753 | 2.617.221.692 | 0.713287 | 0.103918 | 0.609369 | 1.998067 | 1.933596 | 2.009493 |
33 | 8.589.934.592 | 6.121.544.031 | 864.003.530 | 5.257.540.501 | 0.712642 | 0.100583 | 0.612058 | 1.998190 | 1.935827 | 2.008825 |
34 | 17.179.869.184 | 12.232.707.857 | 1.674.225.070 | 10.558.482.787 | 0.712037 | 0.097453 | 0.614585 | 1.998304 | 1.937753 | 2.008255 |
35 | 34.359.738.368 | 24.445.917.059 | 3.247.458.032 | 21.198.459.027 | 0.711470 | 0.094513 | 0.616956 | 1.998406 | 1.939678 | 2.007718 |
36 | 68.719.476.736 | 48.855.096.059 | 6.304.819.172 | 42.550.276.887 | 0.710935 | 0.091747 | 0.619188 | 1.998497 | 1.941463 | 2.007234 |
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 | 3 | 1 | 2 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 2 | 3 | 2 | 1 | 0 | 2 |
3 | 8 | 8 | 3 | 5 | 3 | 2 | 1 | 2 |
4 | 16 | 14 | 6 | 8 | 5 | 3 | 2 | 4 |
5 | 32 | 24 | 13 | 11 | 7 | 6 | 4 | 7 |
6 | 64 | 40 | 23 | 17 | 13 | 11 | 6 | 10 |
7 | 128 | 69 | 40 | 29 | 20 | 18 | 14 | 17 |
8 | 256 | 128 | 69 | 59 | 33 | 33 | 29 | 33 |
9 | 512 | 225 | 114 | 111 | 60 | 59 | 51 | 55 |
10 | 1.024 | 386 | 197 | 189 | 102 | 95 | 87 | 102 |
11 | 2.048 | 702 | 356 | 346 | 181 | 180 | 157 | 184 |
12 | 4.096 | 1.270 | 637 | 633 | 331 | 307 | 305 | 327 |
13 | 8.192 | 2.293 | 1.164 | 1.129 | 580 | 571 | 556 | 586 |
14 | 16.384 | 4.235 | 2.132 | 2.103 | 1.041 | 1.063 | 1.037 | 1.094 |
15 | 32.768 | 7.847 | 3.960 | 3.887 | 1.895 | 1.989 | 1.945 | 2.018 |
16 | 65.536 | 14.491 | 7.286 | 7.205 | 3.519 | 3.661 | 3.568 | 3.743 |
17 | 131.072 | 27.139 | 13.629 | 13.510 | 6.653 | 6.874 | 6.725 | 6.887 |
18 | 262.144 | 51.001 | 25.654 | 25.347 | 12.515 | 12.938 | 12.595 | 12.953 |
19 | 524.288 | 95.995 | 48.242 | 47.753 | 23.734 | 24.289 | 23.743 | 24.229 |
20 | 1.048.576 | 181.378 | 90.991 | 90.387 | 44.803 | 45.896 | 44.772 | 45.907 |
21 | 2.097.152 | 344.026 | 172.639 | 171.387 | 85.095 | 87.141 | 84.755 | 87.035 |
22 | 4.194.304 | 653.678 | 328.213 | 325.465 | 161.694 | 165.122 | 161.276 | 165.586 |
23 | 8.388.608 | 1.245.245 | 625.194 | 620.051 | 307.650 | 314.646 | 307.737 | 315.212 |
24 | 16.777.216 | 2.375.766 | 1.193.066 | 1.182.700 | 587.200 | 600.617 | 587.364 | 600.585 |
25 | 33.554.432 | 4.544.426 | 2.280.764 | 2.263.662 | 1.124.466 | 1.148.080 | 1.123.508 | 1.148.372 |
26 | 67.108.864 | 8.713.560 | 4.371.623 | 4.341.937 | 2.155.975 | 2.200.386 | 2.155.500 | 2.201.699 |
27 | 134.217.728 | 16.727.736 | 8.392.691 | 8.335.045 | 4.140.853 | 4.222.663 | 4.138.936 | 4.225.284 |
28 | 268.435.456 | 32.170.445 | 16.138.706 | 16.031.739 | 7.965.331 | 8.120.528 | 7.964.344 | 8.120.242 |
29 | 536.870.912 | 61.969.103 | 31.082.596 | 30.886.507 | 15.348.541 | 15.635.733 | 15.350.449 | 15.634.380 |
30 | 1.073.741.824 | 119.518.125 | 59.944.102 | 59.574.023 | 29.611.874 | 30.145.941 | 29.615.911 | 30.144.399 |
31 | 2.147.483.648 | 230.825.223 | 115.750.871 | 115.074.352 | 57.207.970 | 58.202.735 | 57.209.705 | 58.204.813 |
32 | 4.294.967.296 | 446.322.753 | 223.783.991 | 222.538.762 | 110.659.074 | 112.502.454 | 110.651.881 | 112.509.344 |
33 | 8.589.934.592 | 864.003.530 | 433.160.892 | 430.842.638 | 214.275.533 | 217.723.213 | 214.266.618 | 217.738.166 |
34 | 17.179.869.184 | 1.674.225.070 | 839.276.416 | 834.948.654 | 415.311.668 | 421.802.361 | 415.301.565 | 421.809.476 |
35 | 34.359.738.368 | 3.247.458.032 | 1.627.787.942 | 1.619.670.090 | 805.776.572 | 817.984.878 | 805.727.026 | 817.969.556 |
36 | 68.719.476.736 | 6.304.819.172 | 3.160.048.197 | 3.144.770.975 | 1.564.696.157 | 1.587.712.599 | 1.564.666.324 | 1.587.744.092 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
4 | 16 | 2 | 1 | 1 | 1 | 0 | 1 | 0 |
5 | 32 | 5 | 2 | 3 | 1 | 1 | 1 | 2 |
6 | 64 | 15 | 7 | 8 | 2 | 3 | 6 | 4 |
7 | 128 | 37 | 16 | 21 | 9 | 8 | 11 | 9 |
8 | 256 | 79 | 39 | 40 | 17 | 20 | 22 | 20 |
9 | 512 | 181 | 96 | 85 | 41 | 41 | 52 | 47 |
10 | 1.024 | 407 | 197 | 210 | 96 | 105 | 112 | 94 |
11 | 2.048 | 858 | 427 | 431 | 200 | 222 | 225 | 211 |
12 | 4.096 | 1.798 | 877 | 921 | 440 | 452 | 457 | 449 |
13 | 8.192 | 3.819 | 1.885 | 1.934 | 934 | 947 | 961 | 977 |
14 | 16.384 | 7.930 | 3.964 | 3.966 | 1.967 | 1.966 | 2.010 | 1.987 |
15 | 32.768 | 16.363 | 8.168 | 8.195 | 4.062 | 4.093 | 4.103 | 4.105 |
16 | 65.536 | 33.729 | 16.817 | 16.912 | 8.406 | 8.457 | 8.447 | 8.419 |
17 | 131.072 | 68.888 | 34.322 | 34.566 | 17.210 | 17.284 | 17.233 | 17.161 |
18 | 262.144 | 140.434 | 70.057 | 70.377 | 35.177 | 35.127 | 35.203 | 34.927 |
19 | 524.288 | 285.577 | 142.492 | 143.085 | 71.348 | 71.352 | 71.574 | 71.303 |
20 | 1.048.576 | 580.168 | 289.663 | 290.505 | 145.037 | 145.089 | 145.230 | 144.812 |
21 | 2.097.152 | 1.175.443 | 587.330 | 588.113 | 294.119 | 293.568 | 293.945 | 293.811 |
22 | 4.194.304 | 2.378.849 | 1.189.272 | 1.189.577 | 594.370 | 594.733 | 595.069 | 594.677 |
23 | 8.388.608 | 4.808.209 | 2.402.997 | 2.405.212 | 1.201.313 | 1.202.409 | 1.202.549 | 1.201.938 |
24 | 16.777.216 | 9.711.077 | 4.852.932 | 4.858.145 | 2.428.487 | 2.427.266 | 2.428.516 | 2.426.808 |
25 | 33.554.432 | 19.590.133 | 9.789.303 | 9.800.830 | 4.900.466 | 4.896.742 | 4.897.217 | 4.895.708 |
26 | 67.108.864 | 39.485.976 | 19.734.576 | 19.751.400 | 9.873.229 | 9.870.357 | 9.872.877 | 9.869.513 |
27 | 134.217.728 | 79.538.638 | 39.756.377 | 39.782.261 | 19.889.413 | 19.879.712 | 19.888.978 | 19.880.535 |
28 | 268.435.456 | 160.123.668 | 80.043.209 | 80.080.459 | 40.042.180 | 40.016.678 | 40.042.797 | 40.022.013 |
29 | 536.870.912 | 322.164.253 | 161.053.532 | 161.110.721 | 80.556.641 | 80.521.974 | 80.558.958 | 80.526.680 |
30 | 1.073.741.824 | 647.901.292 | 323.883.510 | 324.017.782 | 162.010.018 | 161.943.133 | 162.007.028 | 161.941.113 |
31 | 2.147.483.648 | 1.302.428.645 | 651.091.225 | 651.337.420 | 325.677.280 | 325.539.482 | 325.649.432 | 325.562.451 |
32 | 4.294.967.296 | 2.617.221.692 | 1.308.391.905 | 1.308.829.787 | 654.430.477 | 654.201.019 | 654.398.943 | 654.191.253 |
33 | 8.589.934.592 | 5.257.540.501 | 2.628.394.108 | 2.629.146.393 | 1.314.560.669 | 1.314.194.769 | 1.314.597.071 | 1.314.187.992 |
34 | 17.179.869.184 | 10.558.482.787 | 5.278.559.152 | 5.279.923.635 | 2.640.006.988 | 2.639.253.385 | 2.639.974.049 | 2.639.248.365 |
35 | 34.359.738.368 | 21.198.459.027 | 10.597.970.936 | 10.600.488.091 | 5.300.353.647 | 5.298.888.032 | 5.300.310.693 | 5.298.906.655 |
36 | 68.719.476.736 | 42.550.276.887 | 21.272.870.044 | 21.277.406.843 | 10.638.980.599 | 10.636.150.297 | 10.638.868.435 | 10.636.277.556 |