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,2

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).

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A000010, A070633.

Sequence in context: A005127 A140773 A133911 * A056148 A304442 A057567

Adjacent sequences: A069929 A069930 A069931 * A069933 A069934 A069935

Keyword

easy,nonn,changed

Author

Benoit Cloitre, May 05 2002

Status

approved