Related to greatest prime number that divides $n.$

Solution 1:

For briefer notation let $n \in G$, iff $p(n-1) < p(n) < p(n+1)$ (G is for "good"). Also, say that $n \in P$ iff $p(n) > p(n-1),p(n+1)$ (P is for "peak"). The key to the solution is the following simple observation:

Observation: If $n \in P$ then either $n^2 \in G$ or $n^2 \in P$.

Proof: Suppose that $p(n) > p(n-1),p(n+1)$ and $n^2 \not \in G$. Because $n^2-1 = (n-1)(n+1)$, we have that $p(n^2) = p(n) > p(n^2-1)$. Thus, the only way for $n^2 \not \in G$ is if $p(n^2) > p(n^2+1)$. Then clearly $n^2 \in P$. $\square$

We want to prove that $G$ is infinite. For a proof by contradiction, suppose that $G$ is finite. Because $\limsup p(n) = + \infty$, we can select arbitrarily large $n_0$ with $p(n_0)>p(n_0-1)$. If $n_0 > \max G$ (so in particular $n_0 \not \in G$), then $p(n_0) > p(n_0+1)$ and hence $n_0 \in P$.

Let $n_1:= n_0^2$, $n_2 = n_1^2$, and generally $n_{i+1} = n_i^2$ (so in closed form $n_i = n_0^{2^i}$). Because of the above observation, and because $n_0^2 \not \in G$, we have $n_1 = n_0^2 \in P$. Likewise, $n_2 = n_1^2 \in P$, and inductively $n_i \in P$ for all $i$.

Let $p_0 = p(n_0)$. Clearly, $p(n_i) = p_0$ for all $i$. In paricular, $p_0 > p(n_i+1)$ for all $i$. Let $m_i := n_i+1$, and note that $m_{i+1} = (m_i-1)^2+1$. Thus, we have $m_{i+1} \equiv 2 \pmod{m_i}$, $m_{i+2} \equiv 2 \pmod{m_i}$ and generally $m_{j} \equiv 2 \pmod{m_i}$ for $j > i$. Thus, $m_i$ do not share any prime factors, except for $2$. Because $m_i$ are obviously larger than $2$ and are not divisible by $4$, we see that $p(m_i) > 2$ all take different values for different $i$. At the same time, $p(m_i) < p_0$ by construction. Thus, we arrive at a contradiction proving the initial claim.

Solution 2:

If $q$ and $2q+1$ are both prime, with $q > 3$, then $p(2q-1)$ must be less than $q$. This is because one of the three consecutive integers $2q-1,2q,2q+1$ must be divisible by $3$, and we know that $2q$ and $2q+1$ are not. So $3 | (2q-1)$, thus $p(2q-1) \le (2q-1)/3 < q$. So we have the increasing sequence:

$$p(2q-1) < q$$ $$p(2q) = q$$ $$p(2q+1) = 2q+1$$

Such primes $q$ are called Sophie Germain primes, and it is conjectured (though not proven) that there are an infinite number of them.

Edited to add:

And if $2^n+1$ is prime, but $2^{n+1}+1$ is not, then we have the increasing sequence:

$$p(2^{n+1}) = 2$$ $$3 \le p(2^{n+1}+1) < 2^n$$ $$p(2^{n+1}+2) = 2^n+1$$

If $2^n+1$ is prime, then $n$ must be a power of two, and $2^n+1$ is called a Fermat prime. Again, whether there are an infinite number of Fermat primes is an open problem.