Team Selection Test for IMO 2024

Answer: 36.

We will show that this sequence is increasing and consists of all the numbers of the form $p^{2^n}$, where $p$ is a prime and $n$ is a non-negative integer. Thus, all the terms satisfying the condition are $1,2,11,23,\dots ,2^{1024},11^{1024},23^{1024},2^{2048},2^{4096}$.

Let $S$ be the set of positive integers of the described form $p^{2^n}$. We will use induction to prove that $a_n$ is the $n^{\text{th}}$ smallest number of $S$. It is easy to verify that for $n=1,2$ the statement is correct. Assume that it is true for $a_1,a_2,\dots ,a_{n-1}$. Note that the $n^{\text{th}}$ smallest term in the set $S$ already satisfies the problem condition. We will consider two cases.

For the first case, assume that $a_n$ has only one prime divisor, say $p$. If there are no other terms among the first $n-1$ that is not divisible by $p$, then we must have $a_n=p$ by the minimality assumption. Otherwise, assume it is equal to $p^y$ for some $y$. By the induction hypothesis, all the previous terms that are divisible by $p$ are $p,p^2,\dots ,p^{2^{x-1}}$ for some $x$. Then, since the $\sigma$ function is multiplicative for relatively prime numbers we should only consider the powers of $p$ for the divisibility condition. Then, we must have $p^{2^x-1}\mid p^{2^x+y}-1$ which means $2^x\mid 2^x+y$ hence $y\ge 2^x$. Which means, we must have $a_n=p^{2^x}$ since it is the smallest possible choice for $a_n$ and it satisfies the problem conditions. Note that in this case $a_n$ is in the set $S$, it is a number that has not appeared before, and it is the minimal possible number in $S$ satisfying these conditions as claimed.

For the second case, assume that $a_n$ has at least two distinct prime divisors. Let ${\prod }_{i=0}^{n-1}{a}_i=c_n$. By the minimality condition, we can assume that $a_n$ has no prime divisors that is relatively prime to $c_{n-1}$, because in that case that prime divisor itself would satisfy the condition and it is smaller than $a_n$. Assume that the prime divisors of $a_n$ represented in the product $c_{n-1}$ be $p_i^{x_i}$ for $1\le i\le k$ and represented in the product $c_n$ be $p_i^{y_i}$ for $1\le i\le k$. By the induction hypothesis, we have $x_i=2^{z_i}-1$. Therefore, using the divisibility condition we have $$\prod _{i=1}^k(p_i^{2z_i}-1)\mid \prod _{i=1}^k(p_i^{y_i}-1).$$ Since there are at least two primes, at least one of them are odd and both sides are even. Comparing the $v_2$ valuation of both sides and using the LTE Lemma, we have $$v_2(p_i^{2z_i}-1)=v_2(p-1)+v_2(p+1)+z_2-1$$ and $$v_2(p_i^{y_i}-1)\le v_2(p-1)+v_2(p+1)+v_2(y_i)-1$$ therefore at least one index $i$ must satisfy $v_2(y_i)\ge z_i$ and since we have non-negative powers this implies $y_i>2^{z_i}$ and $y_i\ge 2^{z_i+1}$. Then, choosing $a_n=p_i^{2^{z_i}}$ also satisfies the condition and it contradicts the minimality condition. Therefore, $a_n$ can not have two distinct prime divisors. We are done.