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-52x+11
f(0)=11
f(1)=5
f(2)=89
f(3)=17
f(4)=181
f(5)=7
f(6)=53
f(7)=19
f(8)=31
f(9)=47
f(10)=409
f(11)=1
f(12)=67
f(13)=1
f(14)=521
f(15)=1
f(16)=113
f(17)=73
f(18)=601
f(19)=1
f(20)=37
f(21)=1
f(22)=59
f(23)=41
f(24)=661
f(25)=83
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
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)=359
f(59)=1
f(60)=491
f(61)=1
f(62)=631
f(63)=1
f(64)=1
f(65)=107
f(66)=1
f(67)=127
f(68)=157
f(69)=1
f(70)=1
f(71)=1
f(72)=1451
f(73)=193
f(74)=149
f(75)=1
f(76)=367
f(77)=1
f(78)=2039
f(79)=1
f(80)=2251
f(81)=1
f(82)=353
f(83)=1
f(84)=2699
f(85)=1
f(86)=587
f(87)=191
f(88)=1
f(89)=1
f(90)=1
f(91)=1
f(92)=3691
f(93)=239
f(94)=1
f(95)=1
f(96)=1
f(97)=547
f(98)=4519
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-52x+11 could be written as f(y)= y^2-665 with x=y+26
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-26
f'(x)>2x-53 with x > 26
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 | 4 | 6 | 1.000000 | 0.400000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 63 | 35 | 28 | 0.630000 | 0.350000 | 0.630000 | 6.300000 | 8.750000 | 4.666667 |
3 | 1.000 | 928 | 392 | 536 | 0.928000 | 0.392000 | 0.928000 | 14.730159 | 11.200000 | 19.142857 |
4 | 10.000 | 9.888 | 3.965 | 5.923 | 0.988800 | 0.396500 | 0.988800 | 10.655172 | 10.114796 | 11.050373 |
5 | 100.000 | 99.841 | 39.695 | 60.146 | 0.998410 | 0.396950 | 0.998410 | 10.097189 | 10.011350 | 10.154652 |
6 | 1.000.000 | 999.791 | 396.987 | 602.804 | 0.999791 | 0.396987 | 0.999791 | 10.013832 | 10.000932 | 10.022346 |
7 | 10.000.000 | 9.999.742 | 3.969.920 | 6.029.822 | 0.999974 | 0.396992 | 0.999974 | 10.001832 | 10.000126 | 10.002956 |
8 | 100.000.000 | 99.999.696 | 39.699.243 | 60.300.453 | 0.999997 | 0.396992 | 0.999997 | 10.000228 | 10.000011 | 10.000370 |
9 | 1.000.000.000 | 999.999.647 | 396.992.476 | 603.007.171 | 1.000000 | 0.396992 | 1.000000 | 10.000027 | 10.000001 | 10.000044 |
10 | 10.000.000.000 | 9.999.999.598 | 3.969.924.806 | 6.030.074.792 | 1.000000 | 0.396992 | 1.000000 | 10.000004 | 10.000000 | 10.000006 |
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 | 3 | 5 | 1.000000 | 0.375000 | 0.625000 | 1.600000 | 1.000000 | 2.500000 |
4 | 16 | 13 | 5 | 8 | 0.812500 | 0.312500 | 0.500000 | 1.625000 | 1.666667 | 1.600000 |
5 | 32 | 23 | 10 | 13 | 0.718750 | 0.312500 | 0.406250 | 1.769231 | 2.000000 | 1.625000 |
6 | 64 | 37 | 21 | 16 | 0.578125 | 0.328125 | 0.250000 | 1.608696 | 2.100000 | 1.230769 |
7 | 128 | 86 | 46 | 40 | 0.671875 | 0.359375 | 0.312500 | 2.324324 | 2.190476 | 2.500000 |
8 | 256 | 205 | 97 | 108 | 0.800781 | 0.378906 | 0.421875 | 2.383721 | 2.108696 | 2.700000 |
9 | 512 | 449 | 199 | 250 | 0.876953 | 0.388672 | 0.488281 | 2.190244 | 2.051546 | 2.314815 |
10 | 1.024 | 952 | 402 | 550 | 0.929688 | 0.392578 | 0.537109 | 2.120267 | 2.020101 | 2.200000 |
11 | 2.048 | 1.964 | 808 | 1.156 | 0.958984 | 0.394531 | 0.564453 | 2.063025 | 2.009950 | 2.101818 |
12 | 4.096 | 4.001 | 1.621 | 2.380 | 0.976807 | 0.395752 | 0.581055 | 2.037169 | 2.006188 | 2.058824 |
13 | 8.192 | 8.084 | 3.248 | 4.836 | 0.986816 | 0.396484 | 0.590332 | 2.020495 | 2.003701 | 2.031933 |
14 | 16.384 | 16.262 | 6.500 | 9.762 | 0.992554 | 0.396729 | 0.595825 | 2.011628 | 2.001231 | 2.018610 |
15 | 32.768 | 32.632 | 13.003 | 19.629 | 0.995850 | 0.396820 | 0.599030 | 2.006641 | 2.000462 | 2.010756 |
16 | 65.536 | 65.385 | 26.012 | 39.373 | 0.997696 | 0.396912 | 0.600784 | 2.003708 | 2.000461 | 2.005859 |
17 | 131.072 | 130.907 | 52.030 | 78.877 | 0.998741 | 0.396957 | 0.601784 | 2.002095 | 2.000231 | 2.003327 |
18 | 262.144 | 261.964 | 104.065 | 157.899 | 0.999313 | 0.396976 | 0.602337 | 2.001146 | 2.000096 | 2.001838 |
19 | 524.288 | 524.092 | 208.134 | 315.958 | 0.999626 | 0.396984 | 0.602642 | 2.000626 | 2.000038 | 2.001013 |
20 | 1.048.576 | 1.048.365 | 416.272 | 632.093 | 0.999799 | 0.396988 | 0.602811 | 2.000345 | 2.000019 | 2.000560 |
21 | 2.097.152 | 2.096.928 | 832.549 | 1.264.379 | 0.999893 | 0.396990 | 0.602903 | 2.000189 | 2.000012 | 2.000305 |
22 | 4.194.304 | 4.194.066 | 1.665.103 | 2.528.963 | 0.999943 | 0.396991 | 0.602952 | 2.000100 | 2.000006 | 2.000162 |
23 | 8.388.608 | 8.388.354 | 3.330.209 | 5.058.145 | 0.999970 | 0.396992 | 0.602978 | 2.000053 | 2.000002 | 2.000087 |
24 | 16.777.216 | 16.776.951 | 6.660.423 | 10.116.528 | 0.999984 | 0.396992 | 0.602992 | 2.000029 | 2.000001 | 2.000047 |
25 | 33.554.432 | 33.554.152 | 13.320.852 | 20.233.300 | 0.999992 | 0.396992 | 0.602999 | 2.000015 | 2.000001 | 2.000024 |
26 | 67.108.864 | 67.108.570 | 26.641.710 | 40.466.860 | 0.999996 | 0.396992 | 0.603003 | 2.000008 | 2.000000 | 2.000013 |
27 | 134.217.728 | 134.217.419 | 53.283.424 | 80.933.995 | 0.999998 | 0.396992 | 0.603005 | 2.000004 | 2.000000 | 2.000007 |
28 | 268.435.456 | 268.435.131 | 106.566.853 | 161.868.278 | 0.999999 | 0.396992 | 0.603006 | 2.000002 | 2.000000 | 2.000004 |
29 | 536.870.912 | 536.870.571 | 213.133.711 | 323.736.860 | 0.999999 | 0.396992 | 0.603007 | 2.000001 | 2.000000 | 2.000002 |
30 | 1.073.741.824 | 1.073.741.468 | 426.267.426 | 647.474.042 | 1.000000 | 0.396992 | 0.603007 | 2.000001 | 2.000000 | 2.000001 |
31 | 2.147.483.648 | 2.147.483.277 | 852.534.857 | 1.294.948.420 | 1.000000 | 0.396992 | 0.603007 | 2.000000 | 2.000000 | 2.000000 |
32 | 4.294.967.296 | 4.294.966.911 | 1.705.069.718 | 2.589.897.193 | 1.000000 | 0.396992 | 0.603007 | 2.000000 | 2.000000 | 2.000000 |
33 | 8.589.934.592 | 8.589.934.191 | 3.410.139.441 | 5.179.794.750 | 1.000000 | 0.396992 | 0.603007 | 2.000000 | 2.000000 | 2.000000 |
34 | 17.179.869.184 | 17.179.868.761 | 6.820.278.884 | 10.359.589.877 | 1.000000 | 0.396992 | 0.603007 | 2.000000 | 2.000000 | 2.000000 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 3 | 1 | 2 | 1 | 1 | 1 | 0 |
4 | 16 | 5 | 2 | 3 | 3 | 1 | 1 | 0 |
5 | 32 | 10 | 6 | 4 | 5 | 1 | 4 | 0 |
6 | 64 | 21 | 11 | 10 | 8 | 3 | 7 | 3 |
7 | 128 | 46 | 20 | 26 | 8 | 16 | 7 | 15 |
8 | 256 | 97 | 37 | 60 | 8 | 41 | 7 | 41 |
9 | 512 | 199 | 71 | 128 | 8 | 92 | 7 | 92 |
10 | 1.024 | 402 | 138 | 264 | 8 | 193 | 7 | 194 |
11 | 2.048 | 808 | 274 | 534 | 8 | 397 | 7 | 396 |
12 | 4.096 | 1.621 | 545 | 1.076 | 8 | 803 | 7 | 803 |
13 | 8.192 | 3.248 | 1.087 | 2.161 | 8 | 1.617 | 7 | 1.616 |
14 | 16.384 | 6.500 | 2.171 | 4.329 | 8 | 3.242 | 7 | 3.243 |
15 | 32.768 | 13.003 | 4.339 | 8.664 | 8 | 6.494 | 7 | 6.494 |
16 | 65.536 | 26.012 | 8.675 | 17.337 | 8 | 12.999 | 7 | 12.998 |
17 | 131.072 | 52.030 | 17.347 | 34.683 | 8 | 26.008 | 7 | 26.007 |
18 | 262.144 | 104.065 | 34.692 | 69.373 | 8 | 52.025 | 7 | 52.025 |
19 | 524.288 | 208.134 | 69.383 | 138.751 | 8 | 104.060 | 7 | 104.059 |
20 | 1.048.576 | 416.272 | 138.762 | 277.510 | 8 | 208.128 | 7 | 208.129 |
21 | 2.097.152 | 832.549 | 277.521 | 555.028 | 8 | 416.267 | 7 | 416.267 |
22 | 4.194.304 | 1.665.103 | 555.039 | 1.110.064 | 8 | 832.544 | 7 | 832.544 |
23 | 8.388.608 | 3.330.209 | 1.110.074 | 2.220.135 | 8 | 1.665.098 | 7 | 1.665.096 |
24 | 16.777.216 | 6.660.423 | 2.220.145 | 4.440.278 | 8 | 3.330.204 | 7 | 3.330.204 |
25 | 33.554.432 | 13.320.852 | 4.440.288 | 8.880.564 | 8 | 6.660.419 | 7 | 6.660.418 |
26 | 67.108.864 | 26.641.710 | 8.880.574 | 17.761.136 | 8 | 13.320.848 | 7 | 13.320.847 |
27 | 134.217.728 | 53.283.424 | 17.761.146 | 35.522.278 | 8 | 26.641.705 | 7 | 26.641.704 |
28 | 268.435.456 | 106.566.853 | 35.522.289 | 71.044.564 | 8 | 53.283.419 | 7 | 53.283.419 |
29 | 536.870.912 | 213.133.711 | 71.044.575 | 142.089.136 | 8 | 106.566.848 | 7 | 106.566.848 |
30 | 1.073.741.824 | 426.267.426 | 142.089.146 | 284.178.280 | 8 | 213.133.705 | 7 | 213.133.706 |
31 | 2.147.483.648 | 852.534.857 | 284.178.290 | 568.356.567 | 8 | 426.267.422 | 7 | 426.267.420 |
32 | 4.294.967.296 | 1.705.069.718 | 568.356.577 | 1.136.713.141 | 8 | 852.534.851 | 7 | 852.534.852 |
33 | 8.589.934.592 | 3.410.139.441 | 1.136.713.151 | 2.273.426.290 | 8 | 1.705.069.713 | 7 | 1.705.069.713 |
34 | 17.179.869.184 | 6.820.278.884 | 2.273.426.299 | 4.546.852.585 | 8 | 3.410.139.435 | 7 | 3.410.139.434 |
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 | 2 | 0 | 2 | 1 | 0 | 1 | 0 |
3 | 8 | 5 | 2 | 3 | 1 | 1 | 2 | 1 |
4 | 16 | 8 | 3 | 5 | 2 | 2 | 2 | 2 |
5 | 32 | 13 | 5 | 8 | 3 | 5 | 3 | 2 |
6 | 64 | 16 | 6 | 10 | 5 | 5 | 4 | 2 |
7 | 128 | 40 | 20 | 20 | 10 | 14 | 7 | 9 |
8 | 256 | 108 | 58 | 50 | 22 | 35 | 23 | 28 |
9 | 512 | 250 | 140 | 110 | 50 | 77 | 54 | 69 |
10 | 1.024 | 550 | 306 | 244 | 111 | 160 | 117 | 162 |
11 | 2.048 | 1.156 | 641 | 515 | 243 | 342 | 237 | 334 |
12 | 4.096 | 2.380 | 1.317 | 1.063 | 495 | 704 | 491 | 690 |
13 | 8.192 | 4.836 | 2.684 | 2.152 | 997 | 1.421 | 1.004 | 1.414 |
14 | 16.384 | 9.762 | 5.411 | 4.351 | 2.017 | 2.854 | 2.027 | 2.864 |
15 | 32.768 | 19.629 | 10.885 | 8.744 | 4.071 | 5.753 | 4.061 | 5.744 |
16 | 65.536 | 39.373 | 21.829 | 17.544 | 8.159 | 11.537 | 8.158 | 11.519 |
17 | 131.072 | 78.877 | 43.742 | 35.135 | 16.349 | 23.096 | 16.348 | 23.084 |
18 | 262.144 | 157.899 | 87.554 | 70.345 | 32.723 | 46.221 | 32.733 | 46.222 |
19 | 524.288 | 315.958 | 175.191 | 140.767 | 65.490 | 92.485 | 65.494 | 92.489 |
20 | 1.048.576 | 632.093 | 350.467 | 281.626 | 131.023 | 185.030 | 131.024 | 185.016 |
21 | 2.097.152 | 1.264.379 | 701.044 | 563.335 | 262.092 | 370.096 | 262.094 | 370.097 |
22 | 4.194.304 | 2.528.963 | 1.402.185 | 1.126.778 | 524.232 | 740.253 | 524.237 | 740.241 |
23 | 8.388.608 | 5.058.145 | 2.804.482 | 2.253.663 | 1.048.524 | 1.480.548 | 1.048.512 | 1.480.561 |
24 | 16.777.216 | 10.116.528 | 5.609.083 | 4.507.445 | 2.097.087 | 2.961.189 | 2.097.094 | 2.961.158 |
25 | 33.554.432 | 20.233.300 | 11.218.309 | 9.014.991 | 4.194.224 | 5.922.413 | 4.194.256 | 5.922.407 |
26 | 67.108.864 | 40.466.860 | 22.436.748 | 18.030.112 | 8.388.538 | 11.844.902 | 8.388.543 | 11.844.877 |
27 | 134.217.728 | 80.933.995 | 44.873.642 | 36.060.353 | 16.777.154 | 23.689.855 | 16.777.137 | 23.689.849 |
28 | 268.435.456 | 161.868.278 | 89.747.427 | 72.120.851 | 33.554.358 | 47.379.782 | 33.554.358 | 47.379.780 |
29 | 536.870.912 | 323.736.860 | 179.495.017 | 144.241.843 | 67.108.783 | 94.759.645 | 67.108.789 | 94.759.643 |
30 | 1.073.741.824 | 647.474.042 | 358.990.194 | 288.483.848 | 134.217.645 | 189.519.376 | 134.217.647 | 189.519.374 |
31 | 2.147.483.648 | 1.294.948.420 | 717.980.566 | 576.967.854 | 268.435.371 | 379.038.833 | 268.435.369 | 379.038.847 |
32 | 4.294.967.296 | 2.589.897.193 | 1.435.961.302 | 1.153.935.891 | 536.870.827 | 758.077.784 | 536.870.820 | 758.077.762 |
33 | 8.589.934.592 | 5.179.794.750 | 2.871.922.794 | 2.307.871.956 | 1.073.741.736 | 1.516.155.665 | 1.073.741.729 | 1.516.155.620 |
34 | 17.179.869.184 | 10.359.589.877 | 5.743.845.778 | 4.615.744.099 | 2.147.483.550 | 3.032.311.399 | 2.147.483.555 | 3.032.311.373 |