0
$\begingroup$

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$?

$\endgroup$
2
  • $\begingroup$ 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 ? $\endgroup$ – Peter Jan 21 '20 at 21:11
  • 1
    $\begingroup$ @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$. $\endgroup$ – Tots Jan 21 '20 at 21:16
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.