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+12x-109
f(0)=109
f(1)=3
f(2)=1
f(3)=1
f(4)=5
f(5)=1
f(6)=1
f(7)=1
f(8)=17
f(9)=1
f(10)=37
f(11)=1
f(12)=179
f(13)=1
f(14)=1
f(15)=1
f(16)=113
f(17)=1
f(18)=431
f(19)=1
f(20)=59
f(21)=73
f(22)=71
f(23)=29
f(24)=151
f(25)=1
f(26)=293
f(27)=1
f(28)=337
f(29)=1
f(30)=1151
f(31)=1
f(32)=433
f(33)=43
f(34)=97
f(35)=1
f(36)=1619
f(37)=1
f(38)=199
f(39)=47
f(40)=1
f(41)=1
f(42)=127
f(43)=1
f(44)=157
f(45)=307
f(46)=853
f(47)=1
f(48)=163
f(49)=1
f(50)=997
f(51)=1
f(52)=1
f(53)=139
f(54)=691
f(55)=149
f(56)=137
f(57)=239
f(58)=439
f(59)=1
f(60)=4211
f(61)=181
f(62)=1493
f(63)=577
f(64)=317
f(65)=1
f(66)=5039
f(67)=1
f(68)=1777
f(69)=1
f(70)=1877
f(71)=241
f(72)=5939
f(73)=1
f(74)=1
f(75)=401
f(76)=1
f(77)=281
f(78)=6911
f(79)=1
f(80)=2417
f(81)=1
f(82)=1
f(83)=1
f(84)=1
f(85)=1
f(86)=1
f(87)=1063
f(88)=2897
f(89)=1
f(90)=193
f(91)=1
f(92)=1051
f(93)=1
f(94)=1
f(95)=419
f(96)=10259
f(97)=1
f(98)=3557
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+12x-109 could be written as f(y)= y^2-145 with x=y-6
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+6
f'(x)>2x+11
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 | 5 | 2 | 3 | 0.500000 | 0.200000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 54 | 11 | 43 | 0.540000 | 0.110000 | 0.540000 | 10.800000 | 5.500000 | 14.333333 |
3 | 1.000 | 620 | 65 | 555 | 0.620000 | 0.065000 | 0.620000 | 11.481482 | 5.909091 | 12.906977 |
4 | 10.000 | 6.419 | 445 | 5.974 | 0.641900 | 0.044500 | 0.641900 | 10.353226 | 6.846154 | 10.763964 |
5 | 100.000 | 65.323 | 3.522 | 61.801 | 0.653230 | 0.035220 | 0.653230 | 10.176507 | 7.914607 | 10.344995 |
6 | 1.000.000 | 660.245 | 29.113 | 631.132 | 0.660245 | 0.029113 | 0.660245 | 10.107389 | 8.266042 | 10.212327 |
7 | 10.000.000 | 6.648.940 | 244.736 | 6.404.204 | 0.664894 | 0.024474 | 0.664894 | 10.070414 | 8.406416 | 10.147170 |
8 | 100.000.000 | 66.839.629 | 2.119.202 | 64.720.427 | 0.668396 | 0.021192 | 0.668396 | 10.052674 | 8.659135 | 10.105928 |
9 | 1.000.000.000 | 671.114.458 | 18.711.672 | 652.402.786 | 0.671114 | 0.018712 | 0.671114 | 10.040667 | 8.829584 | 10.080323 |
10 | 10.000.000.000 | 6.732.898.459 | 167.457.748 | 6.565.440.711 | 0.673290 | 0.016746 | 0.673290 | 10.032414 | 8.949373 | 10.063477 |
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 | 2 | 1 | 1 | 1.000000 | 0.500000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.500000 | 2.000000 | 1.000000 |
3 | 8 | 4 | 2 | 2 | 0.500000 | 0.250000 | 0.250000 | 1.333333 | 1.000000 | 2.000000 |
4 | 16 | 7 | 3 | 4 | 0.437500 | 0.187500 | 0.250000 | 1.750000 | 1.500000 | 2.000000 |
5 | 32 | 17 | 5 | 12 | 0.531250 | 0.156250 | 0.375000 | 2.428571 | 1.666667 | 3.000000 |
6 | 64 | 37 | 7 | 30 | 0.578125 | 0.109375 | 0.468750 | 2.176471 | 1.400000 | 2.500000 |
7 | 128 | 71 | 13 | 58 | 0.554688 | 0.101562 | 0.453125 | 1.918919 | 1.857143 | 1.933333 |
8 | 256 | 151 | 18 | 133 | 0.589844 | 0.070312 | 0.519531 | 2.126760 | 1.384615 | 2.293103 |
9 | 512 | 313 | 38 | 275 | 0.611328 | 0.074219 | 0.537109 | 2.072848 | 2.111111 | 2.067669 |
10 | 1.024 | 637 | 68 | 569 | 0.622070 | 0.066406 | 0.555664 | 2.035144 | 1.789474 | 2.069091 |
11 | 2.048 | 1.282 | 115 | 1.167 | 0.625977 | 0.056152 | 0.569824 | 2.012559 | 1.691176 | 2.050967 |
12 | 4.096 | 2.591 | 213 | 2.378 | 0.632568 | 0.052002 | 0.580566 | 2.021061 | 1.852174 | 2.037704 |
13 | 8.192 | 5.241 | 382 | 4.859 | 0.639771 | 0.046631 | 0.593140 | 2.022771 | 1.793427 | 2.043314 |
14 | 16.384 | 10.554 | 710 | 9.844 | 0.644165 | 0.043335 | 0.600830 | 2.013738 | 1.858639 | 2.025931 |
15 | 32.768 | 21.238 | 1.330 | 19.908 | 0.648132 | 0.040588 | 0.607544 | 2.012318 | 1.873239 | 2.022349 |
16 | 65.536 | 42.703 | 2.414 | 40.289 | 0.651596 | 0.036835 | 0.614761 | 2.010688 | 1.815038 | 2.023759 |
17 | 131.072 | 85.727 | 4.512 | 81.215 | 0.654045 | 0.034424 | 0.619621 | 2.007517 | 1.869097 | 2.015811 |
18 | 262.144 | 172.145 | 8.517 | 163.628 | 0.656681 | 0.032490 | 0.624191 | 2.008060 | 1.887633 | 2.014751 |
19 | 524.288 | 345.251 | 16.100 | 329.151 | 0.658514 | 0.030708 | 0.627806 | 2.005583 | 1.890337 | 2.011581 |
20 | 1.048.576 | 692.418 | 30.348 | 662.070 | 0.660341 | 0.028942 | 0.631399 | 2.005550 | 1.884969 | 2.011448 |
21 | 2.097.152 | 1.388.003 | 57.607 | 1.330.396 | 0.661851 | 0.027469 | 0.634382 | 2.004574 | 1.898214 | 2.009449 |
22 | 4.194.304 | 2.782.251 | 109.299 | 2.672.952 | 0.663340 | 0.026059 | 0.637281 | 2.004499 | 1.897321 | 2.009140 |
23 | 8.388.608 | 5.574.874 | 207.874 | 5.367.000 | 0.664577 | 0.024781 | 0.639796 | 2.003728 | 1.901884 | 2.007892 |
24 | 16.777.216 | 11.169.699 | 396.395 | 10.773.304 | 0.665766 | 0.023627 | 0.642139 | 2.003579 | 1.906900 | 2.007323 |
25 | 33.554.432 | 22.375.736 | 758.926 | 21.616.810 | 0.666849 | 0.022618 | 0.644231 | 2.003253 | 1.914570 | 2.006516 |
26 | 67.108.864 | 44.818.157 | 1.456.133 | 43.362.024 | 0.667843 | 0.021698 | 0.646145 | 2.002980 | 1.918676 | 2.005940 |
27 | 134.217.728 | 89.762.254 | 2.798.133 | 86.964.121 | 0.668781 | 0.020848 | 0.647933 | 2.002810 | 1.921619 | 2.005537 |
28 | 268.435.456 | 179.752.485 | 5.384.630 | 174.367.855 | 0.669630 | 0.020059 | 0.649571 | 2.002540 | 1.924365 | 2.005055 |
29 | 536.870.912 | 359.937.090 | 10.374.600 | 349.562.490 | 0.670435 | 0.019324 | 0.651111 | 2.002404 | 1.926706 | 2.004742 |
30 | 1.073.741.824 | 720.681.839 | 20.017.772 | 700.664.067 | 0.671187 | 0.018643 | 0.652544 | 2.002244 | 1.929498 | 2.004403 |
31 | 2.147.483.648 | 1.442.864.974 | 38.669.363 | 1.404.195.611 | 0.671886 | 0.018007 | 0.653880 | 2.002083 | 1.931752 | 2.004092 |
32 | 4.294.967.296 | 2.888.548.497 | 74.801.825 | 2.813.746.672 | 0.672543 | 0.017416 | 0.655126 | 2.001953 | 1.934395 | 2.003814 |
33 | 8.589.934.592 | 5.782.404.265 | 144.846.318 | 5.637.557.947 | 0.673160 | 0.016862 | 0.656298 | 2.001837 | 1.936401 | 2.003577 |
34 | 17.179.869.184 | 11.574.834.020 | 280.763.166 | 11.294.070.854 | 0.673744 | 0.016343 | 0.657401 | 2.001734 | 1.938352 | 2.003362 |
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 | 1 | 0 | 0 | 0 | 1 | 0 |
2 | 4 | 2 | 1 | 0 | 0 | 0 | 2 | 0 |
3 | 8 | 2 | 1 | 0 | 0 | 0 | 2 | 0 |
4 | 16 | 3 | 1 | 1 | 0 | 1 | 2 | 0 |
5 | 32 | 5 | 1 | 3 | 0 | 1 | 2 | 2 |
6 | 64 | 7 | 1 | 5 | 0 | 3 | 2 | 2 |
7 | 128 | 13 | 1 | 11 | 0 | 6 | 2 | 5 |
8 | 256 | 18 | 1 | 16 | 0 | 9 | 2 | 7 |
9 | 512 | 38 | 1 | 36 | 0 | 17 | 2 | 19 |
10 | 1.024 | 68 | 1 | 66 | 0 | 33 | 2 | 33 |
11 | 2.048 | 115 | 1 | 113 | 0 | 59 | 2 | 54 |
12 | 4.096 | 213 | 1 | 211 | 0 | 106 | 2 | 105 |
13 | 8.192 | 382 | 1 | 380 | 0 | 191 | 2 | 189 |
14 | 16.384 | 710 | 1 | 708 | 0 | 359 | 2 | 349 |
15 | 32.768 | 1.330 | 1 | 1.328 | 0 | 659 | 2 | 669 |
16 | 65.536 | 2.414 | 1 | 2.412 | 0 | 1.205 | 2 | 1.207 |
17 | 131.072 | 4.512 | 1 | 4.510 | 0 | 2.261 | 2 | 2.249 |
18 | 262.144 | 8.517 | 1 | 8.515 | 0 | 4.263 | 2 | 4.252 |
19 | 524.288 | 16.100 | 1 | 16.098 | 0 | 8.032 | 2 | 8.066 |
20 | 1.048.576 | 30.348 | 1 | 30.346 | 0 | 15.122 | 2 | 15.224 |
21 | 2.097.152 | 57.607 | 1 | 57.605 | 0 | 28.730 | 2 | 28.875 |
22 | 4.194.304 | 109.299 | 1 | 109.297 | 0 | 54.583 | 2 | 54.714 |
23 | 8.388.608 | 207.874 | 1 | 207.872 | 0 | 104.024 | 2 | 103.848 |
24 | 16.777.216 | 396.395 | 1 | 396.393 | 0 | 198.195 | 2 | 198.198 |
25 | 33.554.432 | 758.926 | 1 | 758.924 | 0 | 379.449 | 2 | 379.475 |
26 | 67.108.864 | 1.456.133 | 1 | 1.456.131 | 0 | 727.436 | 2 | 728.695 |
27 | 134.217.728 | 2.798.133 | 1 | 2.798.131 | 0 | 1.398.191 | 2 | 1.399.940 |
28 | 268.435.456 | 5.384.630 | 1 | 5.384.628 | 0 | 2.691.778 | 2 | 2.692.850 |
29 | 536.870.912 | 10.374.600 | 1 | 10.374.598 | 0 | 5.186.701 | 2 | 5.187.897 |
30 | 1.073.741.824 | 20.017.772 | 1 | 20.017.770 | 0 | 10.009.256 | 2 | 10.008.514 |
31 | 2.147.483.648 | 38.669.363 | 1 | 38.669.361 | 0 | 19.336.393 | 2 | 19.332.968 |
32 | 4.294.967.296 | 74.801.825 | 1 | 74.801.823 | 0 | 37.402.255 | 2 | 37.399.568 |
33 | 8.589.934.592 | 144.846.318 | 1 | 144.846.316 | 0 | 72.423.970 | 2 | 72.422.346 |
34 | 17.179.869.184 | 280.763.166 | 1 | 280.763.164 | 0 | 140.388.923 | 2 | 140.374.241 |
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 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 4 | 1 | 2 | 2 | 1 | 1 | 0 |
5 | 32 | 12 | 5 | 5 | 5 | 2 | 2 | 3 |
6 | 64 | 30 | 18 | 10 | 8 | 6 | 9 | 7 |
7 | 128 | 58 | 32 | 24 | 18 | 12 | 18 | 10 |
8 | 256 | 133 | 74 | 57 | 35 | 31 | 41 | 26 |
9 | 512 | 275 | 157 | 116 | 71 | 66 | 79 | 59 |
10 | 1.024 | 569 | 318 | 249 | 146 | 134 | 160 | 129 |
11 | 2.048 | 1.167 | 628 | 537 | 311 | 265 | 319 | 272 |
12 | 4.096 | 2.378 | 1.238 | 1.138 | 640 | 548 | 642 | 548 |
13 | 8.192 | 4.859 | 2.540 | 2.317 | 1.335 | 1.083 | 1.310 | 1.131 |
14 | 16.384 | 9.844 | 5.119 | 4.723 | 2.658 | 2.267 | 2.644 | 2.275 |
15 | 32.768 | 19.908 | 10.281 | 9.625 | 5.318 | 4.579 | 5.360 | 4.651 |
16 | 65.536 | 40.289 | 20.708 | 19.579 | 10.688 | 9.444 | 10.715 | 9.442 |
17 | 131.072 | 81.215 | 41.842 | 39.371 | 21.458 | 19.123 | 21.482 | 19.152 |
18 | 262.144 | 163.628 | 84.018 | 79.608 | 43.099 | 38.603 | 43.162 | 38.764 |
19 | 524.288 | 329.151 | 169.199 | 159.950 | 86.405 | 77.962 | 86.525 | 78.259 |
20 | 1.048.576 | 662.070 | 339.989 | 322.079 | 172.947 | 157.721 | 173.395 | 158.007 |
21 | 2.097.152 | 1.330.396 | 682.084 | 648.310 | 347.131 | 317.923 | 347.742 | 317.600 |
22 | 4.194.304 | 2.672.952 | 1.367.629 | 1.305.321 | 696.294 | 640.135 | 696.937 | 639.586 |
23 | 8.388.608 | 5.367.000 | 2.742.406 | 2.624.592 | 1.394.433 | 1.288.442 | 1.396.338 | 1.287.787 |
24 | 16.777.216 | 10.773.304 | 5.498.645 | 5.274.657 | 2.795.742 | 2.590.367 | 2.797.001 | 2.590.194 |
25 | 33.554.432 | 21.616.810 | 11.021.710 | 10.595.098 | 5.600.812 | 5.206.181 | 5.603.290 | 5.206.527 |
26 | 67.108.864 | 43.362.024 | 22.088.500 | 21.273.522 | 11.216.640 | 10.464.550 | 11.220.368 | 10.460.466 |
27 | 134.217.728 | 86.964.121 | 44.265.339 | 42.698.780 | 22.465.640 | 21.016.362 | 22.467.885 | 21.014.234 |
28 | 268.435.456 | 174.367.855 | 88.682.992 | 85.684.861 | 44.979.598 | 42.199.268 | 44.989.590 | 42.199.399 |
29 | 536.870.912 | 349.562.490 | 177.671.020 | 171.891.468 | 90.057.642 | 84.716.866 | 90.069.359 | 84.718.623 |
30 | 1.073.741.824 | 700.664.067 | 355.908.928 | 344.755.137 | 180.313.959 | 170.012.654 | 180.327.963 | 170.009.491 |
31 | 2.147.483.648 | 1.404.195.611 | 712.839.410 | 691.356.199 | 360.996.121 | 341.095.339 | 360.991.641 | 341.112.510 |
32 | 4.294.967.296 | 2.813.746.672 | 1.427.582.959 | 1.386.163.711 | 722.666.308 | 684.208.747 | 722.665.186 | 684.206.431 |
33 | 8.589.934.592 | 5.637.557.947 | 2.858.834.946 | 2.778.722.999 | 1.446.582.447 | 1.372.185.574 | 1.446.571.653 | 1.372.218.273 |
34 | 17.179.869.184 | 11.294.070.854 | 5.724.652.839 | 5.569.418.013 | 2.895.566.785 | 2.751.472.902 | 2.895.531.399 | 2.751.499.768 |