$5^n+n$ is never prime? In the comments to the question: If $(a^{n}+n ) \mid (b^{n}+n)$ for all $n$, then $ a=b$, there was a claim that $5^n+n$ is never prime (for integer $n>0$).
It does not look obvious to prove, nor have I found a counterexample.
Is this really true?
Update: $5^{7954} + 7954$ has been found to be prime by a computer: http://www.mersenneforum.org/showpost.php?p=233370&postcount=46
Thanks to Douglas (and lavalamp)!
 A: After reading Douglas S. Stones comment I asked mathematica to check if $5^{2\times 3977} + 2\times 3977$ is prime and after about $27$ seconds, found that it is indeed prime. So the claim $5^n +n$ is never prime is false.
Edit: It turns out the function I used in mathematica is not a deterministic algorithm. However we can still say the claim $5^n +n$ is never prime is false is most likely true.
A: A general rule-of-thumb for "is there a prime of the form f(n)?" questions is, unless there exists a set of small divisors D, called a covering set, that divide every number of the form f(n), then there will eventually be a prime.  See, e.g. Sierpinski numbers.
Running WinPFGW (it should be available from the primeform yahoo group http://tech.groups.yahoo.com/group/primeform/), it found that $5^n+n$ is 3-probable prime when n=7954.  Moreover, for every n less than 7954, we have $5^n+n$ is composite.
To actually certify that $5^{7954}+7954$ is a prime, you could use Primo (available from http://www.ellipsa.eu/public/misc/downloads.html).  I've begun running it (so it's passed a few more pseudo-primality tests), but I doubt I will continue until it's completed -- it could take a long time (e.g. a few months).
EDIT: $5^{7954}+7954$ is officially prime.  A proof certificate was given by lavalamp at mersenneforum.org.
A: If $n$ is odd, then $5^n + n$ is always even because LSD of $5^n$ is always $5$ for $n \gt 0$. Hence, for odd $n ( n \gt 0)$, $5 ^n + n$ is composite.
