<p>Perhaps the <a href="http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula" rel="nofollow">Euler-Maclaurin formula</a> can help.</p>

CC BY-SA 2.5
2011-01-15T22:27:26.283Z
2011-01-15T22:27:26.283Z
Yuval Filmus
<p>Check out <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6WK2-4KSVGD3-7&amp;_user=10&amp;_coverDate=06%2F01%2F2007&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1608305166&amp;_rerunOrigin=google&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=7f2ea73a2abc984a62da6994457e4c8d&amp;searchtype=a" rel="nofollow">The generalization of Faulhaber's formula to sums of non-integral powers</a>. 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.</p>

CC BY-SA 2.5
2011-01-16T01:02:12.387Z
2011-01-16T01:02:12.387Z
Gautam Kamath
<p>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?</p>

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

CC BY-SA 2.5
2011-01-15T22:31:41.177Z
related: the sum of square roots problem (i.e a general version of S_n(1/2)): http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
Suresh Venkat
<cc.complexity-theory><time-complexity><nt.number-theory>
Complexity of summing up integral powers
Ganesh
# Complexity of summing up integral powers

(Asked by: username_0 on 2011-01-15)

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

**Tags:** cc.complexity-theory, time-complexity, nt.number-theory
> **Comments:**
> **username_1**: related: the sum of square roots problem (i.e a general version of S_n(1/2)): http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010  

---

## 2 answers

### Answer by username_3 on 2011-01-16. Score: 9 | Accepted answer

Check out [The generalization of Faulhaber's formula to sums of non-integral powers](http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WK2-4KSVGD3-7&_user=10&_coverDate=06%2F01%2F2007&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_searchStrId=1608305166&_rerunOrigin=google&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=7f2ea73a2abc984a62da6994457e4c8d&searchtype=a). 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.


---

### Answer by username_2 on 2011-01-15. Score: 2

Perhaps the [Euler-Maclaurin formula](http://en.wikipedia.org/wiki/Euler%E2%80%93Maclaurin_formula) can help.


---

