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+163
f(0)=163
f(1)=41
f(2)=167
f(3)=43
f(4)=179
f(5)=47
f(6)=199
f(7)=53
f(8)=227
f(9)=61
f(10)=263
f(11)=71
f(12)=307
f(13)=83
f(14)=359
f(15)=97
f(16)=419
f(17)=113
f(18)=487
f(19)=131
f(20)=563
f(21)=151
f(22)=647
f(23)=173
f(24)=739
f(25)=197
f(26)=839
f(27)=223
f(28)=947
f(29)=251
f(30)=1063
f(31)=281
f(32)=1187
f(33)=313
f(34)=1319
f(35)=347
f(36)=1459
f(37)=383
f(38)=1607
f(39)=421
f(40)=1
f(41)=461
f(42)=1
f(43)=503
f(44)=2099
f(45)=547
f(46)=1
f(47)=593
f(48)=2467
f(49)=641
f(50)=2663
f(51)=691
f(52)=1
f(53)=743
f(54)=3079
f(55)=797
f(56)=3299
f(57)=853
f(58)=3527
f(59)=911
f(60)=1
f(61)=971
f(62)=4007
f(63)=1033
f(64)=4259
f(65)=1097
f(66)=4519
f(67)=1163
f(68)=4787
f(69)=1231
f(70)=1
f(71)=1301
f(72)=5347
f(73)=1373
f(74)=5639
f(75)=1447
f(76)=5939
f(77)=1523
f(78)=6247
f(79)=1601
f(80)=6563
f(81)=1
f(82)=1
f(83)=1
f(84)=7219
f(85)=1847
f(86)=7559
f(87)=1933
f(88)=7907
f(89)=1
f(90)=8263
f(91)=2111
f(92)=8627
f(93)=2203
f(94)=8999
f(95)=2297
f(96)=1
f(97)=2393
f(98)=9767
f(99)=1
b) Substitution of the polynom
The polynom f(x)=x^2+163 could be written as f(y)= y^2+163 with x=y+0
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+0
f'(x)>2x-1 with x > 13
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 | 11 | 0 | 1.100000 | 1.100000 | 1.100000 | |||
2 | 100 | 89 | 89 | 0 | 0.890000 | 0.890000 | 0.890000 | 8.090909 | 8.090909 | -nan |
3 | 1.000 | 828 | 616 | 212 | 0.828000 | 0.616000 | 0.828000 | 9.303370 | 6.921348 | inf |
4 | 10.000 | 8.014 | 4.301 | 3.713 | 0.801400 | 0.430100 | 0.801400 | 9.678744 | 6.982143 | 17.514151 |
5 | 100.000 | 77.749 | 33.074 | 44.675 | 0.777490 | 0.330740 | 0.777490 | 9.701647 | 7.689839 | 12.032049 |
6 | 1.000.000 | 762.307 | 268.954 | 493.353 | 0.762307 | 0.268954 | 0.762307 | 9.804718 | 8.131886 | 11.043156 |
7 | 10.000.000 | 7.518.017 | 2.261.339 | 5.256.678 | 0.751802 | 0.226134 | 0.751802 | 9.862190 | 8.407903 | 10.655004 |
8 | 100.000.000 | 74.401.099 | 19.531.700 | 54.869.399 | 0.744011 | 0.195317 | 0.744011 | 9.896373 | 8.637228 | 10.438037 |
9 | 1.000.000.000 | 738.087.517 | 171.903.430 | 566.184.087 | 0.738087 | 0.171903 | 0.738087 | 9.920384 | 8.801252 | 10.318758 |
10 | 10.000.000.000 | 7.334.006.609 | 1.535.355.686 | 5.798.650.923 | 0.733401 | 0.153536 | 0.733401 | 9.936501 | 8.931501 | 10.241635 |
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 | |||
2 | 4 | 5 | 5 | 0 | 1.250000 | 1.250000 | 0.000000 | 1.666667 | 1.666667 | -nan |
3 | 8 | 9 | 9 | 0 | 1.125000 | 1.125000 | 0.000000 | 1.800000 | 1.800000 | -nan |
4 | 16 | 17 | 17 | 0 | 1.062500 | 1.062500 | 0.000000 | 1.888889 | 1.888889 | -nan |
5 | 32 | 33 | 33 | 0 | 1.031250 | 1.031250 | 0.000000 | 1.941176 | 1.941176 | -nan |
6 | 64 | 60 | 60 | 0 | 0.937500 | 0.937500 | 0.000000 | 1.818182 | 1.818182 | -nan |
7 | 128 | 115 | 112 | 3 | 0.898438 | 0.875000 | 0.023438 | 1.916667 | 1.866667 | inf |
8 | 256 | 219 | 200 | 19 | 0.855469 | 0.781250 | 0.074219 | 1.904348 | 1.785714 | 6.333333 |
9 | 512 | 428 | 353 | 75 | 0.835938 | 0.689453 | 0.146484 | 1.954338 | 1.765000 | 3.947368 |
10 | 1.024 | 847 | 628 | 219 | 0.827148 | 0.613281 | 0.213867 | 1.978972 | 1.779037 | 2.920000 |
11 | 2.048 | 1.676 | 1.126 | 550 | 0.818359 | 0.549805 | 0.268555 | 1.978749 | 1.792994 | 2.511415 |
12 | 4.096 | 3.319 | 1.996 | 1.323 | 0.810303 | 0.487305 | 0.322998 | 1.980310 | 1.772647 | 2.405455 |
13 | 8.192 | 6.585 | 3.628 | 2.957 | 0.803833 | 0.442871 | 0.360962 | 1.984031 | 1.817635 | 2.235072 |
14 | 16.384 | 13.015 | 6.628 | 6.387 | 0.794373 | 0.404541 | 0.389832 | 1.976462 | 1.826902 | 2.159959 |
15 | 32.768 | 25.787 | 12.245 | 13.542 | 0.786957 | 0.373688 | 0.413269 | 1.981329 | 1.847465 | 2.120244 |
16 | 65.536 | 51.229 | 22.631 | 28.598 | 0.781693 | 0.345322 | 0.436371 | 1.986621 | 1.848183 | 2.111800 |
17 | 131.072 | 101.690 | 42.243 | 59.447 | 0.775833 | 0.322289 | 0.453545 | 1.985008 | 1.866599 | 2.078712 |
18 | 262.144 | 201.945 | 79.183 | 122.762 | 0.770359 | 0.302059 | 0.468300 | 1.985888 | 1.874464 | 2.065066 |
19 | 524.288 | 401.589 | 148.728 | 252.861 | 0.765970 | 0.283676 | 0.482294 | 1.988606 | 1.878282 | 2.059766 |
20 | 1.048.576 | 799.035 | 280.867 | 518.168 | 0.762019 | 0.267856 | 0.494164 | 1.989684 | 1.888461 | 2.049221 |
21 | 2.097.152 | 1.590.905 | 531.177 | 1.059.728 | 0.758603 | 0.253285 | 0.505318 | 1.991033 | 1.891205 | 2.045144 |
22 | 4.194.304 | 3.168.412 | 1.008.196 | 2.160.216 | 0.755408 | 0.240373 | 0.515036 | 1.991578 | 1.898041 | 2.038463 |
23 | 8.388.608 | 6.312.489 | 1.920.027 | 4.392.462 | 0.752507 | 0.228885 | 0.523622 | 1.992319 | 1.904418 | 2.033344 |
24 | 16.777.216 | 12.580.214 | 3.663.436 | 8.916.778 | 0.749839 | 0.218358 | 0.531481 | 1.992909 | 1.908013 | 2.030018 |
25 | 33.554.432 | 25.079.112 | 7.006.119 | 18.072.993 | 0.747416 | 0.208799 | 0.538617 | 1.993536 | 1.912445 | 2.026852 |
26 | 67.108.864 | 50.008.474 | 13.424.634 | 36.583.840 | 0.745184 | 0.200043 | 0.545142 | 1.994029 | 1.916130 | 2.024227 |
27 | 134.217.728 | 99.746.301 | 25.767.348 | 73.978.953 | 0.743168 | 0.191982 | 0.551186 | 1.994588 | 1.919408 | 2.022176 |
28 | 268.435.456 | 198.986.691 | 49.538.601 | 149.448.090 | 0.741283 | 0.184546 | 0.556738 | 1.994928 | 1.922534 | 2.020144 |
29 | 536.870.912 | 397.041.137 | 95.377.255 | 301.663.882 | 0.739547 | 0.177654 | 0.561893 | 1.995315 | 1.925312 | 2.018519 |
30 | 1.073.741.824 | 792.343.269 | 183.901.069 | 608.442.200 | 0.737927 | 0.171271 | 0.566656 | 1.995620 | 1.928144 | 2.016954 |
31 | 2.147.483.648 | 1.581.443.065 | 355.049.906 | 1.226.393.159 | 0.736417 | 0.165333 | 0.571084 | 1.995906 | 1.930657 | 2.015628 |
32 | 4.294.967.296 | 3.156.817.961 | 686.322.881 | 2.470.495.080 | 0.735004 | 0.159797 | 0.575207 | 1.996163 | 1.933032 | 2.014440 |
33 | 8.589.934.592 | 6.302.254.046 | 1.328.221.309 | 4.974.032.737 | 0.733679 | 0.154625 | 0.579054 | 1.996395 | 1.935272 | 2.013375 |
34 | 17.179.869.184 | 12.583.174.610 | 2.573.130.410 | 10.010.044.200 | 0.732437 | 0.149776 | 0.582661 | 1.996615 | 1.937275 | 2.012460 |
35 | 34.359.738.368 | 25.126.178.502 | 4.989.810.499 | 20.136.368.003 | 0.731268 | 0.145223 | 0.586045 | 1.996808 | 1.939198 | 2.011616 |
36 | 68.719.476.736 | 50.176.715.014 | 9.685.152.523 | 40.491.562.491 | 0.730167 | 0.140938 | 0.589230 | 1.996990 | 1.940986 | 2.010867 |
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 | 1 | 2 | 1 | 1 | 0 | 1 |
2 | 4 | 5 | 2 | 3 | 1 | 3 | 0 | 1 |
3 | 8 | 9 | 3 | 6 | 1 | 4 | 1 | 3 |
4 | 16 | 17 | 6 | 11 | 2 | 7 | 2 | 6 |
5 | 32 | 33 | 11 | 22 | 4 | 13 | 4 | 12 |
6 | 64 | 60 | 20 | 40 | 8 | 22 | 8 | 22 |
7 | 128 | 112 | 37 | 75 | 14 | 41 | 15 | 42 |
8 | 256 | 200 | 67 | 133 | 26 | 72 | 27 | 75 |
9 | 512 | 353 | 120 | 233 | 46 | 130 | 47 | 130 |
10 | 1.024 | 628 | 208 | 420 | 81 | 232 | 85 | 230 |
11 | 2.048 | 1.126 | 375 | 751 | 149 | 414 | 146 | 417 |
12 | 4.096 | 1.996 | 658 | 1.338 | 266 | 736 | 258 | 736 |
13 | 8.192 | 3.628 | 1.218 | 2.410 | 479 | 1.339 | 462 | 1.348 |
14 | 16.384 | 6.628 | 2.208 | 4.420 | 859 | 2.441 | 859 | 2.469 |
15 | 32.768 | 12.245 | 4.106 | 8.139 | 1.598 | 4.508 | 1.589 | 4.550 |
16 | 65.536 | 22.631 | 7.558 | 15.073 | 2.942 | 8.332 | 2.952 | 8.405 |
17 | 131.072 | 42.243 | 14.036 | 28.207 | 5.486 | 15.633 | 5.434 | 15.690 |
18 | 262.144 | 79.183 | 26.335 | 52.848 | 10.148 | 29.404 | 10.180 | 29.451 |
19 | 524.288 | 148.728 | 49.573 | 99.155 | 19.103 | 55.228 | 19.135 | 55.262 |
20 | 1.048.576 | 280.867 | 93.767 | 187.100 | 36.093 | 104.389 | 36.119 | 104.266 |
21 | 2.097.152 | 531.177 | 177.103 | 354.074 | 68.365 | 197.275 | 68.245 | 197.292 |
22 | 4.194.304 | 1.008.196 | 336.134 | 672.062 | 129.309 | 374.675 | 129.385 | 374.827 |
23 | 8.388.608 | 1.920.027 | 639.910 | 1.280.117 | 245.604 | 714.463 | 245.701 | 714.259 |
24 | 16.777.216 | 3.663.436 | 1.221.523 | 2.441.913 | 468.459 | 1.362.899 | 468.495 | 1.363.583 |
25 | 33.554.432 | 7.006.119 | 2.335.707 | 4.670.412 | 895.009 | 2.608.076 | 894.643 | 2.608.391 |
26 | 67.108.864 | 13.424.634 | 4.475.722 | 8.948.912 | 1.714.275 | 4.999.659 | 1.712.733 | 4.997.967 |
27 | 134.217.728 | 25.767.348 | 8.591.108 | 17.176.240 | 3.286.309 | 9.597.262 | 3.285.513 | 9.598.264 |
28 | 268.435.456 | 49.538.601 | 16.514.746 | 33.023.855 | 6.313.508 | 18.457.975 | 6.313.158 | 18.453.960 |
29 | 536.870.912 | 95.377.255 | 31.791.118 | 63.586.137 | 12.142.866 | 35.547.087 | 12.145.159 | 35.542.143 |
30 | 1.073.741.824 | 183.901.069 | 61.297.693 | 122.603.376 | 23.405.241 | 68.548.797 | 23.402.012 | 68.545.019 |
31 | 2.147.483.648 | 355.049.906 | 118.349.505 | 236.700.401 | 45.154.900 | 132.381.076 | 45.147.800 | 132.366.130 |
32 | 4.294.967.296 | 686.322.881 | 228.783.782 | 457.539.099 | 87.231.356 | 255.933.929 | 87.226.319 | 255.931.277 |
33 | 8.589.934.592 | 1.328.221.309 | 442.752.180 | 885.469.129 | 168.712.195 | 495.390.401 | 168.714.314 | 495.404.399 |
34 | 17.179.869.184 | 2.573.130.410 | 857.730.022 | 1.715.400.388 | 326.695.765 | 959.878.823 | 326.671.815 | 959.884.007 |
35 | 34.359.738.368 | 4.989.810.499 | 1.663.294.885 | 3.326.515.614 | 633.205.369 | 1.861.700.812 | 633.178.147 | 1.861.726.171 |
36 | 68.719.476.736 | 9.685.152.523 | 3.228.407.876 | 6.456.744.647 | 1.228.482.279 | 3.614.077.630 | 1.228.455.988 | 3.614.136.626 |
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 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 64 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 128 | 3 | 3 | 0 | 0 | 1 | 1 | 1 |
8 | 256 | 19 | 15 | 4 | 6 | 4 | 5 | 4 |
9 | 512 | 75 | 45 | 30 | 15 | 15 | 27 | 18 |
10 | 1.024 | 219 | 123 | 96 | 54 | 50 | 61 | 54 |
11 | 2.048 | 550 | 302 | 248 | 155 | 125 | 146 | 124 |
12 | 4.096 | 1.323 | 713 | 610 | 362 | 308 | 352 | 301 |
13 | 8.192 | 2.957 | 1.560 | 1.397 | 772 | 687 | 789 | 709 |
14 | 16.384 | 6.387 | 3.350 | 3.037 | 1.664 | 1.511 | 1.683 | 1.529 |
15 | 32.768 | 13.542 | 7.119 | 6.423 | 3.500 | 3.234 | 3.486 | 3.322 |
16 | 65.536 | 28.598 | 14.912 | 13.686 | 7.417 | 6.857 | 7.354 | 6.970 |
17 | 131.072 | 59.447 | 30.801 | 28.646 | 15.356 | 14.356 | 15.307 | 14.428 |
18 | 262.144 | 122.762 | 63.210 | 59.552 | 31.578 | 29.678 | 31.722 | 29.784 |
19 | 524.288 | 252.861 | 129.976 | 122.885 | 64.821 | 61.640 | 64.845 | 61.555 |
20 | 1.048.576 | 518.168 | 265.698 | 252.470 | 132.628 | 126.560 | 132.419 | 126.561 |
21 | 2.097.152 | 1.059.728 | 542.480 | 517.248 | 270.509 | 259.773 | 270.438 | 259.008 |
22 | 4.194.304 | 2.160.216 | 1.104.402 | 1.055.814 | 550.285 | 529.792 | 550.564 | 529.575 |
23 | 8.388.608 | 4.392.462 | 2.242.715 | 2.149.747 | 1.117.276 | 1.078.479 | 1.117.930 | 1.078.777 |
24 | 16.777.216 | 8.916.778 | 4.546.552 | 4.370.226 | 2.265.982 | 2.192.913 | 2.266.351 | 2.191.532 |
25 | 33.554.432 | 18.072.993 | 9.202.404 | 8.870.589 | 4.587.275 | 4.450.247 | 4.588.575 | 4.446.896 |
26 | 67.108.864 | 36.583.840 | 18.607.276 | 17.976.564 | 9.279.229 | 9.013.881 | 9.281.234 | 9.009.496 |
27 | 134.217.728 | 73.978.953 | 37.598.184 | 36.380.769 | 18.753.807 | 18.237.925 | 18.749.488 | 18.237.733 |
28 | 268.435.456 | 149.448.090 | 75.892.597 | 73.555.493 | 37.855.559 | 36.873.677 | 37.848.302 | 36.870.552 |
29 | 536.870.912 | 301.663.882 | 153.075.036 | 148.588.846 | 76.362.535 | 74.469.203 | 76.358.796 | 74.473.348 |
30 | 1.073.741.824 | 608.442.200 | 308.516.532 | 299.925.668 | 153.924.247 | 150.293.806 | 153.924.388 | 150.299.759 |
31 | 2.147.483.648 | 1.226.393.159 | 621.455.404 | 604.937.755 | 310.081.642 | 303.115.104 | 310.073.976 | 303.122.437 |
32 | 4.294.967.296 | 2.470.495.080 | 1.251.148.873 | 1.219.346.207 | 624.316.861 | 610.935.383 | 624.327.284 | 610.915.552 |
33 | 8.589.934.592 | 4.974.032.737 | 2.517.684.431 | 2.456.348.306 | 1.256.420.711 | 1.230.601.798 | 1.256.434.285 | 1.230.575.943 |
34 | 17.179.869.184 | 10.010.044.200 | 5.064.292.741 | 4.945.751.459 | 2.527.435.270 | 2.477.567.072 | 2.527.474.794 | 2.477.567.064 |
35 | 34.359.738.368 | 20.136.368.003 | 10.182.801.550 | 9.953.566.453 | 5.082.291.048 | 4.985.848.419 | 5.082.390.840 | 4.985.837.696 |
36 | 68.719.476.736 | 40.491.562.491 | 20.467.539.099 | 20.024.023.392 | 10.216.145.612 | 10.029.550.221 | 10.216.431.718 | 10.029.434.940 |