IMO 2025 · Problem 4

A proper divisor of a positive integer \(N\) is a positive divisor of \(N\) other than \(N\) itself.

The infinite sequence \(a_1,a_2,\ldots\) consists of positive integers, each of which has at least three proper divisors. For each \(n\geq 1\), the integer \(a_{n+1}\) is the sum of the three largest proper divisors of \(a_n\).

Determine all possible values of \(a_1\).

Official text of the problem. Official problem paper (PDF)

Answer

The possible values are exactly \[ \boxed{a_1=6\cdot12^k m,\qquad k\in\mathbb Z_{\geq0},\quad m\in\mathbb Z_{>0},\quad \gcd(m,10)=1.} \]

Solution

For a positive integer \(N\) with at least three proper divisors, let \(T(N)\) be their three largest members’ sum. If \(d_1<d_2<d_3\) are the three smallest divisors of \(N\) greater than \(1\), allowing \(N\) itself, then \[ T(N)=\frac{N}{d_1}+\frac{N}{d_2}+\frac{N}{d_3}. \]

We first prove that every term of the given infinite sequence is divisible by \(6\).

Every term is even. If \(N\) is odd, all its divisors are odd, so \(T(N)\) is odd. Moreover, every proper divisor of \(N\) is at most \(N/3\). Since the three largest proper divisors are distinct, their sum is strictly less than \(N\). Consequently, an odd term would force all subsequent terms to form a strictly decreasing sequence of positive integers, which is impossible.

Every term is divisible by \(3\). We establish the following implication: \[ 2\mid N,\quad 3\nmid N,\quad 2\mid T(N) \quad\Longrightarrow\quad 3\nmid T(N). \]

Suppose first that \(4\mid N\). Then \(d_1=2\) and \(d_2=4\).

  • If \(d_3\) is even, then \(d_3/2\) is a divisor of \(N\) strictly between \(2\) and \(d_3\). It must therefore equal \(4\), so \(d_3=8\). Hence \[ T(N)=\frac{7N}{8}, \] which is not divisible by \(3\).
  • If \(d_3=q\) is odd, then \(4q\mid N\), and \[ T(N)=\frac{N}{4q}(3q+4). \] Neither factor is divisible by \(3\), so again \(3\nmid T(N)\).

Now suppose that \(4\nmid N\). Let \(p\) be the smallest odd prime divisor of \(N\), which exists because \(N\) has at least three proper divisors. Then \(d_1=2\) and \(d_2=p\). If \(d_3\) were odd, \(N/2\) would be odd while \(N/p\) and \(N/d_3\) would be even, making \(T(N)\) odd. Thus \(d_3\) is even. The smallest even divisor of \(N\) greater than \(2\) is \(2p\), so \(d_3=2p\). Therefore \[ T(N)=\frac{N}{2p}(p+3). \] Since \(3\nmid N\), neither \(N/(2p)\) nor \(p+3\) is divisible by \(3\). This proves the implication.

Furthermore, whenever \(N\) is even and not divisible by \(3\), we have \(d_1=2\), \(d_2\geq4\), and \(d_3\geq5\). Thus \[ T(N)\leq N\left(\frac12+\frac14+\frac15\right) =\frac{19N}{20}<N. \] We already know that every term of our sequence is even. Hence, if some term were not divisible by \(3\), the implication above would ensure that no subsequent term was divisible by \(3\), and the sequence would thereafter strictly decrease. This is impossible. Therefore \[ 6\mid a_n\qquad\text{for every }n\geq1. \]

We now determine the evolution of multiples of \(6\). Their two smallest divisors greater than \(1\) are \(2\) and \(3\), and the third is \(4\), \(5\), or \(6\). Consequently, \[ T(N)= \begin{cases} \dfrac{13N}{12},&4\mid N,\\[4pt] \dfrac{31N}{30},&4\nmid N,\ 5\mid N,\\[4pt] N,&4\nmid N,\ 5\nmid N, \end{cases} \qquad (6\mid N). \] In the middle case, \(N/30\) is odd, so \(T(N)\) is odd. This case cannot occur in our sequence.

Thus every transition either multiplies the current term by \(13/12\), or leaves it fixed. Each multiplication by \(13/12\) decreases the exponent of \(2\) in the term’s prime factorization by \(2\). Since every term is even, there can be only finitely many such transitions. Once a term is fixed, all subsequent terms equal it.

Let there be exactly \(k\geq0\) transitions before the sequence becomes constant. Its first fixed term has the form \[ a_{k+1}=6u,\qquad \gcd(u,10)=1, \] because it is divisible by \(6\), but by neither \(4\) nor \(5\). Also, \[ 6u=\left(\frac{13}{12}\right)^k a_1, \] so \[ 13^k a_1=6\cdot12^k u. \] Since \(13^k\) is relatively prime to \(6\cdot12^k\), it divides \(u\). Writing \(u=13^k m\), we obtain \[ a_1=6\cdot12^k m,\qquad \gcd(m,10)=1. \] This proves necessity.

Conversely, take any \(k\geq0\) and positive integer \(m\) with \(\gcd(m,10)=1\). Starting from \(a_1=6\cdot12^k m\), the recurrence gives \[ a_{j+1}=6\cdot12^{k-j}13^j m \qquad (0\leq j\leq k). \] Indeed, for \(j<k\), the displayed term is divisible by \(12\), so the next term is \(13/12\) times it. The resulting term \[ a_{k+1}=6\cdot13^k m \] is divisible by neither \(4\) nor \(5\), and hence is fixed by \(T\).

All these terms are multiples of \(6\), so each has the three distinct proper divisors \(1,2,3\). The sequence therefore continues indefinitely and satisfies every requirement. This proves sufficiency.

The solution was checked against the official IMO shortlist solutions.