INMO 2025 Problem 1

Consider the sequence defined by $a_1 = 2$, $a_2 = 3$, and $$a_{2k+1} = 2 + 2a_k, a_{2k+2} = 2 + a_k + a_{k+1},$$ for all integers $k \geq 1$. Determine all positive integers $n$ such that $$\frac{a_n}{n}$$ is an integer.

Proposed by Niranjan Balachandran, SS Krishnan, and Prithwijit De.