Problems & Puzzles: Conjectures

Conjecture 16.  n^n+1.

Craig Johnston wrote at (23/12/99):

"I believe that there is no prime of the form (n^n)+1 for n > 4. The are two primes n=2,4. Note that all odd n are even. I have checked exhaustively to n=2500

I have been using PRIMEFORM for the problem. It then checks for probable primality and then tests with the P-1 method."

Questions:

1. Can you provide us some published references about the primality or compositeness of this kind of numbers
2. Would you like to extend this search?

Solution

Patrick De Geest reports three references related to this kind of numbers:
*Ribenboim's book, p. 89  (Reference 1)
*Sloane's Integer Sequence A014566
*An article in the Weisstein's Mathematics Encyclopedia.

According to all these references the numbers S(n) = n^n+1 were studied by Sierspinski in 1958, who found that if S(n) is prime then S(n) must be equal to the Fermat number F(m)=2^(2^m)+1, such that m=j+2^j and n=2^(2^j), for j=>0

For j=0, 1, 2, 3, 4, 5 and 6 the corresponding seven m values are: m=1, 3, 6, 11, 20, 37 & 70.

We know that the Fermat numbers F(m) are prime for m = 0 to 4 and nowadays is believed, but not probed, that all the rest of them are composites.

As a matter of fact:

F(6) was shown to be composite by Clausen in 1856 - despite that the credits has been addressed to Landry (see Ribenboim, Ref. 1, p. 85) - who first factorized it completely.
F(11) was known to be composite since 1899 by Cunningham and was completely factorized by Brent and Brent & Morain as recently as 1988.
F(20) was shown to be composite by Buell & Young in 1987 but no one specific factor has been found yet.
F(37) was shown to be composite by Gary Gostin who found his first and only known factor up today.

(See the details of all factorized Fermat numbers at this wonderful site maintained by Keller & Ballinger)

What about F(70)? No one has probed it is composite neither a factor of him has been found. So if S(n)=n^n+1 is prime for n>4, the smallest number remaining to be tested is F(70).

But... n=2^(2^6)... and then S(2^(2^6))=F(70) is a number that has "more than 3*10^20 digits"!!!...

In conclusion the Johnston's conjecture "I believe that there is no prime of the form (n^n)+1 for n > 4" seems to be true, as true as the current believing for the compositeness of the Fermat numbers F(m) for m>4, having the smallest case undecided  in F(70).

***

After all this information I would say that a good idea - related with the Johnston's conjecture - would be to try to get a prime factor of F(70)...(Brave people is required)

***

"On May 9, 2000, Ray Ballinger discovered a new factor of a Fermat number using Yves Gallot's program Proth.exe: 591909 . 22063 + 1 divides F₂₀₅₉. This is the eighth factor found with Gallot's program. Note that Ballinger's factor is relevant to the open question concerning the possible existence of a prime of the form   n^n + 1  for  n > 4", because  2059 = 2^11+11, then - with a little of algebra - you can demonstrate that  "F₂₀₅₉=(2^(2^11))^(2^(2^11))+1 ! This is the fifth candidate eliminated (with F₆, F₁₁, F₂₀ and F₃₇) and it may take a while before removing another one!"

According to our notation j=1 implies m=2059 and the 9/5/2000 Ray Ballinger has demonstrated that F(2059) is composite; then one more candidate to be prime has been eliminated reinforcing still more the compositeness conjecture about the n^n+1 numbers. 

Thanks for this new to Yves Gallot and Pavlos Saridis
See also http://www.prothsearch.net/index.html 

***