we are given a function F(n) for a number n which is defined as sum of the divisors of n (including 1 and n) ... now given an integer N we have to calculate
G(n) = F(1) + F(2) + F(3) + ..... + F(n)...
is there any formula for it???
i saw "Peter Gustav Lejeune Dirichlet " formula that can be used while surfing the net...can this be used??if yes, please provide an explanation for this formula??if no, then provide another method that can be used
Asked
Active
Viewed 2,943 times
4
rock321987
- 345
1 Answers
2
If $f\left(k,n\right)$ denotes the cardinality of $\left\{ i\in\left\{ 1,\ldots,n\right\} \mid k\text{ divides }i\right\} $ then $G\left(n\right)=\sum_{k=1}^{n}kf\left(k,n\right)$. Here $f\left(k,n\right)=\lfloor\frac{n}{k}\rfloor$ so $G\left(n\right)=\sum_{k=1}^{n}k\times\lfloor\frac{n}{k}\rfloor$.
Take a number, $3$ for instance, and wonder in what $F\left(i\right)$ it will turn up as a term. This is the case if $3$ is a divisor of $i$. Here $f\left(3,n\right)=\lfloor\frac{n}{3}\rfloor$ expresses the number of times that $3$ turns up as a term of $G\left(n\right)$
Edit:
Let say that $X_{k,i}=1$ if $k|i$ and $X_{k,i}=0$ otherwise.
Then for $i\leq n$ we have $F\left(i\right)=\sum_{k=1}^{n}k\times X_{k,i}$. So $G\left(n\right)=\sum_{i=1}^{n}F\left(i\right)=\sum_{i=1}^{n}\sum_{k=1}^{n}k\times X_{k,i}=\sum_{k=1}^{n}\sum_{i=1}^{n}k\times X_{k,i}=\sum_{k=1}^{n}k\sum_{i=1}^{n}X_{k,i}=\sum_{k=1}^{n}k\lfloor\frac{n}{k}\rfloor$
drhab
- 151,093
-
ok i got it...but can u provide any proof for it??can this formula be used for only a single number?? – rock321987 Oct 23 '13 at 09:11
-
Is this (edit answer) enough for you? – drhab Oct 23 '13 at 09:20
-
i think so...thanks a lot...u made it much more easier than i thought – rock321987 Oct 23 '13 at 09:29
-
1Yes, so this is clearly computed in O(n) by above summation, but how do we compute this is O(sqrt(n))? In some programming problems, we require it to compute this sum faster...please share ideas if any :) – Amit Bendkhale Apr 16 '20 at 19:59