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.