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-92x+13
f(0)=13
f(1)=3
f(2)=167
f(3)=127
f(4)=113
f(5)=211
f(6)=503
f(7)=97
f(8)=659
f(9)=367
f(10)=269
f(11)=439
f(12)=947
f(13)=1
f(14)=83
f(15)=571
f(16)=401
f(17)=631
f(18)=1319
f(19)=229
f(20)=1427
f(21)=739
f(22)=509
f(23)=787
f(24)=1619
f(25)=277
f(26)=131
f(27)=67
f(28)=593
f(29)=907
f(30)=1847
f(31)=313
f(32)=1907
f(33)=967
f(34)=653
f(35)=991
f(36)=2003
f(37)=337
f(38)=2039
f(39)=79
f(40)=53
f(41)=1039
f(42)=2087
f(43)=349
f(44)=2099
f(45)=1051
f(46)=701
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=1
f(67)=1
f(68)=1
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=1
f(74)=1
f(75)=1
f(76)=1
f(77)=1
f(78)=1
f(79)=1
f(80)=1
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=1
f(93)=1
f(94)=1
f(95)=149
f(96)=397
f(97)=1
f(98)=601
f(99)=353
b) Substitution of the polynom
The polynom f(x)=x^2-92x+13 could be written as f(y)= y^2-2103 with x=y+46
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-46
f'(x)>2x-93 with x > 46
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 | 49 | 16 | 33 | 0.490000 | 0.160000 | 0.490000 | 4.454545 | 4.000000 | 4.714286 |
3 | 1.000 | 782 | 188 | 594 | 0.782000 | 0.188000 | 0.782000 | 15.959184 | 11.750000 | 18.000000 |
4 | 10.000 | 8.063 | 1.364 | 6.699 | 0.806300 | 0.136400 | 0.806300 | 10.310741 | 7.255319 | 11.277778 |
5 | 100.000 | 78.911 | 10.685 | 68.226 | 0.789110 | 0.106850 | 0.789110 | 9.786804 | 7.833578 | 10.184505 |
6 | 1.000.000 | 773.514 | 87.399 | 686.115 | 0.773514 | 0.087399 | 0.773514 | 9.802360 | 8.179598 | 10.056503 |
7 | 10.000.000 | 7.615.460 | 738.545 | 6.876.915 | 0.761546 | 0.073854 | 0.761546 | 9.845278 | 8.450269 | 10.022977 |
8 | 100.000.000 | 75.256.468 | 6.397.396 | 68.859.072 | 0.752565 | 0.063974 | 0.752565 | 9.882064 | 8.662162 | 10.013076 |
9 | 1.000.000.000 | 745.600.743 | 56.474.361 | 689.126.382 | 0.745601 | 0.056474 | 0.745601 | 9.907465 | 8.827710 | 10.007779 |
10 | 10.000.000.000 | 7.401.106.382 | 505.396.275 | 6.895.710.107 | 0.740111 | 0.050540 | 0.740111 | 9.926367 | 8.949128 | 10.006452 |
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 | 4 | 5 | 1.125000 | 0.500000 | 0.625000 | 1.800000 | 2.000000 | 1.666667 |
4 | 16 | 16 | 5 | 11 | 1.000000 | 0.312500 | 0.687500 | 1.777778 | 1.250000 | 2.200000 |
5 | 32 | 32 | 10 | 22 | 1.000000 | 0.312500 | 0.687500 | 2.000000 | 2.000000 | 2.000000 |
6 | 64 | 45 | 14 | 31 | 0.703125 | 0.218750 | 0.484375 | 1.406250 | 1.400000 | 1.409091 |
7 | 128 | 72 | 25 | 47 | 0.562500 | 0.195312 | 0.367188 | 1.600000 | 1.785714 | 1.516129 |
8 | 256 | 179 | 52 | 127 | 0.699219 | 0.203125 | 0.496094 | 2.486111 | 2.080000 | 2.702128 |
9 | 512 | 388 | 99 | 289 | 0.757812 | 0.193359 | 0.564453 | 2.167598 | 1.903846 | 2.275591 |
10 | 1.024 | 799 | 191 | 608 | 0.780273 | 0.186523 | 0.593750 | 2.059278 | 1.929293 | 2.103806 |
11 | 2.048 | 1.627 | 349 | 1.278 | 0.794434 | 0.170410 | 0.624023 | 2.036295 | 1.827225 | 2.101974 |
12 | 4.096 | 3.292 | 648 | 2.644 | 0.803711 | 0.158203 | 0.645508 | 2.023356 | 1.856734 | 2.068858 |
13 | 8.192 | 6.609 | 1.150 | 5.459 | 0.806763 | 0.140381 | 0.666382 | 2.007594 | 1.774691 | 2.064675 |
14 | 16.384 | 13.146 | 2.110 | 11.036 | 0.802368 | 0.128784 | 0.673584 | 1.989106 | 1.834783 | 2.021616 |
15 | 32.768 | 26.127 | 3.928 | 22.199 | 0.797333 | 0.119873 | 0.677460 | 1.987449 | 1.861611 | 2.011508 |
16 | 65.536 | 51.941 | 7.267 | 44.674 | 0.792557 | 0.110886 | 0.681671 | 1.988020 | 1.850051 | 2.012433 |
17 | 131.072 | 103.201 | 13.633 | 89.568 | 0.787361 | 0.104012 | 0.683350 | 1.986889 | 1.876015 | 2.004925 |
18 | 262.144 | 205.063 | 25.663 | 179.400 | 0.782253 | 0.097897 | 0.684357 | 1.987025 | 1.882418 | 2.002948 |
19 | 524.288 | 407.705 | 48.276 | 359.429 | 0.777636 | 0.092079 | 0.685556 | 1.988194 | 1.881152 | 2.003506 |
20 | 1.048.576 | 810.837 | 91.260 | 719.577 | 0.773274 | 0.087032 | 0.686242 | 1.988784 | 1.890380 | 2.002000 |
21 | 2.097.152 | 1.613.192 | 173.192 | 1.440.000 | 0.769230 | 0.082584 | 0.686646 | 1.989539 | 1.897786 | 2.001176 |
22 | 4.194.304 | 3.211.105 | 329.409 | 2.881.696 | 0.765587 | 0.078537 | 0.687050 | 1.990529 | 1.901987 | 2.001178 |
23 | 8.388.608 | 6.394.723 | 627.435 | 5.767.288 | 0.762310 | 0.074796 | 0.687514 | 1.991440 | 1.904729 | 2.001352 |
24 | 16.777.216 | 12.739.303 | 1.196.917 | 11.542.386 | 0.759322 | 0.071342 | 0.687980 | 1.992159 | 1.907635 | 2.001354 |
25 | 33.554.432 | 25.384.863 | 2.292.149 | 23.092.714 | 0.756528 | 0.068311 | 0.688217 | 1.992642 | 1.915044 | 2.000688 |
26 | 67.108.864 | 50.595.266 | 4.395.718 | 46.199.548 | 0.753928 | 0.065501 | 0.688427 | 1.993127 | 1.917728 | 2.000612 |
27 | 134.217.728 | 100.873.945 | 8.442.318 | 92.431.627 | 0.751569 | 0.062900 | 0.688669 | 1.993743 | 1.920578 | 2.000704 |
28 | 268.435.456 | 201.153.125 | 16.250.404 | 184.902.721 | 0.749354 | 0.060537 | 0.688816 | 1.994104 | 1.924875 | 2.000427 |
29 | 536.870.912 | 401.207.422 | 31.316.749 | 369.890.673 | 0.747307 | 0.058332 | 0.688975 | 1.994537 | 1.927137 | 2.000461 |
30 | 1.073.741.824 | 800.380.884 | 60.420.618 | 739.960.266 | 0.745413 | 0.056271 | 0.689142 | 1.994930 | 1.929339 | 2.000484 |
31 | 2.147.483.648 | 1.596.959.086 | 116.724.671 | 1.480.234.415 | 0.743642 | 0.054354 | 0.689288 | 1.995249 | 1.931868 | 2.000424 |
32 | 4.294.967.296 | 3.186.814.525 | 225.775.959 | 2.961.038.566 | 0.741988 | 0.052568 | 0.689421 | 1.995552 | 1.934261 | 2.000385 |
33 | 8.589.934.592 | 6.360.307.732 | 437.176.594 | 5.923.131.138 | 0.740437 | 0.050894 | 0.689543 | 1.995820 | 1.936329 | 2.000356 |
34 | 17.179.869.184 | 12.695.643.850 | 847.337.684 | 11.848.306.166 | 0.738984 | 0.049322 | 0.689662 | 1.996074 | 1.938205 | 2.000345 |
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 | 1 | 1 | 0 | 0 | 1 | 1 |
2 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 1 |
3 | 8 | 4 | 1 | 3 | 0 | 1 | 1 | 2 |
4 | 16 | 5 | 1 | 4 | 0 | 2 | 1 | 2 |
5 | 32 | 10 | 1 | 9 | 0 | 5 | 1 | 4 |
6 | 64 | 14 | 1 | 13 | 0 | 7 | 1 | 6 |
7 | 128 | 25 | 12 | 13 | 6 | 7 | 6 | 6 |
8 | 256 | 52 | 39 | 13 | 20 | 7 | 19 | 6 |
9 | 512 | 99 | 86 | 13 | 45 | 7 | 41 | 6 |
10 | 1.024 | 191 | 178 | 13 | 89 | 7 | 89 | 6 |
11 | 2.048 | 349 | 336 | 13 | 169 | 7 | 167 | 6 |
12 | 4.096 | 648 | 635 | 13 | 322 | 7 | 313 | 6 |
13 | 8.192 | 1.150 | 1.137 | 13 | 566 | 7 | 571 | 6 |
14 | 16.384 | 2.110 | 2.097 | 13 | 1.059 | 7 | 1.038 | 6 |
15 | 32.768 | 3.928 | 3.915 | 13 | 1.946 | 7 | 1.969 | 6 |
16 | 65.536 | 7.267 | 7.254 | 13 | 3.614 | 7 | 3.640 | 6 |
17 | 131.072 | 13.633 | 13.620 | 13 | 6.809 | 7 | 6.811 | 6 |
18 | 262.144 | 25.663 | 25.650 | 13 | 12.808 | 7 | 12.842 | 6 |
19 | 524.288 | 48.276 | 48.263 | 13 | 24.029 | 7 | 24.234 | 6 |
20 | 1.048.576 | 91.260 | 91.247 | 13 | 45.434 | 7 | 45.813 | 6 |
21 | 2.097.152 | 173.192 | 173.179 | 13 | 86.380 | 7 | 86.799 | 6 |
22 | 4.194.304 | 329.409 | 329.396 | 13 | 164.420 | 7 | 164.976 | 6 |
23 | 8.388.608 | 627.435 | 627.422 | 13 | 313.212 | 7 | 314.210 | 6 |
24 | 16.777.216 | 1.196.917 | 1.196.904 | 13 | 597.665 | 7 | 599.239 | 6 |
25 | 33.554.432 | 2.292.149 | 2.292.136 | 13 | 1.145.074 | 7 | 1.147.062 | 6 |
26 | 67.108.864 | 4.395.718 | 4.395.705 | 13 | 2.196.671 | 7 | 2.199.034 | 6 |
27 | 134.217.728 | 8.442.318 | 8.442.305 | 13 | 4.221.082 | 7 | 4.221.223 | 6 |
28 | 268.435.456 | 16.250.404 | 16.250.391 | 13 | 8.125.623 | 7 | 8.124.768 | 6 |
29 | 536.870.912 | 31.316.749 | 31.316.736 | 13 | 15.657.199 | 7 | 15.659.537 | 6 |
30 | 1.073.741.824 | 60.420.618 | 60.420.605 | 13 | 30.207.809 | 7 | 30.212.796 | 6 |
31 | 2.147.483.648 | 116.724.671 | 116.724.658 | 13 | 58.363.004 | 7 | 58.361.654 | 6 |
32 | 4.294.967.296 | 225.775.959 | 225.775.946 | 13 | 112.895.057 | 7 | 112.880.889 | 6 |
33 | 8.589.934.592 | 437.176.594 | 437.176.581 | 13 | 218.591.580 | 7 | 218.585.001 | 6 |
34 | 17.179.869.184 | 847.337.684 | 847.337.671 | 13 | 423.680.004 | 7 | 423.657.667 | 6 |
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 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 3 | 1 | 1 | 1 | 0 | 0 | 2 |
3 | 8 | 5 | 3 | 1 | 2 | 1 | 0 | 2 |
4 | 16 | 11 | 6 | 4 | 3 | 3 | 1 | 4 |
5 | 32 | 22 | 14 | 7 | 5 | 8 | 4 | 5 |
6 | 64 | 31 | 21 | 9 | 6 | 9 | 7 | 9 |
7 | 128 | 47 | 25 | 21 | 10 | 12 | 11 | 14 |
8 | 256 | 127 | 51 | 75 | 32 | 31 | 33 | 31 |
9 | 512 | 289 | 108 | 180 | 73 | 73 | 75 | 68 |
10 | 1.024 | 608 | 220 | 387 | 154 | 149 | 152 | 153 |
11 | 2.048 | 1.278 | 479 | 798 | 321 | 315 | 331 | 311 |
12 | 4.096 | 2.644 | 1.014 | 1.629 | 660 | 637 | 702 | 645 |
13 | 8.192 | 5.459 | 2.141 | 3.317 | 1.396 | 1.360 | 1.396 | 1.307 |
14 | 16.384 | 11.036 | 4.391 | 6.644 | 2.786 | 2.731 | 2.828 | 2.691 |
15 | 32.768 | 22.199 | 8.992 | 13.206 | 5.570 | 5.485 | 5.677 | 5.467 |
16 | 65.536 | 44.674 | 18.442 | 26.231 | 11.246 | 11.035 | 11.363 | 11.030 |
17 | 131.072 | 89.568 | 37.436 | 52.131 | 22.652 | 22.144 | 22.729 | 22.043 |
18 | 262.144 | 179.400 | 76.102 | 103.297 | 45.491 | 44.274 | 45.352 | 44.283 |
19 | 524.288 | 359.429 | 154.319 | 205.109 | 91.280 | 88.514 | 90.871 | 88.764 |
20 | 1.048.576 | 719.577 | 311.902 | 407.674 | 182.031 | 178.007 | 181.882 | 177.657 |
21 | 2.097.152 | 1.440.000 | 628.593 | 811.406 | 363.852 | 356.014 | 364.440 | 355.694 |
22 | 4.194.304 | 2.881.696 | 1.268.429 | 1.613.266 | 728.147 | 712.675 | 728.568 | 712.306 |
23 | 8.388.608 | 5.767.288 | 2.556.811 | 3.210.476 | 1.456.892 | 1.426.595 | 1.457.364 | 1.426.437 |
24 | 16.777.216 | 11.542.386 | 5.148.004 | 6.394.381 | 2.916.155 | 2.855.395 | 2.915.334 | 2.855.502 |
25 | 33.554.432 | 23.092.714 | 10.354.493 | 12.738.220 | 5.832.092 | 5.717.694 | 5.830.214 | 5.712.714 |
26 | 67.108.864 | 46.199.548 | 20.819.897 | 25.379.650 | 11.662.441 | 11.440.272 | 11.661.038 | 11.435.797 |
27 | 134.217.728 | 92.431.627 | 41.844.389 | 50.587.237 | 23.327.874 | 22.890.707 | 23.326.673 | 22.886.373 |
28 | 268.435.456 | 184.902.721 | 84.055.913 | 100.846.807 | 46.654.727 | 45.797.956 | 46.648.120 | 45.801.918 |
29 | 536.870.912 | 369.890.673 | 168.793.654 | 201.097.018 | 93.303.426 | 91.650.774 | 93.295.013 | 91.641.460 |
30 | 1.073.741.824 | 739.960.266 | 338.847.599 | 401.112.666 | 186.603.930 | 183.378.265 | 186.608.118 | 183.369.953 |
31 | 2.147.483.648 | 1.480.234.415 | 680.009.545 | 800.224.869 | 373.174.294 | 366.936.615 | 373.191.332 | 366.932.174 |
32 | 4.294.967.296 | 2.961.038.566 | 1.364.362.442 | 1.596.676.123 | 746.357.688 | 734.141.978 | 746.367.120 | 734.171.780 |
33 | 8.589.934.592 | 5.923.131.138 | 2.736.846.567 | 3.186.284.570 | 1.492.649.136 | 1.468.885.157 | 1.492.636.078 | 1.468.960.767 |
34 | 17.179.869.184 | 11.848.306.166 | 5.489.060.664 | 6.359.245.501 | 2.985.258.297 | 2.938.857.408 | 2.985.242.176 | 2.938.948.285 |