The amount of numbers that do not divide a number

Question

Say we have a function $\sigma_x(n)$, where $$\sigma_x(n)=\sum_{d\;|\;n} d^x$$ Now, consider that if $\pi(x)$ is the prime-counting function for $x$, then, based on the Sieve of Eratosthenes, we can say that: $$x=\sum_{p_1\leq x}\lfloor {x \over p_1} \rfloor - \sum_{p_1<p_2\leq x}\lfloor {x \over p_1p_2} \rfloor + \sum_{p_1<p_2<p_3\leq x}\lfloor {x \over p_1p_2p_3} \rfloor - \cdots+1$$ Where $p_k$ denotes a prime number. Now, consider that if instead we wrote only some of the terms in the Sieve of Eratosthenes, and those terms could refer to the prime numbers that do not divide $x$, such that this can be written as: $$\sum_{p_1\leq x;\;x\not\equiv 0\pmod {p_1}}\lfloor {x \over p_1} \rfloor - \sum_{p_1<p_2\leq x\;x\not\equiv 0\pmod {p_1p_2}}\lfloor {x \over p_1p_2} \rfloor + \cdots$$ Now, how can we write this in terms of $x$? One might notice that all the values of this Sieve cannot divide $x$, so, one might say that: $$x-\sigma_0(x)-1\geq\sum_{p_1\leq x;\;x\not\equiv 0\pmod {p_1}}\lfloor {x \over p_1} \rfloor - \sum_{p_1<p_2\leq x\;x\not\equiv 0\pmod {p_1p_2}}\lfloor {x \over p_1p_2} \rfloor + \cdots$$ But still, how can we write this in exact terms of $x$?

Answer 1

E. Krätzel (1981), Zahlentheorie, Berlin: VEB Deutscher Verlag der Wissenschaften. p. 130 (German) has, for $x > 0$, $$ \sigma_x(n) = \zeta(x+1)n^x\sum_{m=1}^\infty \frac{c_m(n)}{m^{x+1}} \text{,} $$ where $$ c_m(n) = \sum_{\substack{a = 1 \\ (a,m) = 1}}^m \mathrm{e}^{2 \pi \mathrm{i} \frac{a}{m} n} $$ is a Ramanujan sum and this is mostly encoding the residue information in your two sums of sums over residue classes. Computing the first few of these Ramanujan sums explicitly, \begin{align*} \sigma_x(n) &= \zeta(x+1)n^x \left(1 + \frac{(-1)^n}{2^{x+1}} + \frac{2 \cos (2\pi n/3)}{3^{x+1}} + \right. \\ & \left. \quad{}+ \frac{2 \cos (\pi n/2)}{4^{x+1}} + \cdots \right) \text{,} \end{align*} we can see more clearly that the contributions in the parenthetical expression encode information about $n \pmod{m}$ for each denominator, $m^{x+1}$.

You should be able to adapt this mechanism of encoding residue information to your purposes.