A117544 Least k such that Phi(n,k), the n-th cyclotomic polynomial evaluated at k, is prime.

3, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 6, 1, 4, 3, 2, 1, 2, 1, 2, 1, 4, 1, 2, 1, 1, 2, 2, 14, 3, 1, 2, 10, 2, 1, 2, 1, 25, 11, 2, 1, 5, 1, 6, 30, 11, 1, 7, 7, 2, 5, 7, 1, 3, 1, 2, 3, 1, 2, 9, 1, 85, 2, 3, 1, 3, 1, 16, 59, 7, 2, 2, 1, 2, 1, 61, 1, 7, 2, 2, 8, 5, 1, 2, 11, 4, 2, 6, 44, 4, 1, 2, 63

Offset: 1

Author

T. D. Noe, Mar 28 2006

Keywords

• nonn

Comments

Note that a(n)=1 iff n is a power of a prime.

Because every cyclotomic polynomial is irreducible, it is expected that a(n) exists for all n.

Note that if p=Phi(n,k) is prime and n>1, then p==1 (mod k). - Corrected by Robert Israel, Apr 22 2019

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..5000 (terms 1..1000 from T. D. Noe)

Crossrefs

Cf. A085398, A117545 (least k such that Phi(k, n) is prime), A307687.

Programs

Maple

f:= proc(n) local C, x, k;
  C:= unapply(numtheory:-cyclotomic(n, x), x);
  for k from 1 do if isprime(C(k)) then return k fi od
end proc:
map(f, [$1..200]); # Robert Israel, Apr 22 2019

Mathematica

Table[k=1; While[ !PrimeQ[Cyclotomic[n,k]], k++ ]; k, {n,100}]

PARI

a(n) = my(k=1); while (!isprime(polcyclo(n, k)), k++); k; \\ Michel Marcus, Apr 22 2019

Formula

Phi(n, a(n)) = A307687(n). - Robert Israel, Apr 22 2019