A239666 - OEIS

%I #34 Nov 10 2024 23:06:38

%S 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,

%T 54,1,130,3,4,7,72,1,778,204,30,1,108,1,178,15,14,1,924,28,234,63,

%U 1376,1,44,3,16,27,256,1,180,1,706,51,98,0,546,1,4,153,150,1,170

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

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

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

%C 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

%H William Dean, <a href="/A239666/b239666.txt">Table of n, a(n) for n = 1..1000</a>

%e 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.

%o (PARI)

%o 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))))}

%o 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]

%Y Cf. A097792, A116954, A089001.

%K nonn

%O 1,3

%A _Derek Orr_, Mar 29 2014