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-81x+5
f(0)=5
f(1)=3
f(2)=17
f(3)=229
f(4)=101
f(5)=1
f(6)=89
f(7)=19
f(8)=193
f(9)=643
f(10)=47
f(11)=1
f(12)=823
f(13)=293
f(14)=311
f(15)=197
f(16)=23
f(17)=1
f(18)=1129
f(19)=1
f(20)=1
f(21)=251
f(22)=431
f(23)=443
f(24)=29
f(25)=31
f(26)=1
f(27)=1453
f(28)=1
f(29)=167
f(30)=61
f(31)=103
f(32)=521
f(33)=1579
f(34)=59
f(35)=107
f(36)=1
f(37)=541
f(38)=181
f(39)=71
f(40)=109
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)=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)=257
f(85)=1
f(86)=1
f(87)=1
f(88)=1
f(89)=239
f(90)=163
f(91)=1
f(92)=113
f(93)=1
f(94)=409
f(95)=1
f(96)=1
f(97)=173
f(98)=557
f(99)=1787
b) Substitution of the polynom
The polynom f(x)=x^2-81x+5 could be written as f(y)= y^2-1635.25 with x=y+40.5
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-40.5
f'(x)>2x-82 with x > 40
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 | 3 | 7 | 1.000000 | 0.300000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 34 | 10 | 24 | 0.340000 | 0.100000 | 0.340000 | 3.400000 | 3.333333 | 3.428571 |
3 | 1.000 | 578 | 82 | 496 | 0.578000 | 0.082000 | 0.578000 | 17.000000 | 8.200000 | 20.666666 |
4 | 10.000 | 6.468 | 551 | 5.917 | 0.646800 | 0.055100 | 0.646800 | 11.190311 | 6.719512 | 11.929436 |
5 | 100.000 | 66.168 | 4.262 | 61.906 | 0.661680 | 0.042620 | 0.661680 | 10.230056 | 7.735027 | 10.462397 |
6 | 1.000.000 | 667.692 | 34.702 | 632.990 | 0.667692 | 0.034702 | 0.667692 | 10.090859 | 8.142187 | 10.225019 |
7 | 10.000.000 | 6.710.979 | 293.866 | 6.417.113 | 0.671098 | 0.029387 | 0.671098 | 10.051010 | 8.468273 | 10.137779 |
8 | 100.000.000 | 67.386.240 | 2.548.083 | 64.838.157 | 0.673862 | 0.025481 | 0.673862 | 10.041194 | 8.670901 | 10.103945 |
9 | 1.000.000.000 | 676.002.832 | 22.488.712 | 653.514.120 | 0.676003 | 0.022489 | 0.676003 | 10.031763 | 8.825738 | 10.079160 |
10 | 10.000.000.000 | 6.776.995.812 | 201.274.427 | 6.575.721.385 | 0.677700 | 0.020127 | 0.677700 | 10.025100 | 8.950021 | 10.062096 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 1.000000 | 2.000000 |
4 | 16 | 14 | 4 | 10 | 0.875000 | 0.250000 | 0.625000 | 1.750000 | 2.000000 | 1.666667 |
5 | 32 | 24 | 7 | 17 | 0.750000 | 0.218750 | 0.531250 | 1.714286 | 1.750000 | 1.700000 |
6 | 64 | 29 | 8 | 21 | 0.453125 | 0.125000 | 0.328125 | 1.208333 | 1.142857 | 1.235294 |
7 | 128 | 47 | 13 | 34 | 0.367188 | 0.101562 | 0.265625 | 1.620690 | 1.625000 | 1.619048 |
8 | 256 | 116 | 25 | 91 | 0.453125 | 0.097656 | 0.355469 | 2.468085 | 1.923077 | 2.676471 |
9 | 512 | 271 | 44 | 227 | 0.529297 | 0.085938 | 0.443359 | 2.336207 | 1.760000 | 2.494505 |
10 | 1.024 | 592 | 82 | 510 | 0.578125 | 0.080078 | 0.498047 | 2.184502 | 1.863636 | 2.246696 |
11 | 2.048 | 1.250 | 138 | 1.112 | 0.610352 | 0.067383 | 0.542969 | 2.111486 | 1.682927 | 2.180392 |
12 | 4.096 | 2.583 | 252 | 2.331 | 0.630615 | 0.061523 | 0.569092 | 2.066400 | 1.826087 | 2.096223 |
13 | 8.192 | 5.271 | 472 | 4.799 | 0.643433 | 0.057617 | 0.585815 | 2.040650 | 1.873016 | 2.058773 |
14 | 16.384 | 10.659 | 844 | 9.815 | 0.650574 | 0.051514 | 0.599060 | 2.022197 | 1.788136 | 2.045218 |
15 | 32.768 | 21.521 | 1.577 | 19.944 | 0.656769 | 0.048126 | 0.608643 | 2.019045 | 1.868483 | 2.031992 |
16 | 65.536 | 43.264 | 2.903 | 40.361 | 0.660156 | 0.044296 | 0.615860 | 2.010315 | 1.840837 | 2.023716 |
17 | 131.072 | 86.855 | 5.442 | 81.413 | 0.662651 | 0.041519 | 0.621132 | 2.007558 | 1.874612 | 2.017121 |
18 | 262.144 | 174.293 | 10.174 | 164.119 | 0.664875 | 0.038811 | 0.626064 | 2.006712 | 1.869533 | 2.015882 |
19 | 524.288 | 349.284 | 19.112 | 330.172 | 0.666206 | 0.036453 | 0.629753 | 2.004005 | 1.878514 | 2.011784 |
20 | 1.048.576 | 700.141 | 36.237 | 663.904 | 0.667706 | 0.034558 | 0.633148 | 2.004503 | 1.896034 | 2.010782 |
21 | 2.097.152 | 1.402.490 | 68.726 | 1.333.764 | 0.668759 | 0.032771 | 0.635988 | 2.003154 | 1.896570 | 2.008971 |
22 | 4.194.304 | 2.809.296 | 130.872 | 2.678.424 | 0.669788 | 0.031202 | 0.638586 | 2.003077 | 1.904258 | 2.008169 |
23 | 8.388.608 | 5.627.788 | 249.298 | 5.378.490 | 0.670885 | 0.029719 | 0.641166 | 2.003273 | 1.904899 | 2.008080 |
24 | 16.777.216 | 11.270.458 | 476.548 | 10.793.910 | 0.671772 | 0.028404 | 0.643367 | 2.002644 | 1.911560 | 2.006866 |
25 | 33.554.432 | 22.570.478 | 911.803 | 21.658.675 | 0.672653 | 0.027174 | 0.645479 | 2.002623 | 1.913350 | 2.006564 |
26 | 67.108.864 | 45.193.138 | 1.749.957 | 43.443.181 | 0.673430 | 0.026076 | 0.647354 | 2.002312 | 1.919227 | 2.005810 |
27 | 134.217.728 | 90.487.141 | 3.363.034 | 87.124.107 | 0.674182 | 0.025057 | 0.649125 | 2.002232 | 1.921781 | 2.005472 |
28 | 268.435.456 | 181.154.120 | 6.470.191 | 174.683.929 | 0.674852 | 0.024103 | 0.650748 | 2.001987 | 1.923915 | 2.005001 |
29 | 536.870.912 | 362.641.227 | 12.472.405 | 350.168.822 | 0.675472 | 0.023232 | 0.652240 | 2.001838 | 1.927672 | 2.004585 |
30 | 1.073.741.824 | 725.915.384 | 24.059.864 | 701.855.520 | 0.676061 | 0.022407 | 0.653654 | 2.001745 | 1.929048 | 2.004334 |
31 | 2.147.483.648 | 1.453.005.670 | 46.478.987 | 1.406.526.683 | 0.676609 | 0.021643 | 0.654965 | 2.001619 | 1.931806 | 2.004012 |
32 | 4.294.967.296 | 2.908.197.047 | 89.910.782 | 2.818.286.265 | 0.677117 | 0.020934 | 0.656183 | 2.001504 | 1.934439 | 2.003721 |
33 | 8.589.934.592 | 5.820.515.105 | 174.101.232 | 5.646.413.873 | 0.677597 | 0.020268 | 0.657329 | 2.001417 | 1.936378 | 2.003492 |
34 | 17.179.869.184 | 11.648.825.574 | 337.463.446 | 11.311.362.128 | 0.678051 | 0.019643 | 0.658408 | 2.001339 | 1.938317 | 2.003283 |
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 | 1 | 1 | 0 | 0 | 2 | 0 |
3 | 8 | 2 | 1 | 1 | 0 | 0 | 2 | 0 |
4 | 16 | 4 | 3 | 1 | 0 | 1 | 2 | 1 |
5 | 32 | 7 | 5 | 1 | 1 | 2 | 3 | 1 |
6 | 64 | 8 | 6 | 1 | 1 | 3 | 3 | 1 |
7 | 128 | 13 | 6 | 6 | 3 | 5 | 3 | 2 |
8 | 256 | 25 | 6 | 17 | 6 | 8 | 6 | 5 |
9 | 512 | 44 | 6 | 36 | 11 | 12 | 11 | 10 |
10 | 1.024 | 82 | 6 | 74 | 21 | 23 | 20 | 18 |
11 | 2.048 | 138 | 6 | 130 | 35 | 38 | 35 | 30 |
12 | 4.096 | 252 | 6 | 244 | 64 | 66 | 60 | 62 |
13 | 8.192 | 472 | 6 | 464 | 123 | 123 | 115 | 111 |
14 | 16.384 | 844 | 6 | 836 | 216 | 214 | 209 | 205 |
15 | 32.768 | 1.577 | 6 | 1.569 | 404 | 388 | 389 | 396 |
16 | 65.536 | 2.903 | 6 | 2.895 | 741 | 740 | 709 | 713 |
17 | 131.072 | 5.442 | 6 | 5.434 | 1.361 | 1.370 | 1.347 | 1.364 |
18 | 262.144 | 10.174 | 6 | 10.166 | 2.547 | 2.535 | 2.530 | 2.562 |
19 | 524.288 | 19.112 | 6 | 19.104 | 4.835 | 4.749 | 4.730 | 4.798 |
20 | 1.048.576 | 36.237 | 6 | 36.229 | 9.096 | 9.000 | 8.998 | 9.143 |
21 | 2.097.152 | 68.726 | 6 | 68.718 | 17.320 | 17.031 | 17.166 | 17.209 |
22 | 4.194.304 | 130.872 | 6 | 130.864 | 32.847 | 32.533 | 32.795 | 32.697 |
23 | 8.388.608 | 249.298 | 6 | 249.290 | 62.392 | 62.180 | 62.418 | 62.308 |
24 | 16.777.216 | 476.548 | 6 | 476.540 | 119.211 | 119.080 | 119.268 | 118.989 |
25 | 33.554.432 | 911.803 | 6 | 911.795 | 228.121 | 227.981 | 227.695 | 228.006 |
26 | 67.108.864 | 1.749.957 | 6 | 1.749.949 | 437.231 | 437.115 | 437.489 | 438.122 |
27 | 134.217.728 | 3.363.034 | 6 | 3.363.026 | 840.571 | 841.621 | 840.409 | 840.433 |
28 | 268.435.456 | 6.470.191 | 6 | 6.470.183 | 1.617.165 | 1.619.580 | 1.617.318 | 1.616.128 |
29 | 536.870.912 | 12.472.405 | 6 | 12.472.397 | 3.117.491 | 3.119.408 | 3.118.919 | 3.116.587 |
30 | 1.073.741.824 | 24.059.864 | 6 | 24.059.856 | 6.013.229 | 6.018.066 | 6.015.589 | 6.012.980 |
31 | 2.147.483.648 | 46.478.987 | 6 | 46.478.979 | 11.619.365 | 11.622.957 | 11.619.771 | 11.616.894 |
32 | 4.294.967.296 | 89.910.782 | 6 | 89.910.774 | 22.475.735 | 22.478.108 | 22.478.602 | 22.478.337 |
33 | 8.589.934.592 | 174.101.232 | 6 | 174.101.224 | 43.521.105 | 43.522.294 | 43.527.022 | 43.530.811 |
34 | 17.179.869.184 | 337.463.446 | 6 | 337.463.438 | 84.359.435 | 84.360.371 | 84.372.825 | 84.370.815 |
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 | 1 | 1 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 1 | 1 | 1 | 0 |
3 | 8 | 6 | 2 | 3 | 3 | 2 | 1 | 0 |
4 | 16 | 10 | 2 | 7 | 3 | 2 | 3 | 2 |
5 | 32 | 17 | 4 | 12 | 4 | 4 | 4 | 5 |
6 | 64 | 21 | 7 | 13 | 4 | 5 | 7 | 5 |
7 | 128 | 34 | 13 | 20 | 8 | 6 | 11 | 9 |
8 | 256 | 91 | 49 | 41 | 22 | 22 | 25 | 22 |
9 | 512 | 227 | 127 | 99 | 53 | 54 | 65 | 55 |
10 | 1.024 | 510 | 275 | 234 | 115 | 128 | 140 | 127 |
11 | 2.048 | 1.112 | 584 | 527 | 273 | 286 | 281 | 272 |
12 | 4.096 | 2.331 | 1.204 | 1.126 | 580 | 590 | 574 | 587 |
13 | 8.192 | 4.799 | 2.520 | 2.278 | 1.200 | 1.218 | 1.189 | 1.192 |
14 | 16.384 | 9.815 | 5.179 | 4.635 | 2.433 | 2.474 | 2.493 | 2.415 |
15 | 32.768 | 19.944 | 10.476 | 9.467 | 4.899 | 5.010 | 5.023 | 5.012 |
16 | 65.536 | 40.361 | 21.102 | 19.258 | 9.968 | 10.142 | 10.128 | 10.123 |
17 | 131.072 | 81.413 | 42.349 | 39.063 | 20.227 | 20.437 | 20.360 | 20.389 |
18 | 262.144 | 164.119 | 85.067 | 79.051 | 40.891 | 41.245 | 41.064 | 40.919 |
19 | 524.288 | 330.172 | 170.885 | 159.286 | 82.358 | 82.667 | 82.516 | 82.631 |
20 | 1.048.576 | 663.904 | 342.805 | 321.098 | 166.014 | 166.276 | 165.902 | 165.712 |
21 | 2.097.152 | 1.333.764 | 687.124 | 646.639 | 333.608 | 333.541 | 333.056 | 333.559 |
22 | 4.194.304 | 2.678.424 | 1.378.558 | 1.299.865 | 669.888 | 669.993 | 668.848 | 669.695 |
23 | 8.388.608 | 5.378.490 | 2.762.998 | 2.615.491 | 1.345.112 | 1.345.155 | 1.343.827 | 1.344.396 |
24 | 16.777.216 | 10.793.910 | 5.539.229 | 5.254.680 | 2.700.223 | 2.699.595 | 2.696.755 | 2.697.337 |
25 | 33.554.432 | 21.658.675 | 11.101.582 | 10.557.092 | 5.417.187 | 5.415.801 | 5.411.717 | 5.413.970 |
26 | 67.108.864 | 43.443.181 | 22.246.439 | 21.196.741 | 10.859.253 | 10.861.122 | 10.859.238 | 10.863.568 |
27 | 134.217.728 | 87.124.107 | 44.564.102 | 42.560.004 | 21.781.937 | 21.778.698 | 21.782.637 | 21.780.835 |
28 | 268.435.456 | 174.683.929 | 89.268.380 | 85.415.548 | 43.675.425 | 43.670.721 | 43.668.038 | 43.669.745 |
29 | 536.870.912 | 350.168.822 | 178.793.466 | 171.375.355 | 87.547.483 | 87.544.641 | 87.529.881 | 87.546.817 |
30 | 1.073.741.824 | 701.855.520 | 358.081.273 | 343.774.246 | 175.465.072 | 175.474.037 | 175.458.715 | 175.457.696 |
31 | 2.147.483.648 | 1.406.526.683 | 717.054.602 | 689.472.080 | 351.629.310 | 351.626.992 | 351.659.272 | 351.611.109 |
32 | 4.294.967.296 | 2.818.286.265 | 1.435.769.494 | 1.382.516.770 | 704.576.439 | 704.582.672 | 704.578.253 | 704.548.901 |
33 | 8.589.934.592 | 5.646.413.873 | 2.874.700.979 | 2.771.712.893 | 1.411.626.706 | 1.411.604.585 | 1.411.608.958 | 1.411.573.624 |
34 | 17.179.869.184 | 11.311.362.128 | 5.755.407.915 | 5.555.954.212 | 2.827.880.276 | 2.827.812.184 | 2.827.851.082 | 2.827.818.586 |