Algorithm challenge: build a pile of 'n' cubes whose total volume adds up to 'm'

I'm working on solving an algorithm problem defined as follows (important parts in bold):


Your task is to construct a building which will be a pile of n cubes. The cube at the bottom will have a volume of n^3, the cube above will have volume of (n-1)^3 and so on until the top which will have a volume of 1^3.


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 will be an integer m and you have to return the integer n such as n^3 + (n-1)^3 + ... + 1^3 = m if such a n exists or -1 if there is no such n.

Okay, so here's how I've been approaching the problem from a theoretical standpoint:

-
The summation 1^3 + 2^3 + ... + n^3 is equal to [n(n+1)/2]^2 = m.

-
Taking the square root of both sides yields |n(n+1)/2| = sqrt(m). We can disregard the absolute value sign because n will always be positive. So n(n+1)/2 = sqrt(m).

-
Therefore, n(n+1) = 2sqrt(m). This problem is essentially asking us to find two consecutive numbers, n and n+1, such that their product is equal to 2sqrt(m).

My code

def find_nb(m):
target = 2*math.sqrt(m)
for n in range(1, int(math.sqrt(target))+1):
if n*(n+1) == target:
return n
return -1


Here, I've defined target to be 2*sqrt(m). I'm looping from n=1 to n=sqrt(target) (inclusive) because there is no point in going beyond the square root of the target when trying to find two numbers, n and n+1, whose product equals the target.

The issue...

This code runs into floating-point precision issues that are fairly consistent across all tests that failed. Here are some screenshots of tests that failed:

Notice that in all of these cases, the value I end up returning is 1 less than the value I stopped looping at. This is quite odd, and I'm not sure what could be causing this behavior.

If you compute the values using a good calculator, you'll find that it is inde

Here is a Python function that is about as simple as possible and as fast as possible, assuming the input is valid.

def find_nb(m):
return int(math.sqrt(2 (math.sqrt(1.0 m))))


If the input can be invalid, such as 10252519345963644753026 in the question, and the function should return None accordingly, the Python program can be the following.

def find_nb(m):
# Use float since math.sqrt is wrong for big integers.
target = int(math.sqrt(2 (math.sqrt( 1.0 m))))
# or target = int(1.4142135623730951 * m ** 0.25)

if (target (target + 1) // 2) (target * (target + 1) // 2) == m:
return target
else:
return None


What is happening? According to Daniel Castle's comment, for $m\ge1$,

$$ n=\frac{-1+\sqrt{1+8\sqrt{m}}}{2}=\frac{-1}2+\sqrt{\frac14+2\sqrt{m}} $$
It can be checked easily that $$ n + 0.4 < \sqrt{2\sqrt m} < n + 0.5$$

That means, $n = \lfloor \sqrt{2\sqrt m} \rfloor$ with plenty of room to prevent an error.

StackExchange Computer Science Q#101002, answer score: 3