Hand calculation of divisor summatory function

69 Views Asked by At

Maybe this question is stupid, but there was a problem in a math competition (not even in the highest stage) in my county which asked to

Find $ \sum_{n\leq390} d(n)$, where $d(n)$ is the number of positive divisors of $n$.

It is well known that this is equal to $ \sum_{n\leq390}\lfloor\frac{390}{n}\rfloor$.

The problem is that at that competition calculators are not allowed, and problems shouldn't require any non-elementary knowledge, so how could you get the exact value of this sum (it was not a multiple choice test, so you can't just exstimate it) without brutally evaluating every single fraction (which would almost surely mean making some mistake in the way)? Maybe $390$ is a special number in this context?

1

There are 1 best solutions below

0
On BEST ANSWER

It's well known that $$s(x)=\sum_{n\leq x} d(n)=\sum_{n\leq x}\left\lfloor\frac{x}{n}\right\rfloor,$$ indeed. But I thought a more efficient version of that was general knowledge as well: $$s(x)=2\,\sum_{n\leq u}\left\lfloor\frac{x}{n}\right\rfloor-u^2,$$ where $u=\lfloor\sqrt{x}\rfloor$ (that's the famous hyperbola method invented by Dirichlet, ask a search engine or any textbook of elementary number theory). In this case, we'd have $x=390$ and $u=19$, and a sum of just 19 easily computable summands can be done with pencil and paper (I've done it). But it's still tedious, and doesn't make a lot of sense as a contest problem. After that, we know the result is $2393$, great!