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+1x+5
f(0)=5
f(1)=7
f(2)=11
f(3)=17
f(4)=1
f(5)=1
f(6)=47
f(7)=61
f(8)=1
f(9)=19
f(10)=23
f(11)=137
f(12)=1
f(13)=1
f(14)=43
f(15)=1
f(16)=277
f(17)=311
f(18)=347
f(19)=1
f(20)=1
f(21)=467
f(22)=73
f(23)=557
f(24)=1
f(25)=131
f(26)=101
f(27)=761
f(28)=1
f(29)=1
f(30)=1
f(31)=997
f(32)=1061
f(33)=1
f(34)=239
f(35)=1
f(36)=191
f(37)=83
f(38)=1487
f(39)=313
f(40)=1
f(41)=157
f(42)=1811
f(43)=271
f(44)=397
f(45)=1
f(46)=197
f(47)=1
f(48)=2357
f(49)=491
f(50)=1
f(51)=2657
f(52)=251
f(53)=1
f(54)=1
f(55)=617
f(56)=139
f(57)=1
f(58)=149
f(59)=709
f(60)=733
f(61)=541
f(62)=3911
f(63)=367
f(64)=1
f(65)=859
f(66)=233
f(67)=4561
f(68)=1
f(69)=967
f(70)=199
f(71)=1
f(72)=5261
f(73)=5407
f(74)=1
f(75)=163
f(76)=5857
f(77)=6011
f(78)=881
f(79)=1
f(80)=1297
f(81)=1
f(82)=1
f(83)=6977
f(84)=1429
f(85)=1
f(86)=7487
f(87)=1
f(88)=461
f(89)=229
f(90)=1
f(91)=8377
f(92)=1223
f(93)=8747
f(94)=1787
f(95)=1
f(96)=1
f(97)=9511
f(98)=571
f(99)=283
b) Substitution of the polynom
The polynom f(x)=x^2+1x+5 could be written as f(y)= y^2+4.75 with x=y-0.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+0.5
f'(x)>2x
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 | 8 | 1 | 7 | 0.800000 | 0.100000 | 0.700000 | ||||||||
2 | 100 | 67 | 36 | 31 | 0.670000 | 0.360000 | 0.310000 | 8.375000 | 36.000000 | 4.428571 | |||||
3 | 1000 | 688 | 522 | 166 | 0.688000 | 0.522000 | 0.166000 | 10.268657 | 14.500000 | 5.354839 | |||||
4 | 10000 | 6913 | 5704 | 1209 | 0.691300 | 0.570400 | 0.120900 | 10.047965 | 10.927203 | 7.283133 | |||||
5 | 100000 | 69235 | 60148 | 9087 | 0.692350 | 0.601480 | 0.090870 | 10.015189 | 10.544881 | 7.516129 | |||||
6 | 1000000 | 692815 | 618756 | 74059 | 0.692815 | 0.618756 | 0.074059 | 10.006717 | 10.287225 | 8.149995 | |||||
7 | 10000000 | 6923342 | 6296883 | 626459 | 0.692334 | 0.629688 | 0.062646 | 9.993060 | 10.176682 | 8.458918 | |||||
8 | 100000000 | 69234426 | 63803253 | 5431173 | 0.692344 | 0.638032 | 0.054312 | 10.000145 | 10.132513 | 8.669639 | |||||
9 | 1000000000 | 692318823 | 644410473 | 47908350 | 0.692319 | 0.644410 | 0.047908 | 9.999633 | 10.099963 | 8.820995 | |||||
10 | 10000000000 | 6923109628 | 6494363903 | 428745725 | 0.692311 | 0.649436 | 0.042875 | 9.999886 | 10.077991 | 8.949290 |
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 | 0 | 3 | 1.500000 | 0.000000 | 1.500000 | ||||||||
2 | 4 | 4 | 0 | 4 | 1.000000 | 0.000000 | 1.000000 | 1.333333 | -nan | 1.333333 | |||||
3 | 8 | 6 | 0 | 6 | 0.750000 | 0.000000 | 0.750000 | 1.500000 | -nan | 1.500000 | |||||
4 | 16 | 11 | 2 | 9 | 0.687500 | 0.125000 | 0.562500 | 1.833333 | inf | 1.500000 | |||||
5 | 32 | 21 | 5 | 16 | 0.656250 | 0.156250 | 0.500000 | 1.909091 | 2.500000 | 1.777778 | |||||
6 | 64 | 43 | 22 | 21 | 0.671875 | 0.343750 | 0.328125 | 2.047619 | 4.400000 | 1.312500 | |||||
7 | 128 | 86 | 50 | 36 | 0.671875 | 0.390625 | 0.281250 | 2.000000 | 2.272727 | 1.714286 | |||||
8 | 256 | 175 | 115 | 60 | 0.683594 | 0.449219 | 0.234375 | 2.034884 | 2.300000 | 1.666667 | |||||
9 | 512 | 353 | 261 | 92 | 0.689453 | 0.509766 | 0.179688 | 2.017143 | 2.269565 | 1.533333 | |||||
10 | 1024 | 706 | 535 | 171 | 0.689453 | 0.522461 | 0.166992 | 2.000000 | 2.049809 | 1.858696 | |||||
11 | 2048 | 1407 | 1090 | 317 | 0.687012 | 0.532227 | 0.154785 | 1.992918 | 2.037383 | 1.853801 | |||||
12 | 4096 | 2822 | 2249 | 573 | 0.688965 | 0.549072 | 0.139893 | 2.005686 | 2.063303 | 1.807571 | |||||
13 | 8192 | 5658 | 4637 | 1021 | 0.690674 | 0.566040 | 0.124634 | 2.004961 | 2.061805 | 1.781850 | |||||
14 | 16384 | 11363 | 9515 | 1848 | 0.693542 | 0.580750 | 0.112793 | 2.008307 | 2.051973 | 1.809990 | |||||
15 | 32768 | 22705 | 19380 | 3325 | 0.692902 | 0.591431 | 0.101471 | 1.998152 | 2.036784 | 1.799242 | |||||
16 | 65536 | 45394 | 39178 | 6216 | 0.692657 | 0.597809 | 0.094849 | 1.999295 | 2.021569 | 1.869474 | |||||
17 | 131072 | 90716 | 79101 | 11615 | 0.692108 | 0.603493 | 0.088615 | 1.998414 | 2.019016 | 1.868565 | |||||
18 | 262144 | 181576 | 159867 | 21709 | 0.692657 | 0.609844 | 0.082813 | 2.001587 | 2.021049 | 1.869049 | |||||
19 | 524288 | 363070 | 322127 | 40943 | 0.692501 | 0.614408 | 0.078093 | 1.999548 | 2.014969 | 1.885992 | |||||
20 | 1048576 | 726467 | 649129 | 77338 | 0.692813 | 0.619058 | 0.073755 | 2.000901 | 2.015134 | 1.888919 | |||||
21 | 2097152 | 1452286 | 1305804 | 146482 | 0.692504 | 0.622656 | 0.069848 | 1.999108 | 2.011625 | 1.894050 | |||||
22 | 4194304 | 2904750 | 2626087 | 278663 | 0.692546 | 0.626108 | 0.066438 | 2.000123 | 2.011088 | 1.902370 | |||||
23 | 8388608 | 5808161 | 5276770 | 531391 | 0.692387 | 0.629040 | 0.063347 | 1.999539 | 2.009366 | 1.906931 | |||||
24 | 16777216 | 11616806 | 10600925 | 1015881 | 0.692416 | 0.631864 | 0.060551 | 2.000083 | 2.008980 | 1.911739 | |||||
25 | 33554432 | 23232242 | 21286601 | 1945641 | 0.692375 | 0.634390 | 0.057985 | 1.999882 | 2.007995 | 1.915225 | |||||
26 | 67108864 | 46462543 | 42731020 | 3731523 | 0.692346 | 0.636742 | 0.055604 | 1.999917 | 2.007414 | 1.917889 | |||||
27 | 134217728 | 92923062 | 85755032 | 7168030 | 0.692331 | 0.638925 | 0.053406 | 1.999956 | 2.006857 | 1.920940 | |||||
28 | 268435456 | 185844986 | 172057992 | 13786994 | 0.692327 | 0.640966 | 0.051361 | 1.999988 | 2.006389 | 1.923401 | |||||
29 | 536870912 | 371687163 | 345124284 | 26562879 | 0.692321 | 0.642844 | 0.049477 | 1.999985 | 2.005860 | 1.926662 | |||||
30 | 1073741824 | 743369511 | 692115698 | 51253813 | 0.692317 | 0.644583 | 0.047734 | 1.999987 | 2.005410 | 1.929528 | |||||
31 | 2147483648 | 1486732086 | 1387706036 | 99026050 | 0.692314 | 0.646201 | 0.046113 | 1.999991 | 2.005020 | 1.932072 | |||||
32 | 4294967296 | 2973444940 | 2781900304 | 191544636 | 0.692309 | 0.647712 | 0.044597 | 1.999987 | 2.004676 | 1.934285 | |||||
33 | 8589934592 | 5946893696 | 5576029188 | 370864508 | 0.692310 | 0.649135 | 0.043174 | 2.000001 | 2.004396 | 1.936178 | |||||
34 | 17179869184 | 11893846944 | 11175005042 | 718841902 | 0.692313 | 0.650471 | 0.041842 | 2.000010 | 2.004115 | 1.938287 | |||||
35 | 34359738368 | 23787840868 | 22393163066 | 1394677802 | 0.692317 | 0.651727 | 0.040590 | 2.000012 | 2.003862 | 1.940173 |
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 | 3 | 1 | 2 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 4 | 1 | 3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 6 | 2 | 4 | 1 | 1 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 9 | 3 | 6 | 2 | 1 | 3 | 3 | 2 | 1 | 1 | 0 | 1 | 0 | 1 |
5 | 32 | 16 | 4 | 12 | 3 | 3 | 6 | 4 | 5 | 2 | 3 | 1 | 2 | 1 | 1 |
6 | 64 | 21 | 4 | 17 | 4 | 4 | 7 | 6 | 22 | 11 | 11 | 3 | 6 | 8 | 5 |
7 | 128 | 36 | 10 | 26 | 10 | 6 | 9 | 11 | 50 | 28 | 22 | 9 | 15 | 15 | 11 |
8 | 256 | 60 | 19 | 41 | 15 | 11 | 17 | 17 | 115 | 60 | 55 | 22 | 33 | 31 | 29 |
9 | 512 | 92 | 32 | 60 | 25 | 21 | 23 | 23 | 261 | 140 | 121 | 51 | 64 | 71 | 75 |
10 | 1024 | 171 | 61 | 110 | 44 | 41 | 42 | 44 | 535 | 281 | 254 | 130 | 130 | 137 | 138 |
11 | 2048 | 317 | 111 | 206 | 87 | 80 | 74 | 76 | 1090 | 566 | 524 | 261 | 290 | 259 | 280 |
12 | 4096 | 573 | 204 | 369 | 154 | 143 | 134 | 142 | 2249 | 1166 | 1083 | 556 | 584 | 546 | 563 |
13 | 8192 | 1021 | 340 | 681 | 247 | 253 | 258 | 263 | 4637 | 2346 | 2291 | 1156 | 1197 | 1131 | 1153 |
14 | 16384 | 1848 | 622 | 1226 | 461 | 456 | 469 | 462 | 9515 | 4907 | 4608 | 2375 | 2414 | 2352 | 2374 |
15 | 32768 | 3325 | 1129 | 2196 | 847 | 822 | 832 | 824 | 19380 | 9985 | 9395 | 4797 | 4861 | 4843 | 4879 |
16 | 65536 | 6216 | 2091 | 4125 | 1569 | 1572 | 1548 | 1527 | 39178 | 20218 | 18960 | 9685 | 9871 | 9800 | 9822 |
17 | 131072 | 11615 | 3879 | 7736 | 2934 | 2909 | 2888 | 2884 | 79101 | 40359 | 38742 | 19614 | 19856 | 19831 | 19800 |
18 | 262144 | 21709 | 7279 | 14430 | 5492 | 5461 | 5390 | 5366 | 159867 | 81451 | 78416 | 39821 | 40071 | 40049 | 39926 |
19 | 524288 | 40943 | 13680 | 27263 | 10295 | 10365 | 10144 | 10139 | 322127 | 164252 | 157875 | 80588 | 80462 | 80501 | 80576 |
20 | 1048576 | 77338 | 25761 | 51577 | 19446 | 19458 | 19306 | 19128 | 649129 | 330765 | 318364 | 162392 | 162122 | 162325 | 162290 |
21 | 2097152 | 146482 | 48866 | 97616 | 36684 | 36849 | 36562 | 36387 | 1305804 | 664911 | 640893 | 326510 | 326439 | 326399 | 326456 |
22 | 4194304 | 278663 | 92890 | 185773 | 69583 | 69757 | 69720 | 69603 | 2626087 | 1336781 | 1289306 | 656239 | 656121 | 657231 | 656496 |
23 | 8388608 | 531391 | 177255 | 354136 | 132933 | 132690 | 133109 | 132659 | 5276770 | 2683560 | 2593210 | 1318681 | 1318715 | 1319460 | 1319914 |
24 | 16777216 | 1015881 | 339052 | 676829 | 253907 | 253871 | 254230 | 253873 | 10600925 | 5384541 | 5216384 | 2649152 | 2649153 | 2651468 | 2651152 |
25 | 33554432 | 1945641 | 649278 | 1296363 | 486464 | 486712 | 486318 | 486147 | 21286601 | 10804425 | 10482176 | 5322693 | 5321973 | 5321592 | 5320343 |
26 | 67108864 | 3731523 | 1244632 | 2486891 | 932685 | 933736 | 931803 | 933299 | 42731020 | 21671549 | 21059471 | 10681298 | 10683308 | 10683551 | 10682863 |
27 | 134217728 | 7168030 | 2391046 | 4776984 | 1790965 | 1793641 | 1790556 | 1792868 | 85755032 | 43466986 | 42288046 | 21441677 | 21440006 | 21437003 | 21436346 |
28 | 268435456 | 13786994 | 4597014 | 9189980 | 3445395 | 3448352 | 3445102 | 3448145 | 172057992 | 87157080 | 84900912 | 43010838 | 43022169 | 43015299 | 43009686 |
29 | 536870912 | 26562879 | 8855003 | 17707876 | 6640297 | 6642940 | 6638549 | 6641093 | 345124284 | 174736956 | 170387328 | 86284207 | 86294223 | 86280371 | 86265483 |
30 | 1073741824 | 51253813 | 17085830 | 34167983 | 12813119 | 12818164 | 12810571 | 12811959 | 692115698 | 350247433 | 341868265 | 173029849 | 173051766 | 173021954 | 173012129 |
31 | 2147483648 | 99026050 | 33014070 | 66011980 | 24756907 | 24762164 | 24750827 | 24756152 | 1387706036 | 701930519 | 685775517 | 346923591 | 346959355 | 346919375 | 346903715 |
32 | 4294967296 | 191544636 | 63858790 | 127685846 | 47889915 | 47887925 | 47879898 | 47886898 | 2781900304 | 1406586847 | 1375313457 | 695474498 | 695507585 | 695454948 | 695463273 |
33 | 8589934592 | 370864508 | 123635499 | 247229009 | 92716404 | 92723172 | 92712172 | 92712760 | 5576029188 | 2818266283 | 2757762905 | 1393992928 | 1394051594 | 1393958144 | 1394026522 |
34 | 17179869184 | 718841902 | 239631577 | 479210325 | 179710039 | 179724123 | 179699888 | 179707852 | 11175005042 | 5646033066 | 5528971976 | 2793752264 | 2793766292 | 2793694424 | 2793792062 |
35 | 34359738368 | 1394677802 | 464901435 | 929776367 | 348651117 | 348687775 | 348662005 | 348676905 | 22393163066 | 11310106668 | 11083056398 | 5598290019 | 5598278526 | 5598237855 | 5598356666 |