Problem 1107

§3.5a Solution
We claim the answer is no, such $P$ does not exist.
Clearly we may assume $P$ is nonconstant with positive leading coefficient. Fix $P$ and fix constants $n_{0}, c>0$ such that $c=P\left(n_{0}\right)>0$. We are going to prove that infinitely many terms of the sequence are at most $c$.
We start with the following lemma.
Claim - For each integer $n \geq 2$, there exists an integer $r=r(n)$ such that
- For any prime $p$ which is at most $n$, we have $\nu_{p}(P(r))=\nu_{p}(c)$.
- We have
$$\text { c. } \prod_{\text {prime } p \leq n} \leq r \leq 2 c \cdot \prod_{\text {prime } p \leq n} p \text {. }$$

Proof. This follows by the Chinese remainder theorem: for each $p \leq n$ we require $r \equiv n_{0}$ $\left(\bmod p^{\nu_{p}(c)+1}\right)$, which guarantees $\nu_{p}(P(r))=\nu_{p}\left(P\left(n_{0}\right)\right)=\nu_{p}(c)$. Then there exists such an $r$ modulo $\prod_{p \leq n} p^{\nu_{p}(c)+1}$ as needed.

Assume for contradiction that all $a_{i}$ are eventually larger than $c$. Take $n$ large enough that $n>c$ and $r=r(n)$ has $a_{r}>c$. Then consider the term $a_{r}$ :
- Using the conditions in the lemma it follows there exists a prime $p_{n}>n$ which divides $a_{r}=\operatorname{gcd}\left(P(r), \tau(P(r))\right.$ ) (otherwise $a_{r}$, which divides $P(r)$, is at most $c$ ).
- As $p_{n}$ divides $\tau(P(r))$, this forces $P(r)$ to be divisible by (at least) $q_{n}^{p_{n}-1}$ for some prime $q_{n}$.
- For the small primes $p$ at most $n$, we have $\nu_{p}(P(r))=\nu_{p}(c)n$.
- Ergo,
$$P(r) \geq q_{n}^{p_{n}-1}>n^{n} .$$

In other words, for large enough $n$, we have the asymptotic estimate
$$\text{n n 0 define}$$
$\delta(M):=\prod_{p \leq M}\left(1-\frac{1}{p}\right)$ .
$$$$

Then $\pi(n)<\delta(M) n+\prod_{p \leq M} p$, so it suffices to check that $\lim _{M \rightarrow \infty} \delta(M)=0$. But
$$\frac{1}{\delta(M)}=\prod_{p \leq M}\left(1-\frac{1}{p}\right)^{-1}=\prod_{p \leq M}\left(1+\frac{1}{p}+\frac{1}{p^{2}}+\ldots\right) \geq 1+\frac{1}{2}+\cdots+\frac{1}{M}$$
which diverges for large $M$.