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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.