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

Author

Labos Elemer, Jul 11 2000

Keywords

• nonn

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.

Crossrefs

Cf. A001221, A000010, A073918.

Programs

Mathematica

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

PARI

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

Formula

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