I have read about multiplicative functions. I also came across summations involving summation of multiplicative functions as well. Some summations were only over divisors of a number, which can be proved that the summation also turns out to be multiplicative. But, I was interested in finding if a general efficient algorithm exists for finding he summation of the form :

$\sum_{i=1}^{n} F(i)$, where $F(i)$ is any multiplicative function.

I have seen various problems on project euler based on the above summation (such as this one). So, I was curious to know how to approach such problems and what is the best complexity we can expect?

Any help is appreciated.

  • $\begingroup$ No, in the link, $f(i) = \sum_{d|n} gcd(d, \frac{n}{d})$ is multiplicative, but $F(i) = \sum_{i=1}^{n} f(i)$ is not multiplicative which is what i am trying to ask. $\endgroup$ – likecs Jun 13 '17 at 13:38
  • $\begingroup$ So you are asking how to solve the linked problem. I find $f(k) = \sum_{n | k} gcd(n,\frac{k}{n}) =\sum_{n | k}\sum_{d | n, d |\frac{k}{n}} \varphi(d)$. With $n = de$ we have $n|k,d | n,d | \frac{k}{n}$ iff $de | k, d|de, d|\frac{k}{de}$ iff $d^2e |k$ iff $ e | k,d^2|\frac{k}{e}$, ie. $$f(k) = \sum_{e | k}\sum_{d^2 | \frac{k}{e}}\varphi(d)$$ But I don't see how it helps for $\sum_{k \le 10^5} f(k)$ $\endgroup$ – reuns Jun 13 '17 at 14:52
  • $\begingroup$ The function $f(i)$ in the link mentioned above is multiplicative. Thus for given $n$ it can be computed efficiently. My doubt is how to find the summation efficiently, as I have earlier also seen problems regarding summation of multiplicative functions but found no efficiently solution yet. The problem in the link is just one example. $\endgroup$ – likecs Jun 13 '17 at 15:24
  • 2
    $\begingroup$ Well $M(x) = \sum_{n \le x} \mu(n)$ can be computed with $\sum_{n \le x} M(x/n) = 1$. In general if $f(n)$ is multiplicative and $F(x) = \sum_{n \le x}f(n)$ then $\sum_{n \le x} f^{-1}(n) F(x/n) = 1$ where $f^{-1}$ is the DIrichlet inverse $\endgroup$ – reuns Jun 13 '17 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.