Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem?
It is clear from Faulhaber's formula that the problem takes $O(x)$ steps to solve for natural $x$. But I'm not very clear about rational $x$.
Check out The generalization of Faulhaber's formula to sums of non-integral powers. Specifically, on the last page, it gives a formula indicating an error bound of $O(N^{\sigma - m})$, where $\sigma$ is $x$ (in this paper, it's generalized to complex numbers), and $m = \lfloor \sigma + 1 \rfloor$. $N$ in this case refers to the depth of a summation you have to calculate. So this implies that for rational numbers slightly greater than an integer, it would be a lot faster than for rational numbers slightly less than an integer. Of course, this is a result on real numbers, and there may be a better result for rationals.
