Prove that for any n > 1 there is either a power of 10 with n digits in base 2 or a power of 10 with n digits in base 5, but not both.
Solution
10k has n digits in base 5 iff 5n-1 < 10k < 5n. Similarly, 10h has n digits in base 2 iff 2n-1 < 10h < 2n. So if we can find both 10k with n digits in base 5 and 10h with n digits in base 2, then, multiplying the two inequalities, we have 10n-1 < 10h+k < 10n, which is clearly impossible. This establishes the "but not both" part.
Let S be the set of all positive powers of 2 or 5. Order the members of S in the usual way and let an be the n-1th member of the set. We claim that if an = 2k, then 10k has n digits in base 5, and if an = 5h, then 10h has n digits in base 2. We use induction on n.
a2 = 21, a3 = 22, a4 = 51, a5 = 23, ... . Thus the claim is certainly true for n = 2. Suppose it is true for n.
Note that 10k has n digits in base 5 iff 5n-k-1 < 2k < 5n-k. Similarly, 10h has n digits in base 2 iff 2n-h-1 < 5h < 2n-h. There are 3 cases. Case (1). an = 2k and an+1 = 2k+1. Hence 10k+1 has n+1 digits in base 5. Case (2). an = 2k and an+1 is a power of 5. Hence an+1 must be 5n-k. Hence 2k < 5n-k < 2k+1. Hence 2n < 10n-k < 2n+1. So 10n-k has n+1 digits in base 2. Case (3). an = 5h. Since there is always a power of 2 between two powers of 5, an+1 must be a power of 2. Hence it must be 2n-h. So we have 5h < 2n-h < 5h+1. So 5n < 10n-h < 5n+1 and hence 10n-h has n+1 digits in base 5.
Jacob Tsimerman pointed out that the second part can be done in a similar way to the first - which is neater than the above:
If no power of 10 has n digits in base 2 or 5, then for some h, k: 10h < 2n-1 < 2n < 10h+1 and 10k < 5n-1 < 5n < 10k+1. Hence 10h+k < 10n-1 < 10n < 10h+k+2. But there is only one power of 10 between h+k and h+k+2.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002