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+1
f(0)=1
f(1)=5
f(2)=11
f(3)=19
f(4)=29
f(5)=41
f(6)=1
f(7)=71
f(8)=89
f(9)=109
f(10)=131
f(11)=31
f(12)=181
f(13)=1
f(14)=239
f(15)=271
f(16)=61
f(17)=1
f(18)=379
f(19)=419
f(20)=461
f(21)=101
f(22)=1
f(23)=599
f(24)=59
f(25)=701
f(26)=151
f(27)=811
f(28)=79
f(29)=929
f(30)=991
f(31)=211
f(32)=1
f(33)=1
f(34)=1259
f(35)=1
f(36)=281
f(37)=1481
f(38)=1559
f(39)=149
f(40)=1721
f(41)=1
f(42)=1
f(43)=1979
f(44)=2069
f(45)=2161
f(46)=1
f(47)=2351
f(48)=1
f(49)=2549
f(50)=241
f(51)=1
f(52)=2861
f(53)=2969
f(54)=3079
f(55)=3191
f(56)=661
f(57)=311
f(58)=3539
f(59)=3659
f(60)=199
f(61)=1
f(62)=139
f(63)=4159
f(64)=4289
f(65)=4421
f(66)=911
f(67)=4691
f(68)=439
f(69)=4969
f(70)=269
f(71)=1051
f(72)=491
f(73)=179
f(74)=1
f(75)=5851
f(76)=1201
f(77)=1
f(78)=1
f(79)=1
f(80)=229
f(81)=1361
f(82)=6971
f(83)=1
f(84)=7309
f(85)=7481
f(86)=1531
f(87)=191
f(88)=8009
f(89)=431
f(90)=761
f(91)=1
f(92)=8741
f(93)=8929
f(94)=829
f(95)=9311
f(96)=1901
f(97)=1
f(98)=521
f(99)=10099
b) Substitution of the polynom
The polynom f(x)=x^2+3x+1 could be written as f(y)= y^2-1.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 | 0 | 9 | 0.900000 | 0.000000 | 0.900000 | ||||||||
2 | 100 | 80 | 30 | 50 | 0.800000 | 0.300000 | 0.500000 | 8.888889 | inf | 5.555555 | |||||
3 | 1000 | 769 | 456 | 313 | 0.769000 | 0.456000 | 0.313000 | 9.612500 | 15.200000 | 6.260000 | |||||
4 | 10000 | 7539 | 5351 | 2188 | 0.753900 | 0.535100 | 0.218800 | 9.803641 | 11.734649 | 6.990416 | |||||
5 | 100000 | 74145 | 57070 | 17075 | 0.741450 | 0.570700 | 0.170750 | 9.834859 | 10.665297 | 7.803931 | |||||
6 | 1000000 | 733061 | 593577 | 139484 | 0.733061 | 0.593577 | 0.139484 | 9.886857 | 10.400859 | 8.168901 | |||||
7 | 10000000 | 7269658 | 6089892 | 1179766 | 0.726966 | 0.608989 | 0.117977 | 9.916853 | 10.259649 | 8.458074 | |||||
8 | 100000000 | 72248977 | 62028899 | 10220078 | 0.722490 | 0.620289 | 0.102201 | 9.938429 | 10.185550 | 8.662801 | |||||
9 | 1000000000 | 719036536 | 628877070 | 90159466 | 0.719037 | 0.628877 | 0.090159 | 9.952204 | 10.138453 | 8.821798 | |||||
10 | 10000000000 | 7162972926 | 6356043941 | 806928985 | 0.716297 | 0.635604 | 0.080693 | 9.961904 | 10.106974 | 8.950020 |
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 | 1 | 0 | 1 | 0.500000 | 0.000000 | 0.500000 | ||||||||
2 | 4 | 3 | 0 | 3 | 0.750000 | 0.000000 | 0.750000 | 3.000000 | -nan | 3.000000 | |||||
3 | 8 | 7 | 0 | 7 | 0.875000 | 0.000000 | 0.875000 | 2.333333 | -nan | 2.333333 | |||||
4 | 16 | 14 | 2 | 12 | 0.875000 | 0.125000 | 0.750000 | 2.000000 | inf | 1.714286 | |||||
5 | 32 | 27 | 7 | 20 | 0.843750 | 0.218750 | 0.625000 | 1.928571 | 3.500000 | 1.666667 | |||||
6 | 64 | 51 | 14 | 37 | 0.796875 | 0.218750 | 0.578125 | 1.888889 | 2.000000 | 1.850000 | |||||
7 | 128 | 102 | 46 | 56 | 0.796875 | 0.359375 | 0.437500 | 2.000000 | 3.285714 | 1.513514 | |||||
8 | 256 | 200 | 95 | 105 | 0.781250 | 0.371094 | 0.410156 | 1.960784 | 2.065217 | 1.875000 | |||||
9 | 512 | 396 | 209 | 187 | 0.773438 | 0.408203 | 0.365234 | 1.980000 | 2.200000 | 1.780952 | |||||
10 | 1024 | 787 | 466 | 321 | 0.768555 | 0.455078 | 0.313477 | 1.987374 | 2.229665 | 1.716578 | |||||
11 | 2048 | 1568 | 1007 | 561 | 0.765625 | 0.491699 | 0.273926 | 1.992376 | 2.160944 | 1.747663 | |||||
12 | 4096 | 3121 | 2125 | 996 | 0.761963 | 0.518799 | 0.243164 | 1.990434 | 2.110228 | 1.775401 | |||||
13 | 8192 | 6186 | 4330 | 1856 | 0.755127 | 0.528564 | 0.226562 | 1.982057 | 2.037647 | 1.863454 | |||||
14 | 16384 | 12325 | 8967 | 3358 | 0.752258 | 0.547302 | 0.204956 | 1.992402 | 2.070901 | 1.809267 | |||||
15 | 32768 | 24481 | 18252 | 6229 | 0.747101 | 0.557007 | 0.190094 | 1.986288 | 2.035463 | 1.854973 | |||||
16 | 65536 | 48741 | 37112 | 11629 | 0.743729 | 0.566284 | 0.177444 | 1.990973 | 2.033311 | 1.866913 | |||||
17 | 131072 | 97002 | 75223 | 21779 | 0.740067 | 0.573906 | 0.166161 | 1.990152 | 2.026918 | 1.872818 | |||||
18 | 262144 | 193389 | 152497 | 40892 | 0.737720 | 0.581730 | 0.155991 | 1.993660 | 2.027266 | 1.877589 | |||||
19 | 524288 | 385401 | 308348 | 77053 | 0.735094 | 0.588127 | 0.146967 | 1.992880 | 2.021994 | 1.884305 | |||||
20 | 1048576 | 768483 | 622746 | 145737 | 0.732882 | 0.593897 | 0.138986 | 1.993983 | 2.019621 | 1.891386 | |||||
21 | 2097152 | 1532748 | 1256632 | 276116 | 0.730871 | 0.599209 | 0.131662 | 1.994511 | 2.017889 | 1.894618 | |||||
22 | 4194304 | 3057847 | 2532325 | 525522 | 0.729048 | 0.603753 | 0.125294 | 1.995010 | 2.015168 | 1.903265 | |||||
23 | 8388608 | 6101716 | 5100388 | 1001328 | 0.727381 | 0.608014 | 0.119368 | 1.995429 | 2.014113 | 1.905397 | |||||
24 | 16777216 | 12177678 | 10265184 | 1912494 | 0.725846 | 0.611853 | 0.113994 | 1.995779 | 2.012628 | 1.909958 | |||||
25 | 33554432 | 24309353 | 20649818 | 3659535 | 0.724475 | 0.615413 | 0.109063 | 1.996222 | 2.011636 | 1.913488 | |||||
26 | 67108864 | 48532488 | 41511491 | 7020997 | 0.723190 | 0.618569 | 0.104621 | 1.996453 | 2.010259 | 1.918549 | |||||
27 | 134217728 | 96905447 | 83420010 | 13485437 | 0.722002 | 0.621527 | 0.100474 | 1.996713 | 2.009564 | 1.920730 | |||||
28 | 268435456 | 193515509 | 167568579 | 25946930 | 0.720901 | 0.624242 | 0.096660 | 1.996952 | 2.008734 | 1.924070 | |||||
29 | 536870912 | 386482508 | 336484899 | 49997609 | 0.719880 | 0.626752 | 0.093128 | 1.997166 | 2.008043 | 1.926918 | |||||
30 | 1073741824 | 771959328 | 675502032 | 96457296 | 0.718943 | 0.629110 | 0.089833 | 1.997398 | 2.007525 | 1.929238 | |||||
31 | 2147483648 | 1542017316 | 1355655925 | 186361391 | 0.718058 | 0.631276 | 0.086781 | 1.997537 | 2.006886 | 1.932061 | |||||
32 | 4294967296 | 3080499427 | 2720037214 | 360462213 | 0.717235 | 0.633308 | 0.083927 | 1.997707 | 2.006436 | 1.934211 | |||||
33 | 8589934592 | 6154350432 | 5456368249 | 697982183 | 0.716461 | 0.635205 | 0.081256 | 1.997842 | 2.005990 | 1.936353 | |||||
34 | 17179869184 | 12296237663 | 10943341636 | 1352896027 | 0.715735 | 0.636986 | 0.078749 | 1.997975 | 2.005609 | 1.938296 | |||||
35 | 34359738368 | 24569120864 | 21944288893 | 2624831971 | 0.715056 | 0.638663 | 0.076393 | 1.998101 | 2.005264 | 1.940158 |
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P |
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 | 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 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 3 | 1 | 2 | 0 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 7 | 2 | 5 | 2 | 2 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 12 | 5 | 7 | 2 | 3 | 3 | 4 | 2 | 2 | 0 | 0 | 0 | 1 | 1 |
5 | 32 | 20 | 8 | 12 | 3 | 6 | 5 | 6 | 7 | 5 | 2 | 0 | 2 | 2 | 3 |
6 | 64 | 37 | 11 | 26 | 8 | 10 | 8 | 11 | 14 | 9 | 5 | 2 | 3 | 4 | 5 |
7 | 128 | 56 | 18 | 38 | 13 | 15 | 14 | 14 | 46 | 23 | 23 | 10 | 13 | 10 | 13 |
8 | 256 | 105 | 33 | 72 | 27 | 31 | 22 | 25 | 95 | 53 | 42 | 16 | 32 | 26 | 21 |
9 | 512 | 187 | 60 | 127 | 46 | 47 | 46 | 48 | 209 | 117 | 92 | 55 | 56 | 46 | 52 |
10 | 1024 | 321 | 100 | 221 | 82 | 80 | 81 | 78 | 466 | 240 | 226 | 104 | 124 | 123 | 115 |
11 | 2048 | 561 | 188 | 373 | 137 | 148 | 140 | 136 | 1007 | 531 | 476 | 240 | 244 | 262 | 261 |
12 | 4096 | 996 | 337 | 659 | 242 | 261 | 261 | 232 | 2125 | 1104 | 1021 | 512 | 519 | 548 | 546 |
13 | 8192 | 1856 | 626 | 1230 | 456 | 486 | 469 | 445 | 4330 | 2247 | 2083 | 1042 | 1098 | 1094 | 1096 |
14 | 16384 | 3358 | 1121 | 2237 | 830 | 873 | 865 | 790 | 8967 | 4694 | 4273 | 2202 | 2248 | 2256 | 2261 |
15 | 32768 | 6229 | 2060 | 4169 | 1553 | 1581 | 1597 | 1498 | 18252 | 9532 | 8720 | 4584 | 4537 | 4554 | 4577 |
16 | 65536 | 11629 | 3840 | 7789 | 2877 | 2895 | 2973 | 2884 | 37112 | 19385 | 17727 | 9235 | 9197 | 9346 | 9334 |
17 | 131072 | 21779 | 7232 | 14547 | 5427 | 5489 | 5483 | 5380 | 75223 | 39124 | 36099 | 18757 | 18850 | 18862 | 18754 |
18 | 262144 | 40892 | 13635 | 27257 | 10136 | 10220 | 10303 | 10233 | 152497 | 79144 | 73353 | 38131 | 38046 | 38287 | 38033 |
19 | 524288 | 77053 | 25708 | 51345 | 19141 | 19222 | 19499 | 19191 | 308348 | 159365 | 148983 | 76851 | 77205 | 77396 | 76896 |
20 | 1048576 | 145737 | 48544 | 97193 | 36383 | 36367 | 36673 | 36314 | 622746 | 321282 | 301464 | 155484 | 155474 | 156180 | 155608 |
21 | 2097152 | 276116 | 92189 | 183927 | 68835 | 68900 | 69447 | 68934 | 1256632 | 646877 | 609755 | 314090 | 313279 | 315102 | 314161 |
22 | 4194304 | 525522 | 175090 | 350432 | 130979 | 131350 | 131538 | 131655 | 2532325 | 1301270 | 1231055 | 633418 | 631782 | 634148 | 632977 |
23 | 8388608 | 1001328 | 333902 | 667426 | 249797 | 250557 | 250438 | 250536 | 5100388 | 2617121 | 2483267 | 1274858 | 1274947 | 1275420 | 1275163 |
24 | 16777216 | 1912494 | 638091 | 1274403 | 477375 | 478423 | 478066 | 478630 | 10265184 | 5261037 | 5004147 | 2565482 | 2568698 | 2565775 | 2565229 |
25 | 33554432 | 3659535 | 1220221 | 2439314 | 914341 | 914224 | 915223 | 915747 | 20649818 | 10573049 | 10076769 | 5163253 | 5163820 | 5162260 | 5160485 |
26 | 67108864 | 7020997 | 2341449 | 4679548 | 1754726 | 1755141 | 1755577 | 1755553 | 41511491 | 21230172 | 20281319 | 10377643 | 10378025 | 10378190 | 10377633 |
27 | 134217728 | 13485437 | 4498098 | 8987339 | 3370977 | 3370000 | 3373648 | 3370812 | 83420010 | 42619863 | 40800147 | 20857128 | 20853908 | 20852253 | 20856721 |
28 | 268435456 | 25946930 | 8650127 | 17296803 | 6486066 | 6485099 | 6489171 | 6486594 | 167568579 | 85525121 | 82043458 | 41896566 | 41891986 | 41888821 | 41891206 |
29 | 536870912 | 49997609 | 16668406 | 33329203 | 12496473 | 12499863 | 12502980 | 12498293 | 336484899 | 171596924 | 164887975 | 84122619 | 84124092 | 84121393 | 84116795 |
30 | 1073741824 | 96457296 | 32155383 | 64301913 | 24112275 | 24113586 | 24117612 | 24113823 | 675502032 | 344211141 | 331290891 | 168873783 | 168881978 | 168882449 | 168863822 |
31 | 2147483648 | 186361391 | 62124339 | 124237052 | 46590812 | 46588196 | 46592772 | 46589611 | 1355655925 | 690293653 | 665362272 | 338904565 | 338914861 | 338936040 | 338900459 |
32 | 4294967296 | 360462213 | 120158204 | 240304009 | 90117543 | 90109289 | 90114903 | 90120478 | 2720037214 | 1384098038 | 1335939176 | 679998048 | 679983145 | 680048073 | 680007948 |
33 | 8589934592 | 697982183 | 232667389 | 465314794 | 174495473 | 174480577 | 174499431 | 174506702 | 5456368249 | 2774741760 | 2681626489 | 1364049636 | 1364051876 | 1364146876 | 1364119861 |
34 | 17179869184 | 1352896027 | 450973404 | 901922623 | 338235896 | 338205645 | 338228665 | 338225821 | 10943341636 | 5561818377 | 5381523259 | 2735806560 | 2735821742 | 2735904298 | 2735809036 |
35 | 34359738368 | 2624831971 | 874939657 | 1749892314 | 656210925 | 656191359 | 656210016 | 656219671 | 21944288893 | 11146758934 | 10797529959 | 5486047693 | 5486107546 | 5486102644 | 5486031010 |