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).$$


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$.

  • 1
    $\begingroup$ @dxiv sorry for the demanding tone :) i forget that this isn't aops, apologies. $\endgroup$ – alphasquared Feb 6 '18 at 7:49
  • 2
    $\begingroup$ 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. $\endgroup$ – eyeballfrog Feb 6 '18 at 8:02
  • $\begingroup$ @eyeballfrog thanks. I think this works as none of the prime factors of $n$ and $n+1$ can exceed $n+2$ itself. $\endgroup$ – alphasquared Feb 6 '18 at 8:06
  • 2
    $\begingroup$ 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. $\endgroup$ – eyeballfrog Feb 6 '18 at 8:12

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.