A sum regarding prime factorization 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.
 A: 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.
