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+15x-13
f(0)=13
f(1)=3
f(2)=7
f(3)=41
f(4)=1
f(5)=29
f(6)=113
f(7)=47
f(8)=19
f(9)=1
f(10)=79
f(11)=1
f(12)=311
f(13)=1
f(14)=131
f(15)=23
f(16)=1
f(17)=59
f(18)=83
f(19)=211
f(20)=229
f(21)=743
f(22)=89
f(23)=1
f(24)=71
f(25)=1
f(26)=1
f(27)=1
f(28)=397
f(29)=421
f(30)=191
f(31)=157
f(32)=1
f(33)=1571
f(34)=1
f(35)=193
f(36)=1823
f(37)=1
f(38)=1
f(39)=1
f(40)=1
f(41)=761
f(42)=2381
f(43)=827
f(44)=1
f(45)=2687
f(46)=1
f(47)=967
f(48)=3011
f(49)=347
f(50)=1
f(51)=479
f(52)=1
f(53)=1
f(54)=1
f(55)=1279
f(56)=1321
f(57)=4091
f(58)=67
f(59)=1451
f(60)=641
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=5333
f(67)=1
f(68)=1877
f(69)=5783
f(70)=1979
f(71)=677
f(72)=1
f(73)=2137
f(74)=313
f(75)=6737
f(76)=1
f(77)=2357
f(78)=557
f(79)=353
f(80)=281
f(81)=1109
f(82)=2647
f(83)=2707
f(84)=1
f(85)=1
f(86)=1
f(87)=8861
f(88)=431
f(89)=1
f(90)=9437
f(91)=1
f(92)=1
f(93)=1433
f(94)=379
f(95)=1
f(96)=367
f(97)=3617
f(98)=1229
f(99)=11273
b) Substitution of the polynom
The polynom f(x)=x^2+15x-13 could be written as f(y)= y^2-69.25 with x=y-7.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+7.5
f'(x)>2x+14
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 | 9 | 4 | 5 | 0.900000 | 0.400000 | 0.500000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 63 | 18 | 45 | 0.630000 | 0.180000 | 0.450000 | 7.000000 | 4.500000 | 9.000000 |
3 | 1.000 | 671 | 93 | 578 | 0.671000 | 0.093000 | 0.578000 | 10.650794 | 5.166667 | 12.844444 |
4 | 10.000 | 6.734 | 658 | 6.076 | 0.673400 | 0.065800 | 0.607600 | 10.035768 | 7.075269 | 10.512111 |
5 | 100.000 | 68.006 | 5.190 | 62.816 | 0.680060 | 0.051900 | 0.628160 | 10.098901 | 7.887538 | 10.338381 |
6 | 1.000.000 | 682.076 | 42.141 | 639.935 | 0.682076 | 0.042141 | 0.639935 | 10.029644 | 8.119653 | 10.187452 |
7 | 10.000.000 | 6.834.513 | 356.604 | 6.477.909 | 0.683451 | 0.035660 | 0.647791 | 10.020164 | 8.462163 | 10.122761 |
8 | 100.000.000 | 68.455.929 | 3.087.959 | 65.367.970 | 0.684559 | 0.030880 | 0.653680 | 10.016212 | 8.659350 | 10.090905 |
9 | 1.000.000.000 | 685.406.984 | 27.233.389 | 658.173.595 | 0.685407 | 0.027233 | 0.658174 | 10.012383 | 8.819220 | 10.068748 |
10 | 10.000.000.000 | 6.861.078.258 | 243.708.273 | 6.617.369.985 | 0.686108 | 0.024371 | 0.661737 | 10.010225 | 8.948878 | 10.054141 |
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 | 3 | 1 | 1.000000 | 0.750000 | 0.250000 | 1.333333 | 1.500000 | 1.000000 |
3 | 8 | 8 | 4 | 4 | 1.000000 | 0.500000 | 0.500000 | 2.000000 | 1.333333 | 4.000000 |
4 | 16 | 11 | 5 | 6 | 0.687500 | 0.312500 | 0.375000 | 1.375000 | 1.250000 | 1.500000 |
5 | 32 | 22 | 6 | 16 | 0.687500 | 0.187500 | 0.500000 | 2.000000 | 1.200000 | 2.666667 |
6 | 64 | 38 | 12 | 26 | 0.593750 | 0.187500 | 0.406250 | 1.727273 | 2.000000 | 1.625000 |
7 | 128 | 81 | 19 | 62 | 0.632812 | 0.148438 | 0.484375 | 2.131579 | 1.583333 | 2.384615 |
8 | 256 | 169 | 32 | 137 | 0.660156 | 0.125000 | 0.535156 | 2.086420 | 1.684211 | 2.209677 |
9 | 512 | 342 | 56 | 286 | 0.667969 | 0.109375 | 0.558594 | 2.023669 | 1.750000 | 2.087591 |
10 | 1.024 | 684 | 94 | 590 | 0.667969 | 0.091797 | 0.576172 | 2.000000 | 1.678571 | 2.062937 |
11 | 2.048 | 1.375 | 167 | 1.208 | 0.671387 | 0.081543 | 0.589844 | 2.010234 | 1.776596 | 2.047458 |
12 | 4.096 | 2.759 | 301 | 2.458 | 0.673584 | 0.073486 | 0.600098 | 2.006546 | 1.802395 | 2.034768 |
13 | 8.192 | 5.528 | 553 | 4.975 | 0.674805 | 0.067505 | 0.607300 | 2.003624 | 1.837209 | 2.024003 |
14 | 16.384 | 11.077 | 1.007 | 10.070 | 0.676086 | 0.061462 | 0.614624 | 2.003799 | 1.820976 | 2.024121 |
15 | 32.768 | 22.215 | 1.896 | 20.319 | 0.677948 | 0.057861 | 0.620087 | 2.005507 | 1.882820 | 2.017776 |
16 | 65.536 | 44.540 | 3.540 | 41.000 | 0.679626 | 0.054016 | 0.625610 | 2.004952 | 1.867089 | 2.017816 |
17 | 131.072 | 89.196 | 6.621 | 82.575 | 0.680511 | 0.050514 | 0.629997 | 2.002604 | 1.870339 | 2.014024 |
18 | 262.144 | 178.597 | 12.309 | 166.288 | 0.681293 | 0.046955 | 0.634338 | 2.002298 | 1.859085 | 2.013781 |
19 | 524.288 | 357.539 | 23.139 | 334.400 | 0.681952 | 0.044134 | 0.637817 | 2.001932 | 1.879844 | 2.010969 |
20 | 1.048.576 | 715.254 | 43.994 | 671.260 | 0.682119 | 0.041956 | 0.640163 | 2.000492 | 1.901292 | 2.007356 |
21 | 2.097.152 | 1.431.366 | 83.567 | 1.347.799 | 0.682528 | 0.039848 | 0.642681 | 2.001199 | 1.899509 | 2.007864 |
22 | 4.194.304 | 2.864.536 | 158.669 | 2.705.867 | 0.682959 | 0.037830 | 0.645129 | 2.001260 | 1.898704 | 2.007619 |
23 | 8.388.608 | 5.732.523 | 302.916 | 5.429.607 | 0.683370 | 0.036110 | 0.647260 | 2.001205 | 1.909106 | 2.006605 |
24 | 16.777.216 | 11.471.575 | 578.330 | 10.893.245 | 0.683759 | 0.034471 | 0.649288 | 2.001139 | 1.909209 | 2.006268 |
25 | 33.554.432 | 22.954.402 | 1.106.084 | 21.848.318 | 0.684094 | 0.032964 | 0.651131 | 2.000981 | 1.912548 | 2.005676 |
26 | 67.108.864 | 45.930.672 | 2.121.470 | 43.809.202 | 0.684420 | 0.031612 | 0.652808 | 2.000953 | 1.918001 | 2.005152 |
27 | 134.217.728 | 91.897.039 | 4.074.416 | 87.822.623 | 0.684686 | 0.030357 | 0.654330 | 2.000777 | 1.920563 | 2.004662 |
28 | 268.435.456 | 183.863.198 | 7.837.042 | 176.026.156 | 0.684944 | 0.029195 | 0.655749 | 2.000752 | 1.923476 | 2.004337 |
29 | 536.870.912 | 367.859.852 | 15.101.343 | 352.758.509 | 0.685192 | 0.028128 | 0.657064 | 2.000726 | 1.926919 | 2.004012 |
30 | 1.073.741.824 | 735.975.797 | 29.136.702 | 706.839.095 | 0.685431 | 0.027136 | 0.658295 | 2.000696 | 1.929411 | 2.003748 |
31 | 2.147.483.648 | 1.472.434.258 | 56.293.719 | 1.416.140.539 | 0.685656 | 0.026214 | 0.659442 | 2.000656 | 1.932055 | 2.003484 |
32 | 4.294.967.296 | 2.945.779.708 | 108.876.316 | 2.836.903.392 | 0.685868 | 0.025350 | 0.660518 | 2.000619 | 1.934076 | 2.003264 |
33 | 8.589.934.592 | 5.893.253.578 | 210.809.115 | 5.682.444.463 | 0.686065 | 0.024541 | 0.661524 | 2.000575 | 1.936226 | 2.003045 |
34 | 17.179.869.184 | 11.789.766.497 | 408.590.847 | 11.381.175.650 | 0.686255 | 0.023783 | 0.662472 | 2.000553 | 1.938203 | 2.002866 |
35 | 34.359.738.368 | 23.585.683.322 | 792.685.994 | 22.792.997.328 | 0.686434 | 0.023070 | 0.663364 | 2.000522 | 1.940048 | 2.002693 |
36 | 68.719.476.736 | 47.182.949.498 | 1.539.313.515 | 45.643.635.983 | 0.686602 | 0.022400 | 0.664202 | 2.000491 | 1.941896 | 2.002529 |
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 | 1 | 0 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 1 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 2 | 1 | 1 | 0 |
4 | 16 | 5 | 1 | 3 | 2 | 1 | 1 | 1 |
5 | 32 | 6 | 1 | 4 | 2 | 1 | 1 | 2 |
6 | 64 | 12 | 1 | 10 | 2 | 4 | 2 | 4 |
7 | 128 | 19 | 1 | 17 | 4 | 5 | 5 | 5 |
8 | 256 | 32 | 1 | 29 | 7 | 7 | 10 | 8 |
9 | 512 | 56 | 1 | 53 | 15 | 12 | 17 | 12 |
10 | 1.024 | 94 | 1 | 91 | 22 | 19 | 26 | 27 |
11 | 2.048 | 167 | 1 | 164 | 39 | 38 | 44 | 46 |
12 | 4.096 | 301 | 1 | 298 | 71 | 81 | 79 | 70 |
13 | 8.192 | 553 | 1 | 550 | 139 | 144 | 140 | 130 |
14 | 16.384 | 1.007 | 1 | 1.004 | 258 | 260 | 241 | 248 |
15 | 32.768 | 1.896 | 1 | 1.893 | 468 | 470 | 478 | 480 |
16 | 65.536 | 3.540 | 1 | 3.537 | 866 | 874 | 871 | 929 |
17 | 131.072 | 6.621 | 1 | 6.618 | 1.617 | 1.663 | 1.635 | 1.706 |
18 | 262.144 | 12.309 | 1 | 12.306 | 3.035 | 3.071 | 3.074 | 3.129 |
19 | 524.288 | 23.139 | 1 | 23.136 | 5.755 | 5.813 | 5.709 | 5.862 |
20 | 1.048.576 | 43.994 | 1 | 43.991 | 10.916 | 11.056 | 10.932 | 11.090 |
21 | 2.097.152 | 83.567 | 1 | 83.564 | 20.708 | 20.995 | 20.839 | 21.025 |
22 | 4.194.304 | 158.669 | 1 | 158.666 | 39.635 | 39.711 | 39.494 | 39.829 |
23 | 8.388.608 | 302.916 | 1 | 302.913 | 75.497 | 75.998 | 75.587 | 75.834 |
24 | 16.777.216 | 578.330 | 1 | 578.327 | 144.329 | 144.696 | 144.482 | 144.823 |
25 | 33.554.432 | 1.106.084 | 1 | 1.106.081 | 275.979 | 276.504 | 276.768 | 276.833 |
26 | 67.108.864 | 2.121.470 | 1 | 2.121.467 | 529.945 | 529.937 | 530.754 | 530.834 |
27 | 134.217.728 | 4.074.416 | 1 | 4.074.413 | 1.019.040 | 1.017.418 | 1.019.026 | 1.018.932 |
28 | 268.435.456 | 7.837.042 | 1 | 7.837.039 | 1.958.816 | 1.959.365 | 1.959.891 | 1.958.970 |
29 | 536.870.912 | 15.101.343 | 1 | 15.101.340 | 3.774.711 | 3.775.608 | 3.776.898 | 3.774.126 |
30 | 1.073.741.824 | 29.136.702 | 1 | 29.136.699 | 7.282.956 | 7.284.840 | 7.286.881 | 7.282.025 |
31 | 2.147.483.648 | 56.293.719 | 1 | 56.293.716 | 14.073.495 | 14.077.317 | 14.073.758 | 14.069.149 |
32 | 4.294.967.296 | 108.876.316 | 1 | 108.876.313 | 27.213.631 | 27.226.729 | 27.220.854 | 27.215.102 |
33 | 8.589.934.592 | 210.809.115 | 1 | 210.809.112 | 52.694.307 | 52.708.510 | 52.706.908 | 52.699.390 |
34 | 17.179.869.184 | 408.590.847 | 1 | 408.590.844 | 102.131.201 | 102.157.820 | 102.149.557 | 102.152.269 |
35 | 34.359.738.368 | 792.685.994 | 1 | 792.685.991 | 198.146.712 | 198.170.475 | 198.180.206 | 198.188.601 |
36 | 68.719.476.736 | 1.539.313.515 | 1 | 1.539.313.512 | 384.787.030 | 384.825.482 | 384.836.310 | 384.864.693 |
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 | 0 | 1 |
2 | 4 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
3 | 8 | 4 | 2 | 2 | 0 | 1 | 1 | 2 |
4 | 16 | 6 | 3 | 3 | 0 | 2 | 1 | 3 |
5 | 32 | 16 | 8 | 8 | 1 | 5 | 5 | 5 |
6 | 64 | 26 | 12 | 14 | 5 | 8 | 5 | 8 |
7 | 128 | 62 | 27 | 35 | 15 | 18 | 14 | 15 |
8 | 256 | 137 | 68 | 69 | 36 | 34 | 35 | 32 |
9 | 512 | 286 | 132 | 154 | 76 | 68 | 76 | 66 |
10 | 1.024 | 590 | 268 | 322 | 144 | 146 | 152 | 148 |
11 | 2.048 | 1.208 | 552 | 656 | 305 | 294 | 317 | 292 |
12 | 4.096 | 2.458 | 1.145 | 1.313 | 595 | 603 | 630 | 630 |
13 | 8.192 | 4.975 | 2.375 | 2.600 | 1.225 | 1.249 | 1.256 | 1.245 |
14 | 16.384 | 10.070 | 4.889 | 5.181 | 2.508 | 2.538 | 2.523 | 2.501 |
15 | 32.768 | 20.319 | 9.852 | 10.467 | 5.093 | 5.094 | 5.057 | 5.075 |
16 | 65.536 | 41.000 | 19.941 | 21.059 | 10.302 | 10.192 | 10.190 | 10.316 |
17 | 131.072 | 82.575 | 40.018 | 42.557 | 20.658 | 20.594 | 20.652 | 20.671 |
18 | 262.144 | 166.288 | 80.851 | 85.437 | 41.502 | 41.628 | 41.618 | 41.540 |
19 | 524.288 | 334.400 | 163.302 | 171.098 | 83.723 | 83.630 | 83.680 | 83.367 |
20 | 1.048.576 | 671.260 | 327.726 | 343.534 | 168.037 | 167.778 | 167.875 | 167.570 |
21 | 2.097.152 | 1.347.799 | 659.035 | 688.764 | 336.894 | 336.888 | 337.229 | 336.788 |
22 | 4.194.304 | 2.705.867 | 1.325.528 | 1.380.339 | 676.242 | 676.619 | 676.654 | 676.352 |
23 | 8.388.608 | 5.429.607 | 2.663.641 | 2.765.966 | 1.357.906 | 1.357.648 | 1.356.473 | 1.357.580 |
24 | 16.777.216 | 10.893.245 | 5.348.122 | 5.545.123 | 2.723.507 | 2.722.718 | 2.724.223 | 2.722.797 |
25 | 33.554.432 | 21.848.318 | 10.733.927 | 11.114.391 | 5.460.143 | 5.462.293 | 5.460.899 | 5.464.983 |
26 | 67.108.864 | 43.809.202 | 21.540.506 | 22.268.696 | 10.951.993 | 10.952.454 | 10.950.762 | 10.953.993 |
27 | 134.217.728 | 87.822.623 | 43.211.574 | 44.611.049 | 21.955.128 | 21.954.188 | 21.955.544 | 21.957.763 |
28 | 268.435.456 | 176.026.156 | 86.665.443 | 89.360.713 | 44.001.416 | 44.005.882 | 44.006.636 | 44.012.222 |
29 | 536.870.912 | 352.758.509 | 173.792.740 | 178.965.769 | 88.181.085 | 88.188.095 | 88.185.578 | 88.203.751 |
30 | 1.073.741.824 | 706.839.095 | 348.441.794 | 358.397.301 | 176.700.413 | 176.707.901 | 176.719.728 | 176.711.053 |
31 | 2.147.483.648 | 1.416.140.539 | 698.459.638 | 717.680.901 | 354.023.372 | 354.040.221 | 354.049.367 | 354.027.579 |
32 | 4.294.967.296 | 2.836.903.392 | 1.399.866.298 | 1.437.037.094 | 709.213.921 | 709.271.747 | 709.211.912 | 709.205.812 |
33 | 8.589.934.592 | 5.682.444.463 | 2.805.276.901 | 2.877.167.562 | 1.420.600.993 | 1.420.645.101 | 1.420.631.631 | 1.420.566.738 |
34 | 17.179.869.184 | 11.381.175.650 | 5.620.919.599 | 5.760.256.051 | 2.845.299.712 | 2.845.389.203 | 2.845.300.141 | 2.845.186.594 |
35 | 34.359.738.368 | 22.792.997.328 | 11.261.459.715 | 11.531.537.613 | 5.698.189.348 | 5.698.310.931 | 5.698.264.716 | 5.698.232.333 |
36 | 68.719.476.736 | 45.643.635.983 | 22.559.686.525 | 23.083.949.458 | 11.410.963.421 | 11.410.993.441 | 11.410.863.650 | 11.410.815.471 |