login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A347821 Smallest prime p such that n*p+1 is a perfect power, or 0 if no such p exists. 1

%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)^q-1)/n with q prime.

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

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

%C a(38) = (39^349-1)/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^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.

%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^q-1)/268 with prime q if exists (if such prime exists, then it must be greater than (269^63659-1)/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)^p-1)/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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 13:35 EST 2022. Contains 350511 sequences. (Running on oeis4.)