Summation of certain divisible numbers

40 Views Asked by At

Let $C(N,m)$ be the number of positive integers $\le N$ which are relatively prime to $m$. It can be found by following equation \begin{align} C(N,m)=\sum_{d|m}\mu (d)\left\lfloor\frac{N}{d}\right\rfloor \end{align} Where $\mu (.)$ is the Möbius function. Let \begin{align} S(N,M)=\sum_{m=1}^{M}C(N,m) \end{align} We can use following method \begin{align} \begin{split} S(N,M)&=\sum_{m=1}^{M}C(N,m)\\ &=\sum_{m=1}^{M}\sum_{d|m}\mu (d)\left\lfloor\frac{N}{d}\right\rfloor\\ &=\sum_{d=1}^{M}\mu (d)\left\lfloor\frac{N}{d}\right\rfloor\sum_{i=1}^{\lfloor M/d \rfloor}1\\ &=\sum_{d=1}^{M}\mu (d) \left\lfloor\frac{N}{d}\right\rfloor\left\lfloor\frac{M}{d}\right\rfloor \end{split} \end{align} Let me define a new modified function $C(N,m,k)$ which counts the number of positive integers that are co-prime to $mk$ and $\leq N$. So \begin{align} C(N,m,k)=\sum_{d|mk}\mu (d)\left\lfloor\frac{N}{d}\right\rfloor \end{align} Now I want to evaluate \begin{align} S(N,M,k)=\sum_{m=1}^{\lfloor M/k \rfloor}C(N,m,k) \end{align} I tried to similar approach as the first function, but was unable to get a concise formula. It will be much appreciated if someone can help to get a simple summation like formula for $S(N,M,k)$.