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-38x+59
f(0)=59
f(1)=11
f(2)=13
f(3)=23
f(4)=7
f(5)=53
f(6)=19
f(7)=79
f(8)=181
f(9)=101
f(10)=17
f(11)=1
f(12)=1
f(13)=1
f(14)=277
f(15)=1
f(16)=293
f(17)=149
f(18)=43
f(19)=151
f(20)=1
f(21)=1
f(22)=1
f(23)=1
f(24)=1
f(25)=1
f(26)=1
f(27)=1
f(28)=1
f(29)=1
f(30)=1
f(31)=1
f(32)=1
f(33)=1
f(34)=1
f(35)=1
f(36)=1
f(37)=1
f(38)=1
f(39)=1
f(40)=139
f(41)=1
f(42)=227
f(43)=137
f(44)=1
f(45)=1
f(46)=61
f(47)=241
f(48)=1
f(49)=1
f(50)=659
f(51)=1
f(52)=787
f(53)=1
f(54)=71
f(55)=1
f(56)=97
f(57)=571
f(58)=1
f(59)=1
f(60)=197
f(61)=1
f(62)=1
f(63)=1
f(64)=1723
f(65)=907
f(66)=1907
f(67)=1
f(68)=2099
f(69)=157
f(70)=1
f(71)=1201
f(72)=109
f(73)=1307
f(74)=389
f(75)=1
f(76)=421
f(77)=1531
f(78)=1
f(79)=1
f(80)=263
f(81)=1
f(82)=193
f(83)=271
f(84)=3923
f(85)=2027
f(86)=1
f(87)=2161
f(88)=1
f(89)=1
f(90)=677
f(91)=2441
f(92)=457
f(93)=199
f(94)=5323
f(95)=1
f(96)=331
f(97)=1
f(98)=5939
f(99)=3049
b) Substitution of the polynom
The polynom f(x)=x^2-38x+59 could be written as f(y)= y^2-302 with x=y+19
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-19
f'(x)>2x-39 with x > 17
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 | 8 | 1 | 0.900000 | 0.800000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 47 | 33 | 14 | 0.470000 | 0.330000 | 0.470000 | 5.222222 | 4.125000 | 14.000000 |
3 | 1.000 | 633 | 223 | 410 | 0.633000 | 0.223000 | 0.633000 | 13.468085 | 6.757576 | 29.285715 |
4 | 10.000 | 6.745 | 1.551 | 5.194 | 0.674500 | 0.155100 | 0.674500 | 10.655608 | 6.955157 | 12.668293 |
5 | 100.000 | 68.011 | 11.836 | 56.175 | 0.680110 | 0.118360 | 0.680110 | 10.083173 | 7.631206 | 10.815364 |
6 | 1.000.000 | 682.390 | 96.610 | 585.780 | 0.682390 | 0.096610 | 0.682390 | 10.033524 | 8.162386 | 10.427771 |
7 | 10.000.000 | 6.840.910 | 815.307 | 6.025.603 | 0.684091 | 0.081531 | 0.684091 | 10.024927 | 8.439157 | 10.286461 |
8 | 100.000.000 | 68.510.516 | 7.052.879 | 61.457.637 | 0.685105 | 0.070529 | 0.685105 | 10.014824 | 8.650580 | 10.199417 |
9 | 1.000.000.000 | 685.913.004 | 62.172.952 | 623.740.052 | 0.685913 | 0.062173 | 0.685913 | 10.011792 | 8.815259 | 10.149105 |
10 | 10.000.000.000 | 6.865.898.575 | 555.880.092 | 6.310.018.483 | 0.686590 | 0.055588 | 0.686590 | 10.009868 | 8.940866 | 10.116424 |
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 | 3 | 0 | 1.500000 | 1.500000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 4 | 4 | 0 | 1.000000 | 1.000000 | 0.000000 | 1.333333 | 1.333333 | -nan |
3 | 8 | 8 | 7 | 1 | 1.000000 | 0.875000 | 0.125000 | 2.000000 | 1.750000 | inf |
4 | 16 | 11 | 10 | 1 | 0.687500 | 0.625000 | 0.062500 | 1.375000 | 1.428571 | 1.000000 |
5 | 32 | 14 | 12 | 2 | 0.437500 | 0.375000 | 0.062500 | 1.272727 | 1.200000 | 2.000000 |
6 | 64 | 23 | 20 | 3 | 0.359375 | 0.312500 | 0.046875 | 1.642857 | 1.666667 | 1.500000 |
7 | 128 | 64 | 39 | 25 | 0.500000 | 0.304688 | 0.195312 | 2.782609 | 1.950000 | 8.333333 |
8 | 256 | 145 | 71 | 74 | 0.566406 | 0.277344 | 0.289062 | 2.265625 | 1.820513 | 2.960000 |
9 | 512 | 310 | 122 | 188 | 0.605469 | 0.238281 | 0.367188 | 2.137931 | 1.718310 | 2.540540 |
10 | 1.024 | 649 | 228 | 421 | 0.633789 | 0.222656 | 0.411133 | 2.093548 | 1.868852 | 2.239362 |
11 | 2.048 | 1.341 | 398 | 943 | 0.654785 | 0.194336 | 0.460449 | 2.066256 | 1.745614 | 2.239905 |
12 | 4.096 | 2.736 | 727 | 2.009 | 0.667969 | 0.177490 | 0.490479 | 2.040268 | 1.826633 | 2.130435 |
13 | 8.192 | 5.531 | 1.310 | 4.221 | 0.675171 | 0.159912 | 0.515259 | 2.021564 | 1.801926 | 2.101045 |
14 | 16.384 | 11.102 | 2.409 | 8.693 | 0.677612 | 0.147034 | 0.530579 | 2.007232 | 1.838931 | 2.059465 |
15 | 32.768 | 22.215 | 4.394 | 17.821 | 0.677948 | 0.134094 | 0.543854 | 2.000991 | 1.823993 | 2.050040 |
16 | 65.536 | 44.524 | 8.096 | 36.428 | 0.679382 | 0.123535 | 0.555847 | 2.004231 | 1.842512 | 2.044105 |
17 | 131.072 | 89.157 | 15.129 | 74.028 | 0.680214 | 0.115425 | 0.564789 | 2.002448 | 1.868701 | 2.032173 |
18 | 262.144 | 178.605 | 28.358 | 150.247 | 0.681324 | 0.108177 | 0.573147 | 2.003264 | 1.874413 | 2.029597 |
19 | 524.288 | 357.470 | 53.504 | 303.966 | 0.681820 | 0.102051 | 0.579769 | 2.001456 | 1.886734 | 2.023109 |
20 | 1.048.576 | 715.631 | 100.987 | 614.644 | 0.682479 | 0.096309 | 0.586170 | 2.001933 | 1.887466 | 2.022081 |
21 | 2.097.152 | 1.432.605 | 191.352 | 1.241.253 | 0.683119 | 0.091244 | 0.591876 | 2.001877 | 1.894818 | 2.019467 |
22 | 4.194.304 | 2.867.141 | 363.013 | 2.504.128 | 0.683580 | 0.086549 | 0.597031 | 2.001348 | 1.897095 | 2.017420 |
23 | 8.388.608 | 5.737.814 | 692.172 | 5.045.642 | 0.684001 | 0.082513 | 0.601487 | 2.001232 | 1.906742 | 2.014930 |
24 | 16.777.216 | 11.481.373 | 1.321.265 | 10.160.108 | 0.684343 | 0.078754 | 0.605590 | 2.001001 | 1.908868 | 2.013640 |
25 | 33.554.432 | 22.973.644 | 2.528.023 | 20.445.621 | 0.684668 | 0.075341 | 0.609327 | 2.000949 | 1.913335 | 2.012343 |
26 | 67.108.864 | 45.965.641 | 4.846.474 | 41.119.167 | 0.684941 | 0.072218 | 0.612723 | 2.000799 | 1.917100 | 2.011148 |
27 | 134.217.728 | 91.967.315 | 9.304.979 | 82.662.336 | 0.685210 | 0.069327 | 0.615882 | 2.000784 | 1.919948 | 2.010312 |
28 | 268.435.456 | 184.001.578 | 17.897.881 | 166.103.697 | 0.685459 | 0.066675 | 0.618784 | 2.000728 | 1.923473 | 2.009424 |
29 | 536.870.912 | 368.134.542 | 34.484.487 | 333.650.055 | 0.685704 | 0.064232 | 0.621472 | 2.000714 | 1.926736 | 2.008685 |
30 | 1.073.741.824 | 736.524.761 | 66.512.508 | 670.012.253 | 0.685942 | 0.061945 | 0.623998 | 2.000695 | 1.928766 | 2.008129 |
31 | 2.147.483.648 | 1.473.515.124 | 128.458.239 | 1.345.056.885 | 0.686159 | 0.059818 | 0.626341 | 2.000632 | 1.931340 | 2.007511 |
32 | 4.294.967.296 | 2.947.885.574 | 248.395.963 | 2.699.489.611 | 0.686358 | 0.057834 | 0.628524 | 2.000581 | 1.933671 | 2.006970 |
33 | 8.589.934.592 | 5.897.411.482 | 480.857.174 | 5.416.554.308 | 0.686549 | 0.055979 | 0.630570 | 2.000556 | 1.935849 | 2.006511 |
34 | 17.179.869.184 | 11.797.920.032 | 931.779.755 | 10.866.140.277 | 0.686729 | 0.054237 | 0.632493 | 2.000525 | 1.937747 | 2.006098 |
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 | 3 | 1 | 2 | 0 | 2 | 1 | 0 |
2 | 4 | 4 | 1 | 3 | 0 | 2 | 1 | 1 |
3 | 8 | 7 | 3 | 4 | 0 | 2 | 3 | 2 |
4 | 16 | 10 | 4 | 6 | 0 | 2 | 6 | 2 |
5 | 32 | 12 | 5 | 7 | 0 | 2 | 7 | 3 |
6 | 64 | 20 | 10 | 10 | 2 | 8 | 7 | 3 |
7 | 128 | 39 | 19 | 20 | 7 | 22 | 7 | 3 |
8 | 256 | 71 | 38 | 33 | 16 | 45 | 7 | 3 |
9 | 512 | 122 | 62 | 60 | 24 | 88 | 7 | 3 |
10 | 1.024 | 228 | 116 | 112 | 53 | 165 | 7 | 3 |
11 | 2.048 | 398 | 205 | 193 | 98 | 290 | 7 | 3 |
12 | 4.096 | 727 | 363 | 364 | 170 | 547 | 7 | 3 |
13 | 8.192 | 1.310 | 659 | 651 | 328 | 972 | 7 | 3 |
14 | 16.384 | 2.409 | 1.195 | 1.214 | 602 | 1.797 | 7 | 3 |
15 | 32.768 | 4.394 | 2.185 | 2.209 | 1.099 | 3.285 | 7 | 3 |
16 | 65.536 | 8.096 | 4.032 | 4.064 | 2.050 | 6.036 | 7 | 3 |
17 | 131.072 | 15.129 | 7.571 | 7.558 | 3.821 | 11.298 | 7 | 3 |
18 | 262.144 | 28.358 | 14.311 | 14.047 | 7.174 | 21.174 | 7 | 3 |
19 | 524.288 | 53.504 | 27.017 | 26.487 | 13.571 | 39.923 | 7 | 3 |
20 | 1.048.576 | 100.987 | 50.879 | 50.108 | 25.657 | 75.320 | 7 | 3 |
21 | 2.097.152 | 191.352 | 96.291 | 95.061 | 48.500 | 142.842 | 7 | 3 |
22 | 4.194.304 | 363.013 | 182.580 | 180.433 | 92.121 | 270.882 | 7 | 3 |
23 | 8.388.608 | 692.172 | 347.327 | 344.845 | 175.205 | 516.957 | 7 | 3 |
24 | 16.777.216 | 1.321.265 | 662.962 | 658.303 | 334.262 | 986.993 | 7 | 3 |
25 | 33.554.432 | 2.528.023 | 1.268.065 | 1.259.958 | 639.117 | 1.888.896 | 7 | 3 |
26 | 67.108.864 | 4.846.474 | 2.431.220 | 2.415.254 | 1.224.043 | 3.622.421 | 7 | 3 |
27 | 134.217.728 | 9.304.979 | 4.667.964 | 4.637.015 | 2.349.739 | 6.955.230 | 7 | 3 |
28 | 268.435.456 | 17.897.881 | 8.978.489 | 8.919.392 | 4.519.808 | 13.378.063 | 7 | 3 |
29 | 536.870.912 | 34.484.487 | 17.293.487 | 17.191.000 | 8.702.619 | 25.781.858 | 7 | 3 |
30 | 1.073.741.824 | 66.512.508 | 33.351.815 | 33.160.693 | 16.778.989 | 49.733.509 | 7 | 3 |
31 | 2.147.483.648 | 128.458.239 | 64.414.241 | 64.043.998 | 32.394.346 | 96.063.883 | 7 | 3 |
32 | 4.294.967.296 | 248.395.963 | 124.551.336 | 123.844.627 | 62.619.199 | 185.776.754 | 7 | 3 |
33 | 8.589.934.592 | 480.857.174 | 241.083.784 | 239.773.390 | 121.189.482 | 359.667.682 | 7 | 3 |
34 | 17.179.869.184 | 931.779.755 | 467.105.652 | 464.674.103 | 234.769.908 | 697.009.837 | 7 | 3 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
4 | 16 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
5 | 32 | 2 | 2 | 0 | 0 | 2 | 0 | 0 |
6 | 64 | 3 | 2 | 1 | 0 | 2 | 1 | 0 |
7 | 128 | 25 | 13 | 12 | 6 | 6 | 9 | 4 |
8 | 256 | 74 | 36 | 38 | 20 | 15 | 23 | 16 |
9 | 512 | 188 | 93 | 95 | 50 | 37 | 57 | 44 |
10 | 1.024 | 421 | 204 | 217 | 100 | 87 | 132 | 102 |
11 | 2.048 | 943 | 458 | 485 | 228 | 204 | 266 | 245 |
12 | 4.096 | 2.009 | 981 | 1.028 | 481 | 419 | 575 | 534 |
13 | 8.192 | 4.221 | 2.065 | 2.156 | 1.041 | 879 | 1.187 | 1.114 |
14 | 16.384 | 8.693 | 4.294 | 4.399 | 2.170 | 1.855 | 2.399 | 2.269 |
15 | 32.768 | 17.821 | 8.876 | 8.945 | 4.427 | 3.861 | 4.916 | 4.617 |
16 | 65.536 | 36.428 | 18.202 | 18.226 | 9.051 | 8.006 | 9.991 | 9.380 |
17 | 131.072 | 74.028 | 37.015 | 37.013 | 18.283 | 16.616 | 20.172 | 18.957 |
18 | 262.144 | 150.247 | 75.002 | 75.245 | 37.438 | 33.824 | 40.604 | 38.381 |
19 | 524.288 | 303.966 | 151.768 | 152.198 | 75.478 | 69.177 | 81.545 | 77.766 |
20 | 1.048.576 | 614.644 | 307.053 | 307.591 | 152.790 | 140.800 | 163.944 | 157.110 |
21 | 2.097.152 | 1.241.253 | 620.548 | 620.705 | 308.802 | 286.156 | 329.426 | 316.869 |
22 | 4.194.304 | 2.504.128 | 1.251.467 | 1.252.661 | 623.540 | 580.253 | 662.446 | 637.889 |
23 | 8.388.608 | 5.045.642 | 2.522.256 | 2.523.386 | 1.257.610 | 1.174.676 | 1.330.446 | 1.282.910 |
24 | 16.777.216 | 10.160.108 | 5.079.746 | 5.080.362 | 2.533.772 | 2.374.335 | 2.671.176 | 2.580.825 |
25 | 33.554.432 | 20.445.621 | 10.222.373 | 10.223.248 | 5.100.220 | 4.794.758 | 5.363.384 | 5.187.259 |
26 | 67.108.864 | 41.119.167 | 20.560.093 | 20.559.074 | 10.254.542 | 9.674.049 | 10.760.878 | 10.429.698 |
27 | 134.217.728 | 82.662.336 | 41.335.877 | 41.326.459 | 20.618.038 | 19.503.288 | 21.589.777 | 20.951.233 |
28 | 268.435.456 | 166.103.697 | 83.067.948 | 83.035.749 | 41.438.016 | 39.300.112 | 43.293.273 | 42.072.296 |
29 | 536.870.912 | 333.650.055 | 166.853.987 | 166.796.068 | 83.256.643 | 79.132.646 | 86.811.078 | 84.449.688 |
30 | 1.073.741.824 | 670.012.253 | 335.034.719 | 334.977.534 | 167.214.543 | 159.268.308 | 174.045.212 | 169.484.190 |
31 | 2.147.483.648 | 1.345.056.885 | 672.554.826 | 672.502.059 | 335.714.038 | 320.403.934 | 348.871.273 | 340.067.640 |
32 | 4.294.967.296 | 2.699.489.611 | 1.349.814.745 | 1.349.674.866 | 673.820.254 | 644.258.879 | 699.252.111 | 682.158.367 |
33 | 8.589.934.592 | 5.416.554.308 | 2.708.453.855 | 2.708.100.453 | 1.352.117.123 | 1.294.980.233 | 1.401.277.858 | 1.368.179.094 |
34 | 17.179.869.184 | 10.866.140.277 | 5.433.351.550 | 5.432.788.727 | 2.712.700.196 | 2.602.118.333 | 2.807.777.626 | 2.743.544.122 |