A055734 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

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

(list; graph; refs; listen; history; text; internal format)

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