Computation of the Totient Summatory Function

Abstract

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 algorithm based on the Dirichlet hyperbola method and the Mertens function. The algorithm is then used to compute $\hat{I}¦(10^{19})=30396355092701331435065976498046398788$.

29 pages, 0 figures