7
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ @dxiv sorry for the demanding tone :) i forget that this isn't aops, apologies. $\endgroup$
    – QFTheorist
    Commented Feb 6, 2018 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$ Commented Feb 6, 2018 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$
    – QFTheorist
    Commented Feb 6, 2018 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$ Commented Feb 6, 2018 at 8:12
  • $\begingroup$ @eyeballfrog To show $p(n)<p(n+1)$ infinitely often, we just need that $n+1$ is prime infinitely often, which is true. $\endgroup$ Commented May 13, 2020 at 21:39

1 Answer 1

10
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .