60
$\begingroup$

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)!

  • 0
    @Clearly when $n$ is a multiple of 5 then $5^{n} +n$ doesnt remain a prime. But we will have to think of other cases.2010-09-06
  • 2
    It is also clear that n is even if the number is prime. Considering remainder on division by 6, 5^n will always be congruent to 1, so n must be congruent to 0 or 4 mod 6.2010-09-06
  • 0
    @Asaf: Jonas means the number is prime => n is even, not the other direction2010-09-06
  • 0
    Can anyone factor 5^76+76?2010-09-06
  • 0
    @Derek Jennings It's divisible by 43.2010-09-06
  • 0
    @yjj That was quick. My computer choked on that one :-)2010-09-06
  • 6
    WinPFGW: 5^(2*3977)+(2*3977) is 3-PRP! (1.9963s+0.0004s)2010-09-06
  • 1
    Note: I have checked that $5^n+n$ is composite for all $n \leq 1000$.2010-09-06
  • 0
    @Pete L. Clark: Emm, great!2010-09-06

3 Answers 3

59

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.

  • 8
    I disagree with that heuristic. A better heuristic is that if there is no covering set, and $\sum 1/\log f(n)$ diverges, then there will be a prime. For example, it seems possible that there may be no primes of the form $2^{2^n}+1$ with $n \geq 5$.2010-09-06
  • 0
    Yes, that is better.2010-09-06
  • 0
    Nice! Please do update us if you do let Primo finish.2010-09-06
  • 2
    In fact, if $\sum 1/log f(n)$ diverges and there's no covering set there should be infinitely many primes of form $f(n)$.2010-09-06
  • 0
    Hmm... this heuristic is still not very good in some situations, like f(n)=n^2. (although, I guess nobody is going to ask if there's any primes of the form n^2)2010-09-07
  • 3
    I posted a link at mersenneforum.org (http://www.mersenneforum.org/showthread.php?p=228745) -- I won't be able to complete the proof myself since I will be travelling. Also, their computers are probably significantly faster than mine.2010-09-07
  • 0
    dumb question: what's a 3-probable prime? (I know what a probable prime is)2010-09-08
  • 3
    Fermat's Little Theorem says if p is a prime then 3^p=3 (mod p). A 3-probable prime is a number q that satisfies 3^q=3 (mod q). q might not be prime (but probably is). [if instead q does not satisfy 3^q=3 (mod q) then it is guaranteed to not be a prime]2010-09-08
  • 0
    oh. hmm. well why only test 3? I guess I'm confused why you cited 3-probable + didn't use Miller-Rabin2010-09-08
  • 2
    Two reasons (a) I don't know in advance which n to test, so it's most likely that I would end up testing many composite numbers for primality (so it's more efficient to run weaker tests first, trial division+Fermat's test) and (b) I already have WinPFGW installed and it tests for 3-PRP.2010-09-08
  • 0
    I am going to accept this, as it seems we are almost done proving that this number is prime (in this thread here: mersenneforum.org/showthread.php?p=228745). I suppose you will update the answer once we are sure, with the certificates and all that.2010-10-11
  • 1
    Awesome, now if only I could upvote twice...2010-10-17
12

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.

  • 0
    As this is not an answer this post should be a comment.2010-09-06
  • 49
    @yjj: Crazy has only 1 reputation point. Remember what that was like? It means you can't comment.2010-09-06
  • 0
    @TonyK Do not you think the rep needed for comment is too high? Examples like this are littered all over the site. I find it a bit strange that you are actually allowed to answer but not to comment. Perhaps, if you agree with me, you could bring it up on Meta.2014-02-15
7

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.

  • 6
    To prove primality of numbers of this size can take months...2010-09-06
  • 1
    Is this primality test perfect or does it find "probable" primes? And does/can Mathematica give a certificate of primality?2010-09-06
  • 0
    ShreevatsaR: *Mathematica* has a package `NumberTheory`PrimeQ`` (I don't know the proper context in the newer versions) which uses either of Atkin-Morain or Pratt to provide a primality certificate. As Douglas said, however, it takes lots of time and memory to generate primality certificates for huge enough numbers. (If you have a gamer friend, you might want to borrow his/her PC for this ;))2010-09-06
  • 0
    On a somewhat off-topic note, we can see that this is (probably) a stereotype of mathematicians rather than gamers since P(fast computer|gamer) >> P(fast computer|mathematician) ;)2010-10-14