For each positive integer $m> 1$, let $P (m)$ be the product of all prime numbers that divide $m$. Define the sequence $a_1, a_2, a_3,...$ as followed: $a_1> 1$ is an arbitrary positive integer, $a_{n + 1} = a_n + P (a_n)$ for each positive integer $n$. Prove that there exist positive integers $j$ and $k$ such that $a_j$ is the product of the first $k$ prime numbers.
Problem
Source: Peru IMO TST 2018 p10
Tags: recurrence relation, number theory, number theory with sequences, Product, primes
15.05.2019 03:50
For a positive integer $m$, let's define $Q(m) = \frac{m}{P(m)},$ and call this the "excess function" of $m$. Also, let's define the function $f(n) = n + P(n).$ For two positive integers $a, b \in \mathbb{N},$ let's say that $b$ is reachable from $a$ if $f^{(k)}(a) = b$ for some $k \in \mathbb{N}.$ We'll begin by showing the following useful lemma. Lemma. If $n \in \mathbb{N}$ has excess function $>1$, then there exists some $t \in \mathbb{N}$ with $Q(t) = 1$ such that $t$ is reachable from $n$. Proof. Assume, for contradiction, that the statement of the lemma was false. The first observation is that $Q$ increases by at most $1$ with each application of $f$. With this in mind, let's consider the smallest prime $p > Q(n).$ If $k$ is the smallest $k$ with $Q(f^{(k)}(n)) = p-1$, then $Q(f^{(k+1)}(n)) = 1,$ and this would give a contradiction. Therefore, $Q(f^{(k)}(n)) \neq p-1$ for all $k \in \mathbb{N}.$ Hence, by our observation that $Q$ increases by at most one every time, we know that $Q(f^{(k)}(n)) < p-1$ for all $k \in \mathbb{N}.$ In particular, there are only a finite number of possible values for $Q(f^{(k)}(n)).$ Therefore, by finite Pigeonhole, there must exist some value which appears infinitely often, say $Q(f^{(k)}(n)) = c$ for infinitely many values of $k \in \mathbb{N}.$ Firstly, observe that there cannot ever be a prime divisor of $P(f^{(k)}(n))$ which is greater than $p$ for any $k \in \mathbb{N}.$ Therefore, since the set of positive integers with excess function $c$ and all prime divisors $\le p$ is bounded, we easily obtain a contradiction. $\blacksquare$ With this lemma in mind, we only need to solve the problem under the assumption that $a_1$ is squarefree. For any squarefree number $a$, if we let $p$ be the smallest prime number not dividing it, then it's clear that $ap$ is reachable from $a$ (just apply $f$ $(p-1)$ times). Therefore, if we let $p_1 < p_2 < \cdots$ be the prime numbers which do not divide $a_1$, then $a_1p_1$ is reachable from $a_1$, $a_1p_1p_2$ is reachable from $a_1p_1$, $a_1p_1p_2p_3$ is reachable from $a_1p_1p_2$, etc. In particular, $a_1p_1p_2 \cdots p_{a_1 + 10^{10^{10}}}$ is reachable from $a_1$, and so since this number satisfies the desired condition (being the product of the first $x$ prime numbers for some $x \in \mathbb{N}$, we're done. $\square$