# The amount of numbers that do not divide a number

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 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 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 But still, how can we write this in exact terms of $$x$$?

• In the title, you concentrate on the numbers that do not divide $n$, in the body on the numbers dividing $n$. Which is your intent ? – Peter Jan 21 '20 at 21:11
• @Peter Actually, on the body, I talk regarding the numbers that do not divide $x$, I ask how can you write $\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$ in terms of $x$, and I proposed that this should be $\leq x-\sigma_0(x)$, which is the amount of the numbers that do not divide $x$ up to $x$. – Tots Jan 21 '20 at 21:16

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}$$.