A239279 Smallest k such that n^k - k^n is prime, or 0 if no such number exists.

5, 1, 1, 14, 1, 20, 1, 10, 273, 14, 1, 38, 1, 68, 0

Offset: 2

Author

Derek Orr, Mar 14 2014

Keywords

• nonn
• hard
• more

Comments

It is believed that for all n > 4 and not in A097764, a(n) > 0.

a(n+1) = 1 if and only if n is prime.

If a(n) > 0 then a(n) and n are coprime.

If n is in the sequence A097764, then a(n) = 0 or 1 since n^k-k^n is factorable.

33^2570 - 2570^33 is a probable prime, so a(33) is probably 2570. - Jon E. Schoenfield, Mar 20 2014

Unknown a(n) values checked for k <= 10000 using PFGW. a(97) = 6006 found by Donovan Johnson in 2005. The Lifchitz link shows some large candidates for larger n but a smaller k exists in many of those cases. - Jens Kruse Andersen, Aug 13 2014

Unknown a(n) values checked for k <= 15000 using PFGW.

Examples

			2^1-1^2 = 1 is not prime. 2^2-2^2 = 0 is not prime. 2^3-3^2 = -1 is not prime. 2^4-4^2 = 0 is not prime. 2^5-5^2 = 7 is prime. So a(2) = 5.
		

Links

• H. Lifchitz and R. Lifchitz, PRP Top Records. Search for x^y-y^x
• Derek Orr, Table of n, a(n) for n = 2..99 (unknown k-values are marked "unknown")

Crossrefs

Cf. A072180, A109387, A117705, A117706, A128447, A128448, A128449, A128450.

Programs

PARI

a(n)=k=1; if(n>4, forprime(p=1, 100, if(ispower(n)&&ispower(n)%p==0&&n%p==0, return(0)); if(n%p==n, break))); k=1; while(!ispseudoprime(n^k-k^n), k++); return(k)
vector(15, n, a(n+1))

Python

import sympy
from sympy import isprime
from sympy import gcd
def Min(x):
  k = 1
  while k < 5000:
    if gcd(k,x) == 1:
      if isprime(x**k-k**x):
        return k
      else:
        k += 1
    else:
      k += 1
x = 1
while x < 100:
  print(Min(x))
  x += 1