# Formula for number of $m^{th}$ power sums less than $x$

Let the class of numbers that is calculated by the Faulhaber's formula as-$$S_m(n)=\sum\limits_{i=1}^{n}i^m$$ For $m=1$ it gives the triangular numbers and so on. I want to define a function $$\mathscr S_m(x)=[\text{number of numbers of form }S_m(n)\text{ less than }x]$$ Like $\mathscr S_1(16)=5$ as there are $5$ triangular numbers less than $16$ ie.$1,3,6,10,15$.
So I am not being able to find out a formula for $\mathscr S_m(x)$ or even its approximation .Please help

• When $T_n=x$ is the $n$th triangular number, $n=\dfrac{\sqrt{8x+1}-1}2$ gives the index, therefore the number of triangular numbers less than $x$ is the greatest integer less than that expression. – Jaycob Coleman Nov 1 '13 at 4:10
• @ShivamPatel: Please see the section in my answer below after "added", which shows the floor of the expression there is always either correct or needs to be decreased by $1$ to be correct. – coffeemath Nov 1 '13 at 12:30
• Yours is not the usual definition of polygonal numbers: en.wikipedia.org/wiki/Polygonal_number – lhf Nov 1 '13 at 12:44
• As noted by @lhf "polygonal" is not right (except for first powers). Maybe a better title would be "formula for number of mth power sums less than x". – coffeemath Nov 1 '13 at 23:45

## 2 Answers

The sum $S_m(n)$ is asymptotic to $n^{m+1}/(m+1).$ Using this approximation we can simplify to solving for the largest integer $n$ such that $$\frac{n^{m+1}}{m+1}<x,$$ which on manipulation leads to considering the floor of the function $$p(m,x)=(x(m+1))^{1/(m+1)}.$$ This actually doesn't do too badly. On your example it gives $p(1,16) \approx 5.65$ with the correct floor of $5$ for the number of triangular numbers less than $16$.

The sum of the first 27 cubes is 142884, and finding $p(3,142884) \approx 27.5$ again gives the right thing on taking the floor. I've tried several other examples, and the ones I tried worked, but have not proved the approximation via the asymptotic formula for $S_m$ is accurate enough to guarantee the floor of $p(x,n)$ above always gives the right answer. (In fact I only tried it at actual sums, and likely there are numbers in between where the floor goes off by $1$ or even more, but at least this approach is an approximation as asked in the post.)

ADDED: We can show that the desired number is always either the floor of $p(m,x)$ or one less than that. First by considering the sum $S_m(n)$ as either a lower or upper sum of an integral of $x^m$ we can get $\int_0^n x^m<S_m(n)<\int_0^{n+1}x^n$ so that $$\frac{n^{m+1}}{m+1}<S_m(n)<\frac{(n+1)^{m+1}}{m+1}.$$ Now if we define $A_m(n)=n^{m+1}/(m+1)$ we get a chain of inequalities $$A_m(n)<S_m(n)<A_m(n+1)<S_m(n+1)<A_m(n+2)\tag{1}$$ For a given $x$ the desired $n$ satisfies $S_m(n) < x \le S_m(n+1)$ and from $(1)$ we have $$A_m(n)<x<A_m(n+2)$$ Solving this leads to $n<p(m,x)<n+2$ with the above definition of $p(m,x).$ Since we want to return $n$ here, we see that the floor of $p(m,x)$ is either already the $n$ we seek, or else must be decreased by $1$ in order to be correct.

Typically numbers between successive power sums which are "near the right end" of such intervals are those which wind up requiring the noted subtraction of $1$ from the floor of $p(m,x).$

[note I've edited to try to remove earlier switch of $m,n$ in the presentation.]

For triangular numbers, you can use the fact that $S_1(n)=\frac {n(n+1)}2$, invert it to get $n^2+n-2S_1(n)=0$ and use the quadratic formula to get $n=\frac 12(-1+\sqrt{1+8S_1(n)})$ so given $x$ you can just evaluate $\frac 12(-1+\sqrt{1+x})$ and round down. For sums of squares and cubes you can do the same, although the formulas get much messier. For higher powers, you can use the fact that the sum of $n^p$ from $1$ to $m$ is about $\frac {m^p}{p+1}$, so given $x$ you have about $\sqrt[p]{(p+1)x}$ sums below $x$. Try the one above and the one below (with the full formula) and you have your answer.