Lucas' Test for Mersenne Numbers, 6000 < p < 7000

By Sidney Kravitz and Murray Berg


    Alexander Hurwitz [1] reported that he had applied Lucas' test to investigate the primality of the Mersenne Numbers Mp = 2p - 1, p a prime, 3300 < p < 5000, and  discovered that  M4253 and M4423 are prime numbers. Hurwitz [2] further states† that he tested all prime exponents between 5000 and 6000, where the corresponding Mp was not known to have a factor, without discovering any new Mersenne Primes.

TABLE
pR pR pR
600707707  624700472 665975241*
603721420  625736710 666127165 
604321605  626957356 667913275 
604737000  629971037*670107636 
605353471  632925136*670905700 
607341646  633721676*673335544 
607915712  635951351 676301753 
608932615  636110027*677974306*
609102043  645123476 679141143 
613342630  646951252 682314573*
615163451  654706546 683326431 
621171252  657167142 685763102 
621707377  657745051*690746461*
622124166  658174210*691163345 
622906517  659977554 697165345 
699150365 

    The authors have tested the Mersenne Numbers 6000 < p < 7000 without finding any new primes. A list of the five least significant octal digits of the Sp - 1th remainder from the Lucas test (S1 = 4) is given in the Table. Where a prime is missing from the list it indicates that a factor of the corresponding Mersenne Number was found by Riesel [3,4] or that an unpublished† factor was found by John Brillhart. At the time of completion of these results we learned of similiar work† by Donald B. Gillies on Illiac II. We compared our residues with his and found ten discrepancies. A check revealed that one of our three supposedly identical program decks contained an error. The questionable residues were recalculated and found to agree with Dr. Gillies' values. These residues are marked by an asterisk(*).

    The authors have verified that Riesel's M3217 and Hurwitz's M4253 and M4423 are prime. Hurwitz's octal remainder [1] of 72013 for the prime exponent 3301 was also verified. The running time for p near 6500 was three hours, using an IBM 7090.

Picatinny Arsenal
Dover, New Jersey
Standard Oil Company of California
San Fransico, California

    1. A. HURWITZ, "New Mersenne primes", Math. Comp., v. 16. 1962, p. 249-51.
    2. A. HURWITZ, Private communication to the authors dated March 12, 1962.
    3. H. RIESEL, "Mersenne numbers", MTAC, v. 12, 1958, p. 207.
    4. H. RIESEL, "All factors q < 108 in all Mersenne numbers, 2p - 1, p a prime < 104", Math. Comp., v. 16, 1962, p. 478-82. Errata, Math. Comp., v. 17, 1963, p. 486.
    5. S. KRAVITZ & M. BERG, "Recent research in Mersenne numbers" Recreational Mathematics Magazine, October, 1962, p. 40.

    Received February 6, 1963. Revised April 26, 1963.
    †See Pages 146, 87, and 93 of this issue of Mathematics of Computation.
Return to this paper's entry in Luke's Mersenne Library and Bibliography