Problems & Puzzles: Conjectures Conjecture 16. n^n+1. Craig Johnston wrote at (23/12/99):
Questions: 1.
Can you provide us some published references about the primality or
compositeness of this kind of numbers Solution Patrick
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 F_{2059}. 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_{2059}=(2^(2^11))^(2^(2^11))+1 ! This is the fifth candidate eliminated (with F_{6}, F_{11}, F_{20} and F_{37}) 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 ***





