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

1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15

Offset: 1

Author

Benoit Cloitre, May 05 2002

Keywords

• easy
• nonn

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 1..10000
• Vaclav Kotesovec, Plot of a(n)/log(n)^2 for n = 1..10000

Crossrefs

Cf. A007694, A071521, A062153.

Programs

Mathematica

Table[Length[Select[Range[n], Divisible[#, EulerPhi[#]] &]], {n, 1, 100}] (* Vaclav Kotesovec, Feb 16 2019 *)
Accumulate[Table[If[Divisible[n,EulerPhi[n]],1,0],{n,80}]] (* Harvey P. Dale, Jul 04 2021 *)

PARI

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

Formula

a(n) = Card(k: 1<=k<=n : k==0 (mod phi(k))) asymptotically: a(n) = C*log(n)^2 + o(log(n)^2) with C=0.6....

a(n) = A071521(n) - A062153(n). - Ridouane Oudra, Mar 05 2025