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