Computation of the Totient Summatory Function

Lucas Augustus Brown

An algorithm is devised for computing $\hat{I}¦(n)=\ddot{I}•(1)+\ddot{I}•(2)+\cdots +\ddot{I}•(n)$ in time $\tilde{\hat{I}}˜(n^{2/3})$ and space $\tilde{\hat{I}}˜(n^{1/3})$. The starting point is an existing…