Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Divisor summatory function is a function that is a sum over the divisor function.

$$D(x)=\sum_{n\le x} d(n) = 2 \sum_{k=1}^u \lfloor\frac{x}{k}\rfloor - u^2, \;\;\text{with}\; u = \lfloor \sqrt{x}\rfloor$$

http://en.wikipedia.org/wiki/Divisor_summatory_function#Dirichlet.27s_divisor_problem

I am looking for a formula or an efficient algorithm (complexity less than $O(x)$) to calculate the sum of the dividers of the squares.

$$E(x)=\sum_{n\le x} d(n^2)$$

e.g. $$E(3)=d(1)+d(4)+d(9)=1+3+3=7$$

share|improve this question
    
What's "met"? Is that supposed to say "with"? Also, note that if you write out a word like that in $\TeX$, it gets interpreted as juxtaposed variable names and therefore italicized. To get proper formatting for text inside $\TeX$, use \text{...}. Also note that you can get displayed equations by enclosing them in double dollar signs. Displayed equations look nicer and are easier to read; single dollar signs are intended only for inline equations. –  joriki Apr 18 '12 at 23:52
    
Your requirement $O(n)$ makes no sense, since $n$ is a dummy summation variable. Do you mean $O(x)$? –  joriki Apr 18 '12 at 23:53
    
"met" is dutch for "with" I edited the text –  wnvl Apr 19 '12 at 0:00
1  
Two more $\TeX$ hints: You can get "$\TeX$" using \TeX, and you can see the $\TeX$ commands for anything you see on this site by selecting "Show Math As ... TeX Commands" in the context menu (right-click on the formula). –  joriki Apr 19 '12 at 0:09
2  
This is OEIS sequence A061503. The entry doesn't give an efficient algorithm. –  joriki Apr 19 '12 at 0:32
show 5 more comments

1 Answer 1

up vote 12 down vote accepted

The number of divisors of a square is the divisor function convolved with the square of the Möbius function (see $g(n)$ here)

$$e(n)=d(n^2)=(d\star\mu^2)(n)$$

and since

$$\mu^2(n)=\sum_{d^2|n}\mu(d)$$

therefore

$$e(n)=\sum_{a \left| n \right.} d \left( \frac{n}{a} \right) \sum_{b^2 \left| a \right.} \mu \left( b \right)$$

which can be simplified and rewritten as

$$e(n)=\sum_{b^2 \left| n \right.} \mu \left( b \right) d_3 \left( \frac{n}{b^2} \right)$$

where $d_3(n)$ is the number of ways that a given number can be written as a product of three integers. This identity can be verified by noting that $e(n)$ is multiplicative and checking at prime powers which yields $e(p^a)={2a+1}$ and can be compared with $d(p^a)={a+1}$. In particular note that $d_3(p^a)={\binom{a+2}{2}}$ (see $d_k$ here).

Then the summation of the number of divisors of the square numbers can be computed as:

$$E(x)=\sum_{n\le x} d(n^2) =\sum_{n \leq x} \sum_{b^2 \left| n \right.} \mu \left( b \right) d_3 \left( \frac{n}{b^2} \right)$$

which can be reorganized as:

$$E(x)=\sum_{b \leq \sqrt{x}} \mu \left( b \right) \sum_{n \leq x / b^2} d_3 \left( n \right)$$ $$E(x)=\sum_{a \leq \sqrt{x}} \mu \left( a \right) D_3 \left( \frac{x}{a^2} \right)$$

where $D_3$ is the summatory function for $d_3$. Since $D_3(x)$ can be computed in $O(x^{2/3})$ time complexity using the three dimensional analogue of the hyperbola method, $E(x)$ can also therefore be computed in

$$O(\int_{a=1}^\sqrt{x}{(\frac{x}{a^2})}^{2/3}da)=O(x^{2/3})$$

which is better than $O(x)$ as desired.

By taking an $O(x^{1/3})$ algorithm to compute $D(x)$ and using it for $D_3(x)$, this bound can be reduced to $O(x^{5/9})$. You can find such an algorithm and one formula for $D_3(x)$ in my article here which uses the notation $T(n)$ and $T_3(n)$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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