Associated Topics || Dr. Math Home || Search Dr. Math

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.

more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search