# A problem involving greatest prime divisors

For any positive integer $n>1$, let $p(n)$ denote the greatest prime divisor of $n$. Show that there are infinitely many positive integers $n$ with $$p(n)<p(n+1)<p(n+2).$$

• This is a problem proposed in the 2006 Germany tst for the IMO. I suggest you to check the website AoPS. – Xam Jun 1 '17 at 1:26
• @Xam There seems to be a similar problem from the 2006 Germany tst, but they define $p(n)$ to be number of different prime divisors of $n$, rather than the greatest prime divisor. – Richard Jun 1 '17 at 1:30
• Richard, I'm sorry for misreading your question. Otoh, I'm pretty sure you can modify the argument of the other problem to apply it into your problem. – Xam Jun 1 '17 at 1:36
• I observe that $p(2^k) = 2 < 3 \leq p(2^k+1)$ for all $k \in \{1, 2, 3,...\}$, which may help. Also, $p(2^k +2) = p(2(2^{k-1}+1)) = p(2^{k-1}+1)$. – Michael Jun 1 '17 at 2:14
• From the above comment, it seems that if your result was false, so that $p(2^k+1) > p(2^k+2)$ for all sufficiently large $k$ (recall that consecutive integers have no common factors so we know $p(2^k+1)\neq p(2^k+2)$), then the sequence $p(2^k+1)$ would be strictly increasing for all sufficiently large $k$ (since $p(2^{k+1}+1)>p(2^{k+1}+2)= p(2^{k}+1)$ with inequality holding for all sufficiently large $k$), which may lead to some contradiction. – Michael Jun 1 '17 at 2:25

This is a result of P. Erdős and C. Pomerance, On the largest prime factors of n and n+1. The OEIS sequence is A071869. The proof from the paper quoted:

Suppose $p$ is an odd prime and $$k_0 = \inf\{k:P(p^{2^k}+1) > p\}$$ (note that $P(p^{2^{k_0}} + 1) \equiv 1 \: \mbox{($\mbox{mod } 2^{k_0+1}$)}$, so $k_0 <\infty$). Then $$P(p^{2^{k_0}}-1) < P(p^{2^{k_0}}) < P(p^{2^{k_0}}+1).$$

• How did they conclude $P(p^{2^{k_0}}-1) < P(p^{2^{k_0}})$? [I see the next inequality $< P(p^{2^{k_0}}+1)$ holds by definition of $k_0$.] Also, how did you find this particular paper? – Michael Jun 1 '17 at 2:59
• @Michael I'm afraid I can't look into their minds, so I don't know. I haven't read the full paper, just skimmed until I found what looked like the right identity. I found the paper through OEIS, and I found the OEIS sequence by implementing the problem quickly in Python and looking up the first solutions. – orlp Jun 1 '17 at 3:00
• Wow! That is a very interesting sequence of events that lead you to the paper! I am glad I asked! – Michael Jun 1 '17 at 3:01
• @Michael Honestly, if it takes less than 5 minutes to implement I usually do it because OEIS is just a treasure trove. It's my go-to place to find references/formulas, etc. As for the obscurity, P. Erdős should ring a bell with any mathematician, and Google scholar says it has 38 citations, which is pretty good. – orlp Jun 1 '17 at 3:02
• I figured out how the first inequality holds: $p^{2^{k_0}}-1 = (p-1)(p+1)(p^2+1)(p^{2^2}+1)...(p^{2^{k_0-1}}+1)$, so $P(p^{2^{k_0}}-1)\leq \max[P(p-1), ..., P(p^{2^{k_0-1}}+1)] \leq p$ by definition of $k_0$ (and hence $< p$ since $P(p^{2^{k_0}}-1) \neq P(p^{2^{k_0}}) =p$). Amazing Erdos felt no need to write this! I also observe on page 320 that he writes the following unusual sentence, which only he could get away with: "However we cannot prove either of these two patterns occurs for a positive density of n, although this certainly must be the case." – Michael Jun 1 '17 at 4:42

If we assume the truth of the strongly-conjectured infinitude of Sophie Germain primes:

Take $n{+}2$ as a safe prime. Then $n{+}1$ is twice a Sophie-Germain prime, and $n$ is divisible by $3$ so has a smaller largest prime factor than the two larger numbers.