login
Least k such that (n^k+1)/(n+1) is prime, or 0 if no such prime exists.
21

%I #110 May 10 2023 12:18:11

%S 3,3,3,5,3,3,0,3,5,5,5,3,7,3,3,7,3,17,5,3,3,11,7,3,11,0,3,7,139,109,0,

%T 5,3,11,31,5,5,3,53,17,3,5,7,103,7,5,5,7,1153,3,7,21943,7,3,37,53,3,

%U 17,3,7,11,3,0,19,7,3,757,11,3,5,3,7,13,5,3,37,3,3,5,3,293,19,7,167,7,7,709,13,3,3,37,89,71,43,37

%N Least k such that (n^k+1)/(n+1) is prime, or 0 if no such prime exists.

%C When (n^k+1)/(n+1) is prime, k must be prime. As mentioned by Dubner and Granlund, when n is a perfect power (the power is greater than 2), then (n^k+1)/(n+1) will usually be composite for all k, which is the case for n = 8, 27, 32 and 64. a(n) are only probable primes for n = {53, 124, 150, 182, 205, 222, 296}.

%C a(n) = 0 if n = {8, 27, 32, 64, 125, 243, ...}. - _Eric Chen_, Nov 18 2014

%C More terms: a(124) = 16427, a(150) = 6883, a(182) = 1487, a(205) = 5449, a(222) = 1657, a(296) = 1303. For n up to 300, a(n) is currently unknown only for n = {97, 103, 113, 175, 186, 187, 188, 220, 284}. All other terms up to a(300) are less than 1000. - _Eric Chen_, Nov 18 2014

%C a(97) > 31000. - _Eric Chen_, Nov 18 2014

%C a(311) = 2707, a(313) = 4451. - _Eric Chen_, Nov 20 2014

%C a(n)=3 if and only if n^2-n+1 is a prime; that is, n belongs to A055494. - _Thomas Ordowski_, Sep 19 2015

%C From _Altug Alkan_, Sep 29 2015: (Start)

%C a(n)=5 if and only if Phi(10, n) is prime and Phi(6, n) is composite. n belongs to A246392.

%C a(n)=7 if and only if Phi(14, n) is prime, and Phi(10, n) and Phi(6, n) are both composite. n belongs to A250174.

%C a(n)=11 if and only if Phi(22, n) is prime, and Phi(14, n), Phi(10, n) and Phi(6, n) are all composite. n belongs to A250178.

%C Where Phi(k, n) is the k-th cyclotomic polynomial. (End)

%C a(97) > 800000 (or a(97) = 0). - _Wang Runsen_, May 10 2023

%H Eric Chen, <a href="/A084742/a084742_1.txt">Table of known a(n) up to a(300)</a>

%H H. Dubner and T. Granlund, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/DUBNER/dubner.html">Primes of the Form (b^n+1)/(b+1)</a>, J. Integer Sequences, 3 (2000), #P00.2.7.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Repunit.html">Repunit</a>

%H Robert G. Wilson v, <a href="/A084740/a084740.pdf">Letter to N. J. A. Sloane, circa 1991.</a>

%e a(5) = 5 as (5^5 + 1)/(5 + 1) = 1 - 5 + 5^2 - 5^3 + 5^4 = 521 is a prime.

%e a(7) = 3 as (7^3 + 1)/(7 + 1) = 1 - 7 + 7^2 = 43 is a prime.

%o (PARI) a(n) = {l=List([8, 27, 32, 64, 125, 243, 324, 343]); for(q=1, #l, if(n==l[q], return(0))); k=2; while(k, s=(n^prime(k)+1)/(n+1); if(ispseudoprime(s), return(prime(k))); k++)}

%o n=2; while(n<361, print1(a(n), ", "); n++) \\ _Eric Chen_, Nov 25 2014

%Y Cf. A084741, A065507, A084740, A128164, A126659, A103795.

%K nonn

%O 2,1

%A _Amarnath Murthy_ and Meenakshi Srikanth (menakan_s(AT)yahoo.com), Jun 15 2003

%E More terms from _T. D. Noe_, Jan 22 2004