# A high school Olympiad problem

Let $p(n)$ denote the largest prime factor of $n$. Prove that there are infinitely many $n$ such that $$p(n)<p(n+1)<p(n+2).$$

Edit:

My solution: Choose $n=\prod_{i=1}^{k}p_i$, product of the first $k$ primes. This means that $n+1=\prod_{i=1}^{k}p_i+1$ is either a larger prime or has a prime factor larger than that of all factors of $n$. Still not sure about $n+2$.

• @dxiv sorry for the demanding tone :) i forget that this isn't aops, apologies. – alphasquared Feb 6 '18 at 7:49
• Not sure if this gets to the answer, but suppose $n+2$ is a prime equal to 2 mod 3, of which there are infinitely many. Then $n+1$ is even and $n$ is divisible by 3, which puts a nice limit on how large the largest prime factor of each can be. – eyeballfrog Feb 6 '18 at 8:02
• @eyeballfrog thanks. I think this works as none of the prime factors of $n$ and $n+1$ can exceed $n+2$ itself. – alphasquared Feb 6 '18 at 8:06
• It's not quite there, as you have to prove $p(n) < p(n+1)$ infinitely often. This would be straightforward if $n+1$ was twice a prime infinitely often, but that has yet to be proven. So you'll have to be more clever than that. – eyeballfrog Feb 6 '18 at 8:12

## 1 Answer

The problem is solved in the paper by Erdos and Pomerance "On the largest prime factors of $n$ and $n+1$".

The proof in the paper is quite simple:

Fix a prime $l>2$ and define $k_0=\inf\{k\mid p(l^{2^k}+1)>l\}<\infty$. Then we have $p(n)<p(n+1)<p(n+2)$ when $n=l^{2^{k_0}}-1$.