How many primes of the form $3^n + n^3 $ exist?

Question

I was looking for primes of the form $3^n + n^3$ or equivalently of the form $9^m + 8 m^3$.

I was not able to find any ??

How many exist ?

What are the first few ?

It seems like a trivial thing I missed. Or maybe not since it somewhat resembles questions about fermat primes or mersenne primes. My intuition feels like there should be a mod argument or infinite descent. I listed a few factorizations but found no patterns.

Any help would be greatly appreciated!

Answer 1

You are looking at a special case of $x^y+y^x$.

For $x=3$, it is prime for $y=2, 56, 10112, 63880, 78296, 125330, 222748,\dots$ (see A253471).

For general $x,y\gt 1$, these are called Leyland primes (see A094133 and prime wiki).

Citing Paul Leyland:

More recently still, it was realized that numbers of this form are ideal test cases for general purpose primality proving programs. They have a simple algebraic description but no obvious cyclotomic properties which special purpose algorithms can exploit.

As with most types of primes, it is not known if there are infinitely many of these or not. This will likely remain unproven unless there is a big breakthrough.

Answer 2

A few things :

We can check mod 20 (as exponents mod 4 and bases mod 5 cycle that length) for your form using 9, and 8.

$3m^3-1$ or $ 3m^3+1$ can't be multiples of $5$ to be prime there are 5 cases of each of these . And each happens in 2 cases modulo 4.(The first happens if $m\bmod 4=1,3$ . The second happens if $m\bmod 4=0,2$ ). Noting $m^3$ and $(-m)^3$ are additive inverses mod 5, if $m$ works mod 5,then $-m$ works in the opposite form . Time to check cases :

0 logically fails to be 0 mod 5

1 fails in both so , therefore so will 4. Two cases fallen.

2 works in the second form so 3 works in the first. (Both give 0 mod 5)

So only $m$ that are $3,13 \bmod 20$ fit the first form for failure, and $ 2, 12 \bmod 20$ work in the second for failure.

In this sort of fashion ( using polynomial remainder theorem in bases, and Fermat's little theorem in exponents) you can continue, always eliminating cases modulo their product .

Answer 3

Checking small mods, there’s no obvious reason for all such numbers to be composite and there are in fact several small prime examples. In such cases, a useful heuristic is the Prime Number Theorem. Approximately, the probability of $n$ being prime is $1/\log(n)$. Therefore, the probability of $3^n+n^3$ is around $\frac{1}{n \log(3)}$. Since the harmonic series diverges, in expectancy, there are infinitely many such primes. Of course primes aren’t actually probabilistic and there might be some kind of hidden structure, so it’s not rigorous, but it seems likely that it’s likely true.