A number theory problem by Anmol Jain

My approach

We notice that for $n=1,2$ $p= 2,5$ which are obviously the prime numbers . Further we have that $p<10^{19}\implies n^n+1 <10^{19}$ . Taking $\log$ on both sides we get that $\frac{\log(n^n+1)}{\log(10^{19})} > 1$ for $n=16$ and $\frac{\log(n^n+1)}{\log(10^{19})} < 1$ for $n=15$ . Thus, the range of $n$ is $1\leq n <16$ . .

If $n = kb$ where $k$ is an odd number greater than 1. Then $n^n+1 = (n^b)^k+1$ is divisible by $n^b+1$ ( by factorization ) of $a^n+b^n$ . Hence we arrived that $n$ must be an even number.

Let $n =2l$ and primes number are expressed as $2k_1+1 = n^n+1\implies {\color{#3D99F6}l = \frac{\sqrt[2l]{2k_1}}{2}}$ . This must be in form power of 2 if not then $n^n+1$ is composite. Working out with $2,4,8$ . Only $n= 2,4$ are possible values. Hence , the required primes we have $1^1+1,2^2+1, 4^4+1$ . Hence , the sum of primes we have is $\boxed{2+5+257 =264}$ .

Note $8$ doesn't work since $8^8$ has odd divisors in it power tower.

using $Mathematica$

#^#+1&/@Select[Range@19,PrimeQ[#^#+1]&]

returns {2, 5, 257}

For $n=1$ and $n=2$ , we get primes. An odd $n>1$ yields an even $n^n+1>2$ . So $n$ must be even, i.e $n=2^{2^t}(2k+1)$ .

Since $2^{2^t}+1\bigg|2^{2^t}(2k+1)+1$ , the exponent of $n$ cannot have an odd divisor. Thus $n+2^{2^t}$ or $\displaystyle n^n=\big(2^{2^t}\big)^{2^{2^t}}$ . For $t=0,1$ we get $n^n+1=5,257$ , but when $t=2$ , $p=16^{16}+1=2^{64}+1>16\cdot1000^6+1>10^{19}$ . So there are no other primes besides $2,5,257$ .

Factorise $n$ in prime factors and separate it into two parts: the powers of 2 and the rest: $n=2^m (2r+1)$ , where $m$ and $r$ are non-negative integers.

$n^n+1=n^{2^m (2r+1)}+1=(n^{2^m})^{2r+1}+1^{2r+1}$

This result is in the form $A^s+B^s$ which is divisible by $A+B$ for odd $s$ .

The only way that there is a possibility for $n$ to be prime, is if the divisor equals $n$ or $r=0$ .

So $n=2^m$ .

$m=0\implies n=1\implies n^n+1=2$ which is prime 1.

If $m>0$ , then also 'separate' $m$ : $m=2^t (2u+1)$ leading to $n^n+1=(2^{2^t (2u+1)})^{2^{2^t (2u+1)}}+1=2^{2^t (2u+1) 2^{2^t (2u+1)}}+1 = (2^{2^t 2^{2^t (2u+1)}})^{2u+1}+1$

Again, this can only be prime if $u=0$ . Therefor, $n=2^{2^t}$ are the only candidates.

$t=0\implies n=2\implies n^n+1=5$ (prime 2)

$t=1\implies n=4\implies n^n+1=257$ (prime 3)

$t=2\implies n=16\implies n^n+1=16^{16}+1=2^{64}+1>2^4 2^{60}=16 (2^{10})^6=16 * 1024^6>16 * 10^{18}>10^{19}$ so we are done finding candidates.

Final answer $2 + 5 + 257=264$ .

Here is my approach: First observe that $n=1$ is a trivial solution. Suppose, $n>1$ .It is also easy to see that $n$ must be even

$\textbf{Claim 1: n is a power of 2}$

We prove this by contradiction. It is known that $n$ is even, so let $n=2^tc$ for some integer $t$ and an odd number (greater than $1$ ) $c$ . Then,

$n^n+1=(2^tc)^{2^tc}+1=((2^tc)^{2^t})^c+1$

Since $c$ is odd, $(2^tc)^{2^t}+1$ is a divisor of the above number, and hence it's not a prime. This proves our first claim.

$\textbf{Claim 2: n is a Fermat prime}$ This was proved by Fermat himself that if a number of the form $2^k+1$ is a prime, then $k$ is a power of $2$ . (The proof of this is similar to the above one). Fermat number ( $F_n$ ) is a number of the form $2^{2^n}+1$ . Thus $F_0=3,F_1=5,F_2=17,F_3=257,F_4=65537$ and so on. Since $F_6>10^{19}$ we have to consider only $F_0,F_1,F_2,F_3,F_4,F_5$ . $F_5$ is a composite number. (This was proved by Euler).

We have shown that $n$ is a power of $2$ . i.e. $n=2^k$ for some positive integer $k$ . Thus, $n^n+1=(2^k)^{2^k}+1=2^{k2^{2^k}}+1$ Since this must be a Fermat prime, $k2^k=2^t$ for some integer $t$ . Checking all the cases, we see $(k,t)=(1,1),(2,3)$ are the only solutions. Thus the sum of all such numbers is $2+F_1+F_3=2+5+257=\boxed{264}$

When p=2，5 with n=1，2，they're obviously prime.And we can easily notice that n^n+1 is always even when n is odd，so the odd numbers except 1 are all eliminated.

In fact，because 2^10=1024＞10^3，we can know that 16^16=(2^4)^16=(2^10)^6 2^4＞10^18 10=10^19，with which we know n＜16.

Now comes the key part ，to shrink the range the last time，we can use a equality of factorization as below.

When k is an odd number， we have

n^k+1=(n+1)(n^(k－1)－n^(k－2)+n^(k－3)－…－n+1)

So 6^6+1=(6^2)^3+1，8^8+1 =(2^8)^3+1，10^10=(10^2)^5+1，12^12=(12^4)^3+1，14^14=(14^2)^7+1 out at the same time.

And examine 4^4+1 in the end，we get the answer 2+5+257=264

Suppose $n=mk$ for odd integer $m>1$ . Then $n^n+1=n^{mk}+1=(n^k+1)(n^{(m-1)k}-n^{(m-2)k}+\ldots +1)$ , so in order for $n^n+1$ to be prime, $n$ cannot have an odd divisor greater than $1$ . Thus, $n$ must be a power of $2$ , so let $n=2^k$ . Then $n^n+1=2^{k2^k}+1$ . By a similar argument, $k$ cannot have any odd divisors greater than $1$ , and thus must also be a power of $2$ (or $k=0$ ). If $k=2^s$ , then $n^n+1=2^{2^{s+2^s}}+1$ .

Thus, if this quantity is prime, then in particular it is a Fermat prime. Only $5$ Fermat primes are known: $3, 5, 17, 257,$ and $65,537$ . Only $2$ have the specified form, namely $5$ and $257$ . Since $k$ could be $0$ , we also have $n=1 \implies n^n+1=2$ is another solution. Therefore, the answer is $2+5+257=\boxed{264}$ .

Let's write some code! Python's the best language for this problem since it can easily handle big numbers, and 10^19 is just barely large enough to be annoying for most languages (In java you could use BigInteger but in some languages you'll just have to make your own structure D:)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def isPrime(X):
    factor=2;
    # This while loop claims that if any number X has no factors between 2 and sqrt(x), then X is a prime. 
    # Proof by contradiction: Suppose x is composite.  Then it has 2 factors a and b such that a*b=X.
    # a is greater than sqrt(X), but then b must be greater than sqrt(X), Contradiction! 
    while(factor*factor<=X): 
        if(X%factor==0):
            return False;
        factor+=1;
    return True;

#code begins running here
n = 1
prime_sum = 0
while(n**n<=10**19):
    val = n**n+1;
    if(isPrime(val)):
        prime_sum+=val;
    n+=1;
print(prime_sum);