# Counting couples having least common multiple less than a number

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.

-
I think you mean $g(n) = n + \sum_{k=2}^n \lfloor \frac{n}{k} \rfloor 2^{\tau(k)-1}$. Otherwise the $k=1$ term gives you $n/2$ since $\tau(1) = 0$. –  Robert Israel Apr 17 '12 at 20:18
–  Robert Israel Apr 17 '12 at 20:22
@EricNaslund: the asymptotic wouldn't be too hard because the number of ordered pairs whose LCM is $n$ equals the multiplicative function $1*1*\mu^2$ as it turns out. So the asymptotic would be the residue of $\zeta(s)^3 x^s/s\zeta(2s)$ at $s=1$; the main term is $(3/\pi^2) x\log^2 x$. –  Greg Martin Apr 17 '12 at 20:42
@wnvl: I doubt there's any way to evaluate the sum without doing a calculation for each $n$ in the range. But you can set up the calculation in a much faster way than factoring the $n$ separately: one can modify the "sieve of Eratosthenes" to essentially calculate a multiplicative function on all the integers at once, in time that's barely more than a constant number of operations on average. (needs a lot of space though) This would speed up your formula since $2^{\tau(k)}$ is multiplicative. –  Greg Martin Apr 17 '12 at 20:47
The problem is from project euler projecteuler.net/problem=379. This means that a very efficient solution (+-1min processing time) should be possible. –  wnvl Apr 17 '12 at 20:56