I searched for primes of the form $p^p+2$, where $p$ is prime for a range of $p \le 10^5$ on PARI/GP and found that 29 is the only prime of this form in this range.


$(1)$ Is $29$ the only prime of the form $p^p+2$, where $p$ is prime?

$(2)$ If not, then are there a finite number of primes of the form $p^p+2$? Can you prove/disprove this?

Edit: Since $p^p$ grows really fast and primes get rarer and are spread farther out for large numbers,

I conjecture that $29$ is the only prime of the form $p^p+2$ where $p$ is a prime.

  • 3
    $\begingroup$ I think (2) is likely. maybe (1) as well, and hard to decide. Primes are rare far out, and $p^p$ grows rapidly. Did the question occur to you for any reason other than random curiousity ? $\endgroup$ May 8 '19 at 21:09
  • 2
    $\begingroup$ @EthanBolker Well I like trying to find rare primes, and since $p^p$ grows rapidly I figured primes like that were rare. But still it would be really nice to prove that 29 is the only prime of this form $\endgroup$
    – Mathphile
    May 8 '19 at 21:14
  • 12
    $\begingroup$ @Mathphile For $p=239$ , there is no small factor. So, there is no easy way to show that $p=3$ is the only soluton, if this is actually the case. Did you really arrive at $p=10^6$ ? The number $p^p+2$ is huge for primes near $10^6$. $\endgroup$
    – Peter
    May 8 '19 at 21:29
  • 3
    $\begingroup$ I would guess that there are only a finite number of primes. There are about a $(p \log^2 p)^{-1}$-fraction of numbers of size roughly $p^p$ that are prime, by the Prime Number Thm. So--making some leaps of logic admittedly--it is tempting to say that the number of primes of this form is something like $\sum_{p} (p \log^2 p)^{-1}$ which is bounded $\endgroup$
    – Mike
    May 8 '19 at 22:09
  • 1
    $\begingroup$ Neither $3$ is square module $29$ nor $29$ is square modulo $3$. Would this be a necessary condition? Or perhaps that the two primes are or are not simultaneously quadratic residue one of the other? $\endgroup$
    – Piquito
    May 9 '19 at 0:48

With pfgw, I checked $$p^p+2$$ for the primes from $\ 3\ $ to $\ 24\ 001\ $ The only prime occured for $\ p=3\ $ Hence if another prime of this form exist, it must have more than $\ 100\ 000\ $ digits

  • 1
    $\begingroup$ What is hardware configuration on which you are able to check primality of 100000 digit numbers? $\endgroup$ May 9 '19 at 8:09
  • 4
    $\begingroup$ The program pfgw is specially designed for testing huge numbers for primality. I used the default trial division. I also doublechecked with factordb. Upto $p=20\ 000$ , no other prime. $\endgroup$
    – Peter
    May 9 '19 at 8:22
  • $\begingroup$ So you ran the program on normal laptop? I mean what was the configuration and runtime? $\endgroup$ May 9 '19 at 8:24
  • 2
    $\begingroup$ On a normal PC. No special hardware. It took several hours however on my slow computer. $\endgroup$
    – Peter
    May 9 '19 at 8:25
  • 1
    $\begingroup$ now with my information linked you might be able to push that into millions. $\endgroup$
    – user645636
    May 9 '19 at 19:24

Some working, but no solution:

Note that $p=2$ doesn't work, and $p=3$ does work. Now suppose $p > 3$.

Suppose $p \equiv 1 \pmod{3}$. Then $p^p + 2 \equiv 1^p + 2 \equiv 0 \pmod{3}$, so it isn't prime.

Therefore, $p \equiv -1 \mod{3}$ and $p$ odd so $p \equiv -1 \mod{6}$. This is as far as I could get. Using WolframAlpha for this case yields numbers that do not have many prime factors, and these factors being distinct and large, so I don't see any way to progress from here.

  • 3
    $\begingroup$ Euler's totient theorem and a larger modulus might help. $\endgroup$
    – user645636
    May 9 '19 at 17:51

It seems reasonable to expect that 29 is the only prime, just because primes get rare as numbers get big, so we'd expect almost all of these numbers to be composite.

That is, heuristically, the prime number theorem gives us the "probability" that a number $n$ is prime is about $\frac{1}{\ln(n)}$.

Therefore, the expected number of primes of this form should be $$ \sum_p \frac{1}{\ln(p^p + 2)} < \sum_p \frac{1}{p \ln(p)} $$ where the sum is over all odd primes. This latter sum converges, as shown in $\sum_{p \in \mathcal P} \frac1{p\ln p}$ converges or diverges?, to roughly 0.92 (the sum over all primes is less than 1.64; the sum over all odd primes omits the term $\frac{1}{2\ln(2)}$.)

So, we'd "expect" to find about one prime of this form, and we have.

Of course, this isn't a proof; it assumes that numbers of the form $p^p + 2$ behave "randomly" with respect to prime factorization, rather than the factors having some special properties.

(Note that applying the same argument to numbers of the form $n^n + 2$, without the requirement that $n$ be prime, gives an expected number of primes approximately $\sum \frac{1}{n\ln(n)}$, which is infinite. Indeed, there are already 5 examples before 2000, at $n = 0, 1, 3, 737, 1349$.)

Compare Hardy and Littlewood's Conjecture E in Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes:

There are infinitely many primes of the form $m^2 + 1$. The number $P(n)$ of such primes less than $n$ is given asymptotically by $$P(n) \sim C \frac{\sqrt{n}}{\ln(n)}$$ where $$C = \prod_{p=3}^\infty \Biggl(1 - \frac{1}{p-1}\biggl(\frac{-1}{p}\biggr)\Biggr).$$

Also Conjecture K, which gives an aysmptotic number of primes of the form $m^3 + k$ for any fixed $k$ (except when $k$ is a cube).


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.