2

For $n=0, 1 ,2 \dots$, let $a(n) = \{ x| x=3^k, k = 0, 1, 2, \dots, n \}$ and $b_n$ be a number of elements of $a(n)$ whose most significant digit is $1$. For example, for $n=7$, $a(7)=\{1, 3, 9, 27, 81, 243, 729, \}$ and $b_7=1$ because $1$ satisfies the condition. I tried to figure out $\displaystyle \lim_{n \to \infty} \frac{a_n}{n}$. I assume it converges to $\log_{10} \dfrac{3}{2}$ or something like that, but proof doesn't occur to me. Here's what I've proved:

(1) For $k=1, 2, 3, \dots$, There exists at most one $N$ such that $10^k < 3^N < 2 \times 10^k $.

This gives $0 \leq N \log_{10}3 - K \leq \log_{10} 2$ but I have no clue what to do. Would you give me some hints to solve this problem?

Soling
  • 478
  • 2
    See this near duplicate – lulu Aug 02 '21 at 14:29
  • Who gives the answer of the near duplicate says that "The number 2 is unique to this approach of exact counting". – Soling Aug 02 '21 at 14:37
  • 1
    First digit of any positive integer is controlled by the fractional part of its logarithm in base $10$. More precisely, first digit of $3^n$ is $1$ if and only if ${ \log_{10}3^n } = { n \log_{10}3 } \in [0, \log_{10}2)$. Since $\log_{10} 3$ is irrational, the sequence $n \log_{10} 3$ is equidistributed modulo 1. This means the limit $\frac{a_n}{n}$ has to be $\log_{10}2$. – achille hui Aug 02 '21 at 15:00

1 Answers1

1

I think the near-duplicate doesn't qualify, because an explicit bound is more difficult to obtain in our case. So I'll go through the theory anyway.

Suppose that $a$ is the leading digit of $3^n$ modulo $10$. Then, we know that $a \times 10^k < 3^n < (a+1) \times 10^k$ for some positive integer $k$. Taking logarithms to the base $10$, this tells us that $$k + \log_{10} a < n \log_{10} 3 < k + \log_{10}(a+1)$$

Let $[x]$ be the greatest integer function i.e. $[x]$ is the unique integer such that $[x] \leq x < x+1$. Now, let $\{x\} = x - [x]$ be the distance of $x$ from the first integer below it. The inequality above translates to $\log_{10}a < \{n \log_{10} 3\} < \log_{10}(a+1)$.

Therefore, the condition for $3^n$ to have leading digit $1$, for example, is that $0=\log_{10} 1 < \{n \log_{10} 3\} < \log_{10} 2$.

Now, imagine a circle of circumference $1$. You start at some point on the circle, and take hops of length, say $\frac 16$ or something. You will reach from where you came within $6$ steps, and keep repeating the same steps over and over again. Similarly, if you took hops of length $\frac 5{12}$, then you'd reach back from where you came in $12$ steps, and once again repeat. You can see that if I replace $\frac 5{12}$ by any rational number, you'd still get this repetition. In other words, you are only going to be hitting the same finitely many points on the circle over and over again if you hop like this.

Now, imagine this : you have an irrational number as your hop length. What occurs then? Well, it so turns out that you not only keep hitting distinct points, but the points you hit become uniformly distributed on the circle, in the sense that it becomes more and more difficult to find gaps that you haven't hopped into and covered. Therefore, this other end of the spectrum tells you, that the likelihood that you land in a certain region of the circumference, IF you are hopping with irrational length, should be proportional to the size of that region.

This, is indeed the case, and is referred to as equidistribution.

Indeed, consider the sequence $\{n \log_{10} 3\}$. Now, as $n$ moves forward, this quantity is essentially a move forward on a circle of circumference $1$, by the quantity $\log_{10} 3$.

Is $\log_{10} 3$ irrational, however? Suppose that $\frac pq = \log_{10} 3$ in reduced terms, then $10^p = 3^q$ and prime factorization will do the rest, so it's definitely irrational.

The proof of this result is not particularly easy, since the idea relies upon an integral identity that is derived from the sequence of fractional parts, followed by an approximation argument. I've suggested an elementary approach that I'm not sure would work, but I think we can try to intuit from it, the result. For reference, you could read up this article and more on Weyl's equidistribution criterion.

Suppose that $l$ is an irrational number, and let $0 \leq a < b \leq 1$. Then, we have : $$ \lim_{n \to \infty} \frac{\#\{k \leq n : \{kl\} \in (a,b)\}}{n} = b-a $$ In other words, the proportion of fractional parts that fall into a certain region is equal to the size of that region.

Now, putting this into play, we know that with $l = \log_{10} 3$ : $$ \lim_{n \to \infty} \frac{\#\{k \leq n : \{k\log_{10} 3\} \in (0,\log_{10} 2)\}}{n} = \log_{10} 2 $$

which tells you that the desired limit is $\log_{10} 2$.

Note : It may be possible to consider the following approach for equidistribution of $\{nl\}$ for $l$ irrational.

  • Let $\frac{p_m}{q_m}$ be rationals converging to $l$.

  • Fix $m$ and consider the quantity $\lim_{n \to \infty} \frac{\#\{k \leq n : \{k\frac{p_m}{q_m}\} \in (a,b)\}}{n}$. Let $K = \#\{ 0 \leq k < q_m : a < \{k\frac{p_m}{q_m}\} < b\}$. Note that this $K$ captures the repetition of the fractional parts after $q_m$ steps, so for large enough $N$ we can easily see that the limit is $\frac{K}{q_m}$ following some simple estimations.

  • Fix a $k'$ positive integer. By taking a fixed $m$ large enough, we can always ensure that $[k\frac{p_m}{q_m}]$ and $[kl]$ match up to arbitrarily large quantities ,and by taking $m$ even larger if required (this time depending upon $a$ and $b$) we can ensure that $\{k \frac{p_m}{q_m}\} \in (a,b)$ if and only if $\{kl\} \in (a,b)$, for $1 \leq k \leq k'$. Thus, we can basically make sure that the sequence for $\alpha$ matches with the sequence for $\frac{p_m}{q_m}$ upto $k'$ steps for arbitrary $k$ by taking $m$ large enough.

  • Conclude using a limit exchange criterion.

This is merely a framework, but it will be a good elementary approach instead of using the more complicated result available.

Sarvesh Ravichandran Iyer
  • 76,105