Counting Abelian Groups of Order at Most n in Time O(n1/3) log n)

Let a(m) be the number of abelian groups of order m (A000688) and A(n) = summ<=n a(m) (A063966). The Dirichlet series of a is productk>=1 zeta(ks) = zeta(s) * zeta(2s) * productk>=3 zeta(ks). The last factor is the series of a function g supported on cube-full integers, which gives the exact identity A(n) = sumt<=n g(t) * D([n/t]) with D(y) = suma>=1 [y/a^2], summed over the O(n^(1/3)) cube-full integers t. Each D(y) is computed in O(y^(1/3)) operations, or read from a table of size O(n^(1/3)). The total cost is O(n^(1/3) log n) operations on O(log n)-bit integers and O(n^(1/3)) memory, against Theta(n^(1/2)) for the powerful-number method and Theta(n log log n) for sieving. All claims are proved. On one core, A(10^12) takes 0.919 s with the powerful-number method and 0.025 s with the new method in Python (36.8 times faster); A(10^18) takes 2.705 s in Python and 0.297 s in C, and A(10^19) = 22948565870634163153 takes 0.655 s in C. The values for n = 10^6, ..., 10^19 are tabulated; the OEIS table stops at n = 10^4.