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 M p  = 2 p  - 1, p a prime, 3300 < p < 5000, and  discovered that  M 4253 and M 4423 are prime numbers. Hurwitz [2] further states† that he tested all prime exponents between 5000 and 6000, where the corresponding M p was not known to have a factor, without discovering any new Mersenne Primes.

TABLE
p R p R p R
6007 07707  6247 00472  6659 75241*
6037 21420  6257 36710  6661 27165 
6043 21605  6269 57356  6679 13275 
6047 37000  6299 71037* 6701 07636 
6053 53471  6329 25136* 6709 05700 
6073 41646  6337 21676* 6733 35544 
6079 15712  6359 51351  6763 01753 
6089 32615  6361 10027* 6779 74306*
6091 02043  6451 23476  6791 41143 
6133 42630  6469 51252  6823 14573*
6151 63451  6547 06546  6833 26431 
6211 71252  6571 67142  6857 63102 
6217 07377  6577 45051* 6907 46461*
6221 24166  6581 74210* 6911 63345 
6229 06517  6599 77554  6971 65345 
6991 50365 

    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 S p - 1 th remainder from the Lucas test (S 1  = 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 M 3217 and Hurwitz's M 4253 and M 4423 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 < 10 8 in all Mersenne numbers, 2 p  - 1, p a prime < 10 4 ", 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.