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-56x+151
f(0)=151
f(1)=3
f(2)=43
f(3)=1
f(4)=19
f(5)=13
f(6)=149
f(7)=1
f(8)=233
f(9)=17
f(10)=103
f(11)=1
f(12)=29
f(13)=1
f(14)=23
f(15)=1
f(16)=163
f(17)=1
f(18)=41
f(19)=1
f(20)=569
f(21)=73
f(22)=199
f(23)=1
f(24)=617
f(25)=1
f(26)=37
f(27)=79
f(28)=211
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)=89
f(59)=1
f(60)=1
f(61)=1
f(62)=523
f(63)=1
f(64)=1
f(65)=1
f(66)=811
f(67)=1
f(68)=967
f(69)=131
f(70)=1
f(71)=1
f(72)=1303
f(73)=1
f(74)=1483
f(75)=197
f(76)=557
f(77)=1
f(78)=1867
f(79)=1
f(80)=109
f(81)=1
f(82)=761
f(83)=1
f(84)=2503
f(85)=1
f(86)=2731
f(87)=1
f(88)=1
f(89)=193
f(90)=1
f(91)=139
f(92)=3463
f(93)=449
f(94)=1
f(95)=241
f(96)=307
f(97)=1
f(98)=251
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-56x+151 could be written as f(y)= y^2-633 with x=y+28
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-28
f'(x)>2x-57 with x > 25
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 | 8 | 4 | 4 | 0.800000 | 0.400000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 34 | 15 | 19 | 0.340000 | 0.150000 | 0.340000 | 4.250000 | 3.750000 | 4.750000 |
3 | 1.000 | 588 | 108 | 480 | 0.588000 | 0.108000 | 0.588000 | 17.294117 | 7.200000 | 25.263159 |
4 | 10.000 | 6.443 | 773 | 5.670 | 0.644300 | 0.077300 | 0.644300 | 10.957483 | 7.157407 | 11.812500 |
5 | 100.000 | 65.713 | 6.199 | 59.514 | 0.657130 | 0.061990 | 0.657130 | 10.199131 | 8.019405 | 10.496296 |
6 | 1.000.000 | 664.302 | 50.415 | 613.887 | 0.664302 | 0.050415 | 0.664302 | 10.109141 | 8.132763 | 10.315001 |
7 | 10.000.000 | 6.683.388 | 427.971 | 6.255.417 | 0.668339 | 0.042797 | 0.668339 | 10.060767 | 8.488961 | 10.189851 |
8 | 100.000.000 | 67.148.896 | 3.709.974 | 63.438.922 | 0.671489 | 0.037100 | 0.671489 | 10.047134 | 8.668751 | 10.141438 |
9 | 1.000.000.000 | 673.881.235 | 32.755.708 | 641.125.527 | 0.673881 | 0.032756 | 0.673881 | 10.035626 | 8.829094 | 10.106186 |
10 | 10.000.000.000 | 6.758.117.799 | 293.084.005 | 6.465.033.794 | 0.675812 | 0.029308 | 0.675812 | 10.028648 | 8.947570 | 10.083881 |
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 | 4 | 2 | 2 | 1.000000 | 0.500000 | 0.500000 | 1.333333 | 1.000000 | 2.000000 |
3 | 8 | 7 | 4 | 3 | 0.875000 | 0.500000 | 0.375000 | 1.750000 | 2.000000 | 1.500000 |
4 | 16 | 10 | 4 | 6 | 0.625000 | 0.250000 | 0.375000 | 1.428571 | 1.000000 | 2.000000 |
5 | 32 | 17 | 6 | 11 | 0.531250 | 0.187500 | 0.343750 | 1.700000 | 1.500000 | 1.833333 |
6 | 64 | 18 | 7 | 11 | 0.281250 | 0.109375 | 0.171875 | 1.058824 | 1.166667 | 1.000000 |
7 | 128 | 48 | 18 | 30 | 0.375000 | 0.140625 | 0.234375 | 2.666667 | 2.571429 | 2.727273 |
8 | 256 | 122 | 33 | 89 | 0.476562 | 0.128906 | 0.347656 | 2.541667 | 1.833333 | 2.966667 |
9 | 512 | 279 | 61 | 218 | 0.544922 | 0.119141 | 0.425781 | 2.286885 | 1.848485 | 2.449438 |
10 | 1.024 | 607 | 112 | 495 | 0.592773 | 0.109375 | 0.483398 | 2.175627 | 1.836066 | 2.270642 |
11 | 2.048 | 1.259 | 195 | 1.064 | 0.614746 | 0.095215 | 0.519531 | 2.074135 | 1.741071 | 2.149495 |
12 | 4.096 | 2.601 | 347 | 2.254 | 0.635010 | 0.084717 | 0.550293 | 2.065925 | 1.779487 | 2.118421 |
13 | 8.192 | 5.259 | 648 | 4.611 | 0.641968 | 0.079102 | 0.562866 | 2.021915 | 1.867435 | 2.045696 |
14 | 16.384 | 10.623 | 1.207 | 9.416 | 0.648376 | 0.073669 | 0.574707 | 2.019966 | 1.862654 | 2.042073 |
15 | 32.768 | 21.359 | 2.285 | 19.074 | 0.651825 | 0.069733 | 0.582092 | 2.010637 | 1.893123 | 2.025701 |
16 | 65.536 | 42.968 | 4.246 | 38.722 | 0.655640 | 0.064789 | 0.590851 | 2.011705 | 1.858206 | 2.030093 |
17 | 131.072 | 86.251 | 7.980 | 78.271 | 0.658043 | 0.060883 | 0.597160 | 2.007331 | 1.879416 | 2.021357 |
18 | 262.144 | 173.285 | 14.820 | 158.465 | 0.661030 | 0.056534 | 0.604496 | 2.009078 | 1.857143 | 2.024569 |
19 | 524.288 | 347.559 | 27.901 | 319.658 | 0.662916 | 0.053217 | 0.609699 | 2.005707 | 1.882659 | 2.017215 |
20 | 1.048.576 | 696.837 | 52.574 | 644.263 | 0.664556 | 0.050138 | 0.614417 | 2.004946 | 1.884305 | 2.015476 |
21 | 2.097.152 | 1.396.290 | 99.896 | 1.296.394 | 0.665803 | 0.047634 | 0.618169 | 2.003754 | 1.900103 | 2.012213 |
22 | 4.194.304 | 2.797.599 | 190.275 | 2.607.324 | 0.667000 | 0.045365 | 0.621634 | 2.003595 | 1.904731 | 2.011213 |
23 | 8.388.608 | 5.604.493 | 363.259 | 5.241.234 | 0.668108 | 0.043304 | 0.624804 | 2.003323 | 1.909126 | 2.010197 |
24 | 16.777.216 | 11.226.810 | 694.135 | 10.532.675 | 0.669170 | 0.041374 | 0.627796 | 2.003180 | 1.910854 | 2.009579 |
25 | 33.554.432 | 22.485.700 | 1.328.701 | 21.156.999 | 0.670126 | 0.039598 | 0.630528 | 2.002857 | 1.914182 | 2.008702 |
26 | 67.108.864 | 45.031.034 | 2.547.719 | 42.483.315 | 0.671015 | 0.037964 | 0.633051 | 2.002652 | 1.917451 | 2.008003 |
27 | 134.217.728 | 90.170.078 | 4.897.359 | 85.272.719 | 0.671819 | 0.036488 | 0.635331 | 2.002399 | 1.922252 | 2.007205 |
28 | 268.435.456 | 180.546.442 | 9.424.374 | 171.122.068 | 0.672588 | 0.035109 | 0.637479 | 2.002288 | 1.924379 | 2.006762 |
29 | 536.870.912 | 361.466.814 | 18.160.836 | 343.305.978 | 0.673284 | 0.033827 | 0.639457 | 2.002071 | 1.927007 | 2.006205 |
30 | 1.073.741.824 | 723.648.671 | 35.044.489 | 688.604.182 | 0.673950 | 0.032638 | 0.641313 | 2.001978 | 1.929674 | 2.005803 |
31 | 2.147.483.648 | 1.448.626.474 | 67.692.243 | 1.380.934.231 | 0.674569 | 0.031522 | 0.643048 | 2.001837 | 1.931609 | 2.005411 |
32 | 4.294.967.296 | 2.899.761.943 | 130.925.199 | 2.768.836.744 | 0.675153 | 0.030483 | 0.644670 | 2.001732 | 1.934124 | 2.005046 |
33 | 8.589.934.592 | 5.804.193.718 | 253.516.211 | 5.550.677.507 | 0.675697 | 0.029513 | 0.646184 | 2.001611 | 1.936344 | 2.004696 |
34 | 17.179.869.184 | 11.617.181.919 | 491.380.630 | 11.125.801.289 | 0.676209 | 0.028602 | 0.647607 | 2.001515 | 1.938261 | 2.004404 |
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 | 2 | 0 | 0 | 1 | 0 | 1 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
4 | 16 | 4 | 2 | 2 | 1 | 1 | 1 | 1 |
5 | 32 | 6 | 2 | 4 | 3 | 1 | 1 | 1 |
6 | 64 | 7 | 3 | 4 | 3 | 2 | 1 | 1 |
7 | 128 | 18 | 14 | 4 | 3 | 9 | 1 | 5 |
8 | 256 | 33 | 29 | 4 | 3 | 17 | 1 | 12 |
9 | 512 | 61 | 57 | 4 | 3 | 30 | 1 | 27 |
10 | 1.024 | 112 | 108 | 4 | 3 | 48 | 1 | 60 |
11 | 2.048 | 195 | 191 | 4 | 3 | 84 | 1 | 107 |
12 | 4.096 | 347 | 343 | 4 | 3 | 168 | 1 | 175 |
13 | 8.192 | 648 | 644 | 4 | 3 | 314 | 1 | 330 |
14 | 16.384 | 1.207 | 1.203 | 4 | 3 | 612 | 1 | 591 |
15 | 32.768 | 2.285 | 2.281 | 4 | 3 | 1.167 | 1 | 1.114 |
16 | 65.536 | 4.246 | 4.242 | 4 | 3 | 2.149 | 1 | 2.093 |
17 | 131.072 | 7.980 | 7.976 | 4 | 3 | 4.025 | 1 | 3.951 |
18 | 262.144 | 14.820 | 14.816 | 4 | 3 | 7.444 | 1 | 7.372 |
19 | 524.288 | 27.901 | 27.897 | 4 | 3 | 13.917 | 1 | 13.980 |
20 | 1.048.576 | 52.574 | 52.570 | 4 | 3 | 26.328 | 1 | 26.242 |
21 | 2.097.152 | 99.896 | 99.892 | 4 | 3 | 49.852 | 1 | 50.040 |
22 | 4.194.304 | 190.275 | 190.271 | 4 | 3 | 95.031 | 1 | 95.240 |
23 | 8.388.608 | 363.259 | 363.255 | 4 | 3 | 181.462 | 1 | 181.793 |
24 | 16.777.216 | 694.135 | 694.131 | 4 | 3 | 347.243 | 1 | 346.888 |
25 | 33.554.432 | 1.328.701 | 1.328.697 | 4 | 3 | 664.677 | 1 | 664.020 |
26 | 67.108.864 | 2.547.719 | 2.547.715 | 4 | 3 | 1.274.669 | 1 | 1.273.046 |
27 | 134.217.728 | 4.897.359 | 4.897.355 | 4 | 3 | 2.449.491 | 1 | 2.447.864 |
28 | 268.435.456 | 9.424.374 | 9.424.370 | 4 | 3 | 4.712.669 | 1 | 4.711.701 |
29 | 536.870.912 | 18.160.836 | 18.160.832 | 4 | 3 | 9.078.807 | 1 | 9.082.025 |
30 | 1.073.741.824 | 35.044.489 | 35.044.485 | 4 | 3 | 17.521.819 | 1 | 17.522.666 |
31 | 2.147.483.648 | 67.692.243 | 67.692.239 | 4 | 3 | 33.847.063 | 1 | 33.845.176 |
32 | 4.294.967.296 | 130.925.199 | 130.925.195 | 4 | 3 | 65.462.202 | 1 | 65.462.993 |
33 | 8.589.934.592 | 253.516.211 | 253.516.207 | 4 | 3 | 126.762.404 | 1 | 126.753.803 |
34 | 17.179.869.184 | 491.380.630 | 491.380.626 | 4 | 3 | 245.687.650 | 1 | 245.692.976 |
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 | 1 | 0 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 2 | 0 | 0 | 2 | 1 | 0 |
4 | 16 | 6 | 4 | 1 | 0 | 3 | 2 | 1 |
5 | 32 | 11 | 8 | 2 | 2 | 4 | 2 | 3 |
6 | 64 | 11 | 8 | 2 | 2 | 4 | 2 | 3 |
7 | 128 | 30 | 14 | 15 | 8 | 9 | 7 | 6 |
8 | 256 | 89 | 36 | 52 | 26 | 19 | 24 | 20 |
9 | 512 | 218 | 89 | 128 | 57 | 54 | 59 | 48 |
10 | 1.024 | 495 | 204 | 290 | 128 | 115 | 133 | 119 |
11 | 2.048 | 1.064 | 464 | 599 | 273 | 244 | 290 | 257 |
12 | 4.096 | 2.254 | 998 | 1.255 | 591 | 519 | 615 | 529 |
13 | 8.192 | 4.611 | 2.098 | 2.512 | 1.202 | 1.096 | 1.236 | 1.077 |
14 | 16.384 | 9.416 | 4.265 | 5.150 | 2.477 | 2.214 | 2.496 | 2.229 |
15 | 32.768 | 19.074 | 8.769 | 10.304 | 4.996 | 4.508 | 5.064 | 4.506 |
16 | 65.536 | 38.722 | 17.894 | 20.827 | 10.079 | 9.209 | 10.198 | 9.236 |
17 | 131.072 | 78.271 | 36.580 | 41.690 | 20.334 | 18.668 | 20.378 | 18.891 |
18 | 262.144 | 158.465 | 74.224 | 84.240 | 41.088 | 38.052 | 41.202 | 38.123 |
19 | 524.288 | 319.658 | 150.757 | 168.900 | 82.869 | 77.122 | 82.730 | 76.937 |
20 | 1.048.576 | 644.263 | 303.996 | 340.266 | 166.542 | 155.632 | 166.345 | 155.744 |
21 | 2.097.152 | 1.296.394 | 614.679 | 681.714 | 334.635 | 313.640 | 334.667 | 313.452 |
22 | 4.194.304 | 2.607.324 | 1.239.794 | 1.367.529 | 671.620 | 631.916 | 671.824 | 631.964 |
23 | 8.388.608 | 5.241.234 | 2.500.070 | 2.741.163 | 1.348.449 | 1.272.632 | 1.347.590 | 1.272.563 |
24 | 16.777.216 | 10.532.675 | 5.035.618 | 5.497.056 | 2.705.319 | 2.560.876 | 2.705.031 | 2.561.449 |
25 | 33.554.432 | 21.156.999 | 10.135.396 | 11.021.602 | 5.424.818 | 5.153.931 | 5.426.051 | 5.152.199 |
26 | 67.108.864 | 42.483.315 | 20.397.215 | 22.086.099 | 10.882.478 | 10.358.418 | 10.881.847 | 10.360.572 |
27 | 134.217.728 | 85.272.719 | 41.016.335 | 44.256.383 | 21.823.836 | 20.809.444 | 21.816.693 | 20.822.746 |
28 | 268.435.456 | 171.122.068 | 82.449.710 | 88.672.357 | 43.748.933 | 41.808.294 | 43.743.418 | 41.821.423 |
29 | 536.870.912 | 343.305.978 | 165.665.013 | 177.640.964 | 87.682.885 | 83.970.289 | 87.674.547 | 83.978.257 |
30 | 1.073.741.824 | 688.604.182 | 332.780.113 | 355.824.068 | 175.713.863 | 168.578.496 | 175.724.118 | 168.587.705 |
31 | 2.147.483.648 | 1.380.934.231 | 668.205.678 | 712.728.552 | 352.123.823 | 338.345.285 | 352.117.903 | 338.347.220 |
32 | 4.294.967.296 | 2.768.836.744 | 1.341.416.046 | 1.427.420.697 | 705.536.271 | 678.880.927 | 705.518.618 | 678.900.928 |
33 | 8.589.934.592 | 5.550.677.507 | 2.692.141.745 | 2.858.535.761 | 1.413.450.466 | 1.361.894.462 | 1.413.407.676 | 1.361.924.903 |
34 | 17.179.869.184 | 11.125.801.289 | 5.401.745.441 | 5.724.055.847 | 2.831.346.629 | 2.731.598.703 | 2.831.232.817 | 2.731.623.140 |