A347821 Smallest prime p such that n*p+1 is a perfect power, or 0 if no such p exists.

3, 13, 5, 2, 3, 2801, 5, 3, 7, 50544702849929377, 13, 2, 2, 241, 13, 3, 19, 19, 17, 463, 3, 11, 89, 2, 23, 757, 29, 732541, 31, 917087137, 29, 7, 3

Offset: 1

Author

Eric Chen, Sep 25 2021

Keywords

• nonn

Comments

For every n, all sufficiently large primes p such that n*p+1 is a perfect power are of the form ((n+1)^q-1)/n with q prime.

a(34) = (35^313-1)/34 is too large to include; it has 482 decimal digits.

a(35) - a(37) = {37, 61, 1483}.

a(38) = (39^349-1)/38 is too large to include; it has 554 decimal digits.

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}.

If n*p+1 = m^k, then n*p = m^k-1 = (m-1)*(m^(k-1) + m^(k-2) + ... + m + 1). If p >= n, then m^k = n*p+1 >= n^2+1 > n^2, and we have these three cases: Case 1: m-1 > n, then p can't be prime. Case 2: m-1 = n, this is A084738. Case 3: m-1 < n. If gcd(n, m-1) != m-1, then because m^(k-1) + m^(k-2) + ... + m + 1 > n, p can't be prime. This implies m-1 | n. The three cases means that we only need to check p < n and numbers m such that m-1 | n.

The first numbers n such that a(n) = 0 are {124, 215, 224, 242, ...}. a(268) is unknown; it is the smallest prime of the form (269^q - 1)/268 with prime q if such a prime exists (in which case it must be greater than (269^63659-1)/268), otherwise 0.

Links

• Eric Chen, Table of n, a(n) for n = 1..300 (with unknown term a(268)).

Crossrefs

Cf. A001597, A084738.

Programs

PARI

a(n)=forprime(p=2,2^32,if(ispower(n*p+1),return(p)))

PARI

b(n)=forprime(p=2,2^16,if(ispseudoprime(q=((n+1)^p-1)/n),return(q)))
a(n)=forprime(p=2,2^30,if(ispower(n*p+1),return(p)));b(n) \\ this program might be incorrect beyond a(300)

Formula

a(n) <= A084738(n+1) if A084738(n+1) > 0.