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+41
f(0)=41
f(1)=43
f(2)=47
f(3)=53
f(4)=61
f(5)=71
f(6)=83
f(7)=97
f(8)=113
f(9)=131
f(10)=151
f(11)=173
f(12)=197
f(13)=223
f(14)=251
f(15)=281
f(16)=313
f(17)=347
f(18)=383
f(19)=421
f(20)=461
f(21)=503
f(22)=547
f(23)=593
f(24)=641
f(25)=691
f(26)=743
f(27)=797
f(28)=853
f(29)=911
f(30)=971
f(31)=1033
f(32)=1097
f(33)=1163
f(34)=1231
f(35)=1301
f(36)=1373
f(37)=1447
f(38)=1523
f(39)=1601
f(40)=1
f(41)=1
f(42)=1847
f(43)=1933
f(44)=1
f(45)=2111
f(46)=2203
f(47)=2297
f(48)=2393
f(49)=1
f(50)=2591
f(51)=2693
f(52)=2797
f(53)=2903
f(54)=3011
f(55)=3121
f(56)=1
f(57)=3347
f(58)=3463
f(59)=3581
f(60)=3701
f(61)=3823
f(62)=3947
f(63)=4073
f(64)=4201
f(65)=1
f(66)=4463
f(67)=4597
f(68)=4733
f(69)=4871
f(70)=5011
f(71)=5153
f(72)=5297
f(73)=5443
f(74)=5591
f(75)=5741
f(76)=1
f(77)=6047
f(78)=6203
f(79)=6361
f(80)=6521
f(81)=163
f(82)=167
f(83)=7013
f(84)=1
f(85)=7351
f(86)=7523
f(87)=179
f(88)=7873
f(89)=1
f(90)=8231
f(91)=1
f(92)=8597
f(93)=8783
f(94)=8971
f(95)=9161
f(96)=199
f(97)=9547
f(98)=9743
f(99)=9941
b) Substitution of the polynom
The polynom f(x)=x^2+1x+41 could be written as f(y)= y^2+40.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 | 11 | 0 | 11 | 1.100000 | 0.000000 | 1.100000 | ||||||||
2 | 100 | 91 | 3 | 88 | 0.910000 | 0.030000 | 0.880000 | 8.272727 | inf | 8.000000 | |||||
3 | 1000 | 873 | 290 | 583 | 0.873000 | 0.290000 | 0.583000 | 9.593407 | 96.666664 | 6.625000 | |||||
4 | 10000 | 8338 | 4188 | 4150 | 0.833800 | 0.418800 | 0.415000 | 9.550974 | 14.441380 | 7.118353 | |||||
5 | 100000 | 80567 | 48581 | 31986 | 0.805670 | 0.485810 | 0.319860 | 9.662629 | 11.600048 | 7.707470 | |||||
6 | 1000000 | 786291 | 525209 | 261082 | 0.786291 | 0.525209 | 0.261082 | 9.759467 | 10.810996 | 8.162383 | |||||
7 | 10000000 | 7724383 | 5516185 | 2208198 | 0.772438 | 0.551619 | 0.220820 | 9.823822 | 10.502838 | 8.457871 | |||||
8 | 100000000 | 76218575 | 57085921 | 19132654 | 0.762186 | 0.570859 | 0.191327 | 9.867270 | 10.348804 | 8.664374 | |||||
9 | 1000000000 | 754321278 | 585514536 | 168806742 | 0.754321 | 0.585515 | 0.168807 | 9.896817 | 10.256724 | 8.822965 | |||||
10 | 10000000000 | 7480541977 | 5969865174 | 1510676803 | 0.748054 | 0.596987 | 0.151068 | 9.916918 | 10.195930 | 8.949150 |
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 | 5 | 0 | 5 | 1.250000 | 0.000000 | 1.250000 | 1.666667 | -nan | 1.666667 | |||||
3 | 8 | 9 | 0 | 9 | 1.125000 | 0.000000 | 1.125000 | 1.800000 | -nan | 1.800000 | |||||
4 | 16 | 17 | 0 | 17 | 1.062500 | 0.000000 | 1.062500 | 1.888889 | -nan | 1.888889 | |||||
5 | 32 | 33 | 0 | 33 | 1.031250 | 0.000000 | 1.031250 | 1.941176 | -nan | 1.941176 | |||||
6 | 64 | 60 | 0 | 60 | 0.937500 | 0.000000 | 0.937500 | 1.818182 | -nan | 1.818182 | |||||
7 | 128 | 115 | 8 | 107 | 0.898438 | 0.062500 | 0.835938 | 1.916667 | inf | 1.783333 | |||||
8 | 256 | 230 | 42 | 188 | 0.898438 | 0.164062 | 0.734375 | 2.000000 | 5.250000 | 1.757009 | |||||
9 | 512 | 457 | 122 | 335 | 0.892578 | 0.238281 | 0.654297 | 1.986956 | 2.904762 | 1.781915 | |||||
10 | 1024 | 895 | 300 | 595 | 0.874023 | 0.292969 | 0.581055 | 1.958424 | 2.459016 | 1.776119 | |||||
11 | 2048 | 1763 | 713 | 1050 | 0.860840 | 0.348145 | 0.512695 | 1.969832 | 2.376667 | 1.764706 | |||||
12 | 4096 | 3479 | 1579 | 1900 | 0.849365 | 0.385498 | 0.463867 | 1.973341 | 2.214586 | 1.809524 | |||||
13 | 8192 | 6864 | 3386 | 3478 | 0.837891 | 0.413330 | 0.424561 | 1.972981 | 2.144395 | 1.830526 | |||||
14 | 16384 | 13559 | 7179 | 6380 | 0.827576 | 0.438171 | 0.389404 | 1.975379 | 2.120201 | 1.834388 | |||||
15 | 32768 | 26848 | 15125 | 11723 | 0.819336 | 0.461578 | 0.357758 | 1.980087 | 2.106839 | 1.837461 | |||||
16 | 65536 | 53156 | 31354 | 21802 | 0.811096 | 0.478424 | 0.332672 | 1.979887 | 2.072992 | 1.859763 | |||||
17 | 131072 | 105257 | 64400 | 40857 | 0.803047 | 0.491333 | 0.311714 | 1.980153 | 2.053964 | 1.874002 | |||||
18 | 262144 | 208890 | 132294 | 76596 | 0.796852 | 0.504662 | 0.292191 | 1.984571 | 2.054255 | 1.874734 | |||||
19 | 524288 | 414726 | 270317 | 144409 | 0.791027 | 0.515589 | 0.275438 | 1.985380 | 2.043305 | 1.885333 | |||||
20 | 1048576 | 824269 | 551549 | 272720 | 0.786084 | 0.525998 | 0.260086 | 1.987503 | 2.040379 | 1.888525 | |||||
21 | 2097152 | 1638710 | 1121782 | 516928 | 0.781398 | 0.534907 | 0.246490 | 1.988077 | 2.033875 | 1.895453 | |||||
22 | 4194304 | 3259947 | 2276756 | 983191 | 0.777232 | 0.542821 | 0.234411 | 1.989337 | 2.029589 | 1.901988 | |||||
23 | 8388608 | 6487372 | 4613023 | 1874349 | 0.773355 | 0.549915 | 0.223440 | 1.990024 | 2.026139 | 1.906394 | |||||
24 | 16777216 | 12916716 | 9336772 | 3579944 | 0.769896 | 0.556515 | 0.213381 | 1.991055 | 2.024003 | 1.909967 | |||||
25 | 33554432 | 25725763 | 18871681 | 6854082 | 0.766688 | 0.562420 | 0.204268 | 1.991664 | 2.021221 | 1.914578 | |||||
26 | 67108864 | 51255686 | 38112318 | 13143368 | 0.763769 | 0.567918 | 0.195851 | 1.992387 | 2.019551 | 1.917597 | |||||
27 | 134217728 | 102150135 | 76900823 | 25249312 | 0.761078 | 0.572956 | 0.188122 | 1.992952 | 2.017742 | 1.921069 | |||||
28 | 268435456 | 203630641 | 155054863 | 48575778 | 0.758583 | 0.577624 | 0.180959 | 1.993445 | 2.016297 | 1.923846 | |||||
29 | 536870912 | 406013475 | 312408070 | 93605405 | 0.756259 | 0.581905 | 0.174354 | 1.993872 | 2.014823 | 1.926998 | |||||
30 | 1073741824 | 809713501 | 629115846 | 180597655 | 0.754104 | 0.585910 | 0.168195 | 1.994302 | 2.013763 | 1.929351 | |||||
31 | 2147483648 | 1615089903 | 1266181358 | 348908545 | 0.752085 | 0.589612 | 0.162473 | 1.994644 | 2.012636 | 1.931966 | |||||
32 | 4294967296 | 3222077213 | 2547216292 | 674860921 | 0.750198 | 0.593070 | 0.157128 | 1.994983 | 2.011731 | 1.934206 | |||||
33 | 8589934592 | 6428940628 | 5122206554 | 1306734074 | 0.748427 | 0.596303 | 0.152124 | 1.995278 | 2.010904 | 1.936301 | |||||
34 | 17179869184 | 12829285375 | 10296509617 | 2532775758 | 0.746763 | 0.599336 | 0.147427 | 1.995552 | 2.010171 | 1.938249 | |||||
35 | 34359738368 | 25604775392 | 20690852919 | 4913922473 | 0.745197 | 0.602183 | 0.143014 | 1.995807 | 2.009502 | 1.940133 |
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 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 5 | 2 | 3 | 1 | 1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 9 | 3 | 6 | 3 | 2 | 2 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 17 | 6 | 11 | 5 | 4 | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 32 | 33 | 11 | 22 | 9 | 8 | 8 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 64 | 60 | 20 | 40 | 15 | 14 | 15 | 16 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
7 | 128 | 107 | 35 | 72 | 27 | 25 | 27 | 28 | 8 | 4 | 4 | 0 | 3 | 1 | 4 |
8 | 256 | 188 | 64 | 124 | 46 | 49 | 47 | 46 | 42 | 25 | 17 | 5 | 11 | 15 | 11 |
9 | 512 | 335 | 110 | 225 | 82 | 85 | 85 | 83 | 122 | 66 | 56 | 24 | 30 | 36 | 32 |
10 | 1024 | 595 | 197 | 398 | 149 | 147 | 146 | 153 | 300 | 162 | 138 | 75 | 74 | 80 | 71 |
11 | 2048 | 1050 | 340 | 710 | 267 | 262 | 258 | 263 | 713 | 382 | 331 | 169 | 184 | 183 | 177 |
12 | 4096 | 1900 | 640 | 1260 | 480 | 479 | 462 | 479 | 1579 | 828 | 751 | 380 | 394 | 402 | 403 |
13 | 8192 | 3478 | 1167 | 2311 | 860 | 879 | 859 | 880 | 3386 | 1785 | 1601 | 840 | 833 | 866 | 847 |
14 | 16384 | 6380 | 2144 | 4236 | 1598 | 1590 | 1589 | 1603 | 7179 | 3783 | 3396 | 1758 | 1777 | 1813 | 1831 |
15 | 32768 | 11723 | 3917 | 7806 | 2942 | 2901 | 2952 | 2928 | 15125 | 7891 | 7234 | 3772 | 3756 | 3772 | 3825 |
16 | 65536 | 21802 | 7242 | 14560 | 5486 | 5439 | 5434 | 5443 | 31354 | 16228 | 15126 | 7807 | 7847 | 7845 | 7855 |
17 | 131072 | 40857 | 13566 | 27291 | 10148 | 10280 | 10180 | 10249 | 64400 | 33094 | 31306 | 16030 | 16042 | 16256 | 16072 |
18 | 262144 | 76596 | 25502 | 51094 | 19103 | 19187 | 19135 | 19171 | 132294 | 67958 | 64336 | 33010 | 33063 | 33177 | 33044 |
19 | 524288 | 144409 | 47988 | 96421 | 36093 | 36122 | 36119 | 36075 | 270317 | 138557 | 131760 | 67528 | 67575 | 67692 | 67522 |
20 | 1048576 | 272720 | 90868 | 181852 | 68365 | 68081 | 68245 | 68029 | 551549 | 282056 | 269493 | 137616 | 138138 | 138127 | 137668 |
21 | 2097152 | 516928 | 172254 | 344674 | 129309 | 129400 | 129385 | 128834 | 1121782 | 572844 | 548938 | 280135 | 280508 | 280795 | 280344 |
22 | 4194304 | 983191 | 327542 | 655649 | 245604 | 246242 | 245701 | 245644 | 2276756 | 1161421 | 1115335 | 568146 | 569311 | 569392 | 569907 |
23 | 8388608 | 1874349 | 624898 | 1249451 | 468459 | 468807 | 468495 | 468588 | 4613023 | 2351412 | 2261611 | 1152370 | 1154513 | 1152663 | 1153477 |
24 | 16777216 | 3579944 | 1193641 | 2386303 | 895009 | 895555 | 894643 | 894737 | 9336772 | 4753381 | 4583391 | 2331872 | 2335556 | 2334815 | 2334529 |
25 | 33554432 | 6854082 | 2285354 | 4568728 | 1714275 | 1714166 | 1712733 | 1712908 | 18871681 | 9597396 | 9274285 | 4715498 | 4717781 | 4718291 | 4720111 |
26 | 67108864 | 13143368 | 4382214 | 8761154 | 3286309 | 3286972 | 3285513 | 3284574 | 38112318 | 19367233 | 18745085 | 9528026 | 9527105 | 9527268 | 9529919 |
27 | 134217728 | 25249312 | 8417214 | 16832098 | 6313508 | 6313266 | 6313158 | 6309380 | 76900823 | 39048460 | 37852363 | 19224324 | 19224067 | 19226378 | 19226054 |
28 | 268435456 | 48575778 | 16193403 | 32382375 | 12142866 | 12146334 | 12145159 | 12141419 | 155054863 | 78670179 | 76384684 | 38762259 | 38759391 | 38765120 | 38768093 |
29 | 536870912 | 93605405 | 31204228 | 62401177 | 23405241 | 23399411 | 23402012 | 23398741 | 312408070 | 158395012 | 154013058 | 78096198 | 78100140 | 78104476 | 78107256 |
30 | 1073741824 | 180597655 | 60202463 | 120395192 | 45154900 | 45149753 | 45147800 | 45145202 | 629115846 | 318769485 | 310346361 | 157275414 | 157278833 | 157271969 | 157289630 |
31 | 2147483648 | 348908545 | 116310266 | 232598279 | 87231356 | 87229706 | 87226319 | 87221164 | 1266181358 | 641183998 | 624997360 | 316533312 | 316561920 | 316534447 | 316551679 |
32 | 4294967296 | 674860921 | 224964481 | 449896440 | 168712195 | 168717851 | 168714314 | 168716561 | 2547216292 | 1289212754 | 1258003538 | 636792762 | 636836275 | 636771671 | 636815584 |
33 | 8589934592 | 1306734074 | 435593706 | 871140368 | 326695765 | 326679098 | 326671815 | 326687396 | 5122206554 | 2591251004 | 2530955550 | 1280528078 | 1280595132 | 1280518655 | 1280564689 |
34 | 17179869184 | 2532775758 | 844277390 | 1688498368 | 633205369 | 633194948 | 633178147 | 633197294 | 10296509617 | 5206506300 | 5090003317 | 2574135423 | 2574150863 | 2574109517 | 2574113814 |
35 | 34359738368 | 4913922473 | 1638006939 | 3275915534 | 1228482282 | 1228476950 | 1228455990 | 1228507251 | 20690852919 | 10458107269 | 10232745650 | 5172646501 | 5172768494 | 5172764504 | 5172673420 |