%I
%S 3,13,5,2,3,2801,5,3,7,50544702849929377,13,2,2,241,13,3,19,19,17,463,
%T 3,11,89,2,23,757,29,732541,31,917087137,29,7,3
%N Smallest prime p such that n*p+1 is a perfect power, or 0 if no such p exists.
%C For every n, all sufficiently large primes p such that n*p+1 is a perfect power are of the form ((n+1)^q1)/n with q prime.
%C a(34) = (35^3131)/34 is too large to include, it has 482 decimal digits.
%C a(35)  a(37) = {37, 61, 1483}.
%C a(38) = (39^3491)/38 is too large to include, it has 554 decimal digits.
%C a(39)  a(100) = {5, 2, 43, 3500201, 5, 71, 43, 3851, 178481, 11, 47, 3221, 5, 178250690949465223, 2971, 127, 53, 3, 7, 3541, 61, 2, 59, 2, 61, 17, 3, 751410597400064602523400427092397, 21700501, 4831, 7, 19, 73, 5, 7, 5701, 73, 6007, 79, 39449441, 6481, 19, 79, 48037081, 6218272796370530483675222621221, 2, 3, 438668366137, 89, 5, 23, 331, 89, 654022685443, 11, 1001523179, 97, 3, 792806586866086631668831, 9901, 97, 10303}.
%C If n*p+1 = m^k, then n*p = m^k1 = (m1)*(m^(k1) + m^(k2) + ... + m + 1). If p >= n, then m^k = n*p+1 >= n^2+1 > n^2, and we have these three cases: Case 1: m1 > n, then p can't be prime. Case 2: m1 = n, this is A084738. Case 3: m1 < n. If gcd(n, m1) != m1, then because m^(k1) + m^(k2) + ... + m + 1 > n, p can't be prime. This implies m1  n. The three cases means that we only need to check p < n and numbers m such that m1  n.
%C The first n such that a(n) = 0 are {124, 215, 224, 242, ...}, a(268) is unknown, it is the smallest prime of the form (269^q1)/268 with prime q if exists (if such prime exists, then it must be greater than (269^636591)/268), otherwise 0.
%H Eric Chen, <a href="/A347821/a347821.txt">Table of n, a(n) for n = 1..300</a> (with unknown term a(268)).
%F a(n) <= A084738(n+1) if A084738(n+1) > 0.
%o (PARI) a(n)=forprime(p=2,2^32,if(ispower(n*p+1),return(p)))
%o (PARI) b(n)=forprime(p=2,2^16,if(ispseudoprime(q=((n+1)^p1)/n),return(q)))
%o a(n)=forprime(p=2,2^30,if(ispower(n*p+1),return(p)));b(n) \\ this program might be incorrect beyond a(300)
%Y Cf. A001597, A084738.
%K nonn
%O 1,1
%A _Eric Chen_, Sep 25 2021
