Calculating the amount of cubes needed to form a sum Since I've never done any performance programming (Aside from the better choices such as array vs list etc. The real basics.), I should probably read up on it. But I had to start somewhere, so, someone I know - which is a much better programmer than I am - tasked me with making this "assignment":


  You are given the total volume m of the building. Being given m can you find the number n of cubes you will have to build?
  
  The parameter of the function findNb (find_nb, find-nb) will be an integer m and you have to return the integer n such as \$n^3 + (n-1)^3 + \dots + 1^3 = m\$ if such a n exists or -1 if there is no such n.


He gave me this template with it:

using System;

public class Program
{
    public static void Main()
    {
        Console.WriteLine(findNb(4183059834009));
        Console.WriteLine(findNb(24723578342962));
        Console.WriteLine(findNb(135440716410000));
        Console.WriteLine(findNb(40539911473216));
    }

    public static long findNb(long m)
    {

    }
}


In which I inserted:

for(long n = 1; n &lt; (m / 3); n++)
{
    double vol = 0;
    for(long i = 0; i &lt; n; i++)
        vol += Math.Pow((n - i), 3);

    if(vol &gt; m)
        return -1;

    if(vol == m)
        return n;
}
return -1;


This code works, but it takes incredibly long for the larger numbers, as is my main problem.

What can I do to shorten the time it takes for this code takes to complete?
When there's math to be done, always check if some formula exists

$$1^3+2^3 + \dots+n^3 = m = (1+2 + \dots+n)^2$$

in conjunction with some other formula (interesting wikipedia article title)

$$\sum^n_{k=1}k = \frac{n(n+1)}{2}$$

you get some equation for the result

$$\sqrt{m} = 1+2 + \dots+n = \sum^n_{k=1}k = \frac{n(n+1)}{2}$$
and maybe some closed formula

$$
\begin{align}
\sqrt{m} &amp;= \frac{n(n+1)}{2}\\
2\sqrt{m} &amp;= n(n+1)\\
2\sqrt{m} &amp;= n^2+n\\
0&amp;= n^2+n - 2\sqrt{m}
\end{align}
$$

Which has the 2 solutions

$$n_{1,2} = -\frac12 \pm\sqrt{\frac14+2\sqrt{m}}$$

As \$n\$ should be a positive number, only the first solution makes sense.

Return \$ -\frac12 +\sqrt{\frac14+2\sqrt{m}}\$ if it is an integer or \$-1\$ otherwise.

The results are:

$$
\begin{array}{r|r}
m &amp; n\\
\hline
4183059834009 &amp; 2022\\
24723578342962 &amp; -1\\
135440716410000 &amp; 4824\\
40539911473216 &amp; 3568\\
\end{array}
$$

24723578342962 is a very close call, because

$$\sum^{3153}_{k=1}k^3=24723578342961$$

is only 1 off. The floating point result is \$n=3153.00000000003\$. If you don't want to get false positives due to floating point precision (lack thereof), you can do the check by converting the result to some integer type and see if you get the exact number by doing the calculations with that.