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+11
f(0)=11
f(1)=3
f(2)=5
f(3)=1
f(4)=1
f(5)=1
f(6)=47
f(7)=1
f(8)=1
f(9)=23
f(10)=37
f(11)=1
f(12)=31
f(13)=1
f(14)=1
f(15)=59
f(16)=89
f(17)=1
f(18)=67
f(19)=1
f(20)=137
f(21)=113
f(22)=1
f(23)=1
f(24)=587
f(25)=53
f(26)=229
f(27)=1
f(28)=1
f(29)=71
f(30)=911
f(31)=1
f(32)=1
f(33)=1
f(34)=389
f(35)=103
f(36)=1307
f(37)=1
f(38)=97
f(39)=383
f(40)=179
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=509
f(46)=709
f(47)=1
f(48)=463
f(49)=1
f(50)=1
f(51)=653
f(52)=181
f(53)=1
f(54)=2927
f(55)=1
f(56)=1049
f(57)=163
f(58)=1
f(59)=1
f(60)=157
f(61)=311
f(62)=257
f(63)=199
f(64)=1
f(65)=353
f(66)=397
f(67)=1
f(68)=1
f(69)=1193
f(70)=1637
f(71)=421
f(72)=1039
f(73)=1
f(74)=1
f(75)=1409
f(76)=643
f(77)=1
f(78)=1
f(79)=521
f(80)=2137
f(81)=1
f(82)=449
f(83)=1
f(84)=191
f(85)=1
f(86)=823
f(87)=379
f(88)=1
f(89)=661
f(90)=8111
f(91)=691
f(92)=1
f(93)=433
f(94)=983
f(95)=251
f(96)=9227
f(97)=1
f(98)=641
f(99)=223
b) Substitution of the polynom
The polynom f(x)=x^2+11 could be written as f(y)= y^2+11 with x=y+0
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+0
f'(x)>2x-1 with x > 3
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 | 6 | 4 | 2 | 0.600000 | 0.400000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 58 | 17 | 41 | 0.580000 | 0.170000 | 0.580000 | 9.666667 | 4.250000 | 20.500000 |
3 | 1.000 | 617 | 99 | 518 | 0.617000 | 0.099000 | 0.617000 | 10.637931 | 5.823529 | 12.634147 |
4 | 10.000 | 6.425 | 670 | 5.755 | 0.642500 | 0.067000 | 0.642500 | 10.413290 | 6.767677 | 11.110039 |
5 | 100.000 | 65.352 | 5.049 | 60.303 | 0.653520 | 0.050490 | 0.653520 | 10.171517 | 7.535821 | 10.478367 |
6 | 1.000.000 | 660.508 | 41.197 | 619.311 | 0.660508 | 0.041197 | 0.660508 | 10.106929 | 8.159437 | 10.269986 |
7 | 10.000.000 | 6.650.735 | 348.045 | 6.302.690 | 0.665074 | 0.034805 | 0.665074 | 10.069121 | 8.448309 | 10.176939 |
8 | 100.000.000 | 66.855.521 | 3.002.291 | 63.853.230 | 0.668555 | 0.030023 | 0.668555 | 10.052351 | 8.626158 | 10.131108 |
9 | 1.000.000.000 | 671.233.865 | 26.416.479 | 644.817.386 | 0.671234 | 0.026416 | 0.671234 | 10.040067 | 8.798774 | 10.098431 |
10 | 10.000.000.000 | 6.733.965.726 | 235.944.295 | 6.498.021.431 | 0.673397 | 0.023594 | 0.673397 | 10.032220 | 8.931708 | 10.077305 |
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 | 3 | 2 | 1 | 0.750000 | 0.500000 | 0.250000 | 1.000000 | 1.000000 | 1.000000 |
3 | 8 | 4 | 3 | 1 | 0.500000 | 0.375000 | 0.125000 | 1.333333 | 1.500000 | 1.000000 |
4 | 16 | 9 | 5 | 4 | 0.562500 | 0.312500 | 0.250000 | 2.250000 | 1.666667 | 4.000000 |
5 | 32 | 17 | 8 | 9 | 0.531250 | 0.250000 | 0.281250 | 1.888889 | 1.600000 | 2.250000 |
6 | 64 | 35 | 13 | 22 | 0.546875 | 0.203125 | 0.343750 | 2.058824 | 1.625000 | 2.444444 |
7 | 128 | 75 | 21 | 54 | 0.585938 | 0.164062 | 0.421875 | 2.142857 | 1.615385 | 2.454545 |
8 | 256 | 151 | 34 | 117 | 0.589844 | 0.132812 | 0.457031 | 2.013333 | 1.619048 | 2.166667 |
9 | 512 | 310 | 58 | 252 | 0.605469 | 0.113281 | 0.492188 | 2.052980 | 1.705882 | 2.153846 |
10 | 1.024 | 634 | 102 | 532 | 0.619141 | 0.099609 | 0.519531 | 2.045161 | 1.758621 | 2.111111 |
11 | 2.048 | 1.290 | 175 | 1.115 | 0.629883 | 0.085449 | 0.544434 | 2.034700 | 1.715686 | 2.095865 |
12 | 4.096 | 2.613 | 308 | 2.305 | 0.637939 | 0.075195 | 0.562744 | 2.025581 | 1.760000 | 2.067265 |
13 | 8.192 | 5.262 | 568 | 4.694 | 0.642334 | 0.069336 | 0.572998 | 2.013777 | 1.844156 | 2.036443 |
14 | 16.384 | 10.562 | 1.020 | 9.542 | 0.644653 | 0.062256 | 0.582397 | 2.007222 | 1.795775 | 2.032808 |
15 | 32.768 | 21.270 | 1.892 | 19.378 | 0.649109 | 0.057739 | 0.591370 | 2.013823 | 1.854902 | 2.030811 |
16 | 65.536 | 42.755 | 3.435 | 39.320 | 0.652390 | 0.052414 | 0.599976 | 2.010108 | 1.815539 | 2.029105 |
17 | 131.072 | 85.800 | 6.484 | 79.316 | 0.654602 | 0.049469 | 0.605133 | 2.006783 | 1.887627 | 2.017192 |
18 | 262.144 | 172.233 | 12.179 | 160.054 | 0.657017 | 0.046459 | 0.610558 | 2.007378 | 1.878316 | 2.017928 |
19 | 524.288 | 345.420 | 22.819 | 322.601 | 0.658836 | 0.043524 | 0.615313 | 2.005539 | 1.873635 | 2.015576 |
20 | 1.048.576 | 692.728 | 43.065 | 649.663 | 0.660637 | 0.041070 | 0.619567 | 2.005466 | 1.887243 | 2.013828 |
21 | 2.097.152 | 1.388.446 | 81.606 | 1.306.840 | 0.662063 | 0.038913 | 0.623150 | 2.004316 | 1.894949 | 2.011566 |
22 | 4.194.304 | 2.782.989 | 154.979 | 2.628.010 | 0.663516 | 0.036950 | 0.626566 | 2.004391 | 1.899113 | 2.010965 |
23 | 8.388.608 | 5.576.429 | 295.402 | 5.281.027 | 0.664762 | 0.035215 | 0.629547 | 2.003755 | 1.906078 | 2.009516 |
24 | 16.777.216 | 11.173.388 | 563.455 | 10.609.933 | 0.665986 | 0.033585 | 0.632401 | 2.003682 | 1.907418 | 2.009066 |
25 | 33.554.432 | 22.381.823 | 1.076.821 | 21.305.002 | 0.667030 | 0.032092 | 0.634939 | 2.003137 | 1.911104 | 2.008024 |
26 | 67.108.864 | 44.831.249 | 2.063.436 | 42.767.813 | 0.668038 | 0.030748 | 0.637290 | 2.003020 | 1.916229 | 2.007407 |
27 | 134.217.728 | 89.782.581 | 3.960.821 | 85.821.760 | 0.668932 | 0.029510 | 0.639422 | 2.002679 | 1.919527 | 2.006691 |
28 | 268.435.456 | 179.788.326 | 7.611.968 | 172.176.358 | 0.669764 | 0.028357 | 0.641407 | 2.002486 | 1.921816 | 2.006209 |
29 | 536.870.912 | 360.008.037 | 14.657.519 | 345.350.518 | 0.670567 | 0.027302 | 0.643265 | 2.002399 | 1.925589 | 2.005795 |
30 | 1.073.741.824 | 720.809.310 | 28.259.307 | 692.550.003 | 0.671306 | 0.026319 | 0.644987 | 2.002203 | 1.927974 | 2.005354 |
31 | 2.147.483.648 | 1.443.119.756 | 54.560.914 | 1.388.558.842 | 0.672005 | 0.025407 | 0.646598 | 2.002083 | 1.930724 | 2.004994 |
32 | 4.294.967.296 | 2.889.031.793 | 105.469.218 | 2.783.562.575 | 0.672655 | 0.024556 | 0.648099 | 2.001935 | 1.933054 | 2.004641 |
33 | 8.589.934.592 | 5.783.325.930 | 204.113.422 | 5.579.212.508 | 0.673268 | 0.023762 | 0.649506 | 2.001822 | 1.935289 | 2.004342 |
34 | 17.179.869.184 | 11.576.511.240 | 395.407.261 | 11.181.103.979 | 0.673842 | 0.023016 | 0.650826 | 2.001705 | 1.937194 | 2.004065 |
35 | 34.359.738.368 | 23.171.747.480 | 766.771.730 | 22.404.975.750 | 0.674387 | 0.022316 | 0.652071 | 2.001617 | 1.939195 | 2.003825 |
36 | 68.719.476.736 | 46.378.831.930 | 1.488.285.120 | 44.890.546.810 | 0.674901 | 0.021657 | 0.653243 | 2.001525 | 1.940976 | 2.003597 |
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 | 0 | 2 | 0 | 0 |
2 | 4 | 2 | 0 | 1 | 0 | 2 | 0 | 0 |
3 | 8 | 3 | 0 | 2 | 0 | 2 | 0 | 1 |
4 | 16 | 5 | 0 | 4 | 0 | 3 | 0 | 2 |
5 | 32 | 8 | 0 | 7 | 1 | 4 | 0 | 3 |
6 | 64 | 13 | 0 | 12 | 1 | 5 | 2 | 5 |
7 | 128 | 21 | 0 | 20 | 3 | 8 | 2 | 8 |
8 | 256 | 34 | 0 | 33 | 3 | 13 | 4 | 14 |
9 | 512 | 58 | 0 | 57 | 8 | 21 | 6 | 23 |
10 | 1.024 | 102 | 0 | 101 | 14 | 38 | 12 | 38 |
11 | 2.048 | 175 | 0 | 174 | 25 | 71 | 22 | 57 |
12 | 4.096 | 308 | 0 | 307 | 45 | 123 | 39 | 101 |
13 | 8.192 | 568 | 0 | 567 | 79 | 215 | 73 | 201 |
14 | 16.384 | 1.020 | 0 | 1.019 | 125 | 381 | 129 | 385 |
15 | 32.768 | 1.892 | 0 | 1.891 | 242 | 699 | 235 | 716 |
16 | 65.536 | 3.435 | 0 | 3.434 | 437 | 1.288 | 437 | 1.273 |
17 | 131.072 | 6.484 | 0 | 6.483 | 818 | 2.429 | 845 | 2.392 |
18 | 262.144 | 12.179 | 0 | 12.178 | 1.549 | 4.561 | 1.571 | 4.498 |
19 | 524.288 | 22.819 | 0 | 22.818 | 2.904 | 8.567 | 2.951 | 8.397 |
20 | 1.048.576 | 43.065 | 0 | 43.064 | 5.512 | 16.139 | 5.549 | 15.865 |
21 | 2.097.152 | 81.606 | 0 | 81.605 | 10.492 | 30.479 | 10.512 | 30.123 |
22 | 4.194.304 | 154.979 | 0 | 154.978 | 19.805 | 57.870 | 19.857 | 57.447 |
23 | 8.388.608 | 295.402 | 0 | 295.401 | 37.739 | 110.118 | 37.968 | 109.577 |
24 | 16.777.216 | 563.455 | 0 | 563.454 | 72.051 | 209.651 | 72.219 | 209.534 |
25 | 33.554.432 | 1.076.821 | 0 | 1.076.820 | 137.892 | 400.789 | 137.616 | 400.524 |
26 | 67.108.864 | 2.063.436 | 0 | 2.063.435 | 263.607 | 767.711 | 263.278 | 768.840 |
27 | 134.217.728 | 3.960.821 | 0 | 3.960.820 | 505.602 | 1.474.176 | 504.682 | 1.476.361 |
28 | 268.435.456 | 7.611.968 | 0 | 7.611.967 | 971.205 | 2.834.775 | 969.150 | 2.836.838 |
29 | 536.870.912 | 14.657.519 | 0 | 14.657.518 | 1.866.255 | 5.460.689 | 1.864.390 | 5.466.185 |
30 | 1.073.741.824 | 28.259.307 | 0 | 28.259.306 | 3.596.490 | 10.530.889 | 3.594.051 | 10.537.877 |
31 | 2.147.483.648 | 54.560.914 | 0 | 54.560.913 | 6.940.300 | 20.339.407 | 6.936.493 | 20.344.714 |
32 | 4.294.967.296 | 105.469.218 | 0 | 105.469.217 | 13.407.681 | 39.329.897 | 13.400.929 | 39.330.711 |
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 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
4 | 16 | 4 | 2 | 2 | 1 | 0 | 2 | 1 |
5 | 32 | 9 | 4 | 5 | 2 | 1 | 4 | 2 |
6 | 64 | 22 | 12 | 10 | 5 | 3 | 8 | 6 |
7 | 128 | 54 | 30 | 24 | 13 | 10 | 16 | 15 |
8 | 256 | 117 | 67 | 50 | 28 | 25 | 34 | 30 |
9 | 512 | 252 | 137 | 115 | 58 | 61 | 79 | 54 |
10 | 1.024 | 532 | 290 | 242 | 128 | 133 | 156 | 115 |
11 | 2.048 | 1.115 | 602 | 513 | 283 | 265 | 314 | 253 |
12 | 4.096 | 2.305 | 1.237 | 1.068 | 608 | 531 | 620 | 546 |
13 | 8.192 | 4.694 | 2.520 | 2.174 | 1.235 | 1.106 | 1.229 | 1.124 |
14 | 16.384 | 9.542 | 5.084 | 4.458 | 2.516 | 2.247 | 2.498 | 2.281 |
15 | 32.768 | 19.378 | 10.278 | 9.100 | 5.057 | 4.597 | 5.107 | 4.617 |
16 | 65.536 | 39.320 | 20.691 | 18.629 | 10.299 | 9.395 | 10.223 | 9.403 |
17 | 131.072 | 79.316 | 41.570 | 37.746 | 20.728 | 18.963 | 20.627 | 18.998 |
18 | 262.144 | 160.054 | 83.550 | 76.504 | 41.700 | 38.423 | 41.492 | 38.439 |
19 | 524.288 | 322.601 | 167.757 | 154.844 | 83.624 | 77.809 | 83.417 | 77.751 |
20 | 1.048.576 | 649.663 | 337.220 | 312.443 | 167.963 | 156.962 | 167.871 | 156.867 |
21 | 2.097.152 | 1.306.840 | 677.042 | 629.798 | 337.250 | 316.440 | 336.617 | 316.533 |
22 | 4.194.304 | 2.628.010 | 1.358.345 | 1.269.665 | 676.397 | 637.403 | 676.297 | 637.913 |
23 | 8.388.608 | 5.281.027 | 2.724.361 | 2.556.666 | 1.358.117 | 1.283.436 | 1.357.237 | 1.282.237 |
24 | 16.777.216 | 10.609.933 | 5.465.194 | 5.144.739 | 2.723.350 | 2.582.476 | 2.723.209 | 2.580.898 |
25 | 33.554.432 | 21.305.002 | 10.961.612 | 10.343.390 | 5.461.292 | 5.192.516 | 5.462.997 | 5.188.197 |
26 | 67.108.864 | 42.767.813 | 21.975.182 | 20.792.631 | 10.950.775 | 10.435.786 | 10.952.962 | 10.428.290 |
27 | 134.217.728 | 85.821.760 | 44.036.560 | 41.785.200 | 21.952.451 | 20.964.546 | 21.955.188 | 20.949.575 |
28 | 268.435.456 | 172.176.358 | 88.251.512 | 83.924.846 | 44.003.852 | 42.090.828 | 43.997.715 | 42.083.963 |
29 | 536.870.912 | 345.350.518 | 176.847.438 | 168.503.080 | 88.174.131 | 84.503.416 | 88.182.802 | 84.490.169 |
30 | 1.073.741.824 | 692.550.003 | 354.293.678 | 338.256.325 | 176.690.787 | 169.594.980 | 176.689.000 | 169.575.236 |
31 | 2.147.483.648 | 1.388.558.842 | 709.746.701 | 678.812.141 | 353.982.707 | 340.286.801 | 354.022.988 | 340.266.346 |
32 | 4.294.967.296 | 2.783.562.575 | 1.421.664.018 | 1.361.898.557 | 709.140.486 | 682.634.341 | 709.182.729 | 682.605.019 |
33 | 8.589.934.592 | 5.579.212.508 | 2.847.370.729 | 2.731.841.779 | 1.420.438.147 | 1.369.129.372 | 1.420.526.797 | 1.369.118.192 |
34 | 17.179.869.184 | 11.181.103.979 | 5.702.292.565 | 5.478.811.414 | 2.845.022.508 | 2.745.549.349 | 2.845.065.198 | 2.745.466.924 |
35 | 34.359.738.368 | 22.404.975.750 | 11.418.930.922 | 10.986.044.828 | 5.697.760.933 | 5.504.861.823 | 5.697.697.804 | 5.504.655.190 |
36 | 68.719.476.736 | 44.890.546.810 | 22.864.979.002 | 22.025.567.808 | 11.409.966.003 | 11.035.396.726 | 11.409.917.697 | 11.035.266.384 |