# A fun problem by Arnold using the Poincaré recurrence theorem

I came across this problem by V. I. Arnold while studying his classical mechanics book.

Consider a sequence where the $$n^{th}$$ term is made up by considering the first digit of $$2^n$$, the first terms are: $$1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4,..$$

By using the Poincaré recurrence theorem, say whether (prove that) the number $$7$$ will appear and which number between $$7$$ and $$8$$ will appear more often, and how much.

Now we all know this theorem is very useful in many areas of Physics, especially Statistical Mechanics, but here Arnold is really stressing that it also has an abstract value!

Maybe it's a super easy problem, but I thought about it a bit and couldn't find a decent way to do it.. it's crucial to solve the problem by using this theorem, I'm sure it's easier to do it another way but the goal is to show how applicable the recurrence's theorem is.

• $2^{46}=70\mathord,368\mathord,744\mathord,177\mathord,664$ Apr 23 '15 at 8:59
• I don't think this follows from the Poincaré recurrence theorem which talks about "almost every point" being recurrent, while this is about one particular orbit. For instance it triavially fails if you replace $2$ by $10$. Which is not to say that it does not follow from something considerably easier. Apr 23 '15 at 11:16
• @MarcvanLeeuwen: Agreed, it would be better to refer to Weyl's equidistibution theorem. (As is implicitly done in Christian Blatter's answer.) Apr 23 '15 at 11:53
• Why Poincare's recurrence thorem? Use Benford's law instead (hattip Travis). Apr 23 '15 at 15:35
• @Mitch ..Because Arnold's goal was to show Poincaré's thorem applicability to more abstract problem, I'm sure there are more effective ways to tacke it but the point is to do it that way. Apr 23 '15 at 17:39

$2^{46}=70368744177664$ so 7 does definitely appear.

The first digit of a number $x$ can be found by:

$$\left\lfloor10^{frac\left(\log x\right)}\right\rfloor$$

Here $\log$ is the base 10 logarithm. Thus the first digit is 7 iff:

$$\log7 \le frac\left(\log x\right) \lt \log8$$

And it is 8 iff:

$$\log8 \le frac\left(\log x\right) \lt \log9$$ Now since

$$\log{2^n}=n\log2$$

We get that any range of values within $\left[0;1\right)$ will be represented, and their frequency will be proportional to the size of the range (ie. the distribution is uniform). Since $\log9-\log8\lt\log8-\log7$, we should see the digit $7$ more often than $8$, and in general, the smaller the digit, the more often it will appear.

Indeed, I made my computer calculate the first digits of $2^n$ for $0\le n\lt 1000000$, and it gave me: $$\begin{matrix} 1: & 301030 \\ 2: & 176093 \\ 3: & 124937 \\ 4: & 96911 \\ 5: & 79182 \\ 6: & 66947 \\ 7: & 57990 \\ 8: & 51154 \\ 9: & 45756 \\ \end{matrix}$$

You will notice that these counts are all roughly equal to $1000000\cdot\left(\log{\left(d+1\right)}-\log{d}\right)$

• What do the square brackets mean in $[\log x]$? If you mean (as I suppose) the fractional part, then this is very non-standard notation. Braces have been used for the fractional part; if anything, square brackets usually mean the integer part (floor function). Apr 23 '15 at 10:35
• @MarcvanLeeuwen I do indeed mean the fractional part, but I will change it to make that more clear. Apr 23 '15 at 10:37
• en.wikipedia.org/wiki/Benford%27s_law Apr 23 '15 at 14:39
• @SBareS hmm.. I'm not sure I'm understanding where the Poincaré theorem is crucial in your proof Apr 23 '15 at 17:28
• @rhetoricalphysicist it isn't. Apr 23 '15 at 17:31

A hint:

One has $x_n:=\log_{10}\bigl(2^n\bigr)=n\>\kappa$, where $\kappa:=\log_{10}(2)$ is irrational. It follows that the $x_n$ are uniformly distributed modulo $1$. See also Benford's law.

You don't need Poincaré's recurrence theorem for this.

• Looking at SBareS' answer, this answer is incorrect, then? Apr 23 '15 at 9:47
• Yes! But the point of the exercise is to use that theorem! Apr 23 '15 at 9:53
• @justhalf: To the contrary: SBareS answer is a confirmation of mine and gives additional details. Apr 23 '15 at 10:11
• I think I misunderstood your answer, then. What is $x_n$? When I saw "uniformly distributed" I thought it means "the probability of the digits occurring are all the same", which is different from SBarS' answer. Apr 23 '15 at 10:14
• @justhalf $x_n$ is the logarithm of the number. Thus the logarithms of the first digits are evenly distributed, but not the digits themselves. Apr 23 '15 at 10:57

I remember that one, as well as the questions about how high animals can jump (if animals are approximated by boxes of course)! Really lovely book. Anyways! We will want to write $2^n=a\times10^k$, $1\leq a< 10$, and then take the base 10 logarithm, to get $n \log_{10}2=k+\log_{10}a$. Now I'll just say that the $k$ is unimportant, so we have $n \log_{10}2\equiv \log_{10}a \,(\mod 1)$. The modulo should remind you of a certain geometrical object, so you can apply the theorem and note that probablities are proportional to lengths, and you should find for example $$P_7=P(7\leq a< 8)=P(\log_{10}7\leq a< \log_{10}8)=\log_{10}8-\log_{10}7\approx 5.8\%,$$ and similarly $P_8\approx 5.1\%$, which is a bit unintuitive. I had to tell my computer to do a little loop and confirm it, as I expected there to be more 8's than 7's!

• Approximating animals by boxes? What nonsense! Everybody knows that cows are spherical! Apr 23 '15 at 9:30
• Well, this is a higher order of approximation ;) Apr 23 '15 at 17:43
• @krvolok hmm.. I don't really get how you used the theorem to get the answer, could you a bit more explicit? Also, I'm not sure I fully understand your geometrical interpretation.. Thanks! Apr 24 '15 at 17:50
• The problem is reduced one of the previous ones about rotations by an angle. We've seen that the problem of going through each $2^n$ and looking at the first digit is the same as $n \log_{10}2\equiv \log_{10}a \,(\mod 1)$. Since we want say $P_7$, we want to see "how often" is $\log_{10}7 \leq n \log_{10}2<\log_{10}8$. How often are multiples of an angle between some value. But rotations by an angle are length preserving (which is volume in 1d!) homeomorphisms, and by the theorem, $\forall \delta \exists n\geq 1$ so that $|R^n x-x|<\delta$ where $x\in S^1$ and R is this rotation. Apr 27 '15 at 9:13
• Since the angle is irrational, $\{R^n x\}_{n\in\mathbb N}$ are dense and uniform in $S^1$, and then you can use geometric probability, to see that the probabilities are proportional to the lengths of the segments. Again, if we for our angle $\log_{10}2=:\alpha$ want $\log_{10}7 \leq n\alpha<\log_{10}8$, we are simply looking at the portion of the circle which has angles between these ones. This cute result arguably needs only the result that these points are dense in the circle and doesn't need the Recurrence theorem (maybe its addition is even slightly confusing). But it can be done! Apr 27 '15 at 9:14