A sum regarding prime factorization

168 Views Asked by At

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.

1

There are 1 best solutions below

1
On BEST ANSWER

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.