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-63x-31
f(0)=31
f(1)=3
f(2)=17
f(3)=211
f(4)=89
f(5)=107
f(6)=373
f(7)=47
f(8)=157
f(9)=11
f(10)=1
f(11)=67
f(12)=643
f(13)=227
f(14)=239
f(15)=751
f(16)=29
f(17)=271
f(18)=1
f(19)=1
f(20)=1
f(21)=83
f(22)=311
f(23)=317
f(24)=967
f(25)=109
f(26)=331
f(27)=59
f(28)=337
f(29)=113
f(30)=1021
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)=1
f(41)=1
f(42)=1
f(43)=1
f(44)=1
f(45)=1
f(46)=1
f(47)=1
f(48)=1
f(49)=1
f(50)=1
f(51)=1
f(52)=1
f(53)=1
f(54)=1
f(55)=1
f(56)=1
f(57)=1
f(58)=1
f(59)=1
f(60)=1
f(61)=1
f(62)=1
f(63)=1
f(64)=1
f(65)=1
f(66)=167
f(67)=79
f(68)=103
f(69)=383
f(70)=1
f(71)=179
f(72)=617
f(73)=233
f(74)=1
f(75)=1
f(76)=1
f(77)=349
f(78)=1
f(79)=137
f(80)=443
f(81)=1427
f(82)=509
f(83)=181
f(84)=1733
f(85)=613
f(86)=1
f(87)=1
f(88)=241
f(89)=761
f(90)=2399
f(91)=839
f(92)=293
f(93)=1
f(94)=1
f(95)=1
f(96)=3137
f(97)=1
f(98)=1
f(99)=3533
b) Substitution of the polynom
The polynom f(x)=x^2-63x-31 could be written as f(y)= y^2-1023.25 with x=y+31.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-31.5
f'(x)>2x-64 with x > 32
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 | 3 | 6 | 0.900000 | 0.300000 | 0.600000 | 0.000000 | 0.000000 | 0.000000 |
2 | 100 | 45 | 15 | 30 | 0.450000 | 0.150000 | 0.300000 | 5.000000 | 5.000000 | 5.000000 |
3 | 1.000 | 643 | 128 | 515 | 0.643000 | 0.128000 | 0.515000 | 14.288889 | 8.533334 | 17.166666 |
4 | 10.000 | 6.855 | 852 | 6.003 | 0.685500 | 0.085200 | 0.600300 | 10.660964 | 6.656250 | 11.656311 |
5 | 100.000 | 69.241 | 6.639 | 62.602 | 0.692410 | 0.066390 | 0.626020 | 10.100802 | 7.792253 | 10.428452 |
6 | 1.000.000 | 692.939 | 54.691 | 638.248 | 0.692939 | 0.054691 | 0.638248 | 10.007640 | 8.237837 | 10.195330 |
7 | 10.000.000 | 6.928.252 | 462.523 | 6.465.729 | 0.692825 | 0.046252 | 0.646573 | 9.998358 | 8.457022 | 10.130434 |
8 | 100.000.000 | 69.265.778 | 4.012.168 | 65.253.610 | 0.692658 | 0.040122 | 0.652536 | 9.997583 | 8.674526 | 10.092228 |
9 | 1.000.000.000 | 692.621.726 | 35.422.045 | 657.199.681 | 0.692622 | 0.035422 | 0.657200 | 9.999479 | 8.828654 | 10.071469 |
10 | 10.000.000.000 | 6.926.065.870 | 316.971.647 | 6.609.094.223 | 0.692607 | 0.031697 | 0.660909 | 9.999782 | 8.948429 | 10.056448 |
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 | 1 | 2 | 1.500000 | 0.500000 | 1.000000 | 0.000000 | 0.000000 | 0.000000 |
2 | 4 | 5 | 2 | 3 | 1.250000 | 0.500000 | 0.750000 | 1.666667 | 2.000000 | 1.500000 |
3 | 8 | 9 | 3 | 6 | 1.125000 | 0.375000 | 0.750000 | 1.800000 | 1.500000 | 2.000000 |
4 | 16 | 14 | 5 | 9 | 0.875000 | 0.312500 | 0.562500 | 1.555556 | 1.666667 | 1.500000 |
5 | 32 | 25 | 7 | 18 | 0.781250 | 0.218750 | 0.562500 | 1.785714 | 1.400000 | 2.000000 |
6 | 64 | 25 | 7 | 18 | 0.390625 | 0.109375 | 0.281250 | 1.000000 | 1.000000 | 1.000000 |
7 | 128 | 63 | 21 | 42 | 0.492188 | 0.164062 | 0.328125 | 2.520000 | 3.000000 | 2.333333 |
8 | 256 | 148 | 34 | 114 | 0.578125 | 0.132812 | 0.445312 | 2.349206 | 1.619048 | 2.714286 |
9 | 512 | 321 | 66 | 255 | 0.626953 | 0.128906 | 0.498047 | 2.168919 | 1.941176 | 2.236842 |
10 | 1.024 | 659 | 130 | 529 | 0.643555 | 0.126953 | 0.516602 | 2.052959 | 1.969697 | 2.074510 |
11 | 2.048 | 1.369 | 210 | 1.159 | 0.668457 | 0.102539 | 0.565918 | 2.077390 | 1.615385 | 2.190926 |
12 | 4.096 | 2.783 | 387 | 2.396 | 0.679443 | 0.094482 | 0.584961 | 2.032871 | 1.842857 | 2.067299 |
13 | 8.192 | 5.598 | 714 | 4.884 | 0.683350 | 0.087158 | 0.596191 | 2.011498 | 1.844961 | 2.038397 |
14 | 16.384 | 11.273 | 1.315 | 9.958 | 0.688049 | 0.080261 | 0.607788 | 2.013755 | 1.841737 | 2.038903 |
15 | 32.768 | 22.596 | 2.421 | 20.175 | 0.689575 | 0.073883 | 0.615692 | 2.004435 | 1.841065 | 2.026009 |
16 | 65.536 | 45.276 | 4.537 | 40.739 | 0.690857 | 0.069229 | 0.621628 | 2.003717 | 1.874019 | 2.019281 |
17 | 131.072 | 90.748 | 8.445 | 82.303 | 0.692352 | 0.064430 | 0.627922 | 2.004329 | 1.861362 | 2.020251 |
18 | 262.144 | 181.625 | 15.932 | 165.693 | 0.692844 | 0.060776 | 0.632069 | 2.001421 | 1.886560 | 2.013207 |
19 | 524.288 | 363.277 | 30.082 | 333.195 | 0.692896 | 0.057377 | 0.635519 | 2.000149 | 1.888150 | 2.010918 |
20 | 1.048.576 | 726.563 | 57.146 | 669.417 | 0.692904 | 0.054499 | 0.638406 | 2.000025 | 1.899674 | 2.009085 |
21 | 2.097.152 | 1.453.231 | 108.397 | 1.344.834 | 0.692955 | 0.051688 | 0.641267 | 2.000144 | 1.896843 | 2.008963 |
22 | 4.194.304 | 2.905.960 | 205.851 | 2.700.109 | 0.692835 | 0.049079 | 0.643756 | 1.999655 | 1.899047 | 2.007764 |
23 | 8.388.608 | 5.811.896 | 392.483 | 5.419.413 | 0.692832 | 0.046788 | 0.646044 | 1.999992 | 1.906636 | 2.007109 |
24 | 16.777.216 | 11.622.548 | 750.403 | 10.872.145 | 0.692758 | 0.044728 | 0.648030 | 1.999786 | 1.911938 | 2.006148 |
25 | 33.554.432 | 23.243.402 | 1.436.869 | 21.806.533 | 0.692707 | 0.042822 | 0.649885 | 1.999854 | 1.914796 | 2.005725 |
26 | 67.108.864 | 46.484.744 | 2.756.467 | 43.728.277 | 0.692677 | 0.041075 | 0.651602 | 1.999911 | 1.918384 | 2.005283 |
27 | 134.217.728 | 92.966.487 | 5.295.078 | 87.671.409 | 0.692654 | 0.039451 | 0.653203 | 1.999936 | 1.920966 | 2.004913 |
28 | 268.435.456 | 185.928.276 | 10.191.283 | 175.736.993 | 0.692637 | 0.037965 | 0.654671 | 1.999949 | 1.924671 | 2.004496 |
29 | 536.870.912 | 371.854.614 | 19.638.499 | 352.216.115 | 0.692633 | 0.036580 | 0.656054 | 1.999990 | 1.926990 | 2.004223 |
30 | 1.073.741.824 | 743.697.938 | 37.895.576 | 705.802.362 | 0.692623 | 0.035293 | 0.657330 | 1.999969 | 1.929657 | 2.003890 |
31 | 2.147.483.648 | 1.487.378.446 | 73.212.218 | 1.414.166.228 | 0.692615 | 0.034092 | 0.658522 | 1.999977 | 1.931946 | 2.003629 |
32 | 4.294.967.296 | 2.974.737.112 | 141.599.424 | 2.833.137.688 | 0.692610 | 0.032969 | 0.659641 | 1.999987 | 1.934096 | 2.003398 |
33 | 8.589.934.592 | 5.949.448.294 | 274.180.469 | 5.675.267.825 | 0.692607 | 0.031919 | 0.660688 | 1.999991 | 1.936311 | 2.003174 |
34 | 17.179.869.184 | 11.898.850.358 | 531.428.952 | 11.367.421.406 | 0.692604 | 0.030933 | 0.661671 | 1.999992 | 1.938245 | 2.002975 |
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 | 1 | 0 | 0 | 0 | 0 | 1 |
2 | 4 | 2 | 2 | 0 | 0 | 1 | 0 | 1 |
3 | 8 | 3 | 3 | 0 | 0 | 1 | 1 | 1 |
4 | 16 | 5 | 5 | 0 | 0 | 2 | 1 | 2 |
5 | 32 | 7 | 7 | 0 | 0 | 2 | 2 | 3 |
6 | 64 | 7 | 7 | 0 | 0 | 2 | 2 | 3 |
7 | 128 | 21 | 7 | 14 | 3 | 5 | 5 | 8 |
8 | 256 | 34 | 7 | 27 | 8 | 9 | 6 | 11 |
9 | 512 | 66 | 7 | 59 | 15 | 16 | 17 | 18 |
10 | 1.024 | 130 | 7 | 123 | 30 | 35 | 35 | 30 |
11 | 2.048 | 210 | 7 | 203 | 49 | 53 | 59 | 49 |
12 | 4.096 | 387 | 7 | 379 | 91 | 94 | 106 | 96 |
13 | 8.192 | 714 | 7 | 706 | 170 | 174 | 188 | 182 |
14 | 16.384 | 1.315 | 7 | 1.307 | 316 | 340 | 322 | 337 |
15 | 32.768 | 2.421 | 7 | 2.413 | 609 | 614 | 593 | 605 |
16 | 65.536 | 4.537 | 7 | 4.529 | 1.131 | 1.122 | 1.134 | 1.150 |
17 | 131.072 | 8.445 | 7 | 8.437 | 2.050 | 2.111 | 2.137 | 2.147 |
18 | 262.144 | 15.932 | 7 | 15.924 | 3.953 | 3.979 | 3.997 | 4.003 |
19 | 524.288 | 30.082 | 7 | 30.074 | 7.520 | 7.486 | 7.585 | 7.491 |
20 | 1.048.576 | 57.146 | 7 | 57.138 | 14.292 | 14.224 | 14.371 | 14.259 |
21 | 2.097.152 | 108.397 | 7 | 108.389 | 27.189 | 26.972 | 27.119 | 27.117 |
22 | 4.194.304 | 205.851 | 7 | 205.843 | 51.654 | 51.382 | 51.564 | 51.251 |
23 | 8.388.608 | 392.483 | 7 | 392.475 | 98.205 | 97.943 | 98.362 | 97.973 |
24 | 16.777.216 | 750.403 | 7 | 750.395 | 187.657 | 187.304 | 187.957 | 187.485 |
25 | 33.554.432 | 1.436.869 | 7 | 1.436.861 | 359.048 | 359.265 | 359.740 | 358.816 |
26 | 67.108.864 | 2.756.467 | 7 | 2.756.459 | 688.973 | 688.819 | 689.472 | 689.203 |
27 | 134.217.728 | 5.295.078 | 7 | 5.295.070 | 1.323.603 | 1.324.842 | 1.323.683 | 1.322.950 |
28 | 268.435.456 | 10.191.283 | 7 | 10.191.275 | 2.547.576 | 2.548.078 | 2.548.003 | 2.547.626 |
29 | 536.870.912 | 19.638.499 | 7 | 19.638.491 | 4.906.158 | 4.909.835 | 4.911.301 | 4.911.205 |
30 | 1.073.741.824 | 37.895.576 | 7 | 37.895.568 | 9.471.537 | 9.473.472 | 9.475.747 | 9.474.820 |
31 | 2.147.483.648 | 73.212.218 | 7 | 73.212.210 | 18.301.506 | 18.300.604 | 18.305.700 | 18.304.408 |
32 | 4.294.967.296 | 141.599.424 | 7 | 141.599.416 | 35.396.696 | 35.400.502 | 35.403.235 | 35.398.991 |
33 | 8.589.934.592 | 274.180.469 | 7 | 274.180.461 | 68.541.890 | 68.546.160 | 68.552.532 | 68.539.887 |
34 | 17.179.869.184 | 531.428.952 | 7 | 531.428.944 | 132.853.094 | 132.858.088 | 132.864.842 | 132.852.928 |
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 | 0 | 2 | 2 | 1 | 0 | 0 |
3 | 8 | 6 | 1 | 4 | 2 | 2 | 1 | 1 |
4 | 16 | 9 | 2 | 6 | 2 | 4 | 1 | 2 |
5 | 32 | 18 | 6 | 11 | 4 | 7 | 3 | 4 |
6 | 64 | 18 | 6 | 11 | 4 | 7 | 3 | 4 |
7 | 128 | 42 | 17 | 24 | 9 | 13 | 10 | 10 |
8 | 256 | 114 | 60 | 53 | 24 | 34 | 27 | 29 |
9 | 512 | 255 | 141 | 113 | 59 | 65 | 72 | 59 |
10 | 1.024 | 529 | 281 | 247 | 137 | 128 | 130 | 134 |
11 | 2.048 | 1.159 | 609 | 549 | 281 | 280 | 305 | 293 |
12 | 4.096 | 2.396 | 1.267 | 1.128 | 591 | 608 | 604 | 593 |
13 | 8.192 | 4.884 | 2.555 | 2.328 | 1.223 | 1.212 | 1.225 | 1.224 |
14 | 16.384 | 9.958 | 5.162 | 4.795 | 2.450 | 2.534 | 2.522 | 2.452 |
15 | 32.768 | 20.175 | 10.423 | 9.751 | 4.987 | 5.070 | 5.097 | 5.021 |
16 | 65.536 | 40.739 | 21.107 | 19.631 | 10.086 | 10.320 | 10.195 | 10.138 |
17 | 131.072 | 82.303 | 42.682 | 39.620 | 20.557 | 20.691 | 20.546 | 20.509 |
18 | 262.144 | 165.693 | 85.618 | 80.074 | 41.320 | 41.616 | 41.556 | 41.201 |
19 | 524.288 | 333.195 | 171.880 | 161.314 | 83.261 | 83.224 | 83.608 | 83.102 |
20 | 1.048.576 | 669.417 | 344.462 | 324.954 | 167.428 | 167.340 | 167.827 | 166.822 |
21 | 2.097.152 | 1.344.834 | 690.824 | 654.009 | 336.561 | 336.065 | 336.323 | 335.885 |
22 | 4.194.304 | 2.700.109 | 1.384.281 | 1.315.827 | 674.034 | 676.369 | 675.158 | 674.548 |
23 | 8.388.608 | 5.419.413 | 2.776.839 | 2.642.573 | 1.353.263 | 1.356.915 | 1.354.614 | 1.354.621 |
24 | 16.777.216 | 10.872.145 | 5.565.145 | 5.306.999 | 2.717.482 | 2.719.563 | 2.717.830 | 2.717.270 |
25 | 33.554.432 | 21.806.533 | 11.146.967 | 10.659.565 | 5.449.579 | 5.454.074 | 5.452.354 | 5.450.526 |
26 | 67.108.864 | 43.728.277 | 22.333.394 | 21.394.882 | 10.929.850 | 10.934.257 | 10.931.674 | 10.932.496 |
27 | 134.217.728 | 87.671.409 | 44.736.661 | 42.934.747 | 21.916.776 | 21.919.856 | 21.917.727 | 21.917.050 |
28 | 268.435.456 | 175.736.993 | 89.602.842 | 86.134.150 | 43.930.838 | 43.938.899 | 43.931.692 | 43.935.564 |
29 | 536.870.912 | 352.216.115 | 179.438.876 | 172.777.238 | 88.051.169 | 88.051.040 | 88.056.980 | 88.056.926 |
30 | 1.073.741.824 | 705.802.362 | 359.312.170 | 346.490.191 | 176.447.522 | 176.448.130 | 176.446.686 | 176.460.024 |
31 | 2.147.483.648 | 1.414.166.228 | 719.447.138 | 694.719.089 | 353.541.760 | 353.535.106 | 353.546.903 | 353.542.459 |
32 | 4.294.967.296 | 2.833.137.688 | 1.440.423.076 | 1.392.714.611 | 708.279.964 | 708.270.888 | 708.287.204 | 708.299.632 |
33 | 8.589.934.592 | 5.675.267.825 | 2.883.725.306 | 2.791.542.518 | 1.418.825.567 | 1.418.810.039 | 1.418.803.799 | 1.418.828.420 |
34 | 17.179.869.184 | 11.367.421.406 | 5.772.823.421 | 5.594.597.984 | 2.841.851.568 | 2.841.834.244 | 2.841.833.626 | 2.841.901.968 |