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+92x-113
f(0)=113
f(1)=5
f(2)=3
f(3)=43
f(4)=271
f(5)=31
f(6)=19
f(7)=29
f(8)=229
f(9)=199
f(10)=907
f(11)=17
f(12)=227
f(13)=313
f(14)=457
f(15)=373
f(16)=1
f(17)=1
f(18)=1867
f(19)=499
f(20)=709
f(21)=1
f(22)=479
f(23)=211
f(24)=2671
f(25)=37
f(26)=197
f(27)=1
f(28)=191
f(29)=283
f(30)=3547
f(31)=1
f(32)=257
f(33)=59
f(34)=97
f(35)=1
f(36)=1
f(37)=233
f(38)=1609
f(39)=1249
f(40)=5167
f(41)=89
f(42)=1103
f(43)=1423
f(44)=103
f(45)=1
f(46)=1
f(47)=107
f(48)=6607
f(49)=1699
f(50)=137
f(51)=359
f(52)=1
f(53)=631
f(54)=409
f(55)=1993
f(56)=109
f(57)=419
f(58)=277
f(59)=733
f(60)=9007
f(61)=461
f(62)=1
f(63)=127
f(64)=9871
f(65)=1
f(66)=2063
f(67)=1
f(68)=1
f(69)=2749
f(70)=1
f(71)=1
f(72)=2339
f(73)=157
f(74)=4057
f(75)=1
f(76)=2531
f(77)=1
f(78)=13147
f(79)=1
f(80)=4549
f(81)=139
f(82)=149
f(83)=1201
f(84)=863
f(85)=3733
f(86)=1013
f(87)=773
f(88)=15727
f(89)=1
f(90)=16267
f(91)=827
f(92)=1
f(93)=4273
f(94)=599
f(95)=1471
f(96)=1
f(97)=911
f(98)=1
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+92x-113 could be written as f(y)= y^2-2229 with x=y-46
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+46
f'(x)>2x+91
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 | 11 | 4 | 7 | 1.100000 | 0.400000 | 1.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 71 | 15 | 56 | 0.710000 | 0.150000 | 0.710000 | 6.454545 | 3.750000 | 8.000000 |
3 | 1.000 | 634 | 77 | 557 | 0.634000 | 0.077000 | 0.634000 | 8.929578 | 5.133333 | 9.946428 |
4 | 10.000 | 6.514 | 550 | 5.964 | 0.651400 | 0.055000 | 0.651400 | 10.274448 | 7.142857 | 10.707361 |
5 | 100.000 | 66.251 | 4.268 | 61.983 | 0.662510 | 0.042680 | 0.662510 | 10.170556 | 7.760000 | 10.392858 |
6 | 1.000.000 | 667.952 | 34.900 | 633.052 | 0.667952 | 0.034900 | 0.667952 | 10.082142 | 8.177133 | 10.213317 |
7 | 10.000.000 | 6.713.297 | 296.451 | 6.416.846 | 0.671330 | 0.029645 | 0.671330 | 10.050568 | 8.494298 | 10.136365 |
8 | 100.000.000 | 67.402.723 | 2.571.938 | 64.830.785 | 0.674027 | 0.025719 | 0.674027 | 10.040181 | 8.675761 | 10.103216 |
9 | 1.000.000.000 | 676.129.892 | 22.704.676 | 653.425.216 | 0.676130 | 0.022705 | 0.676130 | 10.031197 | 8.827847 | 10.078935 |
10 | 10.000.000.000 | 6.778.238.436 | 203.161.722 | 6.575.076.714 | 0.677824 | 0.020316 | 0.677824 | 10.025053 | 8.948012 | 10.062478 |
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 | 3 | 2 | 1.250000 | 0.750000 | 0.500000 | 1.666667 | 1.500000 | 2.000000 |
3 | 8 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.000000 | 3.000000 |
4 | 16 | 15 | 4 | 11 | 0.937500 | 0.250000 | 0.687500 | 1.666667 | 1.333333 | 1.833333 |
5 | 32 | 26 | 7 | 19 | 0.812500 | 0.218750 | 0.593750 | 1.733333 | 1.750000 | 1.727273 |
6 | 64 | 50 | 11 | 39 | 0.781250 | 0.171875 | 0.609375 | 1.923077 | 1.571429 | 2.052632 |
7 | 128 | 89 | 17 | 72 | 0.695312 | 0.132812 | 0.562500 | 1.780000 | 1.545455 | 1.846154 |
8 | 256 | 167 | 28 | 139 | 0.652344 | 0.109375 | 0.542969 | 1.876405 | 1.647059 | 1.930556 |
9 | 512 | 323 | 47 | 276 | 0.630859 | 0.091797 | 0.539062 | 1.934132 | 1.678571 | 1.985612 |
10 | 1.024 | 648 | 77 | 571 | 0.632812 | 0.075195 | 0.557617 | 2.006192 | 1.638298 | 2.068841 |
11 | 2.048 | 1.326 | 139 | 1.187 | 0.647461 | 0.067871 | 0.579590 | 2.046296 | 1.805195 | 2.078809 |
12 | 4.096 | 2.647 | 266 | 2.381 | 0.646240 | 0.064941 | 0.581299 | 1.996229 | 1.913669 | 2.005897 |
13 | 8.192 | 5.329 | 468 | 4.861 | 0.650513 | 0.057129 | 0.593384 | 2.013222 | 1.759398 | 2.041579 |
14 | 16.384 | 10.708 | 843 | 9.865 | 0.653564 | 0.051453 | 0.602112 | 2.009383 | 1.801282 | 2.029418 |
15 | 32.768 | 21.576 | 1.550 | 20.026 | 0.658447 | 0.047302 | 0.611145 | 2.014942 | 1.838671 | 2.030005 |
16 | 65.536 | 43.306 | 2.924 | 40.382 | 0.660797 | 0.044617 | 0.616180 | 2.007138 | 1.886452 | 2.016479 |
17 | 131.072 | 86.988 | 5.462 | 81.526 | 0.663666 | 0.041672 | 0.621994 | 2.008682 | 1.867989 | 2.018870 |
18 | 262.144 | 174.434 | 10.274 | 164.160 | 0.665413 | 0.039192 | 0.626221 | 2.005265 | 1.880996 | 2.013591 |
19 | 524.288 | 349.518 | 19.335 | 330.183 | 0.666653 | 0.036879 | 0.629774 | 2.003726 | 1.881935 | 2.011349 |
20 | 1.048.576 | 700.374 | 36.537 | 663.837 | 0.667929 | 0.034844 | 0.633084 | 2.003828 | 1.889682 | 2.010512 |
21 | 2.097.152 | 1.403.238 | 69.473 | 1.333.765 | 0.669116 | 0.033127 | 0.635989 | 2.003555 | 1.901442 | 2.009176 |
22 | 4.194.304 | 2.811.045 | 131.793 | 2.679.252 | 0.670205 | 0.031422 | 0.638783 | 2.003256 | 1.897039 | 2.008789 |
23 | 8.388.608 | 5.629.520 | 251.763 | 5.377.757 | 0.671091 | 0.030012 | 0.641079 | 2.002643 | 1.910291 | 2.007186 |
24 | 16.777.216 | 11.273.947 | 480.852 | 10.793.095 | 0.671980 | 0.028661 | 0.643319 | 2.002648 | 1.909939 | 2.006988 |
25 | 33.554.432 | 22.575.865 | 921.499 | 21.654.366 | 0.672813 | 0.027463 | 0.645350 | 2.002481 | 1.916388 | 2.006317 |
26 | 67.108.864 | 45.205.070 | 1.767.095 | 43.437.975 | 0.673608 | 0.026332 | 0.647276 | 2.002363 | 1.917631 | 2.005969 |
27 | 134.217.728 | 90.505.662 | 3.395.384 | 87.110.278 | 0.674320 | 0.025298 | 0.649022 | 2.002113 | 1.921450 | 2.005394 |
28 | 268.435.456 | 181.192.153 | 6.532.139 | 174.660.014 | 0.674993 | 0.024334 | 0.650659 | 2.001998 | 1.923829 | 2.005045 |
29 | 536.870.912 | 362.712.003 | 12.589.049 | 350.122.954 | 0.675604 | 0.023449 | 0.652155 | 2.001808 | 1.927248 | 2.004597 |
30 | 1.073.741.824 | 726.053.253 | 24.289.554 | 701.763.699 | 0.676190 | 0.022621 | 0.653568 | 2.001735 | 1.929419 | 2.004335 |
31 | 2.147.483.648 | 1.453.276.498 | 46.923.307 | 1.406.353.191 | 0.676735 | 0.021850 | 0.654884 | 2.001611 | 1.931831 | 2.004027 |
32 | 4.294.967.296 | 2.908.751.833 | 90.753.828 | 2.817.998.005 | 0.677247 | 0.021130 | 0.656116 | 2.001513 | 1.934088 | 2.003763 |
33 | 8.589.934.592 | 5.821.598.264 | 175.735.603 | 5.645.862.661 | 0.677723 | 0.020458 | 0.657265 | 2.001408 | 1.936399 | 2.003501 |
34 | 17.179.869.184 | 11.650.895.207 | 340.616.281 | 11.310.278.926 | 0.678171 | 0.019826 | 0.658345 | 2.001323 | 1.938232 | 2.003286 |
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 | 3 | 1 | 1 | 1 | 1 | 0 | 1 |
3 | 8 | 3 | 1 | 1 | 1 | 1 | 0 | 1 |
4 | 16 | 4 | 2 | 1 | 1 | 2 | 0 | 1 |
5 | 32 | 7 | 5 | 1 | 1 | 4 | 0 | 2 |
6 | 64 | 11 | 9 | 1 | 1 | 4 | 0 | 6 |
7 | 128 | 17 | 15 | 1 | 1 | 7 | 0 | 9 |
8 | 256 | 28 | 26 | 1 | 1 | 13 | 0 | 14 |
9 | 512 | 47 | 45 | 1 | 1 | 25 | 0 | 21 |
10 | 1.024 | 77 | 75 | 1 | 1 | 41 | 0 | 35 |
11 | 2.048 | 139 | 137 | 1 | 1 | 73 | 0 | 65 |
12 | 4.096 | 266 | 264 | 1 | 1 | 135 | 0 | 130 |
13 | 8.192 | 468 | 466 | 1 | 1 | 231 | 0 | 236 |
14 | 16.384 | 843 | 841 | 1 | 1 | 424 | 0 | 418 |
15 | 32.768 | 1.550 | 1.548 | 1 | 1 | 775 | 0 | 774 |
16 | 65.536 | 2.924 | 2.922 | 1 | 1 | 1.457 | 0 | 1.466 |
17 | 131.072 | 5.462 | 5.460 | 1 | 1 | 2.717 | 0 | 2.744 |
18 | 262.144 | 10.274 | 10.272 | 1 | 1 | 5.120 | 0 | 5.153 |
19 | 524.288 | 19.335 | 19.333 | 1 | 1 | 9.616 | 0 | 9.718 |
20 | 1.048.576 | 36.537 | 36.535 | 1 | 1 | 18.246 | 0 | 18.290 |
21 | 2.097.152 | 69.473 | 69.471 | 1 | 1 | 34.618 | 0 | 34.854 |
22 | 4.194.304 | 131.793 | 131.791 | 1 | 1 | 65.928 | 0 | 65.864 |
23 | 8.388.608 | 251.763 | 251.761 | 1 | 1 | 125.976 | 0 | 125.786 |
24 | 16.777.216 | 480.852 | 480.850 | 1 | 1 | 240.304 | 0 | 240.547 |
25 | 33.554.432 | 921.499 | 921.497 | 1 | 1 | 460.664 | 0 | 460.834 |
26 | 67.108.864 | 1.767.095 | 1.767.093 | 1 | 1 | 883.220 | 0 | 883.874 |
27 | 134.217.728 | 3.395.384 | 3.395.382 | 1 | 1 | 1.697.277 | 0 | 1.698.106 |
28 | 268.435.456 | 6.532.139 | 6.532.137 | 1 | 1 | 3.265.890 | 0 | 3.266.248 |
29 | 536.870.912 | 12.589.049 | 12.589.047 | 1 | 1 | 6.294.561 | 0 | 6.294.487 |
30 | 1.073.741.824 | 24.289.554 | 24.289.552 | 1 | 1 | 12.143.578 | 0 | 12.145.975 |
31 | 2.147.483.648 | 46.923.307 | 46.923.305 | 1 | 1 | 23.463.705 | 0 | 23.459.601 |
32 | 4.294.967.296 | 90.753.828 | 90.753.826 | 1 | 1 | 45.381.336 | 0 | 45.372.491 |
33 | 8.589.934.592 | 175.735.603 | 175.735.601 | 1 | 1 | 87.870.024 | 0 | 87.865.578 |
34 | 17.179.869.184 | 340.616.281 | 340.616.279 | 1 | 1 | 170.320.772 | 0 | 170.295.508 |
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 | 2 | 1 | 1 | 0 | 1 | 1 | 0 |
3 | 8 | 6 | 4 | 2 | 0 | 2 | 3 | 1 |
4 | 16 | 11 | 8 | 3 | 2 | 3 | 4 | 2 |
5 | 32 | 19 | 12 | 7 | 3 | 6 | 6 | 4 |
6 | 64 | 39 | 24 | 15 | 11 | 9 | 9 | 10 |
7 | 128 | 72 | 40 | 32 | 20 | 19 | 17 | 16 |
8 | 256 | 139 | 78 | 61 | 37 | 34 | 36 | 32 |
9 | 512 | 276 | 157 | 119 | 76 | 65 | 63 | 72 |
10 | 1.024 | 571 | 317 | 254 | 157 | 137 | 136 | 141 |
11 | 2.048 | 1.187 | 652 | 535 | 305 | 283 | 298 | 301 |
12 | 4.096 | 2.381 | 1.303 | 1.078 | 593 | 598 | 600 | 590 |
13 | 8.192 | 4.861 | 2.602 | 2.259 | 1.201 | 1.212 | 1.238 | 1.210 |
14 | 16.384 | 9.865 | 5.227 | 4.638 | 2.440 | 2.416 | 2.568 | 2.441 |
15 | 32.768 | 20.026 | 10.529 | 9.497 | 5.034 | 4.914 | 5.116 | 4.962 |
16 | 65.536 | 40.382 | 21.129 | 19.253 | 10.160 | 9.965 | 10.274 | 9.983 |
17 | 131.072 | 81.526 | 42.647 | 38.879 | 20.601 | 20.213 | 20.514 | 20.198 |
18 | 262.144 | 164.160 | 85.402 | 78.758 | 41.389 | 40.559 | 41.485 | 40.727 |
19 | 524.288 | 330.183 | 171.332 | 158.851 | 83.275 | 81.662 | 83.441 | 81.805 |
20 | 1.048.576 | 663.837 | 343.611 | 320.226 | 166.881 | 164.468 | 167.825 | 164.663 |
21 | 2.097.152 | 1.333.765 | 689.315 | 644.450 | 336.051 | 330.314 | 336.427 | 330.973 |
22 | 4.194.304 | 2.679.252 | 1.381.985 | 1.297.267 | 674.432 | 665.504 | 675.260 | 664.056 |
23 | 8.388.608 | 5.377.757 | 2.769.249 | 2.608.508 | 1.353.410 | 1.335.901 | 1.355.122 | 1.333.324 |
24 | 16.777.216 | 10.793.095 | 5.552.238 | 5.240.857 | 2.716.773 | 2.679.641 | 2.719.221 | 2.677.460 |
25 | 33.554.432 | 21.654.366 | 11.127.133 | 10.527.233 | 5.448.744 | 5.378.782 | 5.452.059 | 5.374.781 |
26 | 67.108.864 | 43.437.975 | 22.296.973 | 21.141.002 | 10.931.438 | 10.786.294 | 10.933.040 | 10.787.203 |
27 | 134.217.728 | 87.110.278 | 44.666.588 | 42.443.690 | 21.916.652 | 21.638.368 | 21.915.625 | 21.639.633 |
28 | 268.435.456 | 174.660.014 | 89.469.520 | 85.190.494 | 43.930.295 | 43.402.562 | 43.924.715 | 43.402.442 |
29 | 536.870.912 | 350.122.954 | 179.196.653 | 170.926.301 | 88.037.746 | 87.040.934 | 88.026.127 | 87.018.147 |
30 | 1.073.741.824 | 701.763.699 | 358.861.166 | 342.902.533 | 176.411.272 | 174.486.082 | 176.399.128 | 174.467.217 |
31 | 2.147.483.648 | 1.406.353.191 | 718.606.032 | 687.747.159 | 353.459.177 | 349.735.776 | 353.440.158 | 349.718.080 |
32 | 4.294.967.296 | 2.817.998.005 | 1.438.855.125 | 1.379.142.880 | 708.085.757 | 700.920.444 | 708.100.068 | 700.891.736 |
33 | 8.589.934.592 | 5.645.862.661 | 2.880.748.609 | 2.765.114.052 | 1.418.408.099 | 1.404.506.679 | 1.418.429.855 | 1.404.518.028 |
34 | 17.179.869.184 | 11.310.278.926 | 5.767.288.769 | 5.542.990.157 | 2.840.986.039 | 2.814.104.294 | 2.841.085.572 | 2.814.103.021 |