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+20x-11
f(0)=11
f(1)=5
f(2)=3
f(3)=29
f(4)=17
f(5)=19
f(6)=1
f(7)=89
f(8)=71
f(9)=1
f(10)=1
f(11)=1
f(12)=373
f(13)=1
f(14)=31
f(15)=257
f(16)=113
f(17)=103
f(18)=673
f(19)=73
f(20)=263
f(21)=1
f(22)=83
f(23)=163
f(24)=1
f(25)=557
f(26)=79
f(27)=37
f(28)=43
f(29)=47
f(30)=1489
f(31)=157
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=401
f(37)=1049
f(38)=1
f(39)=229
f(40)=2389
f(41)=1
f(42)=2593
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=523
f(48)=3253
f(49)=337
f(50)=1163
f(51)=1
f(52)=3733
f(53)=643
f(54)=797
f(55)=1
f(56)=283
f(57)=199
f(58)=4513
f(59)=1
f(60)=4789
f(61)=1
f(62)=1
f(63)=2609
f(64)=1
f(65)=919
f(66)=1
f(67)=2909
f(68)=181
f(69)=613
f(70)=331
f(71)=1
f(72)=389
f(73)=3389
f(74)=463
f(75)=3557
f(76)=1
f(77)=1
f(78)=449
f(79)=1
f(80)=2663
f(81)=1
f(82)=8353
f(83)=1423
f(84)=349
f(85)=4457
f(86)=607
f(87)=4649
f(88)=863
f(89)=1
f(90)=1
f(91)=1009
f(92)=1
f(93)=1
f(94)=2141
f(95)=107
f(96)=1
f(97)=5669
f(98)=3851
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+20x-11 could be written as f(y)= y^2-111 with x=y-10
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+10
f'(x)>2x+19
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 | 2 | 6 | 0.800000 | 0.200000 | 0.800000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 63 | 12 | 51 | 0.630000 | 0.120000 | 0.630000 | 7.875000 | 6.000000 | 8.500000 |
3 | 1.000 | 661 | 68 | 593 | 0.661000 | 0.068000 | 0.661000 | 10.492064 | 5.666667 | 11.627451 |
4 | 10.000 | 6.680 | 477 | 6.203 | 0.668000 | 0.047700 | 0.668000 | 10.105900 | 7.014706 | 10.460371 |
5 | 100.000 | 67.304 | 3.719 | 63.585 | 0.673040 | 0.037190 | 0.673040 | 10.075449 | 7.796646 | 10.250685 |
6 | 1.000.000 | 676.929 | 30.641 | 646.288 | 0.676929 | 0.030641 | 0.676929 | 10.057782 | 8.239042 | 10.164158 |
7 | 10.000.000 | 6.790.076 | 259.572 | 6.530.504 | 0.679008 | 0.025957 | 0.679008 | 10.030706 | 8.471395 | 10.104634 |
8 | 100.000.000 | 68.063.393 | 2.251.228 | 65.812.165 | 0.680634 | 0.022512 | 0.680634 | 10.023952 | 8.672846 | 10.077655 |
9 | 1.000.000.000 | 681.943.887 | 19.865.027 | 662.078.860 | 0.681944 | 0.019865 | 0.681944 | 10.019246 | 8.824085 | 10.060129 |
10 | 10.000.000.000 | 6.830.094.838 | 177.774.036 | 6.652.320.802 | 0.683010 | 0.017777 | 0.683010 | 10.015626 | 8.949096 | 10.047626 |
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 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 1.000000 | 3.000000 |
3 | 8 | 8 | 2 | 6 | 1.000000 | 0.250000 | 0.750000 | 1.600000 | 1.000000 | 2.000000 |
4 | 16 | 12 | 3 | 9 | 0.750000 | 0.187500 | 0.562500 | 1.500000 | 1.500000 | 1.500000 |
5 | 32 | 23 | 5 | 18 | 0.718750 | 0.156250 | 0.562500 | 1.916667 | 1.666667 | 2.000000 |
6 | 64 | 40 | 11 | 29 | 0.625000 | 0.171875 | 0.453125 | 1.739130 | 2.200000 | 1.611111 |
7 | 128 | 79 | 14 | 65 | 0.617188 | 0.109375 | 0.507812 | 1.975000 | 1.272727 | 2.241379 |
8 | 256 | 166 | 24 | 142 | 0.648438 | 0.093750 | 0.554688 | 2.101266 | 1.714286 | 2.184615 |
9 | 512 | 337 | 38 | 299 | 0.658203 | 0.074219 | 0.583984 | 2.030120 | 1.583333 | 2.105634 |
10 | 1.024 | 677 | 69 | 608 | 0.661133 | 0.067383 | 0.593750 | 2.008902 | 1.815789 | 2.033445 |
11 | 2.048 | 1.366 | 127 | 1.239 | 0.666992 | 0.062012 | 0.604980 | 2.017725 | 1.840580 | 2.037829 |
12 | 4.096 | 2.738 | 224 | 2.514 | 0.668457 | 0.054688 | 0.613770 | 2.004392 | 1.763780 | 2.029056 |
13 | 8.192 | 5.473 | 401 | 5.072 | 0.668091 | 0.048950 | 0.619141 | 1.998904 | 1.790179 | 2.017502 |
14 | 16.384 | 10.985 | 722 | 10.263 | 0.670471 | 0.044067 | 0.626404 | 2.007126 | 1.800499 | 2.023462 |
15 | 32.768 | 21.971 | 1.384 | 20.587 | 0.670502 | 0.042236 | 0.628265 | 2.000091 | 1.916898 | 2.005944 |
16 | 65.536 | 44.059 | 2.578 | 41.481 | 0.672287 | 0.039337 | 0.632950 | 2.005325 | 1.862717 | 2.014912 |
17 | 131.072 | 88.309 | 4.752 | 83.557 | 0.673744 | 0.036255 | 0.637489 | 2.004335 | 1.843289 | 2.014344 |
18 | 262.144 | 176.932 | 8.939 | 167.993 | 0.674942 | 0.034100 | 0.640842 | 2.003556 | 1.881103 | 2.010520 |
19 | 524.288 | 354.396 | 16.795 | 337.601 | 0.675957 | 0.032034 | 0.643923 | 2.003007 | 1.878845 | 2.009614 |
20 | 1.048.576 | 709.853 | 32.051 | 677.802 | 0.676969 | 0.030566 | 0.646402 | 2.002994 | 1.908366 | 2.007701 |
21 | 2.097.152 | 1.421.079 | 60.656 | 1.360.423 | 0.677623 | 0.028923 | 0.648700 | 2.001934 | 1.892484 | 2.007110 |
22 | 4.194.304 | 2.844.625 | 115.459 | 2.729.166 | 0.678211 | 0.027528 | 0.650684 | 2.001736 | 1.903505 | 2.006116 |
23 | 8.388.608 | 5.694.666 | 220.489 | 5.474.177 | 0.678857 | 0.026284 | 0.652573 | 2.001904 | 1.909674 | 2.005806 |
24 | 16.777.216 | 11.398.362 | 420.939 | 10.977.423 | 0.679395 | 0.025090 | 0.654305 | 2.001586 | 1.909116 | 2.005310 |
25 | 33.554.432 | 22.813.455 | 806.622 | 22.006.833 | 0.679894 | 0.024039 | 0.655855 | 2.001468 | 1.916244 | 2.004736 |
26 | 67.108.864 | 45.659.152 | 1.546.880 | 44.112.272 | 0.680374 | 0.023050 | 0.657324 | 2.001413 | 1.917726 | 2.004481 |
27 | 134.217.728 | 91.377.676 | 2.971.592 | 88.406.084 | 0.680817 | 0.022140 | 0.658677 | 2.001300 | 1.921023 | 2.004115 |
28 | 268.435.456 | 182.868.611 | 5.715.545 | 177.153.066 | 0.681239 | 0.021292 | 0.659947 | 2.001239 | 1.923395 | 2.003856 |
29 | 536.870.912 | 365.944.543 | 11.013.467 | 354.931.076 | 0.681625 | 0.020514 | 0.661111 | 2.001134 | 1.926932 | 2.003528 |
30 | 1.073.741.824 | 732.271.607 | 21.253.182 | 711.018.425 | 0.681981 | 0.019794 | 0.662188 | 2.001045 | 1.929745 | 2.003258 |
31 | 2.147.483.648 | 1.465.273.971 | 41.060.268 | 1.424.213.703 | 0.682321 | 0.019120 | 0.663201 | 2.000998 | 1.931959 | 2.003062 |
32 | 4.294.967.296 | 2.931.938.588 | 79.416.950 | 2.852.521.638 | 0.682645 | 0.018491 | 0.664154 | 2.000949 | 1.934156 | 2.002875 |
33 | 8.589.934.592 | 5.866.451.186 | 153.773.607 | 5.712.677.579 | 0.682945 | 0.017902 | 0.665043 | 2.000878 | 1.936282 | 2.002676 |
34 | 17.179.869.184 | 11.737.778.517 | 298.045.327 | 11.439.733.190 | 0.683229 | 0.017349 | 0.665880 | 2.000831 | 1.938209 | 2.002517 |
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 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 2 | 0 | 1 | 1 | 1 | 0 | 0 |
4 | 16 | 3 | 1 | 1 | 1 | 1 | 1 | 0 |
5 | 32 | 5 | 3 | 1 | 3 | 1 | 1 | 0 |
6 | 64 | 11 | 9 | 1 | 5 | 1 | 5 | 0 |
7 | 128 | 14 | 12 | 1 | 8 | 1 | 5 | 0 |
8 | 256 | 24 | 22 | 1 | 12 | 1 | 11 | 0 |
9 | 512 | 38 | 36 | 1 | 17 | 1 | 20 | 0 |
10 | 1.024 | 69 | 67 | 1 | 30 | 1 | 38 | 0 |
11 | 2.048 | 127 | 125 | 1 | 55 | 1 | 71 | 0 |
12 | 4.096 | 224 | 222 | 1 | 105 | 1 | 118 | 0 |
13 | 8.192 | 401 | 399 | 1 | 204 | 1 | 196 | 0 |
14 | 16.384 | 722 | 720 | 1 | 356 | 1 | 365 | 0 |
15 | 32.768 | 1.384 | 1.382 | 1 | 695 | 1 | 688 | 0 |
16 | 65.536 | 2.578 | 2.576 | 1 | 1.305 | 1 | 1.272 | 0 |
17 | 131.072 | 4.752 | 4.750 | 1 | 2.404 | 1 | 2.347 | 0 |
18 | 262.144 | 8.939 | 8.937 | 1 | 4.486 | 1 | 4.452 | 0 |
19 | 524.288 | 16.795 | 16.793 | 1 | 8.413 | 1 | 8.381 | 0 |
20 | 1.048.576 | 32.051 | 32.049 | 1 | 16.019 | 1 | 16.031 | 0 |
21 | 2.097.152 | 60.656 | 60.654 | 1 | 30.379 | 1 | 30.276 | 0 |
22 | 4.194.304 | 115.459 | 115.457 | 1 | 57.762 | 1 | 57.696 | 0 |
23 | 8.388.608 | 220.489 | 220.487 | 1 | 110.279 | 1 | 110.209 | 0 |
24 | 16.777.216 | 420.939 | 420.937 | 1 | 210.552 | 1 | 210.386 | 0 |
25 | 33.554.432 | 806.622 | 806.620 | 1 | 403.375 | 1 | 403.246 | 0 |
26 | 67.108.864 | 1.546.880 | 1.546.878 | 1 | 774.075 | 1 | 772.804 | 0 |
27 | 134.217.728 | 2.971.592 | 2.971.590 | 1 | 1.486.447 | 1 | 1.485.144 | 0 |
28 | 268.435.456 | 5.715.545 | 5.715.543 | 1 | 2.857.841 | 1 | 2.857.703 | 0 |
29 | 536.870.912 | 11.013.467 | 11.013.465 | 1 | 5.507.187 | 1 | 5.506.279 | 0 |
30 | 1.073.741.824 | 21.253.182 | 21.253.180 | 1 | 10.627.035 | 1 | 10.626.146 | 0 |
31 | 2.147.483.648 | 41.060.268 | 41.060.266 | 1 | 20.529.810 | 1 | 20.530.457 | 0 |
32 | 4.294.967.296 | 79.416.950 | 79.416.948 | 1 | 39.710.040 | 1 | 39.706.909 | 0 |
33 | 8.589.934.592 | 153.773.607 | 153.773.605 | 1 | 76.886.890 | 1 | 76.886.716 | 0 |
34 | 17.179.869.184 | 298.045.327 | 298.045.325 | 1 | 149.028.269 | 1 | 149.017.057 | 0 |
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 | 3 | 0 | 3 | 1 | 0 | 2 | 0 |
3 | 8 | 6 | 1 | 5 | 2 | 1 | 2 | 1 |
4 | 16 | 9 | 2 | 7 | 4 | 1 | 2 | 2 |
5 | 32 | 18 | 7 | 11 | 5 | 3 | 5 | 5 |
6 | 64 | 29 | 13 | 16 | 9 | 7 | 7 | 6 |
7 | 128 | 65 | 30 | 35 | 17 | 13 | 19 | 16 |
8 | 256 | 142 | 65 | 77 | 36 | 35 | 36 | 35 |
9 | 512 | 299 | 136 | 163 | 73 | 77 | 80 | 69 |
10 | 1.024 | 608 | 281 | 327 | 145 | 152 | 163 | 148 |
11 | 2.048 | 1.239 | 565 | 674 | 292 | 318 | 321 | 308 |
12 | 4.096 | 2.514 | 1.157 | 1.357 | 610 | 653 | 636 | 615 |
13 | 8.192 | 5.072 | 2.325 | 2.747 | 1.232 | 1.243 | 1.311 | 1.286 |
14 | 16.384 | 10.263 | 4.722 | 5.541 | 2.558 | 2.494 | 2.600 | 2.611 |
15 | 32.768 | 20.587 | 9.562 | 11.025 | 5.168 | 5.067 | 5.192 | 5.160 |
16 | 65.536 | 41.481 | 19.354 | 22.127 | 10.415 | 10.200 | 10.615 | 10.251 |
17 | 131.072 | 83.557 | 39.235 | 44.322 | 21.111 | 20.590 | 21.188 | 20.668 |
18 | 262.144 | 167.993 | 79.264 | 88.729 | 42.408 | 41.483 | 42.395 | 41.707 |
19 | 524.288 | 337.601 | 159.952 | 177.649 | 85.160 | 83.438 | 85.112 | 83.891 |
20 | 1.048.576 | 677.802 | 322.671 | 355.131 | 171.050 | 167.822 | 170.904 | 168.026 |
21 | 2.097.152 | 1.360.423 | 649.646 | 710.777 | 343.454 | 337.047 | 342.714 | 337.208 |
22 | 4.194.304 | 2.729.166 | 1.305.975 | 1.423.191 | 688.667 | 676.514 | 687.132 | 676.853 |
23 | 8.388.608 | 5.474.177 | 2.626.203 | 2.847.974 | 1.379.393 | 1.358.201 | 1.377.884 | 1.358.699 |
24 | 16.777.216 | 10.977.423 | 5.275.870 | 5.701.553 | 2.764.891 | 2.724.511 | 2.764.519 | 2.723.502 |
25 | 33.554.432 | 22.006.833 | 10.595.587 | 11.411.246 | 5.541.696 | 5.463.787 | 5.541.170 | 5.460.180 |
26 | 67.108.864 | 44.112.272 | 21.278.616 | 22.833.656 | 11.104.589 | 10.953.157 | 11.104.744 | 10.949.782 |
27 | 134.217.728 | 88.406.084 | 42.711.465 | 45.694.619 | 22.250.930 | 21.957.611 | 22.245.246 | 21.952.297 |
28 | 268.435.456 | 177.153.066 | 85.707.788 | 91.445.278 | 44.582.139 | 44.004.316 | 44.564.873 | 44.001.738 |
29 | 536.870.912 | 354.931.076 | 171.934.302 | 182.996.774 | 89.302.210 | 88.171.800 | 89.281.211 | 88.175.855 |
30 | 1.073.741.824 | 711.018.425 | 344.835.305 | 366.183.120 | 178.850.895 | 176.664.125 | 178.827.833 | 176.675.572 |
31 | 2.147.483.648 | 1.424.213.703 | 691.513.705 | 732.699.998 | 358.175.723 | 353.938.203 | 358.149.238 | 353.950.539 |
32 | 4.294.967.296 | 2.852.521.638 | 1.386.455.670 | 1.466.065.968 | 717.235.686 | 709.027.160 | 717.221.529 | 709.037.263 |
33 | 8.589.934.592 | 5.712.677.579 | 2.779.217.435 | 2.933.460.144 | 1.436.159.333 | 1.420.173.176 | 1.436.137.790 | 1.420.207.280 |
34 | 17.179.869.184 | 11.439.733.190 | 5.570.342.568 | 5.869.390.622 | 2.875.480.934 | 2.844.394.086 | 2.875.450.943 | 2.844.407.227 |