# How to find the sum of $k$th powers of all proper divisors of first $n$ numbers

I am trying this problem but unable to come up with efficient algorithm can someone help with this problem. I have solved the easier version of the problem below is the problem link.

Spoj 14175. Power Factor Sum Sum (hard)

• See Divisor function. Mar 3, 2014 at 17:12
• Thanks for replying, but I need to find the sum of all divisor form 1 to n. Mar 3, 2014 at 17:17
• Could you provide an example for lets say n=4? Mar 3, 2014 at 17:28
• Sure suppose we have to find the sum of all proper divisors up to 4 and power is 1 SOD 4[1,2,4] so sum of k ths power should be let k=1, [1^1+2^1+4^1]=7 3[1,3] SOD [1^1+3^1]=4 2 [1,2] SOD 2[1^1,2^1] =3 1=1 so sum of divisor of Kth power from 1 to 4 is 7+4+3+1=15 that is is the desired result Mar 3, 2014 at 17:48
• Yop can have a look at my python solution I have used the same algo to solve the easier version ideone.com/B69hC0 Mar 3, 2014 at 17:52

Adding up tp r9m answer: The original problem asks you for the sum of all divisors, counting $n$ as a divisor of $n$. An interesting thing to note here is that $$\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor i^k=\sum_{i=1}^x \sum_{j=1}^{\lfloor n/i\rfloor} j^k-x\sum_{j=1}^{\lfloor n/x\rfloor}j^k+\sum_{i=1}^{\lfloor n/x \rfloor} \left\lfloor\frac{n}{i}\right\rfloor i^k\tag1$$.

This can be generalized and proved graphically as follows: For any $f$, and $x,n\in \mathbb N$ such that $0<x\le n$ $$\color{#96A}{\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor f(i)}=\color{#5A5}{\sum_{i=1}^x \sum_{j=1}^{\lfloor n/i\rfloor}f(j)}-\color{#B55}{x\sum_{i=1}^{\lfloor n/x\rfloor}f(i)}+\color{#68A}{\sum_{i=1}^{\lfloor n/x\rfloor} \left\lfloor\frac{n}{i}\right\rfloor f(i)} \tag2$$.

Note: There is actually no problem if $x$ is not in one of the steps of the stair, the proof still works.

But, why would we do such thing? Well, if you set $x=\lfloor \sqrt n\rfloor$, since we can compute $$\sum_{i=1}^{x}i^k$$ in constant(assuming contant time basic arithmetic) time using Faulhaber's polynomials, we have effectively reduced the number of operations necessary to compute $(1)$ to $O(\sqrt n)$. Alas, we need to have previous knowledge of the bound of the bound of $k$, so that we can hard-code the necessary polynomials(but luckily, the bound given in the problem is $1\le k\le10$ which are exactly the polynomials that you can find in the link).

Note that $2$ is a proper factor of half the numbers less $1$, so if the upper limit is $n$ it will contribute $(\lfloor \frac n2 \rfloor -1) 2^k$ to the sum. This avoids factoring any of the numbers.

Simply count the number of times $m$ appears in the list of all the divisors of $\{1,2,...,n\}$, it is $[\frac{n}{m}]$, (where, $[a]$ is the floor of $a$). So the sum of $k$-th power of proper divisors is $\sum\limits_{m=2}^n m^k([\frac{n}{m}]-1)$.

• As the OP is asking for proper divisors only, $\sum_{m={\mathbf 2}}^n m^k\left(\left\lfloor\frac{n}{m}\right\rfloor-1\right)$ would be more appropriate. Mar 3, 2014 at 18:30
• edied .. thanks :) @barto
– r9m
Mar 3, 2014 at 18:38
• Although the SPOJ problem is not asking for this. Mar 3, 2014 at 18:44