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.

  • 1
    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$.2012-04-17
  • 0
    See https://oeis.org/A1820822012-04-17
  • 0
    If you set by definition $\tau(1)=1$, my formula is correct. I will edit the text.2012-04-17
  • 0
    I want to do the calculation for $10^{12}$, this is not feasible with the code described in the link above.2012-04-17
  • 0
    A loop over all numbers from 1 to n should be avoided.2012-04-17
  • 0
    Working out an exact asymptotic seems possible, but looks tricky.2012-04-17
  • 0
    In fact I am not looking for the "asymptotic" behaviour of g(n) when n is going to infinity. But I am looking for an algorithm to calculate the exact value of g(n) for n very large ($10^{12}$).2012-04-17
  • 1
    @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$.2012-04-17
  • 1
    @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.2012-04-17
  • 0
    We have to do the calculation for 10^12, problem is that I do not have $10^{12} * 4=$ 4T memory.2012-04-17
  • 1
    The problem is from project euler http://projecteuler.net/problem=379. This means that a very efficient solution (+-1min processing time) should be possible.2012-04-17
  • 0
    If it's from project euler then it has no business on m.se - the organizers of project euler have made that clear to us.2012-04-18
  • 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