Clearly, for fixed $p$, the numbers $n$ for which $p|n^2+1$ are in two residue classes: $a\mod p$ and $-a\mod p$. (1a) $P(x^2+x+1)=\max\{P(x),P(x+1)\}$ (1b) $P(2x^2)=\max\{P(2x-1),P(2x+1)\}$ (these follow from factorizations) (2) We have $P(2n-1)\le P(2n+1)\ge P(2n+3)$ for infinitely many $n$. (If there were finitely many such $n$, then the sequence $p_n=P(2n-1)$ would be increasing after a while; but $p_n$ can be $2$ or of the form $4k+1$ because it divides a number of the form $N^2+1$, hence in this case, we'd have $p_n\sim 4n$. But this contradicts (1a) for large $n$.) Next idea: if $P(2n-1)\le P(2n+1)\ge P(2n+3)$, then using (1b), we get $P(2n^2)=P(2(n+1)^2)=P(2n+1)=:p$. Also, take the smallest $a$ such that $p|a^2+1$, then if $a$ and $p-a$ aren't among $2n+1,2n^2,2(n+1)^2$, then we have found four numbers with $P(\cdot)=p$. Exception: $a=2n+1$, $p-a=2n^2$, so $p=2n^2+2n+1$. Now we still can do more. If $P(2n)\le P(2n+1)$, then from (1a), we also have $P(4n^2+2n+1)=p$, done. Similarly done if $P(2n+2)\le P(2n+1)$. The remaining case: $P(2n),P(2n+2)>P(2n+1)$. So now we can get using the previous idea that $P(2n) = P(4n^2-2n+1) = P(4n^2+2n+1) = q $ $P(2n+2)=P((2n+2)(2n+1)+1)=P((2n+2)(2n+3)+1)= q'$ Similarly, we are not done only when $4n^2+1=q$ and $(2n+2)^2+1=q'$. Finishing idea: for large $n$, surely $p,q,q'>5$. But we have $(2n)^2+1=q$, $(2n+1)^2+1=2p$, $(2n+2)^2+1=q'$. These are not divisible by $5$, which is only possible if $2n,2n+1,2n+2$ are $-1,0,1$ modulo $5$, respectively. Finally, let $b$ be the smallest number such that $q|b^2+1$. We have $b=2n$ and $q-b=4n^2-2n+1$ and $q+b=4n^2+2n+1$. So $b=-1\mod 5$ and $q=2\mod 5$. We claim that $P(3q-b)$ is $=q$. This is true because $(3q-b)^2+1$ is divisible by $10$ (as $3q-b$ is $2\mod 5$ and it is odd), and it is smaller than $10q^2$. So done: $P(b)=P(q-b)=P(q+b)=P(3q-b)$.

This is problem A. 643. from KöMaL. http://www.komal.hu/verseny/feladat.cgi?a=honap&l=en&h=201504&t=mat