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+136x+23
f(0)=23
f(1)=5
f(2)=13
f(3)=11
f(4)=53
f(5)=7
f(6)=1
f(7)=1
f(8)=47
f(9)=83
f(10)=1483
f(11)=41
f(12)=257
f(13)=1
f(14)=193
f(15)=1
f(16)=491
f(17)=1
f(18)=43
f(19)=1
f(20)=449
f(21)=1
f(22)=3499
f(23)=1
f(24)=3863
f(25)=1
f(26)=1
f(27)=79
f(28)=71
f(29)=601
f(30)=5003
f(31)=1
f(32)=5399
f(33)=1
f(34)=829
f(35)=751
f(36)=113
f(37)=73
f(38)=1327
f(39)=107
f(40)=1009
f(41)=1
f(42)=7499
f(43)=1
f(44)=1
f(45)=1021
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=9323
f(51)=239
f(52)=1
f(53)=251
f(54)=1
f(55)=1
f(56)=431
f(57)=1
f(58)=1
f(59)=131
f(60)=11783
f(61)=1
f(62)=1
f(63)=157
f(64)=12823
f(65)=409
f(66)=2671
f(67)=1
f(68)=397
f(69)=1
f(70)=101
f(71)=1
f(72)=283
f(73)=191
f(74)=197
f(75)=1
f(76)=461
f(77)=2053
f(78)=3343
f(79)=1063
f(80)=1
f(81)=1
f(82)=2557
f(83)=1
f(84)=18503
f(85)=2351
f(86)=3823
f(87)=607
f(88)=3947
f(89)=179
f(90)=2909
f(91)=1
f(92)=1
f(93)=1
f(94)=941
f(95)=1373
f(96)=1
f(97)=1
f(98)=4591
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+136x+23 could be written as f(y)= y^2-4601 with x=y-68
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+68
f'(x)>2x+135
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 | 59 | 13 | 46 | 0.590000 | 0.130000 | 0.590000 | 7.375000 | 6.500000 | 7.666667 |
3 | 1.000 | 577 | 84 | 493 | 0.577000 | 0.084000 | 0.577000 | 9.779661 | 6.461538 | 10.717391 |
4 | 10.000 | 6.039 | 567 | 5.472 | 0.603900 | 0.056700 | 0.603900 | 10.466205 | 6.750000 | 11.099392 |
5 | 100.000 | 62.383 | 4.351 | 58.032 | 0.623830 | 0.043510 | 0.623830 | 10.330022 | 7.673721 | 10.605263 |
6 | 1.000.000 | 636.292 | 35.919 | 600.373 | 0.636292 | 0.035919 | 0.636292 | 10.199766 | 8.255343 | 10.345551 |
7 | 10.000.000 | 6.447.934 | 303.611 | 6.144.323 | 0.644793 | 0.030361 | 0.644793 | 10.133609 | 8.452658 | 10.234176 |
8 | 100.000.000 | 65.110.026 | 2.627.882 | 62.482.144 | 0.651100 | 0.026279 | 0.651100 | 10.097812 | 8.655424 | 10.169086 |
9 | 1.000.000.000 | 655.913.905 | 23.189.823 | 632.724.082 | 0.655914 | 0.023190 | 0.655914 | 10.073932 | 8.824531 | 10.126478 |
10 | 10.000.000.000 | 6.597.446.811 | 207.531.144 | 6.389.915.667 | 0.659745 | 0.020753 | 0.659745 | 10.058403 | 8.949233 | 10.099055 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 1 | 4 | 1.250000 | 0.250000 | 1.000000 | 1.666667 | 1.000000 | 2.000000 |
3 | 8 | 6 | 1 | 5 | 0.750000 | 0.125000 | 0.625000 | 1.200000 | 1.000000 | 1.250000 |
4 | 16 | 12 | 2 | 10 | 0.750000 | 0.125000 | 0.625000 | 2.000000 | 2.000000 | 2.000000 |
5 | 32 | 21 | 7 | 14 | 0.656250 | 0.218750 | 0.437500 | 1.750000 | 3.500000 | 1.400000 |
6 | 64 | 37 | 11 | 26 | 0.578125 | 0.171875 | 0.406250 | 1.761905 | 1.571429 | 1.857143 |
7 | 128 | 74 | 14 | 60 | 0.578125 | 0.109375 | 0.468750 | 2.000000 | 1.272727 | 2.307692 |
8 | 256 | 145 | 28 | 117 | 0.566406 | 0.109375 | 0.457031 | 1.959459 | 2.000000 | 1.950000 |
9 | 512 | 292 | 50 | 242 | 0.570312 | 0.097656 | 0.472656 | 2.013793 | 1.785714 | 2.068376 |
10 | 1.024 | 590 | 85 | 505 | 0.576172 | 0.083008 | 0.493164 | 2.020548 | 1.700000 | 2.086777 |
11 | 2.048 | 1.196 | 156 | 1.040 | 0.583984 | 0.076172 | 0.507812 | 2.027119 | 1.835294 | 2.059406 |
12 | 4.096 | 2.434 | 270 | 2.164 | 0.594238 | 0.065918 | 0.528320 | 2.035117 | 1.730769 | 2.080769 |
13 | 8.192 | 4.931 | 474 | 4.457 | 0.601929 | 0.057861 | 0.544067 | 2.025883 | 1.755556 | 2.059612 |
14 | 16.384 | 10.000 | 867 | 9.133 | 0.610352 | 0.052917 | 0.557434 | 2.027986 | 1.829114 | 2.049136 |
15 | 32.768 | 20.176 | 1.604 | 18.572 | 0.615723 | 0.048950 | 0.566772 | 2.017600 | 1.850058 | 2.033505 |
16 | 65.536 | 40.652 | 2.995 | 37.657 | 0.620300 | 0.045700 | 0.574600 | 2.014869 | 1.867207 | 2.027622 |
17 | 131.072 | 82.050 | 5.601 | 76.449 | 0.625992 | 0.042732 | 0.583260 | 2.018351 | 1.870117 | 2.030140 |
18 | 262.144 | 165.035 | 10.615 | 154.420 | 0.629559 | 0.040493 | 0.589066 | 2.011395 | 1.895197 | 2.019909 |
19 | 524.288 | 332.077 | 19.849 | 312.228 | 0.633387 | 0.037859 | 0.595528 | 2.012161 | 1.869901 | 2.021940 |
20 | 1.048.576 | 667.404 | 37.460 | 629.944 | 0.636486 | 0.035725 | 0.600761 | 2.009787 | 1.887249 | 2.017577 |
21 | 2.097.152 | 1.340.776 | 71.231 | 1.269.545 | 0.639332 | 0.033966 | 0.605366 | 2.008942 | 1.901522 | 2.015330 |
22 | 4.194.304 | 2.692.276 | 135.378 | 2.556.898 | 0.641889 | 0.032277 | 0.609612 | 2.007998 | 1.900549 | 2.014027 |
23 | 8.388.608 | 5.404.452 | 257.596 | 5.146.856 | 0.644261 | 0.030708 | 0.613553 | 2.007391 | 1.902791 | 2.012930 |
24 | 16.777.216 | 10.844.076 | 492.198 | 10.351.878 | 0.646357 | 0.029337 | 0.617020 | 2.006508 | 1.910736 | 2.011301 |
25 | 33.554.432 | 21.753.750 | 941.237 | 20.812.513 | 0.648312 | 0.028051 | 0.620261 | 2.006049 | 1.912314 | 2.010506 |
26 | 67.108.864 | 43.630.096 | 1.805.658 | 41.824.438 | 0.650139 | 0.026906 | 0.623233 | 2.005636 | 1.918388 | 2.009582 |
27 | 134.217.728 | 87.482.101 | 3.468.556 | 84.013.545 | 0.651792 | 0.025843 | 0.625950 | 2.005086 | 1.920937 | 2.008719 |
28 | 268.435.456 | 175.371.459 | 6.672.927 | 168.698.532 | 0.653310 | 0.024859 | 0.628451 | 2.004655 | 1.923834 | 2.007992 |
29 | 536.870.912 | 351.502.751 | 12.856.735 | 338.646.016 | 0.654725 | 0.023948 | 0.630777 | 2.004333 | 1.926701 | 2.007404 |
30 | 1.073.741.824 | 704.423.289 | 24.808.875 | 679.614.414 | 0.656045 | 0.023105 | 0.632940 | 2.004034 | 1.929640 | 2.006858 |
31 | 2.147.483.648 | 1.411.493.707 | 47.933.594 | 1.363.560.113 | 0.657278 | 0.022321 | 0.634957 | 2.003758 | 1.932115 | 2.006373 |
32 | 4.294.967.296 | 2.827.953.324 | 92.708.455 | 2.735.244.869 | 0.658434 | 0.021585 | 0.636849 | 2.003518 | 1.934102 | 2.005958 |
33 | 8.589.934.592 | 5.665.194.836 | 179.515.583 | 5.485.679.253 | 0.659516 | 0.020898 | 0.638617 | 2.003284 | 1.936345 | 2.005553 |
34 | 17.179.869.184 | 11.347.844.465 | 347.941.493 | 10.999.902.972 | 0.660531 | 0.020253 | 0.640279 | 2.003081 | 1.938225 | 2.005203 |
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 | 0 | 1 |
2 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
3 | 8 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
4 | 16 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
5 | 32 | 7 | 2 | 5 | 0 | 4 | 0 | 3 |
6 | 64 | 11 | 3 | 8 | 0 | 6 | 0 | 5 |
7 | 128 | 14 | 5 | 9 | 0 | 6 | 0 | 8 |
8 | 256 | 28 | 10 | 18 | 0 | 15 | 0 | 13 |
9 | 512 | 50 | 18 | 32 | 0 | 28 | 0 | 22 |
10 | 1.024 | 85 | 30 | 55 | 0 | 44 | 0 | 41 |
11 | 2.048 | 156 | 53 | 103 | 0 | 82 | 0 | 74 |
12 | 4.096 | 270 | 87 | 183 | 0 | 135 | 0 | 135 |
13 | 8.192 | 474 | 153 | 321 | 0 | 237 | 0 | 237 |
14 | 16.384 | 867 | 286 | 581 | 0 | 423 | 0 | 444 |
15 | 32.768 | 1.604 | 529 | 1.075 | 0 | 787 | 0 | 817 |
16 | 65.536 | 2.995 | 982 | 2.013 | 0 | 1.478 | 0 | 1.517 |
17 | 131.072 | 5.601 | 1.846 | 3.755 | 0 | 2.777 | 0 | 2.824 |
18 | 262.144 | 10.615 | 3.535 | 7.080 | 0 | 5.316 | 0 | 5.299 |
19 | 524.288 | 19.849 | 6.670 | 13.179 | 0 | 9.901 | 0 | 9.948 |
20 | 1.048.576 | 37.460 | 12.480 | 24.980 | 0 | 18.762 | 0 | 18.698 |
21 | 2.097.152 | 71.231 | 23.791 | 47.440 | 0 | 35.664 | 0 | 35.567 |
22 | 4.194.304 | 135.378 | 45.311 | 90.067 | 0 | 67.768 | 0 | 67.610 |
23 | 8.388.608 | 257.596 | 85.975 | 171.621 | 0 | 129.116 | 0 | 128.480 |
24 | 16.777.216 | 492.198 | 164.410 | 327.788 | 0 | 246.631 | 0 | 245.567 |
25 | 33.554.432 | 941.237 | 313.436 | 627.801 | 0 | 470.602 | 0 | 470.635 |
26 | 67.108.864 | 1.805.658 | 601.442 | 1.204.216 | 0 | 902.711 | 0 | 902.947 |
27 | 134.217.728 | 3.468.556 | 1.155.064 | 2.313.492 | 0 | 1.734.928 | 0 | 1.733.628 |
28 | 268.435.456 | 6.672.927 | 2.222.989 | 4.449.938 | 0 | 3.337.072 | 0 | 3.335.855 |
29 | 536.870.912 | 12.856.735 | 4.284.586 | 8.572.149 | 0 | 6.429.867 | 0 | 6.426.868 |
30 | 1.073.741.824 | 24.808.875 | 8.268.988 | 16.539.887 | 0 | 12.405.559 | 0 | 12.403.316 |
31 | 2.147.483.648 | 47.933.594 | 15.974.337 | 31.959.257 | 0 | 23.969.351 | 0 | 23.964.243 |
32 | 4.294.967.296 | 92.708.455 | 30.896.150 | 61.812.305 | 0 | 46.356.314 | 0 | 46.352.141 |
33 | 8.589.934.592 | 179.515.583 | 59.830.168 | 119.685.415 | 0 | 89.760.147 | 0 | 89.755.436 |
34 | 17.179.869.184 | 347.941.493 | 115.967.337 | 231.974.156 | 0 | 173.968.245 | 0 | 173.973.248 |
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 | 1 | 0 | 0 | 2 | 0 |
2 | 4 | 4 | 1 | 3 | 0 | 1 | 3 | 0 |
3 | 8 | 5 | 1 | 4 | 0 | 1 | 3 | 1 |
4 | 16 | 10 | 2 | 8 | 3 | 3 | 3 | 1 |
5 | 32 | 14 | 4 | 10 | 5 | 3 | 3 | 3 |
6 | 64 | 26 | 10 | 16 | 7 | 6 | 6 | 7 |
7 | 128 | 60 | 28 | 32 | 12 | 12 | 17 | 19 |
8 | 256 | 117 | 58 | 59 | 27 | 29 | 30 | 31 |
9 | 512 | 242 | 121 | 121 | 59 | 57 | 63 | 63 |
10 | 1.024 | 505 | 247 | 258 | 114 | 127 | 136 | 128 |
11 | 2.048 | 1.040 | 529 | 511 | 247 | 259 | 280 | 254 |
12 | 4.096 | 2.164 | 1.091 | 1.073 | 518 | 555 | 554 | 537 |
13 | 8.192 | 4.457 | 2.263 | 2.194 | 1.117 | 1.138 | 1.095 | 1.107 |
14 | 16.384 | 9.133 | 4.642 | 4.491 | 2.275 | 2.324 | 2.243 | 2.291 |
15 | 32.768 | 18.572 | 9.430 | 9.142 | 4.609 | 4.706 | 4.618 | 4.639 |
16 | 65.536 | 37.657 | 19.081 | 18.576 | 9.310 | 9.477 | 9.451 | 9.419 |
17 | 131.072 | 76.449 | 38.714 | 37.735 | 19.022 | 19.202 | 19.099 | 19.126 |
18 | 262.144 | 154.420 | 78.356 | 76.064 | 38.444 | 38.772 | 38.617 | 38.587 |
19 | 524.288 | 312.228 | 158.159 | 154.069 | 77.825 | 78.043 | 78.240 | 78.120 |
20 | 1.048.576 | 629.944 | 318.841 | 311.103 | 157.508 | 157.767 | 157.041 | 157.628 |
21 | 2.097.152 | 1.269.545 | 642.426 | 627.119 | 316.925 | 317.822 | 316.911 | 317.887 |
22 | 4.194.304 | 2.556.898 | 1.292.030 | 1.264.868 | 638.311 | 640.065 | 639.010 | 639.512 |
23 | 8.388.608 | 5.146.856 | 2.600.783 | 2.546.073 | 1.285.601 | 1.286.933 | 1.285.998 | 1.288.324 |
24 | 16.777.216 | 10.351.878 | 5.227.730 | 5.124.148 | 2.585.616 | 2.589.306 | 2.585.876 | 2.591.080 |
25 | 33.554.432 | 20.812.513 | 10.507.098 | 10.305.415 | 5.198.700 | 5.204.358 | 5.199.959 | 5.209.496 |
26 | 67.108.864 | 41.824.438 | 21.105.915 | 20.718.523 | 10.450.320 | 10.459.591 | 10.450.282 | 10.464.245 |
27 | 134.217.728 | 84.013.545 | 42.382.415 | 41.631.130 | 20.986.840 | 21.016.528 | 20.996.136 | 21.014.041 |
28 | 268.435.456 | 168.698.532 | 85.069.125 | 83.629.407 | 42.142.568 | 42.205.047 | 42.155.137 | 42.195.780 |
29 | 536.870.912 | 338.646.016 | 170.703.405 | 167.942.611 | 84.604.117 | 84.715.018 | 84.612.842 | 84.714.039 |
30 | 1.073.741.824 | 679.614.414 | 342.459.456 | 337.154.958 | 169.797.807 | 170.008.965 | 169.797.853 | 170.009.789 |
31 | 2.147.483.648 | 1.363.560.113 | 686.909.480 | 676.650.633 | 340.687.460 | 341.099.522 | 340.687.672 | 341.085.459 |
32 | 4.294.967.296 | 2.735.244.869 | 1.377.509.818 | 1.357.735.051 | 683.416.249 | 684.229.213 | 683.384.500 | 684.214.907 |
33 | 8.589.934.592 | 5.485.679.253 | 2.762.031.455 | 2.723.647.798 | 1.370.628.289 | 1.372.238.952 | 1.370.594.246 | 1.372.217.766 |
34 | 17.179.869.184 | 10.999.902.972 | 5.537.083.659 | 5.462.819.313 | 2.748.446.709 | 2.751.552.094 | 2.748.372.364 | 2.751.531.805 |