7
$\begingroup$

A long time ago I found a question on the internet that went a little like this:

Suppose that we have $n=2^k$ where $k\gt 3$. If $m$ is another number that is a combination of the digits of $2^k$, prove that $m$ cannot be a power of $2$.

I gave up on it a long time ago, but have now become interested in number theory and hope that someone could shed some light on this problem.

Edit: This is only for base 10.

  • 2
    When you say "a combination of the digits", you mean it is obtained by "shuffling them around", but using all of them? The usual mathematical term of that is "permutation" rather than "combination".2011-05-02
  • 0
    @Arturo Yes, you are correct. I meant to say that m is a permutation of the digits of n.2011-05-03

1 Answers 1

5

Assuming you mean shuffle the digits around (in base $10$)

For the case where you don't bring zeroes to the front:

We look at the remainder when you divide by $9$.

If $2^m = 2^n$ modulo $9$, then $m-n$ is divisible by $6$. In which case, they have different number of digits.

  • 1
    I got stuck trying to follow this. The order of 2 mod 9 is 6, and there are no more than 4 consecutive powers of 2 with the same number of digits, so these all differ mod 9 and therefore no one of them is a digit-permutation of another; but how to handle the case when the digit 0 is permuted into the most-significant position? Maybe I am not interpreting the question correctly because I am allowing for e.g. "1024" to be permuted to "0124" which is a valid representation of 124.2011-05-02
  • 0
    @Dan: Good point. That case is not considered in this answer and I have edited the answer to reflect that.2011-05-02
  • 0
    I have heard a version of this problem and I don't recall zeroes being an issue, so I think the correct statement assumes that they aren't at the front.2011-05-02
  • 0
    @Qia: I am guessing that too, but the issue with zeroes probably makes this problem harder (and more interesting). Of course, it might not be true in that case.2011-05-02
  • 1
    A variation which makes it false is including more than one base: 2^20 is a digit-permutation of 7^8, and 2^10 is a digit-permutation of 7^4.2011-05-02
  • 0
    @Dan I think I agree with Moron when he says that bringing zeros to the front isn't really an issue, but, then again, it does add a "twist" that should not be overlooked.2011-05-03
  • 0
    I checked that there are no powers of 2 up to 2^100000 which satisfy it, allowing for leading zeros. I also checked some other small primes up to some smaller exponents and found no matches. (Later when I tried combining prime bases I found 7^8 ~ 2^20 and a few others.) But I am not sure how to go about proving it in any of these cases. Does anyone know a heuristic that it should be true?2011-05-03
  • 0
    The requirement that $2^m\equiv2^n$ under permutations of the digits in base 10 implies that they have the same remainder on division by 9. As noted by Moron, this implies that $m-n\equiv 0\mod(6)$. But in addition, this requires that the sum of the digits be equal. An example of a pair where the sum of the digits are equal is $2^4$ and $2^{10}$ where the digits sum to 7, but this means that the add to one digit is not equal to the subtract to another digit.2011-05-03
  • 0
    How to prove even that the set of powers of two whose normal decimal representation contains k zeroes is finite?2011-05-03
  • 1
    @Dan, no one knows. Guy, Unsolved Problems In Number Theory, F24, lists a bunch of numbers $n$ such that $2^n$ has no zero digit - the biggest in the list is $n=86$ - asks whether that's it, and notes that Dan Hoey has checked there are no others with $n\le2500000000$.2011-05-03