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+32x-71
f(0)=71
f(1)=19
f(2)=3
f(3)=17
f(4)=73
f(5)=1
f(6)=157
f(7)=101
f(8)=83
f(9)=149
f(10)=349
f(11)=67
f(12)=457
f(13)=257
f(14)=191
f(15)=317
f(16)=41
f(17)=127
f(18)=829
f(19)=449
f(20)=1
f(21)=521
f(22)=1117
f(23)=199
f(24)=1
f(25)=677
f(26)=479
f(27)=761
f(28)=1609
f(29)=283
f(30)=1789
f(31)=941
f(32)=659
f(33)=61
f(34)=53
f(35)=379
f(36)=2377
f(37)=1
f(38)=863
f(39)=1
f(40)=1
f(41)=487
f(42)=3037
f(43)=1
f(44)=1091
f(45)=1697
f(46)=3517
f(47)=607
f(48)=3769
f(49)=1949
f(50)=79
f(51)=2081
f(52)=4297
f(53)=739
f(54)=269
f(55)=2357
f(56)=1619
f(57)=1
f(58)=271
f(59)=883
f(60)=5449
f(61)=2801
f(62)=1
f(63)=2957
f(64)=6073
f(65)=1039
f(66)=6397
f(67)=193
f(68)=2243
f(69)=3449
f(70)=7069
f(71)=1
f(72)=7417
f(73)=3797
f(74)=2591
f(75)=97
f(76)=103
f(77)=1
f(78)=1
f(79)=4349
f(80)=2963
f(81)=239
f(82)=9277
f(83)=1579
f(84)=569
f(85)=4937
f(86)=3359
f(87)=1
f(88)=617
f(89)=1783
f(90)=10909
f(91)=1
f(92)=3779
f(93)=109
f(94)=1
f(95)=1999
f(96)=643
f(97)=6221
f(98)=1
f(99)=6449
b) Substitution of the polynom
The polynom f(x)=x^2+32x-71 could be written as f(y)= y^2-327 with x=y-16
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+16
f'(x)>2x+31
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 | 5 | 5 | 1.000000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 80 | 22 | 58 | 0.800000 | 0.220000 | 0.800000 | 8.000000 | 4.400000 | 11.600000 |
3 | 1.000 | 748 | 134 | 614 | 0.748000 | 0.134000 | 0.748000 | 9.350000 | 6.090909 | 10.586206 |
4 | 10.000 | 7.276 | 1.000 | 6.276 | 0.727600 | 0.100000 | 0.727600 | 9.727273 | 7.462687 | 10.221498 |
5 | 100.000 | 72.143 | 7.696 | 64.447 | 0.721430 | 0.076960 | 0.721430 | 9.915200 | 7.696000 | 10.268802 |
6 | 1.000.000 | 717.149 | 63.086 | 654.063 | 0.717149 | 0.063086 | 0.717149 | 9.940660 | 8.197246 | 10.148851 |
7 | 10.000.000 | 7.133.961 | 533.126 | 6.600.835 | 0.713396 | 0.053313 | 0.713396 | 9.947669 | 8.450782 | 10.092048 |
8 | 100.000.000 | 71.066.246 | 4.612.831 | 66.453.415 | 0.710662 | 0.046128 | 0.710662 | 9.961681 | 8.652422 | 10.067426 |
9 | 1.000.000.000 | 708.565.226 | 40.698.034 | 667.867.192 | 0.708565 | 0.040698 | 0.708565 | 9.970490 | 8.822788 | 10.050156 |
10 | 10.000.000.000 | 7.069.132.085 | 364.189.186 | 6.704.942.899 | 0.706913 | 0.036419 | 0.706913 | 9.976685 | 8.948570 | 10.039336 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 1.600000 | 1.333333 | 2.000000 |
4 | 16 | 16 | 6 | 10 | 1.000000 | 0.375000 | 0.625000 | 2.000000 | 1.500000 | 2.500000 |
5 | 32 | 30 | 10 | 20 | 0.937500 | 0.312500 | 0.625000 | 1.875000 | 1.666667 | 2.000000 |
6 | 64 | 53 | 17 | 36 | 0.828125 | 0.265625 | 0.562500 | 1.766667 | 1.700000 | 1.800000 |
7 | 128 | 101 | 28 | 73 | 0.789062 | 0.218750 | 0.570312 | 1.905660 | 1.647059 | 2.027778 |
8 | 256 | 196 | 44 | 152 | 0.765625 | 0.171875 | 0.593750 | 1.940594 | 1.571429 | 2.082192 |
9 | 512 | 389 | 75 | 314 | 0.759766 | 0.146484 | 0.613281 | 1.984694 | 1.704545 | 2.065789 |
10 | 1.024 | 764 | 136 | 628 | 0.746094 | 0.132812 | 0.613281 | 1.964010 | 1.813333 | 2.000000 |
11 | 2.048 | 1.506 | 259 | 1.247 | 0.735352 | 0.126465 | 0.608887 | 1.971204 | 1.904412 | 1.985669 |
12 | 4.096 | 2.997 | 468 | 2.529 | 0.731689 | 0.114258 | 0.617432 | 1.990040 | 1.806950 | 2.028067 |
13 | 8.192 | 5.976 | 858 | 5.118 | 0.729492 | 0.104736 | 0.624756 | 1.993994 | 1.833333 | 2.023725 |
14 | 16.384 | 11.909 | 1.551 | 10.358 | 0.726868 | 0.094666 | 0.632202 | 1.992805 | 1.807692 | 2.023837 |
15 | 32.768 | 23.736 | 2.830 | 20.906 | 0.724365 | 0.086365 | 0.638000 | 1.993114 | 1.824629 | 2.018343 |
16 | 65.536 | 47.333 | 5.259 | 42.074 | 0.722244 | 0.080246 | 0.641998 | 1.994144 | 1.858304 | 2.012532 |
17 | 131.072 | 94.506 | 9.846 | 84.660 | 0.721024 | 0.075119 | 0.645905 | 1.996620 | 1.872219 | 2.012169 |
18 | 262.144 | 188.650 | 18.466 | 170.184 | 0.719643 | 0.070442 | 0.649200 | 1.996170 | 1.875482 | 2.010206 |
19 | 524.288 | 376.466 | 34.942 | 341.524 | 0.718052 | 0.066647 | 0.651405 | 1.995579 | 1.892234 | 2.006793 |
20 | 1.048.576 | 751.973 | 65.951 | 686.022 | 0.717137 | 0.062896 | 0.654242 | 1.997453 | 1.887442 | 2.008708 |
21 | 2.097.152 | 1.501.158 | 125.253 | 1.375.905 | 0.715808 | 0.059725 | 0.656083 | 1.996292 | 1.899183 | 2.005628 |
22 | 4.194.304 | 2.997.398 | 237.616 | 2.759.782 | 0.714635 | 0.056652 | 0.657983 | 1.996724 | 1.897088 | 2.005794 |
23 | 8.388.608 | 5.986.503 | 452.458 | 5.534.045 | 0.713647 | 0.053937 | 0.659710 | 1.997233 | 1.904156 | 2.005247 |
24 | 16.777.216 | 11.957.172 | 863.181 | 11.093.991 | 0.712703 | 0.051450 | 0.661253 | 1.997355 | 1.907759 | 2.004680 |
25 | 33.554.432 | 23.886.441 | 1.652.448 | 22.233.993 | 0.711871 | 0.049247 | 0.662625 | 1.997666 | 1.914370 | 2.004147 |
26 | 67.108.864 | 47.720.263 | 3.169.575 | 44.550.688 | 0.711087 | 0.047230 | 0.663857 | 1.997797 | 1.918109 | 2.003720 |
27 | 134.217.728 | 95.344.041 | 6.087.281 | 89.256.760 | 0.710368 | 0.045354 | 0.665015 | 1.997978 | 1.920535 | 2.003488 |
28 | 268.435.456 | 190.507.991 | 11.711.438 | 178.796.553 | 0.709698 | 0.043629 | 0.666069 | 1.998111 | 1.923919 | 2.003171 |
29 | 536.870.912 | 380.688.292 | 22.563.157 | 358.125.135 | 0.709087 | 0.042027 | 0.667060 | 1.998280 | 1.926591 | 2.002975 |
30 | 1.073.741.824 | 760.756.769 | 43.542.944 | 717.213.825 | 0.708510 | 0.040553 | 0.667957 | 1.998372 | 1.929825 | 2.002691 |
31 | 2.147.483.648 | 1.520.365.431 | 84.105.623 | 1.436.259.808 | 0.707975 | 0.039165 | 0.668811 | 1.998491 | 1.931556 | 2.002555 |
32 | 4.294.967.296 | 3.038.595.410 | 162.682.742 | 2.875.912.668 | 0.707478 | 0.037878 | 0.669601 | 1.998595 | 1.934267 | 2.002362 |
33 | 8.589.934.592 | 6.073.175.183 | 315.023.878 | 5.758.151.305 | 0.707011 | 0.036674 | 0.670337 | 1.998678 | 1.936431 | 2.002200 |
34 | 17.179.869.184 | 12.138.861.839 | 610.599.370 | 11.528.262.469 | 0.706575 | 0.035542 | 0.671033 | 1.998767 | 1.938264 | 2.002077 |
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 | 1 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 1 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 1 | 1 | 1 | 1 | 1 |
4 | 16 | 6 | 4 | 1 | 2 | 1 | 2 | 1 |
5 | 32 | 10 | 8 | 1 | 3 | 1 | 5 | 1 |
6 | 64 | 17 | 15 | 1 | 8 | 1 | 7 | 1 |
7 | 128 | 28 | 26 | 1 | 12 | 1 | 14 | 1 |
8 | 256 | 44 | 42 | 1 | 21 | 1 | 21 | 1 |
9 | 512 | 75 | 73 | 1 | 33 | 1 | 40 | 1 |
10 | 1.024 | 136 | 134 | 1 | 65 | 1 | 69 | 1 |
11 | 2.048 | 259 | 257 | 1 | 123 | 1 | 134 | 1 |
12 | 4.096 | 468 | 466 | 1 | 224 | 1 | 242 | 1 |
13 | 8.192 | 858 | 856 | 1 | 427 | 1 | 429 | 1 |
14 | 16.384 | 1.551 | 1.549 | 1 | 781 | 1 | 768 | 1 |
15 | 32.768 | 2.830 | 2.828 | 1 | 1.421 | 1 | 1.407 | 1 |
16 | 65.536 | 5.259 | 5.257 | 1 | 2.640 | 1 | 2.617 | 1 |
17 | 131.072 | 9.846 | 9.844 | 1 | 4.954 | 1 | 4.890 | 1 |
18 | 262.144 | 18.466 | 18.464 | 1 | 9.305 | 1 | 9.159 | 1 |
19 | 524.288 | 34.942 | 34.940 | 1 | 17.527 | 1 | 17.413 | 1 |
20 | 1.048.576 | 65.951 | 65.949 | 1 | 32.983 | 1 | 32.966 | 1 |
21 | 2.097.152 | 125.253 | 125.251 | 1 | 62.591 | 1 | 62.660 | 1 |
22 | 4.194.304 | 237.616 | 237.614 | 1 | 118.799 | 1 | 118.815 | 1 |
23 | 8.388.608 | 452.458 | 452.456 | 1 | 226.315 | 1 | 226.141 | 1 |
24 | 16.777.216 | 863.181 | 863.179 | 1 | 431.232 | 1 | 431.947 | 1 |
25 | 33.554.432 | 1.652.448 | 1.652.446 | 1 | 825.480 | 1 | 826.966 | 1 |
26 | 67.108.864 | 3.169.575 | 3.169.573 | 1 | 1.584.124 | 1 | 1.585.449 | 1 |
27 | 134.217.728 | 6.087.281 | 6.087.279 | 1 | 3.043.233 | 1 | 3.044.046 | 1 |
28 | 268.435.456 | 11.711.438 | 11.711.436 | 1 | 5.855.829 | 1 | 5.855.607 | 1 |
29 | 536.870.912 | 22.563.157 | 22.563.155 | 1 | 11.280.963 | 1 | 11.282.192 | 1 |
30 | 1.073.741.824 | 43.542.944 | 43.542.942 | 1 | 21.768.251 | 1 | 21.774.691 | 1 |
31 | 2.147.483.648 | 84.105.623 | 84.105.621 | 1 | 42.048.564 | 1 | 42.057.057 | 1 |
32 | 4.294.967.296 | 162.682.742 | 162.682.740 | 1 | 81.333.355 | 1 | 81.349.385 | 1 |
33 | 8.589.934.592 | 315.023.878 | 315.023.876 | 1 | 157.500.036 | 1 | 157.523.840 | 1 |
34 | 17.179.869.184 | 610.599.370 | 610.599.368 | 1 | 305.291.157 | 1 | 305.308.211 | 1 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 4 | 1 | 3 | 1 | 2 | 1 | 0 |
4 | 16 | 10 | 2 | 8 | 3 | 3 | 3 | 1 |
5 | 32 | 20 | 5 | 15 | 6 | 5 | 5 | 4 |
6 | 64 | 36 | 11 | 25 | 9 | 10 | 9 | 8 |
7 | 128 | 73 | 23 | 50 | 19 | 21 | 17 | 16 |
8 | 256 | 152 | 55 | 97 | 41 | 38 | 37 | 36 |
9 | 512 | 314 | 112 | 202 | 83 | 75 | 80 | 76 |
10 | 1.024 | 628 | 234 | 394 | 151 | 160 | 157 | 160 |
11 | 2.048 | 1.247 | 481 | 766 | 300 | 321 | 313 | 313 |
12 | 4.096 | 2.529 | 1.026 | 1.503 | 603 | 644 | 634 | 648 |
13 | 8.192 | 5.118 | 2.124 | 2.994 | 1.232 | 1.299 | 1.267 | 1.320 |
14 | 16.384 | 10.358 | 4.425 | 5.933 | 2.536 | 2.649 | 2.538 | 2.635 |
15 | 32.768 | 20.906 | 8.962 | 11.944 | 5.130 | 5.307 | 5.197 | 5.272 |
16 | 65.536 | 42.074 | 18.281 | 23.793 | 10.363 | 10.724 | 10.433 | 10.554 |
17 | 131.072 | 84.660 | 37.200 | 47.460 | 20.897 | 21.394 | 21.120 | 21.249 |
18 | 262.144 | 170.184 | 75.365 | 94.819 | 42.131 | 43.023 | 42.321 | 42.709 |
19 | 524.288 | 341.524 | 153.086 | 188.438 | 84.652 | 86.009 | 85.041 | 85.822 |
20 | 1.048.576 | 686.022 | 309.766 | 376.256 | 170.758 | 172.685 | 170.397 | 172.182 |
21 | 2.097.152 | 1.375.905 | 625.195 | 750.710 | 342.946 | 345.280 | 342.272 | 345.407 |
22 | 4.194.304 | 2.759.782 | 1.260.112 | 1.499.670 | 688.653 | 692.148 | 687.240 | 691.741 |
23 | 8.388.608 | 5.534.045 | 2.538.644 | 2.995.401 | 1.380.601 | 1.387.789 | 1.378.678 | 1.386.977 |
24 | 16.777.216 | 11.093.991 | 5.110.689 | 5.983.302 | 2.767.270 | 2.781.054 | 2.765.938 | 2.779.729 |
25 | 33.554.432 | 22.233.993 | 10.283.033 | 11.950.960 | 5.544.470 | 5.573.802 | 5.543.730 | 5.571.991 |
26 | 67.108.864 | 44.550.688 | 20.678.836 | 23.871.852 | 11.111.914 | 11.167.666 | 11.109.510 | 11.161.598 |
27 | 134.217.728 | 89.256.760 | 41.560.439 | 47.696.321 | 22.267.493 | 22.362.248 | 22.263.636 | 22.363.383 |
28 | 268.435.456 | 178.796.553 | 83.494.142 | 95.302.411 | 44.604.031 | 44.793.854 | 44.613.268 | 44.785.400 |
29 | 536.870.912 | 358.125.135 | 167.687.719 | 190.437.416 | 89.364.595 | 89.695.390 | 89.366.567 | 89.698.583 |
30 | 1.073.741.824 | 717.213.825 | 336.661.564 | 380.552.261 | 178.995.346 | 179.625.067 | 178.986.642 | 179.606.770 |
31 | 2.147.483.648 | 1.436.259.808 | 675.754.636 | 760.505.172 | 358.487.671 | 359.649.745 | 358.477.706 | 359.644.686 |
32 | 4.294.967.296 | 2.875.912.668 | 1.356.002.388 | 1.519.910.280 | 717.903.606 | 720.060.643 | 717.861.709 | 720.086.710 |
33 | 8.589.934.592 | 5.758.151.305 | 2.720.423.032 | 3.037.728.273 | 1.437.506.723 | 1.441.561.907 | 1.437.477.022 | 1.441.605.653 |
34 | 17.179.869.184 | 11.528.262.469 | 5.456.644.335 | 6.071.618.134 | 2.878.260.652 | 2.885.879.359 | 2.878.185.565 | 2.885.936.893 |