Pqr

Rewrite the equation as $p^{n} = r^{2} - q^{2} = (r - q)(r + q)$ . Now if both $r$ and $q$ are odd primes then $r^{2} - q^{2}$ , and hence also $p^{n}$ , will be even, implying that $p = 2$ . Since $r \gt q \gt 0$ we can let $r - q = 2^{a}$ and $r + q = 2^{b}$ such that $b \gt a \ge 1$ and $a + b = n$ . Adding these two equations gives us that

$2r = 2^{a} + 2^{b} = 2^{a}(1 + 2^{b-a}) \Longrightarrow r = 2^{a - 1}(1 + 2^{b-a})$ .

Now since $r$ is an odd prime it cannot be divisible by $2$ , implying that $a = 1$ , and thus that $r = 2^{b - 1} + 1$ , making $r$ a Fermat prime , of which there are only 5, namely $3,5,17,257$ and $65537$ . Now $r - q = 2^{a} = 2^{1} = 2$ and so $q = r - 2$ . For the 5 Fermat primes $r$ in only one case is $r - 2$ also prime, namely $r = 5, q = 3$ , for which $r^{2} - q^{2} = 25 - 9 = 16 = 2^{4}$ , making $n = 4$ the only possible value for $n$ in this case, (unless another Fermat prime is found that has a lesser "twin" prime, both situations being highly unlikely).

Next we must consider the case where not both of $r,q$ are odd primes, i.e., where $q = 2$ . We then will require that $p^{n} = (r - 2)(r + 2)$ . Again let $r - 2 = p^{a}$ and $r + 2 = p^{b}$ such that $a \lt b$ and $a + b = n$ . Then

$2r = p^{a} + p^{b} = p^{a}(1 + p^{b-a})$ .

Now as both $r - 2$ and $r + 2$ are odd we know that $p \ne 2$ and thus that $1 + p^{b - a}$ is even and hence divisible by $2$ . This implies that $r = kp^{a}$ for some positive integer $k = \dfrac{1}{2}(1 + p^{b - a}) \gt 1$ . (Note that as $p \gt 2$ and $b \gt a$ we have that $1 + p^{b - a} \ge 4$ , and thus $k \ge 2$ ). But since $r$ is prime it can only be divisible by both $k \gt 1$ and $p^{a}$ if $p^{a} = 1 \Longrightarrow a = 0$ . This implies that $r - 2 = p^{a} = 1 \Longrightarrow r = 3$ , for which $r^{2} - q^{2} = 9 - 4 = 5 = 5^{1}$ , thus making $n = 1$ the only possible value for $n$ if $q = 2$ .

Having analyzed all possible cases, we thus find that the only possible values for $n$ are $4$ and $1$ , the sum of which is $\boxed{5}$ .

Here is a solution without considering Fermat primes. Similarly, let $p^n = (r-q)(r+q)$ . This means that $r-q = p^a, r+q = p^b$ where $a,b$ are non-negative integers. First, we get $2r = p^a + p^b$ . Let's first consider the case when $a = 0$ . Thus $2r = 1 + p^b \implies r = \frac{p^b + 1}{2}$ . But with this we find that $q = \frac{p^b - 1}{2}$ . Thus, $r,q$ are a pair of consecutive primes which we know can only be $2,3$ . Fixing $r = 3, q = 2$ we get $r - q = 1, r+q = 5$ and the solution $5^1 + 2^2 = 3^2$ , making $n=1$ one of the numbers we were looking for.

If $b=0$ we have that $r+q = 1$ which is impossible because primes are at least bigger than $1$ .

Let's consider the case $\min \{ a,b \} \geq 1$ . Then from $2r = p^a + p^b$ we get that $2r \equiv 0 \mod p$ . This can only happen in two cases: first, if $r=p$ which would lead to the equation $p^n + q^2 = p^2 \implies q \equiv 0 \mod p \implies q = p \implies p^n + p^2 = p^2$ which is a contradiction. And second, if $p = 2$ . If this is the case we have $r = 2^{a-1} + 2^{b-1}$ . (Note that the exponents cause no problem because of the minimality property of $a,b$ ). However, if $\min \{ a, b \} \geq 2$ we have that $r \equiv 0 \mod 2 \implies r=2$ . This gives us the equation $2^n + q^2 = 2^2$ which is a contradiction (see one of the cases above). This means that either $a$ or $b$ have to equal $1$ .

If $a=1$ then $r = 2^{b-1} + 1$ . And then $r - q = 2^a \implies q = 2^{b-1} - 1$ . Notice that because of this, it is always the case that one of $r,q$ is divisible by 3 and thus is equal to 3. If $r = 3$ that means that $b = 2$ so $q = 2^1 - 1 = 1$ . This is a contradiction because $1$ is not prime. If $q = 3$ then $b = 3$ and thus $r = 2^2 + 1 = 5$ . Computing, this yields the solution $2^4 + 3^2 = 5^2$ . Showing that $n=4$ is one of the numbers we seek. We have already exhausted the possibilities of this case.

If $b=1$ then $r = 2^{a-1} + 1$ . But then $r+q = p^b \implies q = 2 - 2^{a-1} - 1 = 1 - 2^{a-1}$ . This is a contradiction because this will say that $q$ is a non-positive integer.

We have already exhausted all possibilities, showing that only $n=1,4$ have solutions.