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+59x-127
f(0)=127
f(1)=67
f(2)=5
f(3)=59
f(4)=1
f(5)=193
f(6)=263
f(7)=1
f(8)=409
f(9)=97
f(10)=563
f(11)=643
f(12)=29
f(13)=809
f(14)=179
f(15)=983
f(16)=37
f(17)=233
f(18)=1259
f(19)=271
f(20)=1453
f(21)=1553
f(22)=331
f(23)=1759
f(24)=373
f(25)=1973
f(26)=2083
f(27)=439
f(28)=2309
f(29)=1
f(30)=2543
f(31)=2663
f(32)=557
f(33)=2909
f(34)=607
f(35)=3163
f(36)=89
f(37)=137
f(38)=3559
f(39)=739
f(40)=3833
f(41)=1
f(42)=823
f(43)=4259
f(44)=881
f(45)=157
f(46)=4703
f(47)=971
f(48)=5009
f(49)=1033
f(50)=5323
f(51)=5483
f(52)=1129
f(53)=1
f(54)=239
f(55)=6143
f(56)=107
f(57)=1297
f(58)=6659
f(59)=1367
f(60)=7013
f(61)=7193
f(62)=1
f(63)=7559
f(64)=1549
f(65)=7933
f(66)=8123
f(67)=1663
f(68)=1
f(69)=1741
f(70)=307
f(71)=9103
f(72)=1861
f(73)=257
f(74)=1
f(75)=9923
f(76)=10133
f(77)=2069
f(78)=10559
f(79)=431
f(80)=10993
f(81)=11213
f(82)=2287
f(83)=131
f(84)=2377
f(85)=12113
f(86)=12343
f(87)=503
f(88)=12809
f(89)=2609
f(90)=359
f(91)=13523
f(92)=2753
f(93)=14009
f(94)=2851
f(95)=14503
f(96)=14753
f(97)=3001
f(98)=15259
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+59x-127 could be written as f(y)= y^2-997.25 with x=y-29.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+29.5
f'(x)>2x+58
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.100000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 90 | 51 | 39 | 0.900000 | 0.510000 | 0.390000 | 10.000000 | 6.375000 | 39.000000 |
3 | 1.000 | 809 | 342 | 467 | 0.809000 | 0.342000 | 0.467000 | 8.988889 | 6.705883 | 11.974359 |
4 | 10.000 | 7.902 | 2.420 | 5.482 | 0.790200 | 0.242000 | 0.548200 | 9.767614 | 7.076024 | 11.738758 |
5 | 100.000 | 76.739 | 18.900 | 57.839 | 0.767390 | 0.189000 | 0.578390 | 9.711339 | 7.809917 | 10.550712 |
6 | 1.000.000 | 753.668 | 154.841 | 598.827 | 0.753668 | 0.154841 | 0.598827 | 9.821186 | 8.192645 | 10.353343 |
7 | 10.000.000 | 7.444.529 | 1.310.903 | 6.133.626 | 0.744453 | 0.131090 | 0.613363 | 9.877730 | 8.466124 | 10.242735 |
8 | 100.000.000 | 73.779.465 | 11.354.676 | 62.424.789 | 0.737795 | 0.113547 | 0.624248 | 9.910562 | 8.661721 | 10.177469 |
9 | 1.000.000.000 | 732.613.091 | 100.180.187 | 632.432.904 | 0.732613 | 0.100180 | 0.632433 | 9.929770 | 8.822813 | 10.131118 |
10 | 10.000.000.000 | 7.285.059.704 | 896.510.419 | 6.388.549.285 | 0.728506 | 0.089651 | 0.638855 | 9.943938 | 8.948979 | 10.101544 |
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 | 7 | 7 | 0 | 0.875000 | 0.875000 | 0.000000 | 1.750000 | 1.750000 | -nan |
4 | 16 | 15 | 11 | 4 | 0.937500 | 0.687500 | 0.250000 | 2.142857 | 1.571429 | inf |
5 | 32 | 30 | 20 | 10 | 0.937500 | 0.625000 | 0.312500 | 2.000000 | 1.818182 | 2.500000 |
6 | 64 | 58 | 34 | 24 | 0.906250 | 0.531250 | 0.375000 | 1.933333 | 1.700000 | 2.400000 |
7 | 128 | 113 | 59 | 54 | 0.882812 | 0.460938 | 0.421875 | 1.948276 | 1.735294 | 2.250000 |
8 | 256 | 216 | 109 | 107 | 0.843750 | 0.425781 | 0.417969 | 1.911504 | 1.847458 | 1.981481 |
9 | 512 | 426 | 191 | 235 | 0.832031 | 0.373047 | 0.458984 | 1.972222 | 1.752294 | 2.196262 |
10 | 1.024 | 826 | 347 | 479 | 0.806641 | 0.338867 | 0.467773 | 1.938967 | 1.816754 | 2.038298 |
11 | 2.048 | 1.646 | 626 | 1.020 | 0.803711 | 0.305664 | 0.498047 | 1.992736 | 1.804035 | 2.129436 |
12 | 4.096 | 3.283 | 1.119 | 2.164 | 0.801514 | 0.273193 | 0.528320 | 1.994532 | 1.787540 | 2.121569 |
13 | 8.192 | 6.478 | 2.041 | 4.437 | 0.790771 | 0.249146 | 0.541626 | 1.973195 | 1.823950 | 2.050370 |
14 | 16.384 | 12.829 | 3.734 | 9.095 | 0.783020 | 0.227905 | 0.555115 | 1.980395 | 1.829495 | 2.049809 |
15 | 32.768 | 25.435 | 6.959 | 18.476 | 0.776215 | 0.212372 | 0.563843 | 1.982617 | 1.863685 | 2.031446 |
16 | 65.536 | 50.508 | 12.926 | 37.582 | 0.770691 | 0.197235 | 0.573456 | 1.985768 | 1.857451 | 2.034098 |
17 | 131.072 | 100.344 | 24.202 | 76.142 | 0.765564 | 0.184647 | 0.580917 | 1.986695 | 1.872350 | 2.026023 |
18 | 262.144 | 199.495 | 45.353 | 154.142 | 0.761013 | 0.173008 | 0.588005 | 1.988111 | 1.873936 | 2.024402 |
19 | 524.288 | 396.945 | 85.442 | 311.503 | 0.757113 | 0.162968 | 0.594145 | 1.989749 | 1.883933 | 2.020883 |
20 | 1.048.576 | 790.010 | 161.830 | 628.180 | 0.753412 | 0.154333 | 0.599079 | 1.990225 | 1.894033 | 2.016610 |
21 | 2.097.152 | 1.573.614 | 306.868 | 1.266.746 | 0.750358 | 0.146326 | 0.604032 | 1.991891 | 1.896237 | 2.016533 |
22 | 4.194.304 | 3.135.384 | 584.087 | 2.551.297 | 0.747534 | 0.139257 | 0.608277 | 1.992473 | 1.903382 | 2.014056 |
23 | 8.388.608 | 6.249.643 | 1.112.903 | 5.136.740 | 0.745016 | 0.132668 | 0.612347 | 1.993262 | 1.905372 | 2.013384 |
24 | 16.777.216 | 12.462.056 | 2.125.785 | 10.336.271 | 0.742796 | 0.126707 | 0.616090 | 1.994043 | 1.910126 | 2.012224 |
25 | 33.554.432 | 24.854.450 | 4.068.019 | 20.786.431 | 0.740720 | 0.121236 | 0.619484 | 1.994410 | 1.913655 | 2.011019 |
26 | 67.108.864 | 49.581.024 | 7.800.275 | 41.780.749 | 0.738815 | 0.116233 | 0.622582 | 1.994855 | 1.917463 | 2.010001 |
27 | 134.217.728 | 98.924.857 | 14.984.999 | 83.939.858 | 0.737048 | 0.111647 | 0.625401 | 1.995216 | 1.921086 | 2.009056 |
28 | 268.435.456 | 197.415.096 | 28.822.728 | 168.592.368 | 0.735429 | 0.107373 | 0.628056 | 1.995607 | 1.923439 | 2.008490 |
29 | 536.870.912 | 394.006.097 | 55.547.649 | 338.458.448 | 0.733894 | 0.103466 | 0.630428 | 1.995826 | 1.927217 | 2.007555 |
30 | 1.073.741.824 | 786.487.820 | 107.175.353 | 679.312.467 | 0.732474 | 0.099815 | 0.632659 | 1.996131 | 1.929431 | 2.007078 |
31 | 2.147.483.648 | 1.570.126.501 | 207.048.809 | 1.363.077.692 | 0.731147 | 0.096415 | 0.634732 | 1.996377 | 1.931870 | 2.006555 |
32 | 4.294.967.296 | 3.134.942.556 | 400.477.921 | 2.734.464.635 | 0.729911 | 0.093244 | 0.636667 | 1.996618 | 1.934220 | 2.006096 |
33 | 8.589.934.592 | 6.259.929.356 | 775.462.441 | 5.484.466.915 | 0.728752 | 0.090276 | 0.638476 | 1.996824 | 1.936343 | 2.005682 |
34 | 17.179.869.184 | 12.501.160.909 | 1.503.062.993 | 10.998.097.916 | 0.727663 | 0.087490 | 0.640174 | 1.997013 | 1.938280 | 2.005318 |
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 | 4 | 2 | 2 | 0 | 2 | 1 | 1 |
3 | 8 | 7 | 4 | 3 | 2 | 2 | 1 | 2 |
4 | 16 | 11 | 5 | 6 | 3 | 4 | 1 | 3 |
5 | 32 | 20 | 8 | 12 | 4 | 6 | 4 | 6 |
6 | 64 | 34 | 11 | 23 | 7 | 11 | 6 | 10 |
7 | 128 | 59 | 20 | 39 | 13 | 16 | 14 | 16 |
8 | 256 | 109 | 36 | 73 | 28 | 26 | 27 | 28 |
9 | 512 | 191 | 63 | 128 | 48 | 44 | 49 | 50 |
10 | 1.024 | 347 | 118 | 229 | 94 | 81 | 86 | 86 |
11 | 2.048 | 626 | 204 | 422 | 160 | 150 | 161 | 155 |
12 | 4.096 | 1.119 | 378 | 741 | 276 | 267 | 285 | 291 |
13 | 8.192 | 2.041 | 682 | 1.359 | 509 | 489 | 516 | 527 |
14 | 16.384 | 3.734 | 1.254 | 2.480 | 920 | 908 | 949 | 957 |
15 | 32.768 | 6.959 | 2.318 | 4.641 | 1.738 | 1.728 | 1.734 | 1.759 |
16 | 65.536 | 12.926 | 4.320 | 8.606 | 3.203 | 3.247 | 3.239 | 3.237 |
17 | 131.072 | 24.202 | 8.075 | 16.127 | 6.038 | 6.090 | 6.028 | 6.046 |
18 | 262.144 | 45.353 | 15.168 | 30.185 | 11.254 | 11.429 | 11.356 | 11.314 |
19 | 524.288 | 85.442 | 28.596 | 56.846 | 21.399 | 21.337 | 21.439 | 21.267 |
20 | 1.048.576 | 161.830 | 54.178 | 107.652 | 40.468 | 40.355 | 40.522 | 40.485 |
21 | 2.097.152 | 306.868 | 102.532 | 204.336 | 76.669 | 76.492 | 76.857 | 76.850 |
22 | 4.194.304 | 584.087 | 195.099 | 388.988 | 145.923 | 146.090 | 145.883 | 146.191 |
23 | 8.388.608 | 1.112.903 | 371.504 | 741.399 | 278.087 | 278.311 | 277.897 | 278.608 |
24 | 16.777.216 | 2.125.785 | 708.809 | 1.416.976 | 531.355 | 531.392 | 531.212 | 531.826 |
25 | 33.554.432 | 4.068.019 | 1.356.401 | 2.711.618 | 1.017.272 | 1.017.256 | 1.017.031 | 1.016.460 |
26 | 67.108.864 | 7.800.275 | 2.599.621 | 5.200.654 | 1.949.854 | 1.950.576 | 1.950.119 | 1.949.726 |
27 | 134.217.728 | 14.984.999 | 4.994.186 | 9.990.813 | 3.745.332 | 3.745.101 | 3.747.883 | 3.746.683 |
28 | 268.435.456 | 28.822.728 | 9.608.771 | 19.213.957 | 7.206.057 | 7.204.972 | 7.205.957 | 7.205.742 |
29 | 536.870.912 | 55.547.649 | 18.520.936 | 37.026.713 | 13.889.288 | 13.885.994 | 13.887.845 | 13.884.522 |
30 | 1.073.741.824 | 107.175.353 | 35.728.876 | 71.446.477 | 26.797.904 | 26.792.530 | 26.793.062 | 26.791.857 |
31 | 2.147.483.648 | 207.048.809 | 69.018.765 | 138.030.044 | 51.768.906 | 51.760.401 | 51.762.140 | 51.757.362 |
32 | 4.294.967.296 | 400.477.921 | 133.485.607 | 266.992.314 | 100.131.682 | 100.120.573 | 100.115.810 | 100.109.856 |
33 | 8.589.934.592 | 775.462.441 | 258.482.289 | 516.980.152 | 193.889.709 | 193.856.680 | 193.861.639 | 193.854.413 |
34 | 17.179.869.184 | 1.503.062.993 | 501.017.744 | 1.002.045.249 | 375.784.265 | 375.758.304 | 375.762.982 | 375.757.442 |
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 | 4 | 2 | 2 | 1 | 1 | 2 | 0 |
5 | 32 | 10 | 6 | 4 | 2 | 2 | 4 | 2 |
6 | 64 | 24 | 14 | 10 | 8 | 4 | 6 | 6 |
7 | 128 | 54 | 32 | 22 | 17 | 10 | 12 | 15 |
8 | 256 | 107 | 57 | 50 | 28 | 28 | 27 | 24 |
9 | 512 | 235 | 137 | 98 | 55 | 50 | 58 | 72 |
10 | 1.024 | 479 | 277 | 202 | 115 | 108 | 121 | 135 |
11 | 2.048 | 1.020 | 588 | 432 | 255 | 245 | 248 | 272 |
12 | 4.096 | 2.164 | 1.210 | 954 | 534 | 540 | 542 | 548 |
13 | 8.192 | 4.437 | 2.391 | 2.046 | 1.106 | 1.104 | 1.120 | 1.107 |
14 | 16.384 | 9.095 | 4.813 | 4.282 | 2.254 | 2.295 | 2.294 | 2.252 |
15 | 32.768 | 18.476 | 9.854 | 8.622 | 4.574 | 4.660 | 4.675 | 4.567 |
16 | 65.536 | 37.582 | 19.894 | 17.688 | 9.280 | 9.513 | 9.476 | 9.313 |
17 | 131.072 | 76.142 | 39.991 | 36.151 | 18.801 | 19.103 | 19.208 | 19.030 |
18 | 262.144 | 154.142 | 80.611 | 73.531 | 38.302 | 38.675 | 38.623 | 38.542 |
19 | 524.288 | 311.503 | 162.407 | 149.096 | 77.408 | 77.965 | 78.299 | 77.831 |
20 | 1.048.576 | 628.180 | 327.366 | 300.814 | 156.194 | 157.391 | 157.421 | 157.174 |
21 | 2.097.152 | 1.266.746 | 658.597 | 608.149 | 315.713 | 316.723 | 317.680 | 316.630 |
22 | 4.194.304 | 2.551.297 | 1.323.333 | 1.227.964 | 636.930 | 637.976 | 637.910 | 638.481 |
23 | 8.388.608 | 5.136.740 | 2.659.584 | 2.477.156 | 1.283.931 | 1.283.681 | 1.284.095 | 1.285.033 |
24 | 16.777.216 | 10.336.271 | 5.342.382 | 4.993.889 | 2.581.884 | 2.583.504 | 2.585.393 | 2.585.490 |
25 | 33.554.432 | 20.786.431 | 10.726.181 | 10.060.250 | 5.196.070 | 5.196.711 | 5.197.999 | 5.195.651 |
26 | 67.108.864 | 41.780.749 | 21.524.081 | 20.256.668 | 10.443.155 | 10.445.395 | 10.446.680 | 10.445.519 |
27 | 134.217.728 | 83.939.858 | 43.186.377 | 40.753.481 | 20.985.390 | 20.982.536 | 20.984.693 | 20.987.239 |
28 | 268.435.456 | 168.592.368 | 86.631.634 | 81.960.734 | 42.154.195 | 42.148.160 | 42.147.286 | 42.142.727 |
29 | 536.870.912 | 338.458.448 | 173.710.380 | 164.748.068 | 84.618.022 | 84.608.319 | 84.617.110 | 84.614.997 |
30 | 1.073.741.824 | 679.312.467 | 348.287.854 | 331.024.613 | 169.849.507 | 169.822.221 | 169.819.744 | 169.820.995 |
31 | 2.147.483.648 | 1.363.077.692 | 698.200.686 | 664.877.006 | 340.789.440 | 340.760.658 | 340.743.382 | 340.784.212 |
32 | 4.294.967.296 | 2.734.464.635 | 1.399.420.346 | 1.335.044.289 | 683.620.852 | 683.600.793 | 683.608.878 | 683.634.112 |
33 | 8.589.934.592 | 5.484.466.915 | 2.804.483.606 | 2.679.983.309 | 1.371.088.899 | 1.371.113.381 | 1.371.102.778 | 1.371.161.857 |
34 | 17.179.869.184 | 10.998.097.916 | 5.619.563.351 | 5.378.534.565 | 2.749.463.191 | 2.749.505.601 | 2.749.547.405 | 2.749.581.719 |