Problems & Puzzles: Conjectures
Conjecture 16. n^n+1.
Craig Johnston wrote at (23/12/99):
Can you provide us some published references about the primality or
compositeness of this kind of numbers
De Geest reports three references related to this kind of numbers:
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:
(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 F2059. 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 "F2059=(2^(2^11))^(2^(2^11))+1 ! This is the fifth candidate eliminated (with F6, F11, F20 and F37) 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