A342256 Numbers k such that gcd(k, Phi_k(a)) > 1 for some a, where Phi_k is the k-th cyclotomic polynomial.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 27, 29, 31, 32, 34, 37, 38, 39, 41, 42, 43, 46, 47, 49, 50, 52, 53, 54, 55, 57, 58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 78, 79, 81, 82, 83, 86, 89, 93, 94, 97, 98, 100, 101

Offset

1,1

Comments

Indices of columns of A342255 with some elements greater than 1.

For k > 1, let p be the largest prime factor of k, then k is a term if and only if k = p^e*d with d | (p-1). See A342255 for more information.

Also numbers k such that A342257(k) > 1.

Links

Jianing Song, Table of n, a(n) for n = 1..10000

Formula

Equals Union_{p prime} (Union_{d|(p-1)} {d*p, d*p^2, ..., d*p^e, ...}).

Example

6 is a term since gcd(6, Phi_6(2)) = gcd(6, 3) = 3 > 1.
55 is a term since 55 = 11*5, 5 | (11-1). Indeed, gcd(55, Phi_55(3)) = gcd(55, 8138648440293876241) = 11 > 1.
12 is not a term since 12 = 3*4 but 4 does not divide 3-1. Indeed, gcd(12, Phi_12(a)) = gcd(12, a^4-a^2+1) = 1 for all a.

Prog

(PARI) isA342256(k) = if(k>1, my(L=factor(k), d=omega(k), p=L[d, 1]); (p-1)%(k/p^L[d, 2])==0, 0)

Crossrefs

Cf. A342255, A342257. Complement of A253235.

Sequence in context: A135402 A135393 A299703 * A354928 A195044 A033112

Adjacent sequences: A342253 A342254 A342255 * A342257 A342258 A342259

Keyword

nonn,easy

Author

Jianing Song, Mar 07 2021

Status

approved