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-230x-3
f(0)=3
f(1)=29
f(2)=17
f(3)=19
f(4)=907
f(5)=47
f(6)=449
f(7)=23
f(8)=593
f(9)=83
f(10)=2203
f(11)=67
f(12)=97
f(13)=353
f(14)=1009
f(15)=269
f(16)=149
f(17)=151
f(18)=1
f(19)=59
f(20)=467
f(21)=61
f(22)=241
f(23)=397
f(24)=1
f(25)=641
f(26)=1
f(27)=457
f(28)=5659
f(29)=1
f(30)=1
f(31)=1543
f(32)=2113
f(33)=271
f(34)=113
f(35)=569
f(36)=137
f(37)=1
f(38)=811
f(39)=1
f(40)=7603
f(41)=1
f(42)=2633
f(43)=2011
f(44)=2729
f(45)=347
f(46)=8467
f(47)=239
f(48)=971
f(49)=1109
f(50)=3001
f(51)=761
f(52)=197
f(53)=1
f(54)=3169
f(55)=1
f(56)=1
f(57)=1
f(58)=587
f(59)=1
f(60)=179
f(61)=1289
f(62)=1
f(63)=877
f(64)=10627
f(65)=1
f(66)=401
f(67)=2731
f(68)=3673
f(69)=463
f(70)=659
f(71)=941
f(72)=3793
f(73)=1433
f(74)=1283
f(75)=1
f(76)=509
f(77)=491
f(78)=1
f(79)=157
f(80)=4001
f(81)=503
f(82)=199
f(83)=1
f(84)=1
f(85)=1
f(86)=4129
f(87)=1
f(88)=431
f(89)=523
f(90)=4201
f(91)=3163
f(92)=1
f(93)=1
f(94)=673
f(95)=1069
f(96)=4289
f(97)=1613
f(98)=227
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2-230x-3 could be written as f(y)= y^2-13228 with x=y+115
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-115
f'(x)>2x-231 with x > 115
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 | 0.700000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 76 | 19 | 57 | 0.760000 | 0.190000 | 0.570000 | 6.909091 | 4.750000 | 8.142858 |
3 | 1.000 | 543 | 130 | 413 | 0.543000 | 0.130000 | 0.413000 | 7.144737 | 6.842105 | 7.245614 |
4 | 10.000 | 6.333 | 1.009 | 5.324 | 0.633300 | 0.100900 | 0.532400 | 11.662984 | 7.761539 | 12.891041 |
5 | 100.000 | 65.871 | 7.642 | 58.229 | 0.658710 | 0.076420 | 0.582290 | 10.401232 | 7.573835 | 10.937078 |
6 | 1.000.000 | 666.325 | 62.111 | 604.214 | 0.666325 | 0.062111 | 0.604214 | 10.115604 | 8.127584 | 10.376513 |
7 | 10.000.000 | 6.704.083 | 522.467 | 6.181.616 | 0.670408 | 0.052247 | 0.618162 | 10.061281 | 8.411827 | 10.230839 |
8 | 100.000.000 | 67.328.147 | 4.507.077 | 62.821.070 | 0.673281 | 0.045071 | 0.628211 | 10.042856 | 8.626530 | 10.162564 |
9 | 1.000.000.000 | 675.458.726 | 39.630.775 | 635.827.951 | 0.675459 | 0.039631 | 0.635828 | 10.032339 | 8.793011 | 10.121253 |
10 | 10.000.000.000 | 6.772.178.194 | 353.763.695 | 6.418.414.499 | 0.677218 | 0.035376 | 0.641841 | 10.026043 | 8.926489 | 10.094578 |
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 | 17 | 5 | 12 | 1.062500 | 0.312500 | 0.750000 | 1.888889 | 1.666667 | 2.000000 |
5 | 32 | 28 | 8 | 20 | 0.875000 | 0.250000 | 0.625000 | 1.647059 | 1.600000 | 1.666667 |
6 | 64 | 51 | 14 | 37 | 0.796875 | 0.218750 | 0.578125 | 1.821429 | 1.750000 | 1.850000 |
7 | 128 | 86 | 23 | 63 | 0.671875 | 0.179688 | 0.492188 | 1.686275 | 1.642857 | 1.702703 |
8 | 256 | 95 | 28 | 67 | 0.371094 | 0.109375 | 0.261719 | 1.104651 | 1.217391 | 1.063492 |
9 | 512 | 245 | 67 | 178 | 0.478516 | 0.130859 | 0.347656 | 2.578947 | 2.392857 | 2.656716 |
10 | 1.024 | 554 | 133 | 421 | 0.541016 | 0.129883 | 0.411133 | 2.261225 | 1.985075 | 2.365169 |
11 | 2.048 | 1.203 | 254 | 949 | 0.587402 | 0.124023 | 0.463379 | 2.171480 | 1.909774 | 2.254157 |
12 | 4.096 | 2.523 | 465 | 2.058 | 0.615967 | 0.113525 | 0.502441 | 2.097257 | 1.830709 | 2.168598 |
13 | 8.192 | 5.176 | 844 | 4.332 | 0.631836 | 0.103027 | 0.528809 | 2.051526 | 1.815054 | 2.104956 |
14 | 16.384 | 10.546 | 1.555 | 8.991 | 0.643677 | 0.094910 | 0.548767 | 2.037481 | 1.842417 | 2.075485 |
15 | 32.768 | 21.329 | 2.840 | 18.489 | 0.650909 | 0.086670 | 0.564240 | 2.022473 | 1.826367 | 2.056390 |
16 | 65.536 | 43.049 | 5.217 | 37.832 | 0.656876 | 0.079605 | 0.577271 | 2.018332 | 1.836972 | 2.046190 |
17 | 131.072 | 86.384 | 9.793 | 76.591 | 0.659058 | 0.074715 | 0.584343 | 2.006644 | 1.877132 | 2.024503 |
18 | 262.144 | 173.647 | 18.352 | 155.295 | 0.662411 | 0.070007 | 0.592403 | 2.010175 | 1.873992 | 2.027588 |
19 | 524.288 | 348.446 | 34.438 | 314.008 | 0.664608 | 0.065685 | 0.598923 | 2.006634 | 1.876526 | 2.022010 |
20 | 1.048.576 | 698.677 | 64.882 | 633.795 | 0.666310 | 0.061876 | 0.604434 | 2.005123 | 1.884023 | 2.018404 |
21 | 2.097.152 | 1.400.732 | 122.933 | 1.277.799 | 0.667921 | 0.058619 | 0.609302 | 2.004835 | 1.894717 | 2.016108 |
22 | 4.194.304 | 2.806.674 | 233.428 | 2.573.246 | 0.669163 | 0.055654 | 0.613510 | 2.003720 | 1.898823 | 2.013811 |
23 | 8.388.608 | 5.621.894 | 443.703 | 5.178.191 | 0.670182 | 0.052894 | 0.617288 | 2.003045 | 1.900813 | 2.012319 |
24 | 16.777.216 | 11.260.201 | 845.717 | 10.414.484 | 0.671160 | 0.050409 | 0.620752 | 2.002919 | 1.906043 | 2.011220 |
25 | 33.554.432 | 22.550.595 | 1.617.108 | 20.933.487 | 0.672060 | 0.048194 | 0.623867 | 2.002681 | 1.912115 | 2.010036 |
26 | 67.108.864 | 45.152.329 | 3.099.006 | 42.053.323 | 0.672822 | 0.046179 | 0.626643 | 2.002268 | 1.916388 | 2.008902 |
27 | 134.217.728 | 90.405.912 | 5.944.374 | 84.461.538 | 0.673577 | 0.044289 | 0.629287 | 2.002243 | 1.918155 | 2.008439 |
28 | 268.435.456 | 180.997.847 | 11.424.570 | 169.573.277 | 0.674269 | 0.042560 | 0.631710 | 2.002058 | 1.921913 | 2.007698 |
29 | 536.870.912 | 362.340.560 | 21.992.620 | 340.347.940 | 0.674912 | 0.040964 | 0.633947 | 2.001905 | 1.925028 | 2.007085 |
30 | 1.073.741.824 | 725.331.988 | 42.395.685 | 682.936.303 | 0.675518 | 0.039484 | 0.636034 | 2.001796 | 1.927723 | 2.006583 |
31 | 2.147.483.648 | 1.451.873.907 | 81.841.064 | 1.370.032.843 | 0.676081 | 0.038110 | 0.637971 | 2.001668 | 1.930410 | 2.006092 |
32 | 4.294.967.296 | 2.906.043.258 | 158.176.977 | 2.747.866.281 | 0.676616 | 0.036828 | 0.639787 | 2.001581 | 1.932734 | 2.005694 |
33 | 8.589.934.592 | 5.816.363.298 | 306.048.921 | 5.510.314.377 | 0.677114 | 0.035629 | 0.641485 | 2.001472 | 1.934851 | 2.005306 |
34 | 17.179.869.184 | 11.640.787.135 | 592.815.476 | 11.047.971.659 | 0.677583 | 0.034506 | 0.643077 | 2.001386 | 1.936996 | 2.004962 |
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 | 0 | 1 | 1 | 0 |
2 | 4 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
3 | 8 | 3 | 1 | 1 | 0 | 2 | 1 | 0 |
4 | 16 | 5 | 2 | 2 | 1 | 3 | 1 | 0 |
5 | 32 | 8 | 4 | 3 | 2 | 4 | 1 | 1 |
6 | 64 | 14 | 8 | 5 | 3 | 8 | 2 | 1 |
7 | 128 | 23 | 15 | 7 | 4 | 14 | 3 | 2 |
8 | 256 | 28 | 16 | 11 | 5 | 14 | 6 | 3 |
9 | 512 | 67 | 29 | 37 | 12 | 21 | 25 | 9 |
10 | 1.024 | 133 | 45 | 87 | 20 | 29 | 67 | 17 |
11 | 2.048 | 254 | 73 | 180 | 37 | 43 | 143 | 31 |
12 | 4.096 | 465 | 136 | 328 | 60 | 79 | 268 | 58 |
13 | 8.192 | 844 | 242 | 601 | 106 | 129 | 495 | 114 |
14 | 16.384 | 1.555 | 442 | 1.112 | 195 | 227 | 917 | 216 |
15 | 32.768 | 2.840 | 803 | 2.036 | 370 | 419 | 1.666 | 385 |
16 | 65.536 | 5.217 | 1.456 | 3.760 | 648 | 738 | 3.112 | 719 |
17 | 131.072 | 9.793 | 2.676 | 7.116 | 1.241 | 1.347 | 5.875 | 1.330 |
18 | 262.144 | 18.352 | 4.890 | 13.461 | 2.329 | 2.459 | 11.132 | 2.432 |
19 | 524.288 | 34.438 | 9.074 | 25.363 | 4.406 | 4.585 | 20.957 | 4.490 |
20 | 1.048.576 | 64.882 | 17.012 | 47.869 | 8.284 | 8.555 | 39.585 | 8.458 |
21 | 2.097.152 | 122.933 | 32.149 | 90.783 | 15.571 | 16.095 | 75.212 | 16.055 |
22 | 4.194.304 | 233.428 | 61.070 | 172.357 | 29.583 | 30.708 | 142.774 | 30.363 |
23 | 8.388.608 | 443.703 | 115.763 | 327.939 | 56.311 | 57.939 | 271.628 | 57.825 |
24 | 16.777.216 | 845.717 | 219.923 | 625.793 | 107.437 | 109.950 | 518.356 | 109.974 |
25 | 33.554.432 | 1.617.108 | 420.286 | 1.196.821 | 205.599 | 210.434 | 991.222 | 209.853 |
26 | 67.108.864 | 3.099.006 | 803.890 | 2.295.115 | 393.336 | 401.959 | 1.901.779 | 401.932 |
27 | 134.217.728 | 5.944.374 | 1.539.534 | 4.404.839 | 753.637 | 769.855 | 3.651.202 | 769.680 |
28 | 268.435.456 | 11.424.570 | 2.955.716 | 8.468.853 | 1.447.798 | 1.477.622 | 7.021.055 | 1.478.095 |
29 | 536.870.912 | 21.992.620 | 5.682.448 | 16.310.171 | 2.786.233 | 2.841.611 | 13.523.938 | 2.840.838 |
30 | 1.073.741.824 | 42.395.685 | 10.940.164 | 31.455.520 | 5.369.796 | 5.471.076 | 26.085.724 | 5.469.089 |
31 | 2.147.483.648 | 81.841.064 | 21.092.819 | 60.748.244 | 10.361.103 | 10.547.101 | 50.387.141 | 10.545.719 |
32 | 4.294.967.296 | 158.176.977 | 40.723.899 | 117.453.077 | 20.016.803 | 20.364.988 | 97.436.274 | 20.358.912 |
33 | 8.589.934.592 | 306.048.921 | 78.716.384 | 227.332.536 | 38.713.292 | 39.360.927 | 188.619.244 | 39.355.458 |
34 | 17.179.869.184 | 592.815.476 | 152.332.878 | 440.482.597 | 74.954.536 | 76.173.575 | 365.528.061 | 76.159.304 |
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 | 1 | 0 | 0 | 0 |
2 | 4 | 2 | 1 | 1 | 1 | 1 | 0 | 0 |
3 | 8 | 6 | 1 | 5 | 3 | 1 | 0 | 2 |
4 | 16 | 12 | 4 | 8 | 5 | 3 | 2 | 2 |
5 | 32 | 20 | 10 | 10 | 8 | 5 | 4 | 3 |
6 | 64 | 37 | 15 | 22 | 16 | 10 | 6 | 5 |
7 | 128 | 63 | 26 | 37 | 27 | 17 | 9 | 10 |
8 | 256 | 67 | 27 | 40 | 27 | 17 | 10 | 13 |
9 | 512 | 178 | 96 | 82 | 46 | 31 | 44 | 57 |
10 | 1.024 | 421 | 218 | 203 | 87 | 71 | 113 | 150 |
11 | 2.048 | 949 | 480 | 469 | 187 | 171 | 242 | 349 |
12 | 4.096 | 2.058 | 1.061 | 997 | 401 | 412 | 531 | 714 |
13 | 8.192 | 4.332 | 2.214 | 2.118 | 860 | 868 | 1.102 | 1.502 |
14 | 16.384 | 8.991 | 4.568 | 4.423 | 1.808 | 1.823 | 2.301 | 3.059 |
15 | 32.768 | 18.489 | 9.468 | 9.021 | 3.828 | 3.814 | 4.762 | 6.085 |
16 | 65.536 | 37.832 | 19.289 | 18.543 | 7.989 | 7.919 | 9.690 | 12.234 |
17 | 131.072 | 76.591 | 38.777 | 37.814 | 16.311 | 16.328 | 19.599 | 24.353 |
18 | 262.144 | 155.295 | 78.710 | 76.585 | 33.622 | 33.752 | 39.373 | 48.548 |
19 | 524.288 | 314.008 | 159.005 | 155.003 | 68.674 | 68.973 | 79.493 | 96.868 |
20 | 1.048.576 | 633.795 | 320.980 | 312.815 | 139.978 | 140.151 | 160.453 | 193.213 |
21 | 2.097.152 | 1.277.799 | 646.456 | 631.343 | 284.796 | 284.441 | 323.205 | 385.357 |
22 | 4.194.304 | 2.573.246 | 1.300.426 | 1.272.820 | 576.986 | 576.836 | 651.266 | 768.158 |
23 | 8.388.608 | 5.178.191 | 2.614.609 | 2.563.582 | 1.169.429 | 1.168.413 | 1.309.512 | 1.530.837 |
24 | 16.777.216 | 10.414.484 | 5.255.592 | 5.158.892 | 2.364.817 | 2.363.898 | 2.633.172 | 3.052.597 |
25 | 33.554.432 | 20.933.487 | 10.559.972 | 10.373.515 | 4.781.115 | 4.774.943 | 5.288.744 | 6.088.685 |
26 | 67.108.864 | 42.053.323 | 21.207.388 | 20.845.935 | 9.643.877 | 9.637.005 | 10.618.828 | 12.153.613 |
27 | 134.217.728 | 84.461.538 | 42.580.425 | 41.881.113 | 19.449.391 | 19.434.784 | 21.317.588 | 24.259.775 |
28 | 268.435.456 | 169.573.277 | 85.460.864 | 84.112.413 | 39.197.231 | 39.161.361 | 42.775.532 | 48.439.153 |
29 | 536.870.912 | 340.347.940 | 171.486.225 | 168.861.715 | 78.943.161 | 78.873.918 | 85.816.503 | 96.714.358 |
30 | 1.073.741.824 | 682.936.303 | 343.976.613 | 338.959.690 | 158.898.006 | 158.766.315 | 172.119.682 | 193.152.300 |
31 | 2.147.483.648 | 1.370.032.843 | 689.852.761 | 680.180.082 | 319.669.028 | 319.421.954 | 345.172.778 | 385.769.083 |
32 | 4.294.967.296 | 2.747.866.281 | 1.383.275.123 | 1.364.591.158 | 642.843.019 | 642.360.810 | 692.082.318 | 770.580.134 |
33 | 8.589.934.592 | 5.510.314.377 | 2.773.195.574 | 2.737.118.803 | 1.292.199.534 | 1.291.394.140 | 1.387.388.500 | 1.539.332.203 |
34 | 17.179.869.184 | 11.047.971.659 | 5.558.916.735 | 5.489.054.924 | 2.596.643.066 | 2.595.216.341 | 2.780.855.506 | 3.075.256.746 |