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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prime factorization of $n$ is $n = p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$

Let $f(n) = \left((p_1^{a_1}+1)(p_2^{a_2}+1)(p_3^{a_3}+1)\cdots(p_k^{a_k}+1)\right)$ I want to find the value of $$\sum_{n=1}^{N}f(n)$$ For example if $N=6$, then the answer is $(1^{1}+1)+(2^{1}+1)+(3^{1}+1)+(2^{2}+1)+(5^{1}+1)+(2^{1}+1)(3^{1}+1) = 32$

Can I find the value without factorizing all the numbers?

$$ 1=1 \\ 2=2 \\ 3=3 \\ 4=2^2 \\ 5=5 \\ 6=2\cdot3 \\ 7=7 \\ 8=2^3 \\ 9=3^2 \\ 10=2\cdot5 $$

So for $N=10$ answer is $(1+1)+(2+1)+(3+1)+(2^2+1)+(5+1)+(2+1)(3+1)+(7+1)+(2^3+1)+(3^2+1)+(2+1)(5+1) = 77$

So the sum sums over all $n=1$ to $N$. Same term is not added $n$ times.

share|cite|improve this question
Your question before was strangely written. I edited your sum, do you agree it is correct? – 5xum Jun 13 '14 at 11:38
$(1^1+1)$ should just be $1$, shouldn't it? – Hagen von Eitzen Jun 13 '14 at 11:39
The question edits have lost the original meaning. – J. J. Jun 13 '14 at 11:40
Just two cents: $(p_1^{a_1}+1)\cdots (p_k^{a_k}+1)=\sum_{d\mid n, \gcd(d,n/d)=1}d$. – Hagen von Eitzen Jun 13 '14 at 11:41
@Daniel R: Since the author has the off-by-one to the relevant sequence (because he sets the value for $n=1$ as $2$ instead of $1$), the sequence should be 1,4,8,13,19,31,39,48, which is in OEIS. – J. J. Jun 13 '14 at 12:03
up vote 3 down vote accepted

Let $F(N) = \sum_{n=1}^N f(n)$ where $f(n) = \sum_{d|n, \gcd(d,n/d) = 1} d$ as was noted in the comments by Hagen von Eitzen.

Now changing the order of summation and noting that $n$ is of the form $n = n'd$, we have $$F(N) = \sum_{d=1}^N \sum_{\gcd(d,n') = 1, 1 \le n' d \le N} d,$$ which we can also write (by replacing $n'$ by $n$) in the form $$F(N) = \sum_{\gcd(n,d) = 1, 1 \le n d \le N} d$$ where the latter sum now runs over both $n$ and $d$.

Now consider the sum $$\sum_{1 \le n d \le N} d = \sum_{g=1}^\infty \sum_{\gcd(n,d) = g, 1 \le n d \le N} d.$$ By replacing $n$ by $gn'$ and $d$ by $gd'$, we get that this is equal to $$\sum_{g=1}^\infty g \sum_{\gcd(n',d') = 1, 1 \le n' d' \le \left\lfloor \frac{N}{g^2} \right\rfloor} d'= \sum_{g=1}^\infty g F\left(\left\lfloor \frac{N}{g^2} \right\rfloor\right).$$ Moving the terms with $g=2,\dots$ to the other side we get the recurrence relation $$F(N) = \sum_{1 \le nd \le N} d - \sum_{g=2}^{\sqrt{N}} g F\left(\left\lfloor \frac{N}{g^2} \right\rfloor\right).$$

Here the first term is simply $\sum_{d=1}^N d \left\lfloor \frac{N}{d} \right\rfloor$. This can be turned into a pretty fast algorithm by using dynamic programming. See Project Euler for many similar problems utilizing this kind of idea.

share|cite|improve this answer
Thank you very much J.J. Nice explanation. – user156896 Jun 13 '14 at 16:48

Your Answer


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.