Problems & Puzzles:
Puzzles
Puzzle 185. Differences
between consecutive n^{n} values
Enoch Haga sent (16/6/2002) the following
puzzle:
Let to be s(n) = n^{n} 
(n1)^{n1}, n=>2. What are the n values such that s(n) is
prime?
As a matter of fact Enoch
knew the first four
solutions: n =
2, 3, 4, & 7
Using Ubasic
I found the next four
solutions:
n = 11, 17, 106 and 120.
Then
I switched to my old but beloved
PRIMEFORM and found one more solution: n=1907 [BTW,
s(1907) has
6256 digits, and
currently it's only a probable prime]
I found no more solutions up to
n=5300.
See EIS
A072164
Questions:
1. Can you prove that s(1907)
is prime?*
2. Can you find
another
probable prime in s(n)?
____________
*
Nowadays it seems that the most
appropriate tool for doing
this is the
Primo code.
Solution:
Alireza Bakhtiari and Daniel Gronau have
been working  by separate  in the same (unexpected)
subject: identifying the general
conditions for the compositeness of s(n).
Here is the Alireza's
contribution:
The sequence S(n) produces an infinite number of
composites.
I have proved that of S(n) is composite for every number
of the form n = mp^2  (m+2)p +2, where p is an arbitrary prime number and
n a natural number. Below you can see the proof. Its very easy as it only
uses Fermat's little theorem. Since mp^2  (m+2)p +2 must be greater than
zero, the following pairs of (p,m) : (2,1) , (2,2) , (3,1) are not allowed
in the relation.
n = mp^2  (m+2)p +2 = (p1)(mp2)
n = 2 mod(p) & n1 = 1 mod(p)
S(n) = 2^((p1)(mp2))  1^(mp^2  (m+2)p +1 ) mod(p)
and as you know for (a,p)=1 , a^(p1) = 1 mod(p) so 2^((p1)(mp2)) = 1
mod(p)
then S(n) = 1  1 = 0 mod(p), that is S(n) is divisible by p.
But it must be mentioned that the relation does not produce all of the
composites, for example when the prime number is 5 the relation says that
all the numbers of the form 20k8 or it's equivalent 20k+12 produce a
composite. However for n=20k+19 there are also composites which cannot be
deduced from this formula. Here are some examples of numbers which can't
be found using the above relation
n=21k+9
n=42k+26
n=42k+38
It is easy to prove that these produce composites and I don't think it is
necessary to write the proofs here. Anyhow the relation can be used in
several ways, here are some applications for it:
1If the last two digits of n are 12,32,52,72,92,19,39,59,79,99 , then
S(n) is a composite.
If you solve the relation for p, you will find:
p=(m+2+ SQRT((m2)^2 +4mn)) / 2m where p is a prime and m a natural number
and n the number you want to examine. For m=1,2,3,.... the following
concepts can be deduced:
2For every integer n, if (1/2)(3+SQRT(1+4n)) is a prime, then S(n) is a
composite.
3For every integer n, if (1/6)(3+SQRT(1+4n)) is a prime, then S(n) is a
composite.
4For every integer n, if (1/10)(5+SQRT(1+12n)) is a prime, then S(n) is a
composite.
5For every integer n, if 1+(1/2)SQRT(2n)) is a prime, then S(n) is a
composite.
and ... By following the pattern, you can find many
relations to check S(n).
And now the Gronau's contribution to the same
issue:
N(n) := n^n  (n1)^(n1)
It's easy to show that:
3N(n) if n = 2 mod 6
5N(n) if n is in {12,19} mod 20
7N(n) if n is in {9,26,30,38} mod 42
If p is prime, we can always find such congruences in module p(p1).
====================================
For some "special" values of n or (n1) we can compute a factor
immediately:
Suppose a = y^k. When we have luck, a+1 or a1 is z*k. Set b := z*k.
Now we can factorize N with
N =  a^a  b^b 
We have:
N =  (y^a)^k  (b^z)^k 
Therefore N is composite with:
abs( b^z  y^a )  N
Example:
Given: a = 64
a = 4^3, y = 4, k = 3
k(64  1)
b = 64  1 = 3 * 21, z = 21
N := a^a  b^b =
3_91737_33160_04751_21672_99139_58780_64482_82678_92024_57429_55734_/
11833_86111_72454_05418_22064_75823_62345_21976_68790_03504_88519_63969
(y^a  b^z) = 4^64  63^21 =
2791_66843_08935_84313_05543_54661_08193_40993
and this is in fact a divisor of N (amazing: it is PRIME!)
***
On December 2005 J.K.Andersen wrote:
http://www.primenumbers.net/prptop/prptop.php says:
7918^79187917^7917 (30870 digits) found by Henri Lifchitz in 2001.
I don't know whether there has been an exhaustive search to this.
