Complexity of summing up integral powers
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.