A055734 Number of distinct primes dividing phi(n).

0, 0, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 1, 2, 1, 2, 2, 2, 2, 2, 1, 2, 2, 3, 2, 2, 2, 2, 1, 3, 2, 1, 2, 2, 2, 2, 2, 2, 2, 2, 1, 3, 3, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 2, 2, 2, 2, 3, 2, 3, 1, 2, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 1, 2, 3, 3, 2, 2, 1, 3, 2, 2

Offset

1,7

Comments

Murty and Murty show that the normal order of a(n) is (log log n)^2/2, that is, sum_{1 <= k <= n} a(k) ~ n/2 * (log log n)^2. - Charles R Greathouse IV, Sep 13 2013. See also Erdos-Pomerance (1985) and Erdos-Granville-et-al. (1990). - N. J. A. Sloane, Sep 02 2017

Links

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000

Paul Erdős and C. Pomerance, On the normal number of prime factors of phi(n), Rocky Mountain Math. J. 15 (1985), 343-352.

Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.

Paul Erdős, Andrew Granville, Carl Pomerance and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]

M. Ram Murty and V. Kumar Murty, Prime divisors of Fourier coefficients of modular forms, Duke Math. J. 51:1 (1984), pp. 57-76.

Formula

a(n) = A001221(A000010(n)).

Mathematica

Table[PrimeNu[EulerPhi[n]], {n, 1, 50}] (* G. C. Greubel, May 08 2017 *)

Prog

(PARI) a(n)=omega(eulerphi(n)) \\ Charles R Greathouse IV, Sep 13 2013

Crossrefs

Cf. A001221, A000010, A073918.

Sequence in context: A161274 A160978 A231776 * A295660 A193169 A193453

Adjacent sequences: A055731 A055732 A055733 * A055735 A055736 A055737

Keyword

nonn

Author

Labos Elemer, Jul 11 2000

Status

approved