How to prove this fact about the first digits of 2^n?

Question

I think this is a very interesting problem.

Let k be any positive integer. Show that there exists a positive integer n such that the first digits of 2^n are the digits of k. For example, if k = 2781, then there exists n such that the first 4 digits of 2^n, from the left to the right, are 2781.

Answer 1

Brent L beat me to it, but I'll try to be more explicit in proof:

In order for 2^n to match the first digits of an arbitrary sequence of m integers, log(2^n) must have the fractional part (mantissa) matching the mantissa of the sequence to the accuracy required for the number of digits.

Case in point: to match k = 2781, note that
log(2781) = 3.444201 , and
log(2782) = 3.444357
This means that any x such that
0.444201 < mantissa(x) < 0.444357
will begin with the sequence 2781

In general, the condition will be:
mantissa(k) < mantissa(x) < mantissa(k+1)

So, how can we ensure that there is a number 2^n satisfying this condition on x? We can refer back to your earlier problem, to show that the fractional part of the terms in the sequence
a(n) = n * p (where p is irrational and n = 1, 2, 3...)
form a sequence that is dense in [0, 1]. That implies that if we look at sequence:
b(n) = n * log(2)
that the mantissas of the b(n) are dense in the unit interval, and hence infinitely many of them fall in the interval
[mantissa(k), mantissa(k+1)].
Hence, there are infinitely many values of n for which 2^n lead off with the right integer sequence to match k.

OK, I need to do two house-keeping chores:

- Proof that log(2) is irrational, so that the quoted theorem applies:
If log(2) were NOT irrational, then
log(2) = p/q for some integers p and q.
Then
q*log(2) = p , and
10^(q*log(2)) = 10^p , or
2^q = 10^p
But this is impossible, because 10^p has factors of 5, and 2^q cannot have any factors of 5. Hence, log(2) is irrational.

- Proof of the theorem that the fractional part of the sequence
a(n) = n * p (where p is irrational and n = 1, 2, 3...)
forms a sequence dense in [0,1]: I will prove that in the section dedicated to that problem, which is referenced.

Answer 2

If we know that a number has particular first digits, we know that the fractional part of its base-10 logarithm must fall within a particular interval. We don't need to know the number's order of magnitude; that's related directly to the integer part of its logarithm.

log 2 is irrational. That means that for any interval between 0 and 1, there exists an integer n such that the fractional part of n log 2 falls within that interval. n log 2 = log 2^n, of course, so this means that for any number k you give, we can find a power of 2 that starts with the digits of k.

Answer 3

i don't feel like doing this, but i would use induction. assume this is true for some n, then using that assumption, try to show that it's true for n+1. if you can show that, and also show that it's true for n=1 or n=0, then that proves that it's true for n