Base 2001 Representation of n!

Date: 10/05/2003 at 04:51:29
From: Mark 
Subject: base 2001 representation of n!

The question is as follows: Find all positive integers n such that 
the base 2001 representation of n! consists entirely of 0's and 1's.

I've tried applying the problem to smaller bases (3,4, etc.), but I 
can't seem to find a pattern.  I've been struggling off and on with 
it for quite some time.

I was thinking that you might use Legendre's formula to relate how 
different powers of 2001 would divide n!.  However, 2001 is not prime;
it is equal to 29*23*3.  That might help since for every power of 2001
that goes into n!, the same power on 3 goes in as well.

Anyway, I hope you can help me out or at least give me some hint as to
how to solve it.

Date: 10/05/2003 at 08:15:12
From: Doctor Jacques
Subject: Re: base 2001 representation of n!

Hi Mark,

There are first the obvious choices n = 0 and n = 1.  I believe that 
there are no other possibilities.

Assume, by contradiction, that n >= 2, and N = n! has the required 
form.  Since obviously 2! has not the required form, we may even 
assume that n >= 3.

Let k be the position of the rightmost '1' digit in N = n!, in base 
2001.  We may write:

  N = M * 2001^k

where M = 1 (mod 2001). In particular, M is not divisible by 3.

Since 2001 is divisible by 3 but not by 9, this shows that 3^k is the 
highest power of 3 that divides N.  In the same way, we find that 3,
23, and 29 have the same exponent (k) in the factorization of N.

But, for n >= 3, the exponent of 3 (k_3) will always be greater than 
the exponent of 23 (k_23) in n!.  Indeed, those exponents are given by:

  k_3  = floor(n!/3) + floor(n!/(3^2)) + ...

  k_23 = floor (n!/23) + floor (n!/(23^2)) + ...

Each term of the first sum is greater than or equal to the
corresponding term in the second sum; if n >= 3, the first term of 
k_3 is strictly greater than the first term of k_23, and therefore 
k_3 > k_23, which gives the desired contradiction.

Note that the fact that the prime factors of 2001 are not repeated is 
crucial.  Indeed, in base n!, we always have n! = 10.

Does this help?  Write back if you'd like to talk about this some
more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/