A070633 a(n) is the number of k>0 such that phi(k) divides n.

2, 5, 2, 9, 2, 9, 2, 14, 2, 7, 2, 19, 2, 5, 2, 20, 2, 13, 2, 16, 2, 7, 2, 34, 2, 5, 2, 11, 2, 13, 2, 27, 2, 5, 2, 31, 2, 5, 2, 30, 2, 13, 2, 14, 2, 7, 2, 51, 2, 7, 2, 11, 2, 15, 2, 19, 2, 7, 2, 37, 2, 5, 2, 35, 2, 13, 2, 9, 2, 9, 2, 63, 2, 5, 2, 9, 2, 11, 2, 46, 2, 7, 2, 31, 2, 5, 2, 25, 2, 17, 2

Offset: 1

Author

Benoit Cloitre, May 13 2002

Keywords

• easy
• nonn

Comments

Inverse Möbius transform of A014197. - Antti Karttunen, Sep 10 2018

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Crossrefs

Cf. A000010, A014197, A069932, A071181, A319048.

Row lengths of A378638.

Programs

PARI

for(n=1,120,print1(sum(i=1,100*n,if(n%eulerphi(i),0,1)),","));

PARI

\\ In contrast to above program, this is safe in any range 1..n:
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))}; \\ From A014197 by M. F. Hasler
A070633(n) = sumdiv(n, d, A014197(d)); \\ Antti Karttunen, Sep 10 2018

PARI

a(n) = sumdiv(n, d, invphiNum(d)); \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

Formula

From Antti Karttunen, Sep 10 2018: (Start)

a(n) = Sum_{d|n} A014197(d).

a(n) >= A069932(n).

a(A000010(n)) = A071181(n).

(End)