A069932 Number of k, 1<=k<=n, such that phi(k) divides n.

1, 2, 2, 4, 2, 5, 2, 7, 2, 5, 2, 11, 2, 5, 2, 11, 2, 9, 2, 10, 2, 5, 2, 19, 2, 5, 2, 9, 2, 11, 2, 16, 2, 5, 2, 20, 2, 5, 2, 18, 2, 9, 2, 10, 2, 5, 2, 32, 2, 7, 2, 9, 2, 13, 2, 15, 2, 5, 2, 26, 2, 5, 2, 22, 2, 11, 2, 9, 2, 7, 2, 38, 2, 5, 2, 9, 2, 9, 2, 30, 2, 5, 2, 23, 2, 5, 2, 17, 2, 17, 2, 10, 2, 5

Offset: 1

Author

Benoit Cloitre, May 05 2002

Keywords

• easy
• nonn

Comments

Unlike A070633, this sequence does not give the number of all integers of the form phi(k) dividing n (for some n and some m > n, phi(m) divides n).

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537
• Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
• Vaclav Kotesovec, Plot of Sum_{k=1..n} a(k)/(n*log(n)) for n = 2..65537 (based on b-file).

Crossrefs

Cf. A000010, A070633, A378642.

Row lengths of A378636.

Programs

Mathematica

a[n_] := Boole[ Divisible[n, EulerPhi[#]]] & /@ Range[n] // Total; Table[a[n], {n, 1, 94}] (* Jean-François Alcover, May 23 2013 *)

PARI

for(n=1,150,print1(sum(i=1,n,if(n%eulerphi(i),0,1)),","))

PARI

a(n)=if(n<1,0,polcoeff(sum(k=1,n,1/(1-x^eulerphi(k)),x*O(x^n)),n))

PARI

A069932(n) = sum(k=1, n, !(n%eulerphi(k))); \\ Antti Karttunen, Sep 10 2018

PARI

a(n) = sumdiv(n, d, #select(x -> x<=n, invphi(d))); \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

Formula

Asymptotically (still conjectured): Sum_{k=1..n} a(k) = C*n*log(n) + o(n*log(n)) with C = 1.5...

G.f.: Sum_{k>=1} 1/(1-x^phi(k)).

a(n) <= A070633(n). - Antti Karttunen, Sep 10 2018

a(n) = Sum_{k=1..n} (1 - ceiling(n/phi(k)) + floor(n/phi(k))). - Wesley Ivan Hurt, Apr 21 2023

a(n) = n - A378642(n). - Paolo Xausa, Dec 06 2024