Computing sums of divisors in $O(\sqrt n)$ time?

Question

I have a sequence: $1,3,5,8,10,14,16,20,23,27,\dots$

I know that the recursive relation is:

$$p[i] := p[i-1] + \text{number of factors of $i$}, \quad \text{with $p[1]=1$.}$$

How do I solve this recursive relation in $O(n^{0.5})$ time? I have to write a program for it, and $n$ can be as large as $10^9$. So, some appropriate precomputation and prestorage is allowed, provided that they comply (memory and time wise) with the range of $n$.

Answer 1

You are looking for $p_n = \sum_{k=1}^n d(k)$, where $d(k)$ is the number of divisors of $k$.

This paper claims an algorithm running in $O(n^{1/3})$ time and $O(\log n)$ space. See also Deterministic methods to find primes by Tao, Croot Ill and Helfgott sprung from a Polymath project.

Note that formula (4) in the first link gives a simple $O(\sqrt n)$ algorithm:

$$p(n) = 2\sum_{k=1}^{\lfloor\sqrt{n} \rfloor} \left\lfloor\frac{n}{k} \right\rfloor- \lfloor\sqrt n \rfloor^2$$