For any k-digit number M there exist a number n such that the string of first k digits of 2^n equals M .

Prove it.

Remarkable but true, in base 10.

Let b be some positive integer with the constraint that 0<b<(10^m-1), since we are going to multiply some power of 10, 10^m, by M.

Start with 2^n=M*10^m+b
Dividing by 2^m (m is obviously smaller than n):
2^(n-m)=1/(2^m)*(b+M*10^m)
The RHS is b/2^m+M*5^m
2^(n-m)=b/2^m+M*5^m
2^(n-m)-b/2^m=M*5^m
1/2^m*(2^n-b)=M*5^m

Let a=1/2^m*(2^n-b); we can 'start with any a we wish', b just has to be even and bigger than a (if a is a power of 2, then b is a bit larger than normal) and m cycles through the natural numbers.
So it is always possible to construct some RHS to have the same value as the LHS within the constraint first mentioned.

The desired result then follows at once.

Edited on January 30, 2011, 7:10 am

Posted by broll on 2011-01-30 03:59:41