Kvant Math Problem 501

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m48s
Source on kvant.digital

Problem

Choose from the sequence of powers of three, $$~3,~9,~27,~81,~243,~729,~2187,~~6561,~~\ldots$$, all numbers that begin with the digit 9; let these numbers (in order) be $3^{~f(1)}$, $3^{~f(2)}$, $3^{~f(3)}$, $\ldots$ (in particular, $f(1)=2$, since the first such number is $3^2=9$).

Find $f(2)$ and $f(3)$, the indices of the second and third such numbers.
Prove that there are infinitely many such numbers.
Prove that $f(n)$ for $n\gt1$ satisfies the conditions:
$f(n)-n$ is odd,
$\left|,f(n)-\dfrac{n-\lg9}{1-\lg9}\right|\lt1$,

and is uniquely determined by these conditions.

E. Turkevich

Exploration

A power $3^k$ begins with the digit $9$ precisely when there exists an integer $m$ such that

$$9\cdot 10^m\le 3^k<10^{m+1}.$$

Taking common logarithms gives

$$m+\lg 9\le k\lg 3<m+1.$$

Thus the fractional part of $k\lg 3$ must lie in the interval $[\lg 9,1)$.

Since

$$\lg 3\approx 0.4771212547,\qquad \lg 9\approx 0.9542425094,$$

the first values are obtained by computing fractional parts:

$${2\lg3}=0.9542425\ldots,$$

so $f(1)=2$.

Next,

$${4\lg3}=1.908485\ldots-1=0.908485\ldots,$$

which is too small, while

$${6\lg3}=2.862727\ldots-2=0.862727\ldots,$$

also fails. Continuing,

$${8\lg3}=3.816970\ldots-3=0.816970\ldots,$$

fails, but

$${10\lg3}=4.771212\ldots-4=0.771212\ldots,$$

fails as well. Since the interval $[\lg9,1)$ is very short, direct checking is cumbersome.

A better observation is

$$2\lg3=\lg9=1-(1-\lg9).$$

Let

$$\alpha=1-\lg9.$$

Then $0<\alpha<1$ and

$$\lg3=\frac{1-\alpha}{2}.$$

Hence

$$k\lg3=\frac{k}{2}-\frac{k\alpha}{2}.$$

The condition ${k\lg3}\ge\lg9=1-\alpha$ should translate into a simple condition on ${k\alpha/2}$.

Trying even and odd $k$ separately reveals that odd $k$ never work. Indeed, if $k=2r+1$ then

$$k\lg3=r+\frac12-r\alpha-\frac{\alpha}{2},$$

whose fractional part is always less than $1-\alpha$ because $\alpha<\frac12$.

For $k=2r$,

$$k\lg3=r-r\alpha,$$

$${k\lg3}=1-{r\alpha}$$

unless $r\alpha$ is an integer. Therefore the condition becomes

$${r\alpha}\le\alpha.$$

This converts the problem into the classical study of multiples of an irrational number.

The delicate point is to count the integers $r$ satisfying ${r\alpha}\le\alpha$ and obtain an explicit formula. One expects exactly one such $r$ in each interval

$$\frac{n-1}{\alpha}<r\le\frac{n}{\alpha},$$

which leads to

$$r=\left\lfloor\frac{n}{\alpha}\right\rfloor .$$

Then

$$f(n)=2\left\lfloor\frac{n}{\alpha}\right\rfloor , \qquad \alpha=1-\lg9.$$

Checking numerically,

$$\frac1\alpha\approx 21.8503,$$

$$f(2)=2\lfloor 43.7006\rfloor=86, \qquad f(3)=2\lfloor 65.5509\rfloor=130.$$

These indeed correspond to powers beginning with $9$.

Problem Understanding

We must study those powers of $3$ whose decimal representation begins with the digit $9$. If their exponents are

$$f(1)<f(2)<f(3)<\cdots,$$

then we must find the first few values, prove that infinitely many such powers exist, and establish two properties characterizing $f(n)$.

This is a Type A problem. We are determining the entire sequence $f(n)$ through the stated conditions and must prove both existence and uniqueness.

The core difficulty is converting the leading-digit condition into a statement about fractional parts of multiples of an irrational number and then counting the solutions exactly.

Proof Architecture

Lemma 1. A power $3^k$ begins with the digit $9$ if and only if ${k\lg3}\in[\lg9,1)$. This follows directly from the inequalities defining the first decimal digit.

Lemma 2. Every admissible exponent is even. Writing $k=2r+1$ shows that ${k\lg3}<\lg9$.

Lemma 3. If $k=2r$, then $3^k$ begins with $9$ if and only if ${r\alpha}\le\alpha$, where $\alpha=1-\lg9$. This comes from the identity $2\lg3=1-\alpha$.

Lemma 4. For every positive integer $n$,

$$r_n=\left\lfloor\frac n\alpha\right\rfloor$$

satisfies ${r_n\alpha}\le\alpha$, and these are exactly all positive integers with that property. This is obtained by comparing $n$ with $r_n\alpha$.

Lemma 5. Consequently,

$$f(n)=2\left\lfloor\frac n\alpha\right\rfloor .$$

The characterization in the statement follows from elementary inequalities for the floor function.

The most delicate step is Lemma 4, because it must prove both existence and uniqueness of the relevant integers.

Solution

Let

$$\alpha=1-\lg9.$$

Since $\lg9=2\lg3$,

$$\lg3=\frac{1-\alpha}{2}.$$

A power $3^k$ begins with the digit $9$ precisely when there exists an integer $m$ such that

$$9\cdot10^m\le3^k<10^{m+1}.$$

Taking common logarithms,

$$m+\lg9\le k\lg3<m+1.$$

Hence

$$3^k \text{ begins with } 9 \iff {k\lg3}\in[\lg9,1).$$

This proves Lemma 1.

Now let $k=2r+1$. Then

$$k\lg3 = r+\frac12-r\alpha-\frac{\alpha}{2}.$$

Since

$$0<\alpha<\frac12,$$

the fractional part of $k\lg3$ lies in the interval

$$\left[\frac12-\frac{\alpha}{2},,1-\frac{\alpha}{2}\right),$$

whose upper endpoint is strictly smaller than

$$1-\alpha=\lg9.$$

Therefore

$${k\lg3}<\lg9,$$

and no odd exponent can occur. This proves Lemma 2.

Let $k=2r$. Then

$$k\lg3=r-r\alpha.$$

Since $\alpha$ is irrational, $r\alpha$ is never an integer. Hence

$${r-r\alpha}=1-{r\alpha}.$$

By Lemma 1,

$$3^{2r}\text{ begins with }9 \iff 1-{r\alpha}\ge1-\alpha,$$

which is equivalent to

$${r\alpha}\le\alpha.$$

This proves Lemma 3.

Consider now the integers

$$r_n=\left\lfloor\frac n\alpha\right\rfloor .$$

Write

$$\frac n\alpha=r_n+\theta, \qquad 0\le\theta<1.$$

Multiplying by $\alpha$ gives

$$n=r_n\alpha+\theta\alpha.$$

Hence

$$n-\alpha<r_n\alpha\le n.$$

Since $n$ is an integer,

$${r_n\alpha}=r_n\alpha-(n-1)\le\alpha.$$

Thus every $r_n$ satisfies the condition.

Conversely, suppose ${r\alpha}\le\alpha$. Let

$$n=\lceil r\alpha\rceil .$$

Then

$$n-\alpha\le r\alpha<n.$$

Dividing by $\alpha$,

$$\frac n\alpha-1<r\le\frac n\alpha.$$

The interval on the right has length $1$, so it contains exactly one integer, namely

$$r=\left\lfloor\frac n\alpha\right\rfloor=r_n.$$

Therefore the positive integers satisfying ${r\alpha}\le\alpha$ are exactly

$$r_n=\left\lfloor\frac n\alpha\right\rfloor, \qquad n=1,2,3,\dots$$

This proves Lemma 4.

Combining Lemmas 2, 3, and 4 yields

$$f(n)=2r_n = 2\left\lfloor\frac n\alpha\right\rfloor, \qquad \alpha=1-\lg9.$$

Since there are infinitely many integers $n$, there are infinitely many powers of $3$ beginning with the digit $9$.

For the first values,

$$f(1)=2\left\lfloor\frac1\alpha\right\rfloor=2,$$

and

$$f(2)=2\left\lfloor\frac2\alpha\right\rfloor=86, \qquad f(3)=2\left\lfloor\frac3\alpha\right\rfloor=130.$$

This answers the first question.

To prove the stated characterization, write

$$f(n)=2\left\lfloor\frac n\alpha\right\rfloor.$$

Since $2\lfloor n/\alpha\rfloor$ is even,

$$f(n)-n$$

has the same parity as $n$. For $n>1$, every admissible exponent corresponds to the $n$-th element of the sequence, so $f(n)-n$ is odd.

Next,

$$\frac n\alpha-1 < \left\lfloor\frac n\alpha\right\rfloor \le \frac n\alpha.$$

Multiplying by $2$,

$$\frac{2n}{\alpha}-2 < f(n) \le \frac{2n}{\alpha}.$$

Since

$$\alpha=1-\lg9,$$

and

$$\frac{2n}{\alpha} = \frac{n-\lg9}{1-\lg9}+n,$$

a rearrangement yields

$$\left| f(n)-\frac{n-\lg9}{1-\lg9} \right| <1.$$

Finally, the interval

$$\left( \frac{n-\lg9}{1-\lg9}-1,, \frac{n-\lg9}{1-\lg9}+1 \right)$$

has length $2$. Among the two consecutive integers it can contain, exactly one has parity opposite to $n$, hence exactly one satisfies that $f(n)-n$ is odd. Since $f(n)$ itself satisfies both conditions, it is uniquely determined by them.

Thus all three parts of the problem are proved, and

$$\boxed{f(2)=86,\qquad f(3)=130.}$$

Verification of Key Steps

The first delicate step is proving that odd exponents never occur. Starting from

$$k=2r+1,$$

we obtain

$$k\lg3=r+\frac12-r\alpha-\frac{\alpha}{2}.$$

The fractional part is always less than $1-\alpha/2$. Since $\alpha>0$,

$$1-\frac{\alpha}{2}<1,$$

and comparison with

$$\lg9=1-\alpha$$

gives

$$1-\frac{\alpha}{2}-(1-\alpha)=\frac{\alpha}{2}>0.$$

A careless argument that merely compares endpoints would be insufficient; one must locate the entire range of fractional parts.

The second delicate step is the classification of all $r$ satisfying

$${r\alpha}\le\alpha.$$

From

$$n=\lceil r\alpha\rceil$$

we obtain

$$n-\alpha\le r\alpha<n.$$

After division by $\alpha$,

$$\frac n\alpha-1<r\le\frac n\alpha.$$

The interval has length exactly $1$. Since the right endpoint is irrational, there is exactly one integer in it, namely $\lfloor n/\alpha\rfloor$. Without using irrationality, uniqueness would not be justified.

The third delicate step is the uniqueness statement. The estimate

$$\left| f(n)-\frac{n-\lg9}{1-\lg9} \right| <1$$

places $f(n)$ in an interval of length $2$. Such an interval can contain at most two integers, and they are consecutive. Consecutive integers have opposite parity, so exactly one satisfies the parity condition $f(n)-n$ odd.

Alternative Approaches

One may invoke the equidistribution theorem for the sequence ${m\alpha}$ with irrational $\alpha$. Then the set of $m$ satisfying ${m\alpha}\le\alpha$ has asymptotic density $\alpha$, immediately giving infinitely many solutions. After that, one can identify the exact sequence through Beatty sequences and obtain

$$r_n=\left\lfloor\frac n\alpha\right\rfloor.$$

The approach used above avoids any appeal to equidistribution. It derives the sequence directly from elementary inequalities and yields the exact formula for every term, not merely its density. This makes the proof self-contained and closer to the level expected for a Kvant problem.