Competition problem — Number theory

Library / /17 of 92

Number theory Difficulty 5.9 AIME, harder Prove it Iran

Determine all increasing sequence $a_1, a_2, a_3, \ldots$ of positive integers such that for every $i, j \in \mathbb{N}$ , the number of positive divisors of $i + j$ and $a_i + a_j$ are equal (A sequence $a_1, a_2, a_3, \ldots$ is increasing if $i \le j$ implies $a_i \le a_j$ ).

Solution

First it is easy to show that the sequence is strictly increasing. Assume that $a_i = a_{i+1}$ for some $i$ . Let $j = p - i$ for a large prime $p$ . Now $i + j$ is a prime number. So $a_i + a_j$ is prime too. But from $a_i = a_{i+1}$ we get $a_{i+1} + a_j$ and $i + 1 + j$ are prime numbers. So $i + j$ and $i + j + 1$ are two consecutive large prime numbers, contradiction.

Now put $i = j = 2^{p-2}$ for a large prime $p$ . So the number of divisors of $2a_i = 2^{p-1}$ equals $p$ . Hence $2a_i$ is of the form $q^{p-1}$ for a prime $q$ . Obviously $q$ should be $2$ and therefore we have $a_{2^{p-2}} = 2^{p-2}$ .

Now we have a strictly increasing sequence of integers with infinitely many fixed points. So, for each $n$ , $a_n = n$ . $\square$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.