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+17x-41
f(0)=41
f(1)=23
f(2)=3
f(3)=19
f(4)=43
f(5)=1
f(6)=97
f(7)=127
f(8)=53
f(9)=193
f(10)=229
f(11)=89
f(12)=307
f(13)=349
f(14)=131
f(15)=439
f(16)=487
f(17)=179
f(18)=31
f(19)=643
f(20)=233
f(21)=757
f(22)=1
f(23)=293
f(24)=1
f(25)=1009
f(26)=359
f(27)=37
f(28)=1
f(29)=431
f(30)=1
f(31)=1447
f(32)=509
f(33)=1609
f(34)=1693
f(35)=593
f(36)=1867
f(37)=103
f(38)=683
f(39)=2143
f(40)=2239
f(41)=1
f(42)=2437
f(43)=2539
f(44)=881
f(45)=2749
f(46)=2857
f(47)=1
f(48)=3079
f(49)=1
f(50)=1103
f(51)=149
f(52)=3547
f(53)=1223
f(54)=3793
f(55)=3919
f(56)=71
f(57)=4177
f(58)=139
f(59)=1481
f(60)=241
f(61)=1
f(62)=1619
f(63)=4999
f(64)=1
f(65)=1
f(66)=5437
f(67)=151
f(68)=1913
f(69)=83
f(70)=263
f(71)=2069
f(72)=6367
f(73)=6529
f(74)=1
f(75)=1
f(76)=7027
f(77)=2399
f(78)=7369
f(79)=397
f(80)=1
f(81)=1
f(82)=197
f(83)=2753
f(84)=8443
f(85)=8629
f(86)=2939
f(87)=9007
f(88)=9199
f(89)=101
f(90)=223
f(91)=9787
f(92)=3329
f(93)=443
f(94)=547
f(95)=3533
f(96)=107
f(97)=479
f(98)=1
f(99)=11443
b) Substitution of the polynom
The polynom f(x)=x^2+17x-41 could be written as f(y)= y^2-113.25 with x=y-8.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+8.5
f'(x)>2x+16
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 | 9 | 1 | 1.000000 | 0.900000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 78 | 44 | 34 | 0.780000 | 0.440000 | 0.780000 | 7.800000 | 4.888889 | 34.000000 |
3 | 1.000 | 751 | 260 | 491 | 0.751000 | 0.260000 | 0.751000 | 9.628205 | 5.909091 | 14.441176 |
4 | 10.000 | 7.356 | 1.880 | 5.476 | 0.735600 | 0.188000 | 0.735600 | 9.794940 | 7.230769 | 11.152749 |
5 | 100.000 | 73.005 | 14.717 | 58.288 | 0.730050 | 0.147170 | 0.730050 | 9.924551 | 7.828191 | 10.644266 |
6 | 1.000.000 | 723.761 | 119.964 | 603.797 | 0.723761 | 0.119964 | 0.723761 | 9.913856 | 8.151389 | 10.358856 |
7 | 10.000.000 | 7.192.213 | 1.013.658 | 6.178.555 | 0.719221 | 0.101366 | 0.719221 | 9.937276 | 8.449685 | 10.232835 |
8 | 100.000.000 | 71.568.386 | 8.782.979 | 62.785.407 | 0.715684 | 0.087830 | 0.715684 | 9.950815 | 8.664638 | 10.161827 |
9 | 1.000.000.000 | 713.039.220 | 77.502.001 | 635.537.219 | 0.713039 | 0.077502 | 0.713039 | 9.963048 | 8.824113 | 10.122372 |
10 | 10.000.000.000 | 7.109.478.757 | 693.605.900 | 6.415.872.857 | 0.710948 | 0.069361 | 0.710948 | 9.970670 | 8.949522 | 10.095197 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 1.600000 | 1.400000 | inf |
4 | 16 | 16 | 13 | 3 | 1.000000 | 0.812500 | 0.187500 | 2.000000 | 1.857143 | 3.000000 |
5 | 32 | 26 | 17 | 9 | 0.812500 | 0.531250 | 0.281250 | 1.625000 | 1.307692 | 3.000000 |
6 | 64 | 52 | 32 | 20 | 0.812500 | 0.500000 | 0.312500 | 2.000000 | 1.882353 | 2.222222 |
7 | 128 | 99 | 52 | 47 | 0.773438 | 0.406250 | 0.367188 | 1.903846 | 1.625000 | 2.350000 |
8 | 256 | 197 | 92 | 105 | 0.769531 | 0.359375 | 0.410156 | 1.989899 | 1.769231 | 2.234043 |
9 | 512 | 391 | 146 | 245 | 0.763672 | 0.285156 | 0.478516 | 1.984772 | 1.586957 | 2.333333 |
10 | 1.024 | 772 | 267 | 505 | 0.753906 | 0.260742 | 0.493164 | 1.974425 | 1.828767 | 2.061224 |
11 | 2.048 | 1.530 | 490 | 1.040 | 0.747070 | 0.239258 | 0.507812 | 1.981865 | 1.835206 | 2.059406 |
12 | 4.096 | 3.039 | 864 | 2.175 | 0.741943 | 0.210938 | 0.531006 | 1.986274 | 1.763265 | 2.091346 |
13 | 8.192 | 6.048 | 1.577 | 4.471 | 0.738281 | 0.192505 | 0.545776 | 1.990128 | 1.825231 | 2.055632 |
14 | 16.384 | 12.026 | 2.920 | 9.106 | 0.734009 | 0.178223 | 0.555786 | 1.988426 | 1.851617 | 2.036681 |
15 | 32.768 | 24.025 | 5.385 | 18.640 | 0.733185 | 0.164337 | 0.568848 | 1.997755 | 1.844178 | 2.047002 |
16 | 65.536 | 47.905 | 10.050 | 37.855 | 0.730972 | 0.153351 | 0.577621 | 1.993965 | 1.866295 | 2.030848 |
17 | 131.072 | 95.561 | 18.753 | 76.808 | 0.729073 | 0.143074 | 0.585999 | 1.994802 | 1.865970 | 2.029006 |
18 | 262.144 | 190.541 | 35.216 | 155.325 | 0.726856 | 0.134338 | 0.592518 | 1.993920 | 1.877886 | 2.022250 |
19 | 524.288 | 380.344 | 66.278 | 314.066 | 0.725449 | 0.126415 | 0.599033 | 1.996127 | 1.882042 | 2.021993 |
20 | 1.048.576 | 758.808 | 125.219 | 633.589 | 0.723656 | 0.119418 | 0.604238 | 1.995057 | 1.889300 | 2.017375 |
21 | 2.097.152 | 1.514.348 | 237.560 | 1.276.788 | 0.722097 | 0.113277 | 0.608820 | 1.995693 | 1.897156 | 2.015167 |
22 | 4.194.304 | 3.023.248 | 451.885 | 2.571.363 | 0.720798 | 0.107738 | 0.613061 | 1.996402 | 1.902193 | 2.013931 |
23 | 8.388.608 | 6.035.662 | 860.791 | 5.174.871 | 0.719507 | 0.102614 | 0.616893 | 1.996416 | 1.904889 | 2.012501 |
24 | 16.777.216 | 12.051.566 | 1.642.446 | 10.409.120 | 0.718329 | 0.097897 | 0.620432 | 1.996727 | 1.908066 | 2.011474 |
25 | 33.554.432 | 24.066.096 | 3.146.241 | 20.919.855 | 0.717226 | 0.093765 | 0.623460 | 1.996927 | 1.915583 | 2.009762 |
26 | 67.108.864 | 48.065.095 | 6.033.239 | 42.031.856 | 0.716226 | 0.089902 | 0.626323 | 1.997212 | 1.917602 | 2.009185 |
27 | 134.217.728 | 96.007.570 | 11.590.736 | 84.416.834 | 0.715312 | 0.086358 | 0.628954 | 1.997449 | 1.921147 | 2.008401 |
28 | 268.435.456 | 191.792.394 | 22.300.503 | 169.491.891 | 0.714482 | 0.083076 | 0.631406 | 1.997680 | 1.923994 | 2.007797 |
29 | 536.870.912 | 383.162.046 | 42.973.752 | 340.188.294 | 0.713695 | 0.080045 | 0.633650 | 1.997796 | 1.927031 | 2.007107 |
30 | 1.073.741.824 | 765.548.118 | 82.915.152 | 682.632.966 | 0.712972 | 0.077221 | 0.635751 | 1.997975 | 1.929437 | 2.006633 |
31 | 2.147.483.648 | 1.529.639.812 | 160.205.267 | 1.369.434.545 | 0.712294 | 0.074601 | 0.637693 | 1.998098 | 1.932159 | 2.006107 |
32 | 4.294.967.296 | 3.056.570.809 | 309.842.823 | 2.746.727.986 | 0.711663 | 0.072141 | 0.639522 | 1.998229 | 1.934036 | 2.005739 |
33 | 8.589.934.592 | 6.108.065.581 | 599.970.123 | 5.508.095.458 | 0.711072 | 0.069846 | 0.641227 | 1.998339 | 1.936369 | 2.005330 |
34 | 17.179.869.184 | 12.206.616.194 | 1.162.902.494 | 11.043.713.700 | 0.710519 | 0.067690 | 0.642829 | 1.998442 | 1.938267 | 2.004997 |
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 | 3 | 0 | 2 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 2 | 2 | 1 | 3 | 0 | 1 |
3 | 8 | 7 | 4 | 2 | 2 | 3 | 0 | 2 |
4 | 16 | 13 | 10 | 2 | 3 | 4 | 2 | 4 |
5 | 32 | 17 | 14 | 2 | 4 | 5 | 3 | 5 |
6 | 64 | 32 | 29 | 2 | 8 | 8 | 6 | 10 |
7 | 128 | 52 | 49 | 2 | 14 | 15 | 9 | 14 |
8 | 256 | 92 | 89 | 2 | 24 | 21 | 18 | 29 |
9 | 512 | 146 | 143 | 2 | 36 | 33 | 33 | 44 |
10 | 1.024 | 267 | 264 | 2 | 64 | 65 | 66 | 72 |
11 | 2.048 | 490 | 487 | 2 | 121 | 124 | 126 | 119 |
12 | 4.096 | 864 | 861 | 2 | 215 | 224 | 223 | 202 |
13 | 8.192 | 1.577 | 1.574 | 2 | 408 | 398 | 398 | 373 |
14 | 16.384 | 2.920 | 2.917 | 2 | 751 | 746 | 735 | 688 |
15 | 32.768 | 5.385 | 5.382 | 2 | 1.374 | 1.350 | 1.376 | 1.285 |
16 | 65.536 | 10.050 | 10.047 | 2 | 2.524 | 2.511 | 2.525 | 2.490 |
17 | 131.072 | 18.753 | 18.750 | 2 | 4.734 | 4.693 | 4.692 | 4.634 |
18 | 262.144 | 35.216 | 35.213 | 2 | 8.856 | 8.865 | 8.774 | 8.721 |
19 | 524.288 | 66.278 | 66.275 | 2 | 16.632 | 16.668 | 16.541 | 16.437 |
20 | 1.048.576 | 125.219 | 125.216 | 2 | 31.436 | 31.469 | 31.188 | 31.126 |
21 | 2.097.152 | 237.560 | 237.557 | 2 | 59.662 | 59.405 | 59.296 | 59.197 |
22 | 4.194.304 | 451.885 | 451.882 | 2 | 113.184 | 113.084 | 112.825 | 112.792 |
23 | 8.388.608 | 860.791 | 860.788 | 2 | 215.896 | 214.864 | 214.935 | 215.096 |
24 | 16.777.216 | 1.642.446 | 1.642.443 | 2 | 411.190 | 410.226 | 410.596 | 410.434 |
25 | 33.554.432 | 3.146.241 | 3.146.238 | 2 | 786.911 | 785.965 | 786.620 | 786.745 |
26 | 67.108.864 | 6.033.239 | 6.033.236 | 2 | 1.509.135 | 1.507.358 | 1.508.637 | 1.508.109 |
27 | 134.217.728 | 11.590.736 | 11.590.733 | 2 | 2.897.912 | 2.897.005 | 2.898.211 | 2.897.608 |
28 | 268.435.456 | 22.300.503 | 22.300.500 | 2 | 5.575.924 | 5.573.966 | 5.576.191 | 5.574.422 |
29 | 536.870.912 | 42.973.752 | 42.973.749 | 2 | 10.745.492 | 10.741.053 | 10.743.184 | 10.744.023 |
30 | 1.073.741.824 | 82.915.152 | 82.915.149 | 2 | 20.731.930 | 20.729.478 | 20.725.933 | 20.727.811 |
31 | 2.147.483.648 | 160.205.267 | 160.205.264 | 2 | 40.054.789 | 40.051.264 | 40.048.760 | 40.050.454 |
32 | 4.294.967.296 | 309.842.823 | 309.842.820 | 2 | 77.458.728 | 77.466.665 | 77.456.799 | 77.460.631 |
33 | 8.589.934.592 | 599.970.123 | 599.970.120 | 2 | 149.995.941 | 150.002.834 | 149.977.562 | 149.993.786 |
34 | 17.179.869.184 | 1.162.902.494 | 1.162.902.491 | 2 | 290.736.909 | 290.734.846 | 290.705.195 | 290.725.544 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
4 | 16 | 3 | 0 | 3 | 1 | 1 | 1 | 0 |
5 | 32 | 9 | 0 | 9 | 2 | 2 | 3 | 2 |
6 | 64 | 20 | 3 | 17 | 6 | 5 | 4 | 5 |
7 | 128 | 47 | 9 | 38 | 14 | 10 | 11 | 12 |
8 | 256 | 105 | 32 | 73 | 26 | 26 | 27 | 26 |
9 | 512 | 245 | 81 | 164 | 61 | 66 | 60 | 58 |
10 | 1.024 | 505 | 175 | 330 | 118 | 130 | 134 | 123 |
11 | 2.048 | 1.040 | 383 | 657 | 251 | 259 | 274 | 256 |
12 | 4.096 | 2.175 | 854 | 1.321 | 525 | 554 | 536 | 560 |
13 | 8.192 | 4.471 | 1.768 | 2.703 | 1.097 | 1.128 | 1.124 | 1.122 |
14 | 16.384 | 9.106 | 3.746 | 5.360 | 2.287 | 2.266 | 2.279 | 2.274 |
15 | 32.768 | 18.640 | 7.864 | 10.776 | 4.623 | 4.673 | 4.701 | 4.643 |
16 | 65.536 | 37.855 | 16.210 | 21.645 | 9.406 | 9.512 | 9.461 | 9.476 |
17 | 131.072 | 76.808 | 33.294 | 43.514 | 19.057 | 19.228 | 19.141 | 19.382 |
18 | 262.144 | 155.325 | 68.123 | 87.202 | 38.660 | 38.830 | 39.038 | 38.797 |
19 | 524.288 | 314.066 | 139.156 | 174.910 | 78.279 | 78.555 | 78.815 | 78.417 |
20 | 1.048.576 | 633.589 | 283.243 | 350.346 | 158.208 | 158.442 | 158.811 | 158.128 |
21 | 2.097.152 | 1.276.788 | 575.172 | 701.616 | 319.013 | 319.578 | 319.675 | 318.522 |
22 | 4.194.304 | 2.571.363 | 1.165.594 | 1.405.769 | 642.568 | 643.046 | 643.432 | 642.317 |
23 | 8.388.608 | 5.174.871 | 2.360.133 | 2.814.738 | 1.293.289 | 1.293.476 | 1.294.532 | 1.293.574 |
24 | 16.777.216 | 10.409.120 | 4.770.764 | 5.638.356 | 2.601.167 | 2.601.055 | 2.603.155 | 2.603.743 |
25 | 33.554.432 | 20.919.855 | 9.631.643 | 11.288.212 | 5.228.336 | 5.229.202 | 5.231.255 | 5.231.062 |
26 | 67.108.864 | 42.031.856 | 19.432.532 | 22.599.324 | 10.504.151 | 10.507.445 | 10.511.584 | 10.508.676 |
27 | 134.217.728 | 84.416.834 | 39.171.325 | 45.245.509 | 21.099.478 | 21.106.457 | 21.107.588 | 21.103.311 |
28 | 268.435.456 | 169.491.891 | 78.905.054 | 90.586.837 | 42.373.442 | 42.377.785 | 42.369.428 | 42.371.236 |
29 | 536.870.912 | 340.188.294 | 158.850.567 | 181.337.727 | 85.050.740 | 85.057.151 | 85.046.181 | 85.034.222 |
30 | 1.073.741.824 | 682.632.966 | 319.634.031 | 362.998.935 | 170.656.538 | 170.666.313 | 170.655.542 | 170.654.573 |
31 | 2.147.483.648 | 1.369.434.545 | 642.878.355 | 726.556.190 | 342.353.115 | 342.387.262 | 342.348.262 | 342.345.906 |
32 | 4.294.967.296 | 2.746.727.986 | 1.292.549.387 | 1.454.178.599 | 686.660.930 | 686.697.378 | 686.689.610 | 686.680.068 |
33 | 8.589.934.592 | 5.508.095.458 | 2.597.736.154 | 2.910.359.304 | 1.377.008.217 | 1.377.028.481 | 1.377.029.968 | 1.377.028.792 |
34 | 17.179.869.184 | 11.043.713.700 | 5.219.228.008 | 5.824.485.692 | 2.760.931.877 | 2.760.899.091 | 2.760.962.305 | 2.760.920.427 |