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+3x-47
f(0)=47
f(1)=43
f(2)=37
f(3)=29
f(4)=19
f(5)=7
f(6)=1
f(7)=23
f(8)=41
f(9)=61
f(10)=83
f(11)=107
f(12)=1
f(13)=1
f(14)=191
f(15)=223
f(16)=257
f(17)=293
f(18)=331
f(19)=53
f(20)=59
f(21)=457
f(22)=503
f(23)=1
f(24)=601
f(25)=653
f(26)=101
f(27)=109
f(28)=821
f(29)=881
f(30)=1
f(31)=1
f(32)=1
f(33)=163
f(34)=173
f(35)=1283
f(36)=1
f(37)=1433
f(38)=1511
f(39)=1
f(40)=239
f(41)=251
f(42)=97
f(43)=1931
f(44)=1
f(45)=2113
f(46)=2207
f(47)=1
f(48)=1
f(49)=1
f(50)=137
f(51)=2707
f(52)=1
f(53)=127
f(54)=433
f(55)=449
f(56)=3257
f(57)=3373
f(58)=3491
f(59)=157
f(60)=3733
f(61)=1
f(62)=569
f(63)=4111
f(64)=4241
f(65)=4373
f(66)=4507
f(67)=4643
f(68)=683
f(69)=1
f(70)=1
f(71)=1
f(72)=1
f(73)=5501
f(74)=5651
f(75)=829
f(76)=1
f(77)=6113
f(78)=6271
f(79)=1
f(80)=347
f(81)=233
f(82)=1
f(83)=1013
f(84)=1
f(85)=7433
f(86)=7607
f(87)=181
f(88)=419
f(89)=1163
f(90)=1
f(91)=1
f(92)=8693
f(93)=1
f(94)=193
f(95)=1
f(96)=1
f(97)=197
f(98)=9851
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+3x-47 could be written as f(y)= y^2-49.25 with x=y-1.5
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+1.5
f'(x)>2x+2
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 | 9 | 0 | 0.900000 | 0.900000 | 0.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 71 | 47 | 24 | 0.710000 | 0.470000 | 0.240000 | 7.888889 | 5.222222 | inf |
3 | 1.000 | 727 | 287 | 440 | 0.727000 | 0.287000 | 0.440000 | 10.239436 | 6.106383 | 18.333334 |
4 | 10.000 | 7.269 | 2.016 | 5.253 | 0.726900 | 0.201600 | 0.525300 | 9.998625 | 7.024390 | 11.938637 |
5 | 100.000 | 72.020 | 15.706 | 56.314 | 0.720200 | 0.157060 | 0.563140 | 9.907827 | 7.790675 | 10.720350 |
6 | 1.000.000 | 715.399 | 126.962 | 588.437 | 0.715399 | 0.126962 | 0.588437 | 9.933338 | 8.083662 | 10.449213 |
7 | 10.000.000 | 7.120.386 | 1.074.023 | 6.046.363 | 0.712039 | 0.107402 | 0.604636 | 9.953028 | 8.459405 | 10.275293 |
8 | 100.000.000 | 70.952.432 | 9.302.970 | 61.649.462 | 0.709524 | 0.093030 | 0.616495 | 9.964689 | 8.661798 | 10.196123 |
9 | 1.000.000.000 | 707.548.102 | 82.090.287 | 625.457.815 | 0.707548 | 0.082090 | 0.625458 | 9.972147 | 8.824095 | 10.145389 |
10 | 10.000.000.000 | 7.060.032.708 | 734.610.058 | 6.325.422.650 | 0.706003 | 0.073461 | 0.632542 | 9.978167 | 8.948806 | 10.113269 |
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 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.400000 | 1.400000 | -nan |
4 | 16 | 13 | 13 | 0 | 0.812500 | 0.812500 | 0.000000 | 1.857143 | 1.857143 | -nan |
5 | 32 | 25 | 21 | 4 | 0.781250 | 0.656250 | 0.125000 | 1.923077 | 1.615385 | inf |
6 | 64 | 49 | 34 | 15 | 0.765625 | 0.531250 | 0.234375 | 1.960000 | 1.619048 | 3.750000 |
7 | 128 | 95 | 57 | 38 | 0.742188 | 0.445312 | 0.296875 | 1.938776 | 1.676471 | 2.533333 |
8 | 256 | 189 | 96 | 93 | 0.738281 | 0.375000 | 0.363281 | 1.989474 | 1.684211 | 2.447368 |
9 | 512 | 375 | 162 | 213 | 0.732422 | 0.316406 | 0.416016 | 1.984127 | 1.687500 | 2.290323 |
10 | 1.024 | 746 | 294 | 452 | 0.728516 | 0.287109 | 0.441406 | 1.989333 | 1.814815 | 2.122066 |
11 | 2.048 | 1.477 | 530 | 947 | 0.721191 | 0.258789 | 0.462402 | 1.979893 | 1.802721 | 2.095133 |
12 | 4.096 | 2.977 | 943 | 2.034 | 0.726807 | 0.230225 | 0.496582 | 2.015572 | 1.779245 | 2.147835 |
13 | 8.192 | 5.942 | 1.697 | 4.245 | 0.725342 | 0.207153 | 0.518188 | 1.995969 | 1.799576 | 2.087021 |
14 | 16.384 | 11.888 | 3.126 | 8.762 | 0.725586 | 0.190796 | 0.534790 | 2.000673 | 1.842074 | 2.064075 |
15 | 32.768 | 23.728 | 5.777 | 17.951 | 0.724121 | 0.176300 | 0.547821 | 1.995962 | 1.848049 | 2.048733 |
16 | 65.536 | 47.223 | 10.753 | 36.470 | 0.720566 | 0.164078 | 0.556488 | 1.990180 | 1.861347 | 2.031642 |
17 | 131.072 | 94.255 | 20.027 | 74.228 | 0.719109 | 0.152794 | 0.566315 | 1.995955 | 1.862457 | 2.035317 |
18 | 262.144 | 188.218 | 37.379 | 150.839 | 0.717995 | 0.142590 | 0.575405 | 1.996902 | 1.866430 | 2.032104 |
19 | 524.288 | 375.659 | 70.163 | 305.496 | 0.716513 | 0.133825 | 0.582687 | 1.995872 | 1.877070 | 2.025312 |
20 | 1.048.576 | 750.041 | 132.607 | 617.434 | 0.715295 | 0.126464 | 0.588831 | 1.996601 | 1.889985 | 2.021087 |
21 | 2.097.152 | 1.497.777 | 251.371 | 1.246.406 | 0.714196 | 0.119863 | 0.594333 | 1.996927 | 1.895609 | 2.018687 |
22 | 4.194.304 | 2.991.134 | 478.268 | 2.512.866 | 0.713142 | 0.114028 | 0.599114 | 1.997049 | 1.902638 | 2.016089 |
23 | 8.388.608 | 5.974.475 | 911.619 | 5.062.856 | 0.712213 | 0.108673 | 0.603539 | 1.997395 | 1.906084 | 2.014774 |
24 | 16.777.216 | 11.936.034 | 1.741.291 | 10.194.743 | 0.711443 | 0.103789 | 0.607654 | 1.997838 | 1.910108 | 2.013635 |
25 | 33.554.432 | 23.845.848 | 3.332.945 | 20.512.903 | 0.710662 | 0.099330 | 0.611332 | 1.997803 | 1.914065 | 2.012106 |
26 | 67.108.864 | 47.641.492 | 6.391.742 | 41.249.750 | 0.709914 | 0.095244 | 0.614669 | 1.997895 | 1.917746 | 2.010917 |
27 | 134.217.728 | 95.192.821 | 12.277.602 | 82.915.219 | 0.709242 | 0.091475 | 0.617766 | 1.998108 | 1.920854 | 2.010078 |
28 | 268.435.456 | 190.214.141 | 23.623.169 | 166.590.972 | 0.708603 | 0.088003 | 0.620600 | 1.998198 | 1.924086 | 2.009172 |
29 | 536.870.912 | 380.120.479 | 45.513.184 | 334.607.295 | 0.708030 | 0.084775 | 0.623255 | 1.998382 | 1.926633 | 2.008556 |
30 | 1.073.741.824 | 759.664.593 | 87.823.830 | 671.840.763 | 0.707493 | 0.081792 | 0.625700 | 1.998484 | 1.929635 | 2.007849 |
31 | 2.147.483.648 | 1.518.262.637 | 169.662.549 | 1.348.600.088 | 0.706996 | 0.079005 | 0.627991 | 1.998596 | 1.931851 | 2.007321 |
32 | 4.294.967.296 | 3.034.531.136 | 328.162.575 | 2.706.368.561 | 0.706532 | 0.076406 | 0.630126 | 1.998687 | 1.934207 | 2.006799 |
33 | 8.589.934.592 | 6.065.320.377 | 635.426.743 | 5.429.893.634 | 0.706096 | 0.073973 | 0.632123 | 1.998767 | 1.936317 | 2.006339 |
34 | 17.179.869.184 | 12.123.629.413 | 1.231.624.778 | 10.892.004.635 | 0.705688 | 0.071690 | 0.633998 | 1.998844 | 1.938264 | 2.005933 |
35 | 34.359.738.368 | 24.234.105.540 | 2.389.528.942 | 21.844.576.598 | 0.705305 | 0.069544 | 0.635761 | 1.998915 | 1.940143 | 2.005561 |
36 | 68.719.476.736 | 48.443.552.693 | 4.640.128.826 | 43.803.423.867 | 0.704946 | 0.067523 | 0.637424 | 1.998983 | 1.941859 | 2.005231 |
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 | 2 | 1 | 0 | 1 | 1 | 1 |
2 | 4 | 5 | 3 | 2 | 0 | 2 | 2 | 1 |
3 | 8 | 7 | 3 | 4 | 1 | 2 | 2 | 2 |
4 | 16 | 13 | 5 | 8 | 2 | 4 | 3 | 4 |
5 | 32 | 21 | 8 | 13 | 5 | 5 | 6 | 5 |
6 | 64 | 34 | 13 | 21 | 9 | 9 | 8 | 8 |
7 | 128 | 57 | 20 | 37 | 14 | 16 | 16 | 11 |
8 | 256 | 96 | 33 | 63 | 21 | 30 | 26 | 19 |
9 | 512 | 162 | 53 | 109 | 45 | 47 | 38 | 32 |
10 | 1.024 | 294 | 97 | 197 | 77 | 75 | 72 | 70 |
11 | 2.048 | 530 | 180 | 350 | 132 | 136 | 128 | 134 |
12 | 4.096 | 943 | 322 | 621 | 227 | 237 | 240 | 239 |
13 | 8.192 | 1.697 | 573 | 1.124 | 408 | 420 | 435 | 434 |
14 | 16.384 | 3.126 | 1.051 | 2.075 | 758 | 792 | 784 | 792 |
15 | 32.768 | 5.777 | 1.966 | 3.811 | 1.409 | 1.460 | 1.453 | 1.455 |
16 | 65.536 | 10.753 | 3.651 | 7.102 | 2.701 | 2.666 | 2.712 | 2.674 |
17 | 131.072 | 20.027 | 6.726 | 13.301 | 5.030 | 5.028 | 4.990 | 4.979 |
18 | 262.144 | 37.379 | 12.554 | 24.825 | 9.283 | 9.387 | 9.411 | 9.298 |
19 | 524.288 | 70.163 | 23.626 | 46.537 | 17.438 | 17.660 | 17.560 | 17.505 |
20 | 1.048.576 | 132.607 | 44.375 | 88.232 | 32.908 | 33.336 | 33.163 | 33.200 |
21 | 2.097.152 | 251.371 | 83.829 | 167.542 | 62.664 | 63.010 | 62.842 | 62.855 |
22 | 4.194.304 | 478.268 | 159.603 | 318.665 | 119.604 | 119.783 | 119.318 | 119.563 |
23 | 8.388.608 | 911.619 | 304.292 | 607.327 | 227.877 | 228.221 | 227.513 | 228.008 |
24 | 16.777.216 | 1.741.291 | 580.960 | 1.160.331 | 435.270 | 435.694 | 435.216 | 435.111 |
25 | 33.554.432 | 3.332.945 | 1.111.214 | 2.221.731 | 833.230 | 833.239 | 833.440 | 833.036 |
26 | 67.108.864 | 6.391.742 | 2.130.446 | 4.261.296 | 1.597.791 | 1.598.573 | 1.597.833 | 1.597.545 |
27 | 134.217.728 | 12.277.602 | 4.093.471 | 8.184.131 | 3.070.197 | 3.069.050 | 3.070.128 | 3.068.227 |
28 | 268.435.456 | 23.623.169 | 7.874.436 | 15.748.733 | 5.905.770 | 5.904.767 | 5.907.688 | 5.904.944 |
29 | 536.870.912 | 45.513.184 | 15.172.774 | 30.340.410 | 11.379.432 | 11.376.106 | 11.379.686 | 11.377.960 |
30 | 1.073.741.824 | 87.823.830 | 29.272.633 | 58.551.197 | 21.954.499 | 21.956.611 | 21.955.178 | 21.957.542 |
31 | 2.147.483.648 | 169.662.549 | 56.553.677 | 113.108.872 | 42.410.312 | 42.419.725 | 42.415.135 | 42.417.377 |
32 | 4.294.967.296 | 328.162.575 | 109.388.122 | 218.774.453 | 82.033.534 | 82.046.765 | 82.037.613 | 82.044.663 |
33 | 8.589.934.592 | 635.426.743 | 211.809.313 | 423.617.430 | 158.843.060 | 158.868.339 | 158.854.104 | 158.861.240 |
34 | 17.179.869.184 | 1.231.624.778 | 410.546.408 | 821.078.370 | 307.890.348 | 307.925.113 | 307.886.089 | 307.923.228 |
35 | 34.359.738.368 | 2.389.528.942 | 796.518.497 | 1.593.010.445 | 597.368.470 | 597.393.690 | 597.367.485 | 597.399.297 |
36 | 68.719.476.736 | 4.640.128.826 | 1.546.716.394 | 3.093.412.432 | 1.160.029.052 | 1.160.036.490 | 1.160.024.490 | 1.160.038.794 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 4 | 1 | 3 | 0 | 1 | 3 | 0 |
6 | 64 | 15 | 6 | 9 | 5 | 3 | 5 | 2 |
7 | 128 | 38 | 16 | 22 | 12 | 10 | 10 | 6 |
8 | 256 | 93 | 42 | 51 | 29 | 26 | 19 | 19 |
9 | 512 | 213 | 95 | 118 | 57 | 53 | 52 | 51 |
10 | 1.024 | 452 | 205 | 247 | 106 | 115 | 116 | 115 |
11 | 2.048 | 947 | 427 | 520 | 228 | 242 | 236 | 241 |
12 | 4.096 | 2.034 | 957 | 1.077 | 524 | 515 | 505 | 490 |
13 | 8.192 | 4.245 | 2.045 | 2.200 | 1.056 | 1.072 | 1.094 | 1.023 |
14 | 16.384 | 8.762 | 4.230 | 4.532 | 2.152 | 2.187 | 2.227 | 2.196 |
15 | 32.768 | 17.951 | 8.814 | 9.137 | 4.457 | 4.472 | 4.512 | 4.510 |
16 | 65.536 | 36.470 | 17.906 | 18.564 | 9.029 | 9.044 | 9.294 | 9.103 |
17 | 131.072 | 74.228 | 36.311 | 37.917 | 18.529 | 18.471 | 18.659 | 18.569 |
18 | 262.144 | 150.839 | 73.874 | 76.965 | 37.793 | 37.632 | 37.820 | 37.594 |
19 | 524.288 | 305.496 | 149.907 | 155.589 | 76.263 | 76.473 | 76.517 | 76.243 |
20 | 1.048.576 | 617.434 | 303.623 | 313.811 | 154.044 | 154.392 | 154.589 | 154.409 |
21 | 2.097.152 | 1.246.406 | 613.352 | 633.054 | 311.370 | 311.797 | 311.303 | 311.936 |
22 | 4.194.304 | 2.512.866 | 1.238.007 | 1.274.859 | 628.172 | 627.897 | 628.624 | 628.173 |
23 | 8.388.608 | 5.062.856 | 2.496.781 | 2.566.075 | 1.265.603 | 1.265.435 | 1.265.490 | 1.266.328 |
24 | 16.777.216 | 10.194.743 | 5.030.309 | 5.164.434 | 2.547.284 | 2.549.471 | 2.548.893 | 2.549.095 |
25 | 33.554.432 | 20.512.903 | 10.127.247 | 10.385.656 | 5.129.947 | 5.127.364 | 5.126.935 | 5.128.657 |
26 | 67.108.864 | 41.249.750 | 20.377.754 | 20.871.996 | 10.316.266 | 10.313.110 | 10.310.213 | 10.310.161 |
27 | 134.217.728 | 82.915.219 | 40.977.888 | 41.937.331 | 20.734.097 | 20.728.761 | 20.726.494 | 20.725.867 |
28 | 268.435.456 | 166.590.972 | 82.381.038 | 84.209.934 | 41.655.207 | 41.646.662 | 41.643.373 | 41.645.730 |
29 | 536.870.912 | 334.607.295 | 165.546.882 | 169.060.413 | 83.665.263 | 83.652.667 | 83.649.484 | 83.639.881 |
30 | 1.073.741.824 | 671.840.763 | 332.537.016 | 339.303.747 | 167.977.891 | 167.951.034 | 167.969.632 | 167.942.206 |
31 | 2.147.483.648 | 1.348.600.088 | 667.752.518 | 680.847.570 | 337.179.724 | 337.124.357 | 337.158.834 | 337.137.173 |
32 | 4.294.967.296 | 2.706.368.561 | 1.340.489.213 | 1.365.879.348 | 676.612.607 | 676.556.454 | 676.585.566 | 676.613.934 |
33 | 8.589.934.592 | 5.429.893.634 | 2.690.334.748 | 2.739.558.886 | 1.357.494.403 | 1.357.441.958 | 1.357.455.366 | 1.357.501.907 |
34 | 17.179.869.184 | 10.892.004.635 | 5.398.240.567 | 5.493.764.068 | 2.723.023.488 | 2.722.958.692 | 2.723.002.302 | 2.723.020.153 |
35 | 34.359.738.368 | 21.844.576.598 | 10.829.601.786 | 11.014.974.812 | 5.461.117.656 | 5.461.118.080 | 5.461.171.436 | 5.461.169.426 |
36 | 68.719.476.736 | 43.803.423.867 | 21.721.797.471 | 22.081.626.396 | 10.950.831.146 | 10.950.829.836 | 10.950.843.761 | 10.950.919.124 |