2
$\begingroup$

Let f(n) be the number of couples (x,y) with x and y positive integers, $x\leq y$ and the least common multiple of x and y equal to n.

Let g be the summatory function of f, i.e.:

$g(n) = \sum_{i=1}^{n}f(i)$.

I am looking for advice on a formula or an algorithm to calculate g(n) in a very efficient way for very large numbers of n. Complexity should be smaller than O(n).

I got already the following formula

$g(n) = \sum_{k=1}^n \lfloor \frac{n}{k} \rfloor 2^{\tau(k)-1}$

with $\tau(k)$ the number of prime factors of k and $\tau(1)=1$ by definition.

but I am looking for a more efficient algorithm.

  • 0
    In fact I am not a participant to Project Euler, but got to know this problem on a Dutch forum http://www.wiskundeforum.nl/viewtopic.php?f=28&t=6282 where I got intrigued by this problem. I am just asking for ideas on how to construct an algorithm / formula, not for implementations or the actual result.2012-04-18

0 Answers 0