Find all primes of the form $n^n + 1$ less than $10^{19}$ Find all primes of the form $n^n + 1$ less than $10^{19}$
The first two primes are obvious: $n = 1, 2$ yields the primes $2, 5$. After that, it is clear that $n$ has to be even to yield an odd number.
So, $n = 2k \implies p = (2k)^{2k} + 1 \implies p-1 = (2k)^{k^2} = 2^{k^2}k^{k^2}$. All of  these transformations don't seem to help. Is there any theorem I can use? Or is there something I'm missing?

How can you factorize $x^k+1$? Well you can do that if $k$ is odd.
So we can factorize $n^n+1$ if $n$ has an odd prime factor, in other words if $n$ is not a power of $2$.
More precisely, if $n=dk$ with $k>1$ odd we see that $n^n+1=(n^d)^k+1$ is divisible by $n^d+1$ and hence not a prime.
So we are left to check the cases where $n=2^k$.
If $n=1,2$ you already checked.
If $n=4$ we have $4^4+1=257$ is a prime.
If $n=8$ we have $8^8+1=2^{24}+1$ is divisible by $2^8+1$ as above.
And then one checks that $16^{16}+1$ is already larger than $10^{19}$.
One way to see this is to note that
$16^{16}=2^{64}=16 \cdot 1024^6>10 \cdot 1000^6=10^{19}.$
