3
$\begingroup$

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)

$\endgroup$
6
  • $\begingroup$ See Divisor function. $\endgroup$
    – Lucian
    Mar 3, 2014 at 17:12
  • $\begingroup$ Thanks for replying, but I need to find the sum of all divisor form 1 to n. $\endgroup$
    – Lakshman
    Mar 3, 2014 at 17:17
  • $\begingroup$ Could you provide an example for lets say n=4? $\endgroup$
    – kingW3
    Mar 3, 2014 at 17:28
  • $\begingroup$ 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 $\endgroup$
    – Lakshman
    Mar 3, 2014 at 17:48
  • $\begingroup$ Yop can have a look at my python solution I have used the same algo to solve the easier version ideone.com/B69hC0 $\endgroup$
    – Lakshman
    Mar 3, 2014 at 17:52

3 Answers 3

2
$\begingroup$

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

Result Suma1 Suma2 Suma3 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).

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 3, 2014 at 18:30
  • $\begingroup$ edied .. thanks :) @barto $\endgroup$
    – r9m
    Mar 3, 2014 at 18:38
  • $\begingroup$ Although the SPOJ problem is not asking for this. $\endgroup$
    – chubakueno
    Mar 3, 2014 at 18:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .