1

The question is to show that

there is a power of $2$ whose decimal representation starts with the digits $1999$.

[Hint : apply pigeon hole principle]

How to approach this problem?

Steve Lin
  • 335
chelsea
  • 195

2 Answers2

2

I would use the equidistribution theorem, which says the multiples of an irrational number have their fractional parts equidistributed in the unit interval. Given $n=2^k$ we have $\log_{10}n=k\log_{10}2$. We know that $\log_{10}2$ is irrational. We then just have to claim the existence of a $k$ such that the fractional part of $k\log_{10}2$ is between $\log_{10}1.999$ and $\log_{10}2$

Ross Millikan
  • 374,822
  • I don't really understand your solution. Are you using Dirichlet's approximation theorem? – chelsea Nov 11 '17 at 16:19
  • I put in the Wikipedia reference to the equidistribution theorem. No, it is not the approxiimation theorem. I don't care how close we are to a rational, just that we have on number in the interval claimed. – Ross Millikan Nov 11 '17 at 16:26
  • If I claim that your same reasoning applies to any number $abcd $ with $a\ne0$ other than $1999$ , am I wrong? It is then true that for all $N$ of $n$ digits there exists $ n $ such that $ 2 ^ n$ begins with $N$? – Piquito Nov 12 '17 at 17:53
  • @Piquito: that is correct. There was nothing special about 1999, except probably the year the problem was asked. – Ross Millikan Nov 12 '17 at 18:22
  • Thank you. I have an empirical calculation of a "counterexample" certainly wrong, – Piquito Nov 12 '17 at 18:31
2

Just to complete Ross Millikan's answer (+1 to him) we may compute the first terms of the continued fraction of $\log_{10} 2$ and get $$ \log_{10}2 = [0;3, 3, 9, 2, 2, 4, \color{red}{6}, 2, 1, 1, 3, 1, 18,\ldots]$$ and by truncating the continued fraction at the highlighted term we get $$ 13301\log_{10}2 = 4004-\varepsilon,\qquad 0<\varepsilon<3\cdot 10^{-5} $$ hence $\color{red}{2^{13302}}$ is a number with the wanted property.

Small addendedum: a proof of the irrationality of $\alpha=\log_{10}(2)$. Assuming $\alpha\in\mathbb{Q}$ we have $10^p=2^q$ for some $p,q\in\mathbb{N}^+$, but while $5\mid 10^p$, $5\nmid 2^q$, so we have a contradiction.

Jack D'Aurizio
  • 353,855
  • If I claim that Ross Millikan's reasoning applies to any number $abcd $ with $a\ne0$ other than $1999$ , am I wrong? It is then true that for all $N$ of $n$ digits there exists $ n $ such that $ 2 ^ n$ begins with $N$?. Regards. – Piquito Nov 12 '17 at 17:55
  • @Piquito: that is certainly true. The irrationality of $\log_{10} 2$ implies the equidistribution of ${ n \log_{10} 2}$, which on its turn implies the density of ${n\log_{10} 2}$ in $(0,1)$ (here ${ x}$ stands for the fractional part of $x$) – Jack D'Aurizio Nov 12 '17 at 18:13
  • Thank you. I have an empirical calculation of a "counterexample" certainly wrong, – Piquito Nov 12 '17 at 18:31