7
$\begingroup$

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$.

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Perhaps the Euler-Maclaurin formula can help.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.