A161506 Number of divisors of n that are greater than phi(n)/2, where phi is Euler's totient function.

1, 2, 1, 2, 1, 3, 1, 2, 1, 2, 1, 4, 1, 2, 2, 2, 1, 3, 1, 3, 2, 2, 1, 4, 1, 2, 1, 3, 1, 5, 1, 2, 2, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 3, 2, 2, 1, 4, 1, 2, 2, 3, 1, 3, 1, 3, 2, 2, 1, 6, 1, 2, 2, 2, 1, 4, 1, 3, 2, 3, 1, 4, 1, 2, 2, 3, 1, 4, 1, 3, 1, 2, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 2, 1, 4, 1, 2, 2, 3, 1, 4, 1, 3, 2

Offset

1,2

Comments

When computing the cyclotomic polynomial Phi(n,x) as the quotient of sparse polynomials (see Arnold and Monagan), the divisors of n greater than phi(n)/2 are not required because only powers up to phi(n)/2 need to be computed; the remaining terms can be inferred because all cyclotomic polynomials are palindromic for n>1. This sequence grows slowly; k first occurs at A161507(k).

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

Andrew Arnold and Michael Monagan Calculating cyclotomic polynomials of very large height

Mathematica

Table[d=Divisors[n]; e=EulerPhi[n]; Length[Select[d, #>e/2&]], {n, 100}]

Prog

(PARI) A161506(n) = { my(p2 = eulerphi(n)); sumdiv(n, d, ((2*d)>p2)); }; \\ Antti Karttunen, Jan 19 2020

Crossrefs

Cf. A000005, A000010.

Sequence in context: A055874 A195155 A178544 * A066451 A328048 A363522

Adjacent sequences: A161503 A161504 A161505 * A161507 A161508 A161509

Keyword

nonn

Author

T. D. Noe, Jun 17 2009

Status

approved