Balkan Mathematical Olympiad Shortlist

Consider the sequence $b_0, b_1, \dots$, defined by the initial conditions $b_0 = 1$, $b_1 = 2$, and the recursion $b_{n+1} = 4b_n - b_{n-1}$ for $n \ge 1$. We have $a_n = b_{n+1} - 1$, for all $n \ge 0$. In particular, $a_{2^k-1} = b_{2^k} - 1$, $k \ge 0$. It is not hard to see that the general formula for $b_n$ is
$$b_n = \frac{(2 + \sqrt{3})^n + (2 - \sqrt{3})^n}{2}, \quad n \ge 2. \qquad (1)$$
Let $k \ge 3$ be fixed. It follows from (1) that $b_{2^k} = \sum_{j=0}^{2^{k-1}} \binom{2^k}{2j} 2^{2^k-2j} 3^j$ and thus
$$b_{2^k} \equiv 1 \pmod{3} \text{ and } b_{2^k} \equiv 1 \pmod{4}. \quad (2)$$
It is easy to see that the terms of the sequence, defined by $c_n = \frac{(2+\sqrt{3})^n - (2-\sqrt{3})^n}{2\sqrt{3}}$,
are positive integers, which satisfy $b_n^2 - 3c_n^2 = 1$ for all $n \in \mathbb{N}$. In particular, we have
$$b_{2k}^2 - 1 = 3c_{2k}^2. \tag{3}$$
Applying the identity $(x^{2^s} - y^{2^s})(x^{2^s} + y^{2^s}) = (x^{2^{s+1}} - y^{2^{s+1}})$ with $x = 2+\sqrt{3}$ and $y = 2-\sqrt{3}$
for $s = 0, 1, \dots, k-1$, we get
$$2\sqrt{3} \prod_{j=0}^{k-1} (2b_{2^j}) = (2 + \sqrt{3})^{2k} - (2 - \sqrt{3})^{2k}.$$
Therefore,
$$c_{2^k} = 2^{k+1} b_2 b_{2^2} \dots b_{2^{k-1}}. \qquad (4)$$
It follows from (2) and (3) that
$$2 \mid b_{2^k} + 1; \text{ and } \gcd(b_{2^j}, 6) = 1 \text{ for every } j = 1, 2, \dots, k-1. \quad (5)$$
Since $b_{2^k} + 1 \equiv 2 \pmod{3}$, by (3), (4) and (5) we have
$$3 \mid b_{2^k} - 1 \text{ and } 2^{2^{k+1}} \mid b_{2^k} - 1. \qquad (6)$$
Now, suppose that there exists an $m \ge 3$ such that $b_{2^m} - 1$ has at most two prime factors. Then it follows from the relations in (2) that these prime factors must be 2 and (or) 3. Furthermore, (6) implies that we must have $b_{2^m} = 2^{2^{m+1}} \cdot 3 + 1$ (7). Therefore, by (3) we get
$$c_{2^m}^2 = \frac{b_{2^m}^2 - 1}{3} = 4^{m+1}(3.4^m + 1). \qquad (8)$$
On the other hand, by (4) we have $c_{2^m}^2 = 4^{m+1} \prod_{j=1}^{m-1} b_{2^j}^2 > 4^{m+1}(3c_{2^{m-1}}+1)$, and thus $c_{2^m}^2 > 4^{m+1}(3.4^m + 1)$ as $c_{2^{m-1}} \ge 2^m$ by (4). This is a contradiction to (8) and therefore $a_{2^{k-1}}$ has at least three prime factors for every positive integer $k \ge 3$.

Alternative solution:

This approach is based on the fact that all linear sequences are periodic modulo arbitrary positive integer. We show that $a_{2^{k-1}}$ is divisible by $2$, $3$, $7$. Observe that if $a_n$ is even for some $n$, then $a_{n+2} = 4a_{n+1} - a_n + 2$ is also even. Since $a_1 = 6$ is even, we conclude that $a_{2t-1}$ is even for all positive integers $t$. Therefore, $a_{2^{k-1}}$ is even.
Let $b_n = a_n \pmod{3}$. Since $b_0 = 1$ and $b_1 = 0$, it follows by induction that $b_{2t} = 1$ and $b_{2t+1} = 0$. Hence, $b_{2^{k-1}} = 0$, i.e. $a_{2^{k-1}}$ is divisible by $3$.
Let $c_n = a_n \pmod{7}$. We have
$$c_0 = 1,\ c_1 = -1,\ c_2 = -3,\ c_3 = -2,\ c_4 = -3,\ c_5 = -1,\ c_6 = 1,\ c_7 = 0,\ c_8 = 1,\ c_9 = -1.$$
Since $c_0 = 1$, $c_1 = -1$ and $c_8 = 1$, $c_9 = -1$, we conclude that the sequence $c_1, c_2, \dots$ is periodic with period $8$. It follows from $c_7 = 0$ that $c_{7+8t} = 0$ for all positive integers $t$. It remains to notice that $2^k - 1 = 7 + 8(2^{k-3} - 1)$, implying that $c_{2^{k-1}} = 0$. Therefore, $a_{2^{k-1}}$ is divisible by $7$.