1

This is a programming question I found on Atcoder and I am trying to solve it just using mathematics. I want a simple formula to find number of tuples without using a computer. So I derived a formula to calculate it: $Sn = \sum_{x=1}^n [\frac{n-1}{x}]$

But this formula is so complicated. The best approximation I found is $Sn \approx [(n-1) ln(n)]$ is there any way to simplify it even more ? I need the formula to work for all positive integers up to $10^6$.

Mohammad Alshareef
  • 183
  • Have you tried looking it up on OEIS? – Jair Taylor Nov 30 '20 at 23:34
  • 1
    This is $D(N-1)$ where $D(x)$ is the divisor summatory function. It is known that $$D(x) = 2\sum\limits_{k=1}^u \left\lfloor \frac{x}{k}\right\rfloor - u^2$$ where $u = \lfloor \sqrt{x}\rfloor$. This is essentially the formula in Hagen von Eitzen's answer. It is also known $D(x) = x\log x + x(2\gamma -1)+ \Delta(x)$ and the non-leading term is $\Delta(x) = O(\sqrt{x})$. There is no "closed form" for $D(x)$ and the leading behavior of $\Delta(x)$ for large $x$ is a well known open problem. See above wiki entry for more information. – achille hui Dec 01 '20 at 00:03

1 Answers1

2

First count the cases with $A=B$: There are $$\tag1\lfloor \sqrt{N-1}\rfloor$$ of these.

Next count the cases with $A<B$: For each $A$, there are $\lfloor\frac {N-1}A\rfloor-A$. So all together contribute $$\tag2 \sum_{A=1}^{\lfloor\sqrt{N-1}\rfloor}\left(\left\lfloor\frac{N-1}A\right\rfloor-A\right)$$ Finally, the cases with $A>B$ are the same as $(2)$.

This is now only $O(\sqrt N)$ times as opposed to the $O(N)$ in your formula.

Hagen von Eitzen
  • 374,180