A342257 Period of the sequence {gcd(n, Phi_n(a)): a in Z}, where Phi_n is the n-th cyclotomic polynomial.

1, 2, 3, 2, 5, 3, 7, 2, 3, 5, 11, 1, 13, 7, 1, 2, 17, 3, 19, 5, 7, 11, 23, 1, 5, 13, 3, 1, 29, 1, 31, 2, 1, 17, 1, 1, 37, 19, 13, 1, 41, 7, 43, 1, 1, 23, 47, 1, 7, 5, 1, 13, 53, 3, 11, 1, 19, 29, 59, 1, 61, 31, 1, 2, 1, 1, 67, 17, 1, 1, 71, 1, 73, 37, 1

Offset: 1

Author

Jianing Song, Mar 07 2021

Keywords

• nonn
• easy

Comments

a(n) is the period of the n-th column of A342255. See A342255 for more information.

Also a(n) is the maximum value of the n-th column of A342255. - Jianing Song, Aug 09 2022

Examples

			gcd(6, Phi_6(a)) = gcd(6, a^2-a+1) = 3 for a == 2 (mod 3), 1 otherwise, so {gcd(6, Phi_6(a)): a in Z} has period 3, hence a(6) = 3.
gcd(12, Phi_12(a)) = gcd(12, a^4-a^2+1) = 1 for all n, so {gcd(12, Phi_12(a)): a in Z} has period 1, hence a(12) = 1.
		

Links

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

Crossrefs

Cf. A342255, A253235 (indices of 1), A342256 (indices of terms other than 1), A006530, A013595 (coefficients of cyclotomic polynomials).

Programs

PARI

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

Formula

a(n) is the largest prime factor of n if n is in A342256, 1 otherwise.