37
$\begingroup$

This question already has an answer here:

This is a contest math problem which I was not able to solve. A hint toward the solution would be helpful as well.

Problem: Show that there are infinitely many powers of 2 starting with the digit 7.

Thanks in advance.

$\endgroup$

marked as duplicate by Watson, zhoraster, TomGrubb, rschwieb abstract-algebra Apr 13 '17 at 15:01

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are you familiar with the result that for every string of digits $s$, there exists a power of 2 ending in $s$ in decimal notation ? $\endgroup$ – user230452 Apr 12 '17 at 15:25
  • 19
    $\begingroup$ @user230452: There exists a power of 2 ending in the string "3"? $\endgroup$ – Michael Seifert Apr 12 '17 at 16:28
  • 1
    $\begingroup$ @MichaelSeifert Based on the answer below, I suspect user230452 meant "beginning with $s$." Which was news to me but follows easily from Rajiv's answer below. $\endgroup$ – Richard Rast Apr 12 '17 at 18:02
  • $\begingroup$ Yes. My apologies for the mistake. Are you familiar with that result ? There's a really neat proof in Ross Honsberger's Ingenuity in Mathematics ! $\endgroup$ – user230452 Apr 12 '17 at 23:29
  • 1
    $\begingroup$ See also: powers of 2 starting with 2011 and Fibonacci number starting with a prefix. $\endgroup$ – ShreevatsaR Apr 13 '17 at 8:48
60
$\begingroup$

I think this was a V.I Arnold problem (correct me if I am wrong). I think have seen this solution to your problem before:

The statement $2^k$ starts with a $7$ is equivalent to the existence of an integer $m$ such that $ \frac{2^k}{10^m} \in [7, 8)$. Now we just need to show that the set of all numbers of the above form is dense in the set of real numbers. Showing that $\{ \frac{2^n}{5^m} : m,n \in \mathbb{Z}\}$ is dense is good enough (cancelled powers of two). Apply the function $\log_2$ to the fraction. This function is continuous, so it is enough to prove that $\{ n-m\log_2{5} :m,n \in \mathbb{Z} \}$ is dense. This is an additive group, which is not cyclic since $\log_2 {5}$ is irrational (and $\implies$ $1$ and $\log_2 {5}$ cannot both be integer multiples of the same number). It follows that this group is dense in the real numbers. Hence the statement is true.

We also have the existence of such a number in any non-empty open interval in $\mathbb{R}$, which implies that there are infinite powers of two starting with any string of integers.

$\endgroup$
  • $\begingroup$ I am not sure of the origin of the problem as I got it as a stand alone one (forwarded by a friend). Thanks for the solution. $\endgroup$ – user424290 Apr 12 '17 at 4:22
  • $\begingroup$ This is an additive group, which is not cyclic since is irrational (and and cannot both be integer multiples of the same number). It follows that this group is dense in the real numbers. I don't understand this part. $\endgroup$ – Mockingbird Apr 12 '17 at 11:50
  • 3
    $\begingroup$ Theorem: A nontrivial subgroup of the additive group of real numbers is either cyclic or it is dense in the set of real numbers. $\endgroup$ – Blitzkrieg Apr 12 '17 at 12:08
  • 3
    $\begingroup$ A version of this problem does in fact appear at the end of Chapter 3 of Arnold's Mathematical Methods of Classical Mechanics. I'm not 100% sure whether it originated with him, but I wouldn't be surprised if it did. $\endgroup$ – Michael Seifert Apr 12 '17 at 16:23
  • 2
    $\begingroup$ Also note that this technique can be extended to prove the existence of a power of two starting with any sequence of digits when expressed in base 10. $\endgroup$ – Michael Seifert Apr 12 '17 at 18:25
67
$\begingroup$

I was intrigued. Not being smart enough to get a theoretic proof I used brute force. Definitely ugly. Only redeeming aspect is it is constructive.

Here is how I proceeded.

Remark: If two numbers are powers of 2 then so is their product.

IDEA: I will get one power of 2 starting with 7; then I'll use the above remark to multiply by a suitable power of 2 that will again start with 7. As this is an infinite process this should do.

$a=2^{46}=70368744177664$ (at least one exists!)

$b=2^{10}=1024$

$c=2^{53}=9007199254740992$

Let us take these three numbers. Let $x$ be a good number (that is a number that is a power of 2 which starts with 7). Then either $bx$ or $cx$ is good.

If the second digit of $x$ is less than 8 you can multiply by $b$ (i.e.1024), other wise multiply by c. QED

$\endgroup$
  • 11
    $\begingroup$ You are using induction which I don't find ugly at all. It is way more understandable than Rajiv's answer (to probably most people) and thus leaves less room for errors in the proof. $\endgroup$ – Alfe Apr 12 '17 at 8:02
  • 11
    $\begingroup$ The ugly part IMO is to check things like "$9007199254740992\times 79$---" is a number starting with $7$ $\endgroup$ – P Vanchinathan Apr 12 '17 at 8:11
  • $\begingroup$ I think this solution is excellent! @PVanchinathan: It suffices to check that $7 \cdot 1.024 < 8\cdot .9007199254740992$, which is more immediate. $\endgroup$ – A. Rex Apr 12 '17 at 17:24
  • 2
    $\begingroup$ Given Rajiv's existence proof, it should be possible in principle to use this technique to construct an infinite number of powers of two starting with any sequence of integers. The problem is that the powers required might be significantly larger than this. $\endgroup$ – Michael Seifert Apr 12 '17 at 18:25
  • 2
    $\begingroup$ It made me wonder what the sequence of exponents such that the power of two starts with 7 looks like. It is: $$46, 56, 66, 76, 86, 96, 149, 159, 169, 179, 189, 242, 252, 262, 272, 282, 292, 345, 355, 365, 375, 385, 438, \ldots$$ I could not find it in OEIS. $\endgroup$ – Jeppe Stig Nielsen Apr 12 '17 at 21:05
18
$\begingroup$

A general idea for how to approach this problem would be to take logs. If $7 \cdot 10^k < 2^n < 8 \cdot 10^k$, then we have $$k + \log_{10} 7 < n \log_{10} 2 < k + \log_{10} 8.$$ Since $k$ is just an arbitrary integer, we can rephrase this as $$\log_{10} 7 < \{n \log_{10} 2\} < \log_{10} 8,$$ where $\{x\} = x - \lfloor x \rfloor$ denotes the fractional part of $x$.

After this, there are many approaches to solving the problem. For example, if we focus on powers of the form $2^{10n} = 1024^n$, the fractional part is $\{n \log_{10} 1024\} = \{n \log_{10} 1.024\}$. As you increase $n$, $ \{n \log_{10} 1.024\}$ will increase by $\log_{10} 1.024 \approx 0.01$, until this would make it bigger than $1$ and it wraps around (this happens every $97$ or $98$ steps).

But the interval $[\log_{10} 7, \log_{10} 8]$ has width about $0.058$, so going in steps of $0.01$ we will never miss it. Therefore in every cycle of about $97$ steps, we'll see this interval at least once, which means we'll have at least one power of $2$ with a first digit of $7$.

$\endgroup$
13
$\begingroup$

Repeatedly multiplying by $2^{10} = 1024$ lets the first digit of any number $n$ increase monotonously (well, if you accept digit $0$ as the successor of digit $9$), but not strictly; in fact each digit is visited several times before the next is reached. For the largest number not starting with a digit $7$ (i. e. $699999999...$) we get $716799999...$ in one step and $734003199...$ in the next, so we never can "skip" the $7$ as first digit when repeatedly multiplying by $1024$.

If this works for any $n$ it works for any power of two. Products of several powers of two are powers of two as well, so the generated number is a power of two larger than $n$, hence, by induction, we can generate an infinite number of powers of two all starting with the digit $7$. $\Box$

Generation Rule for Numbers Starting With Digit 7

For any given number $n$ ($n \in \mathbb{N}$, $n>9$) you have to multiply it by $2 ^ {10 \cdot p}$ to get a number starting with the digit $7$, with

$$p = \left \lfloor \log_{1.024} {750 \over n'} \right \rfloor$$ and $n'$ being the first two digits of $n$ (which exist because of $n>9$).

Example:

$$n = 3956$$ $$\Rightarrow n' = 39$$ $$\Rightarrow p = \left \lfloor \log_{1.024} {750 \over 39} \right \rfloor = 124$$ $$3956 \cdot 2 ^ {10 \cdot 124} = {748946690\dots} \mbox{ (377 digits)}$$

$\endgroup$
  • 2
    $\begingroup$ I was going to post something along these lines but your answer is better. This seems to be the most straightforward answer in my opinion. $\endgroup$ – Jason S Apr 12 '17 at 16:05
4
$\begingroup$

Let us demonstrate that we can get arbitrarily close to some $10^n$ factor if we just let $k$ get large enough in $2^k$.

$$\log_{10}({2^k}) = k\log_{10}(2)$$ If we now accept $\log_{10}(2)$ is irrational (easy to show), then this means in practice that doubling does not create any periodicity in it's ten representation.

By selecting $k_1,k_2$ we can then get $\epsilon$ in $(10+\epsilon)^{k_1} = 2^{k_2}$ to be arbitrarily small, so no matter how close a $7a_1a_2\cdots a_n$ is to $80\cdots 0$ we can always find a power of 2 that if multiplied with the previous number would squeeze in between 7 and 8, (although no guarantee of how many new digits on the end).

$\endgroup$