Problem 1967

For a moment, assume $a_2 \neq a_4$. Through the following solution, we shall several times use the fact that $\frac{n}{2} < a_n < 2n$. We divide the solution into three parts;

i. Large primes part; We prove that for each prime $p \ge 5$ the only prime less than or equal to $p$ that divides $a_p, a_{p^2}, \dots$ is $p$;

ii. We shall prove $a_{p^k} = p^k$ for all primes $p \ge 5$;

iii. Small primes part; We resolve the problem for $p = 2, p = 3$ and conclude the proof.

In order to prove part one; for each prime $p$, we define sets of primes $A_p, B_p$ as follows;
$$A_p = \{q \le p : q \mid a_{p^k}, k = 1, 2, \dots\},$$
$$B_p = \{q : q \mid a_{p^k}, k = 1, \dots\}$$
That is, $A_p = B_p \cap [1, p]$. We shall firstly prove $A_p$'s as well as $B_p$'s are disjoint. Notice that for prime $p \neq q$ we have $\gcd(a_{p^k}, a_{q^l}) = 1$. Hence, $B_p$'s are disjoint. Analogously, $A_p$'s are disjoint. We shall then prove that $A_p$ is non-empty for $p \ge 5$. Assume to the contrary that $A_p$ is empty for some $p \ge 5$. Notice that $a_{p^{k+1}} \neq a_{p^k}$ since $a_{p^k} < 2p^k < \frac{1}{2}p^{k+1} < a_{p^{k+1}}$. Moreover, $a_{p^k}$ divides $a_{p^{k+1}}$ since otherwise, there is at least one prime $q > p$ such that $v_q(a_{p^k}) > v_q(a_{p^{k+1}})$. Hence, $\gcd(a_{p^{k+1}}, a_{p^k}) \le \frac{a_{p^k}}{q} < \frac{a_{p^k}}{p}$.

On the other hand,
$$\frac{\gcd(a_{p^{k+1}}, a_{p^k})}{\gcd(p^k, p^{k+1})} < \frac{a_{p^k}}{p^{k+1}} < \frac{2}{p} < \frac{1}{2}.$$
A contradiction. Thus, $a_{p^k} \nmid a_{p^{k+1}}$. Hence, for each $n \ge 1$ there would be a prime number $q_n > p$ that $q_n \nmid \frac{a_{p^n}}{a_{p^{n-1}}}$. Hence,
$$a_{p^n} \ge q_1 \cdots q_n > (p+1)^n.$$
Choose $n$ suitably large to ensure that $(p+1)^n > 2p^n$, we are done. Thus, $A_p$ is not empty for $p \ge 5$. Now, for each $N$; $\bigcup_{p<N} A_p \subset \{p \in \mathbb{P}, p < N\}$, where $\mathbb{P}$ is the set of prime numbers.

Then, $A_2 \cup A_3 \cup A_5 \subset \{2, 3, 5\}$. Notice that $A_2, A_3, A_5$ are disjoint. Further, since $a_2 \in \{2, 3\}, a_3 \in \{2, 3, 4, 5\}$ we find that if $a_2 \neq 2$ then $A_2$ is empty and hence—and as you would see in the small primes part—we can prove that $a_3 \in \{2, 4\}$ hence, $A_3$ has one element. Since $\gcd(a_5, a_3) = \gcd(a_5, a_2) = 1$ we find that $A_5 = \{5\}$ and for all $p \ge 5$, $A_p$ and $\{2, 3, 5\}$ are disjoint.

We are ready to prove the part ii. Now, comparing the sizes, we find that $|A_p| = 1$ and $\bigcup_{p<N} A_p = \{p \in \mathbb{P}, p < N\}$, for each $N$. Hence, $A_p = \{p\}$ for all $p \ge 5$. Now, if there is a $q \neq p$ in $B_p$ then $q$ would not be a member of $B_q$ and hence $A_q$ which is a contradiction. Yielding $B_p = \{p\}$ and hence $a_{p^k} = p^k$ for all $p \ge 5$.

For the small prime part. We shall firstly prove $a_3 \neq 5$, indeed, If $a_3 = 5$ it follows that $1 < \gcd(a_6, a_2) < 4$. Hence, $3\mid a_6$. By the same reasoning, $\frac{3}{2} < \gcd(a_6, a_3) < 6$ hence, $5\mid a_6$. It follows that $a_6 \ge 15$, a contradiction.

Now, since $a_1 = 1$ and $a_2 \in \{2, 3\}$. If $a_2 = 3$ then $a_3 \in \{2, 4\}$. Hence, $a_3 \neq 5$. If $a_3 \in \{2, 4\}$ then $a_6$ must be divisible by 6 and $a_6 < 12$ yielding $a_6 = 6$. On the other hand, $a_4 = 3$. A contradiction. Hence, $a_2 = 2$. Now, we shall prove that $a_3 = 3$. Indeed, if $a_3 = 5$ since $a_5 = 5$, we yield a contradiction. Finally, notice that $a_{p^k} = p^k\mid a_{mp^k}$. Hence, $n\mid a_n$ and then $a_n = n$.

It is now time to remove banal condition $a_2 \neq a_4$ in the following way. Indeed, if $a_2 = 3$ and $a_3 \in \{2, 4\}$ it follows that $(a_{2n})$, $(a_{3n})$ would be powers of 3 and 2, respectively. Let $N = 2^a3^bT$, $\text{gcd}(T, 6) = 1$. Then, we can prove that $a_T = T$ and hence, from $\frac{1}{2}T < \text{gcd}(T, a_N) < 2T$ we find that $T\mid a_N$.

Let $(v_2(a_N), v_3(a_N)) = (c, d)$. It follows that $\frac{1}{2} < \frac{\text{gcd}(a_N, a_{2C})}{\text{gcd}(N, 2^C)} < 2$. Choose $C$ large enough such that $C > a$ and $v_3(a_{2C}) > d$ it follows that $2^{a-1} < 3^d < 2^{a+1}$. Analogously, choosing $D > b$, $v_2(a_{3D}) > c$ yields $\frac{3^b}{2} < 2^c < 2 \cdot 3^b$. It is now clear that if $a=1$ then $d=1$. If $2^c > \frac{4}{3} \cdot 3^b$ then $a_N \geq 3 \cdot \frac{4}{3} \cdot 3^b \cdot T = 2N$, a contradiction. Hence, $2^c \leq \frac{4}{3} \cdot 3^b$.

Since the sequence $\{(n \cdot \log_2 3)\}$ is dense on $(0, 1)$, for all $\varepsilon > 0$ there is an integer $d$ such that $\{d \cdot \log_2 3\} \in (1 + \log_2 \frac{2}{3}, 1 + \log_2(\varepsilon + \frac{2}{3}))$. Then, $\frac{2}{3} \cdot 2^{a_1} < 3^d < (\frac{2}{3} + \varepsilon)2^{a_1}$, for some $a_1$. Let $N = 2^{a_1} \cdot 3^b \cdot T$ now, by choosing $\varepsilon$ small enough, it follows that $v_3(a_N) = d$. Now, if $2^{v_2(a_N)} < \frac{3}{4+\varepsilon}3^b$, for some $\varepsilon > 0$ it follows that $a_N < \frac{3}{4+\varepsilon}3^b \cdot (\frac{2}{3} + \varepsilon)2^{a_1} \cdot T$, it follows that $a_N < \frac{N}{2}$. A contradiction. Hence, we find that $\frac{3}{4+\varepsilon}3^b \leq 2^{v_2(a_N)} \leq \frac{4}{3} \cdot 3^b$.

Now, choose $c$ such that $\{c \cdot \log_3 2\} \in (1 + \log_3 \frac{2}{3}, 1 + \log_3 \frac{3}{4+\varepsilon})$, it follows that $\frac{2}{3} \cdot 3^{b_1} < 2^c < \frac{3}{4+\varepsilon} \cdot 3^{b_1}$. Choosing $N = 2^{a_1}3^{b_1}T$, it follows that $v_2(a_N) \in \{c, c+1\}$. On the other hand, from
$$\frac{3}{4+\varepsilon}3^{b_1} \leq 2^{v_2(a_N)} \leq \frac{4}{3} \cdot 3^{b_1}$$
We find that $v_2(a_N) = c + 1$. But then $2^c = \frac{2^{v_2(a_N)}}{2} > \frac{2}{3} \cdot 3^{b_1}$. Yielding $2^{v_2(a_N)} > \frac{4}{3} \cdot 3^{b_1}$, a contradiction.

Finally, We now rule out the case $a_3 = 5$. Suppose $a_3 = 5$. As $\text{gcd}(a_{3k}, a_3) > 1$, the $a_{3k}$ are all divisible by 5. By the preceding, $p \mid a_p$ for all primes $p \neq 3$; as $\text{gcd}(a_{3k}, a_p) = 1$ for these primes, the $a_{3k}$ are all powers of 5; say, $a_{3k} = 5^{m_k}$. By Kronecker's density theorem, as $n$ runs through the positive integers, the fractional parts $\{n \log_3 5\}$ form a dense set in $(0, 1)$. Hence $\log_3 2 < \{n \log_3 5\} < \log_3 \frac{5}{2}$ for some $n$. Let $k = \lfloor n \log_3 5 \rfloor$ and carry out obvious calculations to get $5^{n-1} < \frac{1}{2} \cdot 3^k$ and $2 \cdot 3^k < 5^n$. As $\frac{1}{2} \cdot 3^k < a_{3k} < 2 \cdot 3^k$, it follows that $5^{n-1} < \frac{1}{2} \cdot 3^k < 5^{m_k} < 2 \cdot 3^k < 5^n$, so $n-1 < m_k < n$. This contradiction implies $a_3 = 3$ and $A_3 = B_3 = \{3\}$, as desired.

Finally, by the preceding, $A_5 = \{5\}$, as it is non-empty and disjoint from both $A_2$ and $A_3$. Now, $a_5 < 10$ forces $a_5 = 5$, so $B_5 = \{5\}$.