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.
Thanks in advance
Spoj 14175. Power Factor Sum Sum (hard)
 A: 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).
A: 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.
A: 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)$. 
