Solution to Problem #4



Prime factors were found by Philippe Fondanaiche of Paris (France), Al Zimmermann of White Plains NY, Chris Welty of London (England), Marc Ziegler of Los Gatos CA, Gene Hall of Soquel CA, and Robin Stokes of the University of New England (Australia). The factors found were 3, 19, 43, 97, 661, and 8243. Note that the fact that 3 is a factor can be easily determined using the criterion that a number is divisible by 3 if the sum of the digits are. The other factors were found by computer. Robin Stokes has tested all primes less than 25 million and found no other factors. Marc Ziegler has extended the search past 5.32 billion with no new factors found. He also notes that for numbers of this form, the first one which is prime is 828180...321.

Note (January 09): Dave Beckman of Santa Barbara CA found the following additional prime factors:

75027897535039
4034615565495091676921
7815589571751242903723

Here is his e-mail message. 

I have done some more searching for factors of 200019991998...321 (the number presented in Challenge problem #4 of 1999-2000).

After finding the factors of 3, 19, 43, 97, 661, 8243 by trial division, I wrote a Pollard-rho algorithm using the 
GNU MP (multiple precision integer) library, which found a 14-digit factor:

    a = 7502 78975 35039 .

This can be verified to be prime using the factorization

  a-1 = 2 * 3 * 7 * 169111 * 10563349 ;

6 is a primitive root of Z_a.
(To verify primality, check that Z_a has order a-1 by showing that
6^(a-1) == 1 but 6^((a-1)/p) != 1 for any factor p of a-1.)

This was about the limit for Pollard rho.  I downloaded GNU-ECM (Elliptic Curve Method) and fed in the 6867-digit quotient; 
after about an hour it found a 22-digit factor

    b = 40 34615 56549 50916 76921 ,

which can be verified prime as before with

  b-1 = 2^3 * 5 * 250963 * 401913386185921  (7 is a primitive root).

After another day or so it found another 22-digit prime factor in the resulting 6845-digit quotient,

    c = 78 15589 57175 12429 03723

with

  c-1 = 2 * 31 * 1423 * 1657 * 145391 * 367709731 and 2 primitive.

This leaves a 6823-digit quotient, which is unsurprisingly still composite.  

After searching for quite a while with ECM, though, I haven't found any more factors, which I think means that it is
unlikely to have any factors with fewer than about 35-40 digits.

Perhaps it will make a nice test when the first quantum computers come online.


Back to the Archives
Back to the Math Department Homepage.