A239666 a(n) = least number k such that n*k^n+1 is prime, or 0 if no such number exists.

1, 1, 4, 1, 8, 1, 4, 3, 10, 1, 42, 1, 60, 15, 22, 1, 8, 1, 198, 42, 10, 1, 8, 115, 34, 21, 0, 1, 54, 1, 130, 3, 4, 7, 72, 1, 778, 204, 30, 1, 108, 1, 178, 15, 14, 1, 924, 28, 234, 63, 1376, 1, 44, 3, 16, 27, 256, 1, 180, 1, 706, 51, 98, 0, 546, 1, 4, 153, 150, 1, 170

Offset: 1

Author

Derek Orr, Mar 29 2014

Keywords

• nonn

Comments

a(n) = 1 iff n+1 is prime.

If a(n) = 0, then n is in A097792. Note that the converse is not true: a(4) = 1, not 0.

If n is in A097792 and n > 4, then a(n) = 0. For a sketch of this proof, either n = 4b^4 for some positive integer b > 2 or n = (bp)^p for some prime p > 2 and some positive integer b. In the first case, n*k^n+1 can be factored by Sophie Germain's identity into two trinomials where neither can equal 1 since b > 2, so n*k^n+1 must be composite. In the second case, (bpk^{b^p p^(p-1)}+1) is a factor of n*k^n+1 since p is odd. - William Dean, Oct 23 2024

Examples

			3*1^3+1 = 4 is not prime. 3*2^3+1 = 25 is not prime. 3*3^3+1 = 82 is not prime. 3*4^3+1 = 193 is prime. Thus, a(3) = 4.
		

Links

• William Dean, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A097792, A116954, A089001.

Programs

PARI

is_A097792(n)={my(p,t); n%4==0 && ispower(n\4, 4) || ((2 < p = ispower(n, , &t)) && if(isprime(p), t%p==0, foreach(factor(p)[, 1], q, q%2 && n%q==0 && return(1))))}
a(n) = if(n!=4 && is_A097792(n), 0, for(k=1,oo,if(ispseudoprime(n*k^n+1),return(k)))); \\ [corrected by Andrew Howroyd, Oct 25 2024]