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.

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|improve this question
    
Your question before was strangely written. I edited your sum, do you agree it is correct? –  5xum Jun 13 at 11:38
2  
$(1^1+1)$ should just be $1$, shouldn't it? –  Hagen von Eitzen Jun 13 at 11:39
1  
The question edits have lost the original meaning. –  J. J. Jun 13 at 11:40
2  
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 at 11:41
2  
@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 at 12:03

1 Answer 1

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|improve this answer
    
Thank you very much J.J. Nice explanation. –  user156896 Jun 13 at 16:48

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.