Does anyone know how to find number of partitions of $n$ into sum of three squares with asymtotic time complexity faster than $O(n)$ ?
I found some info on https://oeis.org/A000164, but there are an $O(n)$-algo in FORMULA section (because we need to find all divisors of each $n-k^2$ number for compute $e(n-k^2)$) and $O(n)$-algo in MAPLE section.