%I #55 Nov 17 2023 20:44:33
%S 2,2,2,21,209,72,260,17,3311,4469,94259,55599
%N Least k > 1 such that k^(3^n)*(k^(3^n)+1) + 1 is prime.
%C Numbers of the form k^n*(k^n+1) + 1 with n > 0, k > 1 may be primes only if n has the form 3^j. When n is even k^(4*n) + k^(2*n) + 1 = (k^(2*n)+1)^2 - (k^n)^2 = (k^(2*n)+k^n+1)*(k^(2*n)-k^n+1) so composite. But why if n odd > 3 and not a power of 3 is k^n*(k^n+1) + 1 always composite?
%C Phi[3^(n+1),k] = k^(3^n)*(k^(3^n)+1)+1. When m <> 3^n in k^m*(k^m+1)+1, Phi[3m,k] < k^m*(k^m+1)+1 and is a divisor of it. - _Lei Zhou_, Feb 09 2012
%C The prime number corresponding to the 10th term is a 587458-digit number. - _Lei Zhou_, Jul 04 2014
%C x^(2*k) + x^k + 1 = (x^(3*k) - 1)/(x^k - 1) is the product over n dividing 3k but not dividing k of cyclotomic polynomials Phi(n). If k is a power of 3, n = 3k is the only such divisor and we have a single irreducible cyclotomic polynomial Phi(3k). Otherwise we have the product of more than one polynomial, with integer values > 1 for integer x > 1, and thus always composite numbers. - _Martin Becker_, Jun 22 2021
%H Lei Zhou, <a href="https://t5k.org/primes/page.php?id=118125">Prime Database Entry</a>, July 04, 2014.
%H R. Propper and S. Batalov, <a href="https://t5k.org/primes/page.php?id=136668">Prime Database Entry</a>, Nov 17, 2023.
%F a(n) = A085398(3^(n+1)). - _Jinyuan Wang_, Jan 01 2023
%t Table[i = 1; m = 3^u; While[i++; cp = 1 + i^m + i^(2*m); ! PrimeQ[cp]]; i, {u, 1, 7}] (* _Lei Zhou_, Feb 01 2012 *)
%o (PARI) a(n) = my(k=2); while (!isprime(k^(3^n)*(k^(3^n)+1) + 1), k++); k; \\ _Michel Marcus_, Jan 01 2023
%Y Cf. A056993, A085398, A101406, A153436.
%K nonn,more,hard
%O 0,1
%A _Pierre CAMI_, Dec 26 2008
%E 3311 from _Lei Zhou_ using OpenPFGW, Feb 01 2012
%E 4469 from _Lei Zhou_ using OpenPFGW, Feb 09 2012
%E New term, 94259, from _Lei Zhou_ using OpenPFGW, Jul 04 2014
%E Name and Comment corrected by _Robert Price_, Nov 11 2018
%E a(0) inserted by _Jinyuan Wang_, Jan 01 2023
%E a(11) from _Ryan Propper_ and _Serge Batalov_, Nov 17 2023