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+28x+67
f(0)=67
f(1)=3
f(2)=127
f(3)=5
f(4)=13
f(5)=29
f(6)=271
f(7)=1
f(8)=71
f(9)=1
f(10)=149
f(11)=31
f(12)=547
f(13)=1
f(14)=131
f(15)=89
f(16)=257
f(17)=1
f(18)=179
f(19)=1
f(20)=79
f(21)=137
f(22)=389
f(23)=1
f(24)=263
f(25)=1
f(26)=1471
f(27)=97
f(28)=109
f(29)=43
f(30)=139
f(31)=1
f(32)=1987
f(33)=1
f(34)=1
f(35)=1
f(36)=2371
f(37)=103
f(38)=1
f(39)=1
f(40)=929
f(41)=181
f(42)=1
f(43)=1
f(44)=647
f(45)=419
f(46)=1
f(47)=449
f(48)=743
f(49)=1
f(50)=3967
f(51)=1
f(52)=1409
f(53)=1
f(54)=1
f(55)=193
f(56)=367
f(57)=307
f(58)=337
f(59)=1
f(60)=5347
f(61)=229
f(62)=5647
f(63)=1
f(64)=397
f(65)=191
f(66)=6271
f(67)=1
f(68)=1319
f(69)=1
f(70)=2309
f(71)=887
f(72)=1
f(73)=1
f(74)=1523
f(75)=487
f(76)=2657
f(77)=1019
f(78)=1667
f(79)=1
f(80)=8707
f(81)=1
f(82)=233
f(83)=1
f(84)=379
f(85)=1
f(86)=9871
f(87)=1259
f(88)=1
f(89)=1
f(90)=10687
f(91)=227
f(92)=383
f(93)=283
f(94)=769
f(95)=113
f(96)=11971
f(97)=1
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+28x+67 could be written as f(y)= y^2-129 with x=y-14
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+14
f'(x)>2x+27
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 | 3 | 5 | 0.800000 | 0.300000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 64 | 15 | 49 | 0.640000 | 0.150000 | 0.640000 | 8.000000 | 5.000000 | 9.800000 |
3 | 1.000 | 636 | 93 | 543 | 0.636000 | 0.093000 | 0.636000 | 9.937500 | 6.200000 | 11.081633 |
4 | 10.000 | 6.515 | 652 | 5.863 | 0.651500 | 0.065200 | 0.651500 | 10.243711 | 7.010753 | 10.797421 |
5 | 100.000 | 66.148 | 5.036 | 61.112 | 0.661480 | 0.050360 | 0.661480 | 10.153185 | 7.723927 | 10.423333 |
6 | 1.000.000 | 666.351 | 41.483 | 624.868 | 0.666351 | 0.041483 | 0.666351 | 10.073638 | 8.237291 | 10.224964 |
7 | 10.000.000 | 6.701.169 | 350.139 | 6.351.030 | 0.670117 | 0.035014 | 0.670117 | 10.056516 | 8.440542 | 10.163795 |
8 | 100.000.000 | 67.293.980 | 3.032.393 | 64.261.587 | 0.672940 | 0.030324 | 0.672940 | 10.042126 | 8.660541 | 10.118294 |
9 | 1.000.000.000 | 675.138.700 | 26.750.253 | 648.388.447 | 0.675139 | 0.026750 | 0.675139 | 10.032675 | 8.821499 | 10.089828 |
10 | 10.000.000.000 | 6.769.085.861 | 239.407.637 | 6.529.678.224 | 0.676909 | 0.023941 | 0.676909 | 10.026216 | 8.949734 | 10.070628 |
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 | 3 | 4 | 0.875000 | 0.375000 | 0.500000 | 1.750000 | 1.500000 | 2.000000 |
4 | 16 | 13 | 4 | 9 | 0.812500 | 0.250000 | 0.562500 | 1.857143 | 1.333333 | 2.250000 |
5 | 32 | 24 | 6 | 18 | 0.750000 | 0.187500 | 0.562500 | 1.846154 | 1.500000 | 2.000000 |
6 | 64 | 42 | 10 | 32 | 0.656250 | 0.156250 | 0.500000 | 1.750000 | 1.666667 | 1.777778 |
7 | 128 | 79 | 19 | 60 | 0.617188 | 0.148438 | 0.468750 | 1.880952 | 1.900000 | 1.875000 |
8 | 256 | 160 | 32 | 128 | 0.625000 | 0.125000 | 0.500000 | 2.025316 | 1.684211 | 2.133333 |
9 | 512 | 321 | 51 | 270 | 0.626953 | 0.099609 | 0.527344 | 2.006250 | 1.593750 | 2.109375 |
10 | 1.024 | 649 | 94 | 555 | 0.633789 | 0.091797 | 0.541992 | 2.021807 | 1.843137 | 2.055556 |
11 | 2.048 | 1.314 | 164 | 1.150 | 0.641602 | 0.080078 | 0.561523 | 2.024653 | 1.744681 | 2.072072 |
12 | 4.096 | 2.648 | 295 | 2.353 | 0.646484 | 0.072021 | 0.574463 | 2.015221 | 1.798780 | 2.046087 |
13 | 8.192 | 5.325 | 549 | 4.776 | 0.650024 | 0.067017 | 0.583008 | 2.010952 | 1.861017 | 2.029749 |
14 | 16.384 | 10.712 | 990 | 9.722 | 0.653809 | 0.060425 | 0.593384 | 2.011643 | 1.803279 | 2.035595 |
15 | 32.768 | 21.538 | 1.866 | 19.672 | 0.657288 | 0.056946 | 0.600342 | 2.010642 | 1.884848 | 2.023452 |
16 | 65.536 | 43.245 | 3.448 | 39.797 | 0.659866 | 0.052612 | 0.607254 | 2.007847 | 1.847803 | 2.023028 |
17 | 131.072 | 86.755 | 6.424 | 80.331 | 0.661888 | 0.049011 | 0.612877 | 2.006128 | 1.863109 | 2.018519 |
18 | 262.144 | 173.901 | 12.044 | 161.857 | 0.663380 | 0.045944 | 0.617435 | 2.004507 | 1.874844 | 2.014876 |
19 | 524.288 | 348.553 | 22.942 | 325.611 | 0.664812 | 0.043758 | 0.621054 | 2.004318 | 1.904849 | 2.011720 |
20 | 1.048.576 | 698.766 | 43.366 | 655.400 | 0.666395 | 0.041357 | 0.625038 | 2.004763 | 1.890245 | 2.012831 |
21 | 2.097.152 | 1.400.031 | 82.084 | 1.317.947 | 0.667587 | 0.039141 | 0.628446 | 2.003576 | 1.892819 | 2.010905 |
22 | 4.194.304 | 2.805.367 | 155.879 | 2.649.488 | 0.668852 | 0.037164 | 0.631687 | 2.003789 | 1.899018 | 2.010314 |
23 | 8.388.608 | 5.619.311 | 297.409 | 5.321.902 | 0.669874 | 0.035454 | 0.634420 | 2.003057 | 1.907948 | 2.008653 |
24 | 16.777.216 | 11.253.910 | 567.917 | 10.685.993 | 0.670785 | 0.033850 | 0.636935 | 2.002721 | 1.909549 | 2.007927 |
25 | 33.554.432 | 22.538.443 | 1.085.925 | 21.452.518 | 0.671698 | 0.032363 | 0.639335 | 2.002721 | 1.912119 | 2.007536 |
26 | 67.108.864 | 45.131.180 | 2.083.134 | 43.048.046 | 0.672507 | 0.031041 | 0.641466 | 2.002409 | 1.918304 | 2.006666 |
27 | 134.217.728 | 90.362.067 | 4.001.212 | 86.360.855 | 0.673250 | 0.029811 | 0.643439 | 2.002209 | 1.920766 | 2.006150 |
28 | 268.435.456 | 180.909.722 | 7.697.034 | 173.212.688 | 0.673941 | 0.028674 | 0.645268 | 2.002054 | 1.923676 | 2.005685 |
29 | 536.870.912 | 362.170.274 | 14.831.428 | 347.338.846 | 0.674595 | 0.027626 | 0.646969 | 2.001939 | 1.926902 | 2.005274 |
30 | 1.073.741.824 | 724.990.381 | 28.616.677 | 696.373.704 | 0.675200 | 0.026651 | 0.648549 | 2.001794 | 1.929462 | 2.004883 |
31 | 2.147.483.648 | 1.451.200.918 | 55.289.162 | 1.395.911.756 | 0.675768 | 0.025746 | 0.650022 | 2.001683 | 1.932061 | 2.004544 |
32 | 4.294.967.296 | 2.904.695.489 | 106.949.130 | 2.797.746.359 | 0.676302 | 0.024901 | 0.651401 | 2.001580 | 1.934360 | 2.004243 |
33 | 8.589.934.592 | 5.813.698.957 | 207.087.732 | 5.606.611.225 | 0.676804 | 0.024108 | 0.652695 | 2.001483 | 1.936320 | 2.003974 |
34 | 17.179.869.184 | 11.635.503.791 | 401.387.308 | 11.234.116.483 | 0.677275 | 0.023364 | 0.653912 | 2.001394 | 1.938248 | 2.003727 |
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 | 3 | 3 | 0 | 0 | 1 | 0 | 2 |
4 | 16 | 4 | 4 | 0 | 0 | 2 | 0 | 2 |
5 | 32 | 6 | 6 | 0 | 0 | 3 | 0 | 3 |
6 | 64 | 10 | 10 | 0 | 0 | 5 | 0 | 5 |
7 | 128 | 19 | 19 | 0 | 0 | 8 | 0 | 11 |
8 | 256 | 32 | 32 | 0 | 0 | 15 | 0 | 17 |
9 | 512 | 51 | 51 | 0 | 0 | 26 | 0 | 25 |
10 | 1.024 | 94 | 94 | 0 | 0 | 45 | 0 | 49 |
11 | 2.048 | 164 | 164 | 0 | 0 | 80 | 0 | 84 |
12 | 4.096 | 295 | 295 | 0 | 0 | 145 | 0 | 150 |
13 | 8.192 | 549 | 549 | 0 | 0 | 273 | 0 | 276 |
14 | 16.384 | 990 | 990 | 0 | 0 | 501 | 0 | 489 |
15 | 32.768 | 1.866 | 1.866 | 0 | 0 | 925 | 0 | 941 |
16 | 65.536 | 3.448 | 3.448 | 0 | 0 | 1.728 | 0 | 1.720 |
17 | 131.072 | 6.424 | 6.424 | 0 | 0 | 3.224 | 0 | 3.200 |
18 | 262.144 | 12.044 | 12.044 | 0 | 0 | 6.051 | 0 | 5.993 |
19 | 524.288 | 22.942 | 22.942 | 0 | 0 | 11.523 | 0 | 11.419 |
20 | 1.048.576 | 43.366 | 43.366 | 0 | 0 | 21.743 | 0 | 21.623 |
21 | 2.097.152 | 82.084 | 82.084 | 0 | 0 | 41.038 | 0 | 41.046 |
22 | 4.194.304 | 155.879 | 155.879 | 0 | 0 | 77.869 | 0 | 78.010 |
23 | 8.388.608 | 297.409 | 297.409 | 0 | 0 | 148.541 | 0 | 148.868 |
24 | 16.777.216 | 567.917 | 567.917 | 0 | 0 | 283.650 | 0 | 284.267 |
25 | 33.554.432 | 1.085.925 | 1.085.925 | 0 | 0 | 542.464 | 0 | 543.461 |
26 | 67.108.864 | 2.083.134 | 2.083.134 | 0 | 0 | 1.040.473 | 0 | 1.042.661 |
27 | 134.217.728 | 4.001.212 | 4.001.212 | 0 | 0 | 1.999.106 | 0 | 2.002.106 |
28 | 268.435.456 | 7.697.034 | 7.697.034 | 0 | 0 | 3.846.415 | 0 | 3.850.619 |
29 | 536.870.912 | 14.831.428 | 14.831.428 | 0 | 0 | 7.414.768 | 0 | 7.416.660 |
30 | 1.073.741.824 | 28.616.677 | 28.616.677 | 0 | 0 | 14.309.881 | 0 | 14.306.796 |
31 | 2.147.483.648 | 55.289.162 | 55.289.162 | 0 | 0 | 27.644.699 | 0 | 27.644.463 |
32 | 4.294.967.296 | 106.949.130 | 106.949.130 | 0 | 0 | 53.478.619 | 0 | 53.470.511 |
33 | 8.589.934.592 | 207.087.732 | 207.087.732 | 0 | 0 | 103.547.084 | 0 | 103.540.648 |
34 | 17.179.869.184 | 401.387.308 | 401.387.308 | 0 | 0 | 200.688.495 | 0 | 200.698.813 |
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 | 1 | 1 | 0 |
3 | 8 | 4 | 1 | 2 | 0 | 1 | 2 | 1 |
4 | 16 | 9 | 2 | 6 | 2 | 2 | 3 | 2 |
5 | 32 | 18 | 6 | 11 | 4 | 4 | 5 | 5 |
6 | 64 | 32 | 14 | 17 | 9 | 6 | 8 | 9 |
7 | 128 | 60 | 24 | 35 | 15 | 15 | 12 | 18 |
8 | 256 | 128 | 47 | 80 | 34 | 33 | 29 | 32 |
9 | 512 | 270 | 108 | 161 | 65 | 65 | 68 | 72 |
10 | 1.024 | 555 | 234 | 320 | 144 | 138 | 133 | 140 |
11 | 2.048 | 1.150 | 482 | 667 | 280 | 294 | 296 | 280 |
12 | 4.096 | 2.353 | 1.017 | 1.335 | 595 | 594 | 606 | 558 |
13 | 8.192 | 4.776 | 2.145 | 2.630 | 1.229 | 1.187 | 1.190 | 1.170 |
14 | 16.384 | 9.722 | 4.430 | 5.291 | 2.428 | 2.412 | 2.494 | 2.388 |
15 | 32.768 | 19.672 | 9.081 | 10.590 | 4.948 | 4.878 | 5.048 | 4.798 |
16 | 65.536 | 39.797 | 18.421 | 21.375 | 10.012 | 9.772 | 10.177 | 9.836 |
17 | 131.072 | 80.331 | 37.496 | 42.834 | 20.127 | 19.844 | 20.378 | 19.982 |
18 | 262.144 | 161.857 | 76.028 | 85.828 | 40.625 | 40.042 | 40.793 | 40.397 |
19 | 524.288 | 325.611 | 153.639 | 171.971 | 81.806 | 80.568 | 82.486 | 80.751 |
20 | 1.048.576 | 655.400 | 310.433 | 344.966 | 164.748 | 162.550 | 165.537 | 162.565 |
21 | 2.097.152 | 1.317.947 | 626.363 | 691.583 | 331.737 | 326.667 | 332.710 | 326.833 |
22 | 4.194.304 | 2.649.488 | 1.262.611 | 1.386.876 | 667.060 | 656.983 | 667.767 | 657.678 |
23 | 8.388.608 | 5.321.902 | 2.542.534 | 2.779.367 | 1.339.104 | 1.320.676 | 1.340.308 | 1.321.814 |
24 | 16.777.216 | 10.685.993 | 5.116.393 | 5.569.599 | 2.688.068 | 2.654.744 | 2.689.417 | 2.653.764 |
25 | 33.554.432 | 21.452.518 | 10.294.332 | 11.158.185 | 5.395.262 | 5.329.946 | 5.397.720 | 5.329.590 |
26 | 67.108.864 | 43.048.046 | 20.697.044 | 22.351.001 | 10.824.833 | 10.697.732 | 10.830.673 | 10.694.808 |
27 | 134.217.728 | 86.360.855 | 41.594.357 | 44.766.497 | 21.710.308 | 21.466.158 | 21.718.145 | 21.466.244 |
28 | 268.435.456 | 173.212.688 | 83.551.754 | 89.660.933 | 43.528.543 | 43.071.532 | 43.539.727 | 43.072.886 |
29 | 536.870.912 | 347.338.846 | 167.788.505 | 179.550.340 | 87.267.420 | 86.391.106 | 87.277.868 | 86.402.452 |
30 | 1.073.741.824 | 696.373.704 | 336.838.708 | 359.534.995 | 174.941.618 | 173.230.219 | 174.947.866 | 173.254.001 |
31 | 2.147.483.648 | 1.395.911.756 | 676.071.464 | 719.840.291 | 350.606.162 | 347.330.175 | 350.622.168 | 347.353.251 |
32 | 4.294.967.296 | 2.797.746.359 | 1.356.565.679 | 1.441.180.679 | 702.605.509 | 696.250.377 | 702.610.728 | 696.279.745 |
33 | 8.589.934.592 | 5.606.611.225 | 2.721.410.670 | 2.885.200.554 | 1.407.776.298 | 1.395.523.808 | 1.407.781.051 | 1.395.530.068 |
34 | 17.179.869.184 | 11.234.116.483 | 5.458.443.235 | 5.775.673.247 | 2.820.347.848 | 2.796.715.813 | 2.820.329.596 | 2.796.723.226 |