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

  • $\begingroup$ This is a problem proposed in the 2006 Germany tst for the IMO. I suggest you to check the website AoPS. $\endgroup$ – Xam Jun 1 '17 at 1:26
  • $\begingroup$ @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. $\endgroup$ – Richard Jun 1 '17 at 1:30
  • $\begingroup$ 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. $\endgroup$ – Xam Jun 1 '17 at 1:36
  • $\begingroup$ 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)$. $\endgroup$ – Michael Jun 1 '17 at 2:14
  • $\begingroup$ 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. $\endgroup$ – 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).$$

  • $\begingroup$ 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? $\endgroup$ – Michael Jun 1 '17 at 2:59
  • $\begingroup$ @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. $\endgroup$ – orlp Jun 1 '17 at 3:00
  • $\begingroup$ Wow! That is a very interesting sequence of events that lead you to the paper! I am glad I asked! $\endgroup$ – Michael Jun 1 '17 at 3:01
  • $\begingroup$ @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. $\endgroup$ – orlp Jun 1 '17 at 3:02
  • $\begingroup$ 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." $\endgroup$ – 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.


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.