Prime numbers and primality testing Yahoo Group Prime gaps (not necessarily consecutive) =============================================== mad37wriggle Message 1 of 5 Nov 26 3:16 AM ----------------------------------------------- Has it been proved that given any positive integer k there exists at least one pair of primes (not necessarily consecutive) such that their difference = 2k ? If not, has any significant progress been made in this direction? Thanks Richard =============================================== mikeoakes2@aol.com Message 2 of 5 Nov 26 11:12 AM ----------------------------------------------- In a message dated 26/11/2004 11:19:05 GMT Standard Time, fitzhughrichard@... writes: >Has it been proved that given any positive integer k there exists at least one pair of primes >(not necessarily consecutive) such that their difference = 2k ? > >If not, has any significant progress been made in this direction? I have never seen such a proof. In Paul Ribenboim's "The New Book of Prime Number Records" (Springer, 1995), p. 297, he remarks that J-R Chen's famous 1966 proof of the "2-almost-prime" variants of the Goldbach and twin-prime conjectures "is good to show that for even integer 2k >= 2 there are infinitely many primes p such that p + 2k is a P2" [i.e. has at most 2 factors]. This is stronger than what you want [infinitely many rather rather than 1] but weaker [p+2k is not necessarily prime]. If it indeed hasn't been proved till now, and if it defeated the mighty Chen and others, then it is bound to be VERY HARD and none of us need even think about trying :-) -Mike Oakes [Non-text portions of this message have been removed] =============================================== ed pegg Message 3 of 5 Nov 26 12:00 PM ----------------------------------------------- > I have never seen such a proof. Nor have I. Proving P2-P1=googleplex seems difficult. I took a look at this with Mathematica. AA = Table[Prime[n], {n, 1, 300}]; BB = Map[First[Select[AA + #, PrimeQ]] - # &, Range[2, 30000, 2]]; Complement[Prime[Range[38]], Union[BB]] (* gives 2, 131 *) Flatten[Map[2 First[Position[BB, #]] &, Union[BB]]] {2, 6, 22, 116, 88, 470, 112, 284, 242, 202, 772, 1326, 718, 1334, 1328, 2558, 1762, 1642, 2402, 3274, 1732, 7094, 9512, 7984, 5246, 12688, 10532, 9952, 16766, 7702, 9974, 25708, 5888, 13528, 10342, 25678} 5 is needed for a primegap of 6, 7 is needed for a primegap of 22, 11 is needed for a primegap of 116, and so on. I didn't let this run high enough to find the first primegap to use the prime 131. The first 38 primes are enough to provide starting values for primegaps up to 30000. Ed Pegg Jr =============================================== Jens Kruse Andersen Message 4 of 5 Nov 26 4:07 PM ----------------------------------------------- Ed Pegg Jr wrote: > 5 is needed for a primegap of 6, > 7 is needed for a primegap of 22, > 11 is needed for a primegap of 116, and so on. g is the smallest gap which has the first occurrence from p to p+g. Below are results from an exhaustive search for g < 3*10^10. p g ---- ----------- 3 2 5 6 7 22 13 88 19 112 11 116 31 202 29 242 23 284 17 470 43 718 37 772 41 1326 53 1328 47 1334 67 1642 79 1732 61 1762 71 2402 59 2558 73 3274 101 5246 149 5888 83 7094 127 7702 97 7984 89 9512 109 9952 137 9974 157 10342 107 10532 103 12688 151 13528 113 16766 163 25678 139 25708 181 37666 197 59894 131 60458 193 61756 167 62156 191 69500 173 69518 227 76004 199 76168 179 76838 223 81784 211 100558 307 103102 241 103528 349 108412 229 108532 239 111512 233 139058 257 162134 379 180814 277 190006 271 190096 373 194218 263 250280 283 286114 269 294404 409 359662 251 365258 331 406918 337 413242 313 416704 281 430418 317 438314 311 460232 347 484652 293 610124 431 651362 359 676412 421 677758 367 690634 419 713618 397 774376 619 872698 389 1017902 467 1053116 353 1053848 401 1067816 433 1229638 439 1334848 383 1385444 503 1514984 449 1568648 487 1911352 479 2017034 547 2282872 443 2346404 523 2359474 631 2373478 457 2491042 463 2498458 571 2738728 461 2740622 541 2902342 509 3132044 521 3591806 499 4005292 593 4874258 617 4910546 569 5081192 491 5768912 563 5832878 661 6088792 557 7099472 691 7642528 607 7655806 643 8042218 601 8734948 641 8914196 613 9012928 751 9244552 727 9878542 577 11991484 757 13038352 811 13591192 587 13720004 719 14808734 787 15412972 709 16708792 673 16766338 647 17211872 769 18063208 599 19171058 739 19700218 773 22176548 733 22671958 677 22842824 829 24318988 653 27349526 701 28160402 683 31480166 797 32602814 821 34726238 1093 34857778 853 37572784 883 39127618 877 40203172 743 41570636 839 42018188 857 44688542 659 47225708 991 48726448 919 50361532 823 53936758 859 54545692 1117 55076404 953 55115978 827 56808482 907 61334716 761 65396288 929 73094972 937 73410502 1033 75884164 881 76097852 947 79296956 809 86388902 967 96330292 997 109611364 1051 112930942 1087 125676016 863 131079974 887 137987162 1217 147838742 977 154861334 911 164594336 1039 172682308 1021 173260042 1009 178260934 1069 185472202 1103 238205144 1031 239201918 1109 251531444 1279 255172912 1129 268571944 1019 319732832 1123 336671788 971 360236108 1013 374378834 1237 382362826 1181 398579282 1229 402377288 1091 435146828 1277 441358094 1171 441573238 941 444571916 1063 451714258 1153 474819178 1061 476723492 1423 532932016 1249 536796808 1049 541913234 1097 551437862 983 566051996 1223 593888264 1231 610710082 1201 620215306 1381 636335578 1291 645446962 1373 647722436 1187 648067634 1409 658548458 1213 673805014 1303 735935908 1321 785148508 1151 824722442 1453 847434106 1481 916861118 1429 935409214 1297 991647586 1301 1028680076 1307 1154038124 1163 1196773574 1289 1257220178 1259 1268850092 1193 1392085826 1367 1602623234 1531 1606274038 1361 1746162182 1549 1834890388 1451 1873545218 1327 2010159922 1399 2058479002 1579 2136557938 1511 2177804666 1283 2271372674 1471 2544495082 1459 2575289824 1759 2583022822 1319 2908496564 1427 3026372642 1877 3220560764 1597 3223205122 1609 3270099058 1483 3287328298 1489 3478603012 1699 3623443228 1433 3652026998 1447 3916848772 1499 4060828922 1567 4227211162 1487 4300211324 1439 4717151294 1627 4738962244 1607 4796950934 1559 5121642404 1583 5122716218 2239 5880449914 1543 5942175436 1553 6530792714 1789 6762499438 1783 7260663988 1493 7288310924 1777 7364581984 1663 7459545466 1571 7507539476 1753 7732777354 1723 7975223296 1879 8359726222 1523 8988682988 1669 9025905478 1637 9059125532 1621 9103725262 1657 9249017152 1747 9274383442 1619 9627720644 1873 9709006654 1693 10009858036 1697 10133678774 1601 10605247472 1787 10790071076 1741 10841132716 1831 11529890332 2141 11691729188 1667 11810687576 1811 13374986246 1823 13617424424 1801 14551617628 1931 14999483288 1871 15731703242 2083 16964487538 1613 17190939806 1847 17989476584 2063 18265616426 1709 19270456922 1993 19553504956 1861 19705555288 2143 20405452048 1867 20440585822 1933 22279195054 1721 22410653816 1997 23023103954 2113 23107401658 1901 25156426202 1733 25473995978 1951 27783214582 The two last "champions" (larger p than any smaller g) are: 1877 3220560764 2239 5880449914 5880449914 requires 45 more primes than the previous champion. A surprisingly large jump, still unbeaten at 3*10^10. -- Jens Kruse Andersen =============================================== Jens Kruse Andersen Message 5 of 5 Nov 27 8:55 AM ----------------------------------------------- I wrote: > g is the smallest gap which has the first occurrence from p to p+g. > Below are results from an exhaustive search for g < 3*10^10. > > p g > ---- ----------- > 3 2 ..... > 1951 27783214582 Continuing to 10^12: p g ---- ------------ 2053 30951355588 1913 32787870254 2003 33028012868 1889 34039311422 1987 34624333624 1907 34854676022 2273 37353552998 1979 38773518788 2081 38861638766 2011 41202942658 2029 41521932538 1949 44225336588 2251 46517928298 2039 47615574428 1999 50419344298 2017 51920439664 2111 52163106482 2089 54619934752 2203 57081791686 2287 60267472366 2269 61596348004 2027 62555320874 1973 64196183384 2129 68807011628 2281 70865077762 2179 71304622798 2131 75946694686 2153 79649763554 2207 80257682114 2243 85004292728 2213 88998762008 2161 92826902668 2137 98679435592 2069 102018602732 2087 103358778674 2383 104420637988 2293 104443210708 2447 107077145114 2297 108031971062 2237 110697390302 2221 119344858132 2659 129211053052 2557 131797165432 2267 136497039716 2099 139051405202 2423 148733228408 2417 151760564906 2311 154207168168 2521 164897129806 2377 179185498522 2671 181750049542 2473 186337227808 2399 188225534402 2707 192652748062 2689 199312446748 2393 201028699484 2539 201111710488 2339 210043698212 2617 212207793334 2347 212329834612 2371 215042988562 2549 219004563542 2467 226850753356 2341 229287309802 2381 231043770746 2797 232092024712 2389 234733275562 2693 246623378966 2459 250866977342 2551 255165761728 2503 257265170044 2333 278795484194 2309 289646183252 2351 293838302678 2411 328965870908 2437 332331507082 3037 357304776394 2593 372777694378 2719 382901722612 2441 388977832262 2713 391573241716 2579 394105297832 2791 395327811352 2357 401855015192 2819 419085029054 2677 450536846446 2647 471863780746 3307 496562420542 2683 500406690634 2963 503533515176 2543 513339873908 2591 524041696916 2477 524816934704 2851 563006209642 2837 594237705086 3089 596877919304 2609 610385657978 2857 752262201736 3049 788369669992 2833 794448239476 2971 807786968242 2621 864907042322 2749 871261882432 2633 871513262174 2801 884588260508 2531 908072344106 2657 922831865342 3301 951380992312 2953 969188906968 2729 984136086308 2789 995701560428 2663 is the smallest missing p for g < 10^12. All the found g champions (larger p than any smaller g): p g ---- ------------ 3 2 5 6 7 22 13 88 19 112 31 202 43 718 53 1328 67 1642 79 1732 101 5246 149 5888 157 10342 163 25678 181 37666 197 59894 227 76004 307 103102 349 108412 379 180814 409 359662 431 651362 619 872698 631 2373478 661 6088792 691 7642528 751 9244552 757 13038352 811 13591192 829 24318988 1093 34857778 1117 55076404 1217 147838742 1279 255172912 1423 532932016 1453 847434106 1481 916861118 1531 1606274038 1549 1834890388 1579 2136557938 1759 2583022822 1877 3220560764 2239 5880449914 2273 37353552998 2287 60267472366 2383 104420637988 2447 107077145114 2659 129211053052 2671 181750049542 2707 192652748062 2797 232092024712 3037 357304776394 3307 496562420542 The p increase from 1877 to 2239 is still the largest jump. 3307 is the 464th odd prime, so 496562420542 avoids the first 463. If p and q are distinct primes and q divides g, then q never divides p+g. If q does not divide g then q divides p+g with probability 1/(q-1). This means g without small factors are more likely to need large p. The smallest odd factor in a listed g champion above 200 is 19 in 104420637988 = 2^2*19*21187*64849. I conjecture all odd primes p occur. It would of course be easier to find large p if g does not have to be minimal, so huge g can be tried. g = n# gives p>n, since q divides q+n# for all primes q<=n. If we want to find a much smaller g with large p then it seems better to try g without any small odd factor. I don't know of theoretical or computational work on this subject. Google and OEIS searches on g or the p sequence gave nothing. I plan to submit some sequences to OEIS with a link to this thread. -- Jens Kruse Andersen =============================================== Cached by Georg Fischer at Nov 14 2019 12:47 with clean_yahoo.pl V1.4