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

Question

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)

Answer 1

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).

Answer 2

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.

Answer 3

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)$.