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+3
f(0)=3
f(1)=5
f(2)=1
f(3)=1
f(4)=23
f(5)=11
f(6)=1
f(7)=59
f(8)=1
f(9)=31
f(10)=113
f(11)=1
f(12)=53
f(13)=37
f(14)=71
f(15)=1
f(16)=1
f(17)=103
f(18)=1
f(19)=383
f(20)=47
f(21)=1
f(22)=509
f(23)=1
f(24)=67
f(25)=653
f(26)=1
f(27)=1
f(28)=163
f(29)=97
f(30)=311
f(31)=199
f(32)=353
f(33)=1
f(34)=1193
f(35)=421
f(36)=89
f(37)=1409
f(38)=1
f(39)=521
f(40)=1
f(41)=1
f(42)=1
f(43)=379
f(44)=661
f(45)=691
f(46)=433
f(47)=251
f(48)=157
f(49)=223
f(50)=1
f(51)=1
f(52)=1
f(53)=191
f(54)=991
f(55)=3083
f(56)=1
f(57)=1103
f(58)=137
f(59)=1181
f(60)=1
f(61)=757
f(62)=1303
f(63)=269
f(64)=181
f(65)=1
f(66)=1
f(67)=1
f(68)=313
f(69)=179
f(70)=4973
f(71)=1
f(72)=1753
f(73)=1
f(74)=617
f(75)=1901
f(76)=1171
f(77)=2003
f(78)=1
f(79)=6323
f(80)=2161
f(81)=443
f(82)=619
f(83)=1
f(84)=2381
f(85)=1
f(86)=499
f(87)=1
f(88)=1567
f(89)=2671
f(90)=2731
f(91)=1
f(92)=317
f(93)=1
f(94)=8933
f(95)=3041
f(96)=1
f(97)=257
f(98)=647
f(99)=3301
b) Substitution of the polynom
The polynom f(x)=x^2+1x+3 could be written as f(y)= y^2+2.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 | 7 | 1 | 6 | 0.700000 | 0.100000 | 0.600000 | ||||||||
2 | 100 | 67 | 51 | 16 | 0.670000 | 0.510000 | 0.160000 | 9.571428 | 51.000000 | 2.666667 | |||||
3 | 1000 | 685 | 590 | 95 | 0.685000 | 0.590000 | 0.095000 | 10.223881 | 11.568627 | 5.937500 | |||||
4 | 10000 | 6833 | 6203 | 630 | 0.683300 | 0.620300 | 0.063000 | 9.975183 | 10.513559 | 6.631579 | |||||
5 | 100000 | 68606 | 63705 | 4901 | 0.686060 | 0.637050 | 0.049010 | 10.040392 | 10.270031 | 7.779365 | |||||
6 | 1000000 | 686977 | 646939 | 40038 | 0.686977 | 0.646939 | 0.040038 | 10.013366 | 10.155231 | 8.169353 | |||||
7 | 10000000 | 6876687 | 6536861 | 339826 | 0.687669 | 0.653686 | 0.033983 | 10.010069 | 10.104293 | 8.487587 | |||||
8 | 100000000 | 68819201 | 65878168 | 2941033 | 0.688192 | 0.658782 | 0.029410 | 10.007609 | 10.077951 | 8.654526 | |||||
9 | 1000000000 | 688610714 | 662669682 | 25941032 | 0.688611 | 0.662670 | 0.025941 | 10.006083 | 10.059018 | 8.820381 | |||||
10 | 10000000000 | 6889718462 | 6657579225 | 232139237 | 0.688972 | 0.665758 | 0.023214 | 10.005244 | 10.046602 | 8.948728 |
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 | 2 | 0 | 2 | 1.000000 | 0.000000 | 1.000000 | ||||||||
2 | 4 | 3 | 0 | 3 | 0.750000 | 0.000000 | 0.750000 | 1.500000 | -nan | 1.500000 | |||||
3 | 8 | 5 | 0 | 5 | 0.625000 | 0.000000 | 0.625000 | 1.666667 | -nan | 1.666667 | |||||
4 | 16 | 10 | 4 | 6 | 0.625000 | 0.250000 | 0.375000 | 2.000000 | inf | 1.200000 | |||||
5 | 32 | 21 | 12 | 9 | 0.656250 | 0.375000 | 0.281250 | 2.100000 | 3.000000 | 1.500000 | |||||
6 | 64 | 43 | 31 | 12 | 0.671875 | 0.484375 | 0.187500 | 2.047619 | 2.583333 | 1.333333 | |||||
7 | 128 | 82 | 65 | 17 | 0.640625 | 0.507812 | 0.132812 | 1.906977 | 2.096774 | 1.416667 | |||||
8 | 256 | 169 | 138 | 31 | 0.660156 | 0.539062 | 0.121094 | 2.060976 | 2.123077 | 1.823529 | |||||
9 | 512 | 346 | 290 | 56 | 0.675781 | 0.566406 | 0.109375 | 2.047337 | 2.101449 | 1.806452 | |||||
10 | 1024 | 697 | 600 | 97 | 0.680664 | 0.585938 | 0.094727 | 2.014451 | 2.068965 | 1.732143 | |||||
11 | 2048 | 1399 | 1230 | 169 | 0.683105 | 0.600586 | 0.082520 | 2.007174 | 2.050000 | 1.742268 | |||||
12 | 4096 | 2790 | 2485 | 305 | 0.681152 | 0.606689 | 0.074463 | 1.994282 | 2.020325 | 1.804734 | |||||
13 | 8192 | 5578 | 5051 | 527 | 0.680908 | 0.616577 | 0.064331 | 1.999283 | 2.032596 | 1.727869 | |||||
14 | 16384 | 11211 | 10230 | 981 | 0.684265 | 0.624390 | 0.059875 | 2.009860 | 2.025342 | 1.861480 | |||||
15 | 32768 | 22468 | 20717 | 1751 | 0.685669 | 0.632233 | 0.053436 | 2.004103 | 2.025122 | 1.784913 | |||||
16 | 65536 | 44970 | 41640 | 3330 | 0.686188 | 0.635376 | 0.050812 | 2.001513 | 2.009943 | 1.901770 | |||||
17 | 131072 | 89947 | 83698 | 6249 | 0.686241 | 0.638565 | 0.047676 | 2.000156 | 2.010038 | 1.876577 | |||||
18 | 262144 | 180011 | 168301 | 11710 | 0.686687 | 0.642017 | 0.044670 | 2.001301 | 2.010813 | 1.873900 | |||||
19 | 524288 | 360032 | 337956 | 22076 | 0.686707 | 0.644600 | 0.042107 | 2.000056 | 2.008045 | 1.885226 | |||||
20 | 1048576 | 720352 | 678465 | 41887 | 0.686981 | 0.647035 | 0.039947 | 2.000800 | 2.007554 | 1.897400 | |||||
21 | 2097152 | 1441258 | 1362037 | 79221 | 0.687245 | 0.649470 | 0.037776 | 2.000769 | 2.007527 | 1.891303 | |||||
22 | 4194304 | 2883112 | 2731889 | 151223 | 0.687387 | 0.651333 | 0.036054 | 2.000413 | 2.005738 | 1.908875 | |||||
23 | 8388608 | 5768245 | 5479833 | 288412 | 0.687628 | 0.653247 | 0.034381 | 2.000701 | 2.005877 | 1.907197 | |||||
24 | 16777216 | 11539657 | 10988944 | 550713 | 0.687817 | 0.654992 | 0.032825 | 2.000549 | 2.005343 | 1.909466 | |||||
25 | 33554432 | 23084526 | 22030424 | 1054102 | 0.687972 | 0.656558 | 0.031415 | 2.000452 | 2.004781 | 1.914068 | |||||
26 | 67108864 | 46179036 | 44158054 | 2020982 | 0.688121 | 0.658006 | 0.030115 | 2.000432 | 2.004412 | 1.917255 | |||||
27 | 134217728 | 92373572 | 88493172 | 3880400 | 0.688237 | 0.659325 | 0.028911 | 2.000335 | 2.004009 | 1.920057 | |||||
28 | 268435456 | 184784350 | 177319658 | 7464692 | 0.688375 | 0.660567 | 0.027808 | 2.000403 | 2.003767 | 1.923691 | |||||
29 | 536870912 | 369640253 | 355257105 | 14383148 | 0.688509 | 0.661718 | 0.026791 | 2.000387 | 2.003484 | 1.926824 | |||||
30 | 1073741824 | 739407359 | 711653449 | 27753910 | 0.688627 | 0.662779 | 0.025848 | 2.000343 | 2.003207 | 1.929613 | |||||
31 | 2147483648 | 1479059243 | 1425443228 | 53616015 | 0.688741 | 0.663774 | 0.024967 | 2.000331 | 2.003002 | 1.931836 | |||||
32 | 4294967296 | 2958581909 | 2854866509 | 103715400 | 0.688849 | 0.664700 | 0.024148 | 2.000314 | 2.002792 | 1.934411 | |||||
33 | 8589934592 | 5918041683 | 5717236782 | 200804901 | 0.688951 | 0.665574 | 0.023377 | 2.000297 | 2.002629 | 1.936115 | |||||
34 | 17179869184 | 11837814862 | 11448605527 | 389209335 | 0.689052 | 0.666397 | 0.022655 | 2.000293 | 2.002472 | 1.938246 | |||||
35 | 34359738368 | 23678881878 | 22923767661 | 755114217 | 0.689146 | 0.667169 | 0.021977 | 2.000275 | 2.002320 | 1.940124 |
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 | 2 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 4 | 3 | 0 | 2 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3 | 8 | 5 | 0 | 3 | 1 | 2 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4 | 16 | 6 | 0 | 4 | 2 | 2 | 1 | 1 | 4 | 2 | 2 | 0 | 0 | 2 | 2 |
5 | 32 | 9 | 0 | 7 | 2 | 2 | 3 | 2 | 12 | 7 | 5 | 2 | 2 | 2 | 6 |
6 | 64 | 12 | 0 | 10 | 4 | 3 | 3 | 2 | 31 | 18 | 13 | 6 | 5 | 9 | 11 |
7 | 128 | 17 | 0 | 15 | 4 | 5 | 5 | 3 | 65 | 40 | 25 | 13 | 17 | 19 | 16 |
8 | 256 | 31 | 0 | 29 | 9 | 8 | 7 | 7 | 138 | 76 | 62 | 26 | 37 | 40 | 35 |
9 | 512 | 56 | 0 | 54 | 15 | 15 | 13 | 13 | 290 | 156 | 134 | 57 | 80 | 78 | 75 |
10 | 1024 | 97 | 0 | 95 | 26 | 28 | 23 | 20 | 600 | 327 | 273 | 135 | 156 | 161 | 148 |
11 | 2048 | 169 | 0 | 167 | 46 | 47 | 40 | 36 | 1230 | 670 | 560 | 291 | 320 | 309 | 310 |
12 | 4096 | 305 | 0 | 303 | 80 | 76 | 74 | 75 | 2485 | 1329 | 1156 | 604 | 648 | 613 | 620 |
13 | 8192 | 527 | 0 | 525 | 126 | 129 | 130 | 142 | 5051 | 2670 | 2381 | 1257 | 1257 | 1270 | 1267 |
14 | 16384 | 981 | 0 | 979 | 243 | 247 | 236 | 255 | 10230 | 5406 | 4824 | 2534 | 2563 | 2559 | 2574 |
15 | 32768 | 1751 | 0 | 1749 | 438 | 441 | 438 | 434 | 20717 | 10883 | 9834 | 5164 | 5183 | 5162 | 5208 |
16 | 65536 | 3330 | 0 | 3328 | 819 | 848 | 846 | 817 | 41640 | 21851 | 19789 | 10453 | 10448 | 10384 | 10355 |
17 | 131072 | 6249 | 0 | 6247 | 1550 | 1588 | 1572 | 1539 | 83698 | 43589 | 40109 | 20983 | 20925 | 20880 | 20910 |
18 | 262144 | 11710 | 0 | 11708 | 2905 | 2962 | 2952 | 2891 | 168301 | 87352 | 80949 | 42156 | 42070 | 41985 | 42090 |
19 | 524288 | 22076 | 0 | 22074 | 5513 | 5574 | 5550 | 5439 | 337956 | 175091 | 162865 | 84440 | 84381 | 84575 | 84560 |
20 | 1048576 | 41887 | 0 | 41885 | 10493 | 10544 | 10513 | 10337 | 678465 | 351198 | 327267 | 169571 | 169533 | 169361 | 170000 |
21 | 2097152 | 79221 | 0 | 79219 | 19806 | 19881 | 19858 | 19676 | 1362037 | 703737 | 658300 | 340223 | 340447 | 340467 | 340900 |
22 | 4194304 | 151223 | 0 | 151221 | 37740 | 37790 | 37969 | 37724 | 2731889 | 1408401 | 1323488 | 683535 | 682916 | 682764 | 682674 |
23 | 8388608 | 288412 | 0 | 288410 | 72052 | 72084 | 72220 | 72056 | 5479833 | 2821555 | 2658278 | 1370171 | 1370195 | 1369529 | 1369938 |
24 | 16777216 | 550713 | 0 | 550711 | 137893 | 137576 | 137617 | 137627 | 10988944 | 5652122 | 5336822 | 2746644 | 2748223 | 2747766 | 2746311 |
25 | 33554432 | 1054102 | 0 | 1054100 | 263608 | 263447 | 263279 | 263768 | 22030424 | 11317398 | 10713026 | 5506071 | 5510064 | 5508860 | 5505429 |
26 | 67108864 | 2020982 | 0 | 2020980 | 505603 | 505111 | 504683 | 505585 | 44158054 | 22654966 | 21503088 | 11037504 | 11044421 | 11041435 | 11034694 |
27 | 134217728 | 3880400 | 0 | 3880398 | 971206 | 970208 | 969151 | 969835 | 88493172 | 45351192 | 43141980 | 22117861 | 22132420 | 22125204 | 22117687 |
28 | 268435456 | 7464692 | 0 | 7464690 | 1866256 | 1865851 | 1864391 | 1868194 | 177319658 | 90789573 | 86530085 | 44317476 | 44343752 | 44328775 | 44329655 |
29 | 536870912 | 14383148 | 0 | 14383146 | 3596491 | 3594411 | 3594052 | 3598194 | 355257105 | 181720378 | 173536727 | 88805826 | 88831695 | 88807071 | 88812513 |
30 | 1073741824 | 27753910 | 0 | 27753908 | 6940301 | 6936037 | 6936494 | 6941078 | 711653449 | 363707452 | 347945997 | 177904498 | 177916311 | 177910880 | 177921760 |
31 | 2147483648 | 53616015 | 0 | 53616013 | 13407682 | 13400685 | 13400930 | 13406718 | 1425443228 | 727929442 | 697513786 | 356362604 | 356361430 | 356360909 | 356358285 |
32 | 4294967296 | 103715400 | 0 | 103715398 | 25933303 | 25927382 | 25924017 | 25930698 | 2854866509 | 1456806657 | 1398059852 | 713701447 | 713707927 | 713730808 | 713726327 |
33 | 8589934592 | 200804901 | 0 | 200804899 | 50209494 | 50202007 | 50195390 | 50198010 | 5717236782 | 2915421224 | 2801815558 | 1429322768 | 1429288700 | 1429320426 | 1429304888 |
34 | 17179869184 | 389209335 | 0 | 389209333 | 97315392 | 97294847 | 97300267 | 97298829 | 11448605527 | 5834229421 | 5614376106 | 2862181307 | 2862167965 | 2862122964 | 2862133291 |
35 | 34359738368 | 755114217 | 0 | 755114215 | 188788059 | 188767354 | 188782416 | 188776388 | 22923767661 | 11674929185 | 11248838476 | 5730977877 | 5730945677 | 5730997308 | 5730846799 |