Find the nearest (small) number x where x can be represented by sum of cubes I recently came across a problem where a number \$x\$ is given and I have to find \$y\$:


\$y &lt; x &gt; 1\$
\$y\$ can be expressed as \$a^3 + b^3\$ (more than one combination) 

Example:

If 4105 is \$x\$ then 4104 is the answer, where 4104 can be expressed as \$16^3 + 2^3\$ and also \$15^3 + 9^3\$.


I am able to write a program in Objective-C, but I am sure that my method is not optimized and is not best.

I am posting this to find out


the best algorithms to solve this problem 
Flaws in my way of solving




#import &lt;Foundation/Foundation.h&gt;

BOOL isPerfectCube(int cubeValue)
{
    float CalculatedCubeRoot = powf(cubeValue, 1.0/3.0);
    CalculatedCubeRoot = floorf(CalculatedCubeRoot * 100) / 100;
    return ((CalculatedCubeRoot - (int) CalculatedCubeRoot) == 0);
}

int cubeRoot(int value)
{
    return powf((float)value, 1.0/3.0);
}

int nearbyNumber(int numberUnderInvestigation)
{
    if(numberUnderInvestigation &lt; 2)
    {
        return -1;
    }
    else
    {
        int firstCube = 1;
        int combination = 0;

        for(int i=2;firstCube&lt;numberUnderInvestigation;i++)
        {
            firstCube = i*i*i;
            int nextCubeNumber = numberUnderInvestigation - firstCube;
            if(isPerfectCube(nextCubeNumber))
            {
                combination++;
            }
        }

        if(combination &gt; 3)
        {
            return numberUnderInvestigation;
        }
        else
        {
            return nearbyNumber(numberUnderInvestigation - 1);
        }
    }
}

int main(int argc, const char * argv[])
{
    @autoreleasepool
    {
        int inputNumber = 4150;

        NSLog(@"%d",nearbyNumber(inputNumber));
    }

}
personally I would calculate that value like e.g. this:

/* 
 * check the updated algorithm, please
 *
- (Float64)neareastSmallerSumOfCubes:(NSInteger)originalNumber {
    if (originalNumber &gt; 1) {
        Float64 _firstAttempt = pow((Float64)originalNumber, 1.0/3.0);
        if (_firstAttempt == floor(_firstAttempt)) originalNumber--;
        NSInteger _a = pow((Float64)originalNumber, 1.0/3.0);
        NSInteger _b = pow((Float64)originalNumber - pow(_a, 3.0), 1.0/3.0);
        return pow(_a, 3.0) + pow(_b, 3.0);
    } else {
        return MAXFLOAT;
    }
}
*/


update


thank for @Szu, he has highlighted an issue with some large numbers;
thank for @Rob, he has highlighted an issue when input is already a pure sum of cubed;


I've updated the algorithm a bit according to the feedbacks, here is the final solution:

- (Float64) neareastSmallerSumOfCubes:(NSInteger)originalNumber {
    if (originalNumber &gt; 1) {
        Float64 _firstAttempt = pow((Float64)originalNumber, 1.0/3.0);
        if (_firstAttempt == floor(_firstAttempt)) originalNumber--;
        NSInteger _a = pow((Float64)originalNumber, 1.0/3.0);
        NSInteger _b = pow((Float64)originalNumber - pow(_a, 3.0), 1.0/3.0);
        if (_b &gt; 1) _b--;
        NSInteger _s = round(pow((Float64)originalNumber / 2.0, 1.0/3.0));
        Float64 _neareast = 0.0;
        do {
            Float64 _possibleNearest = pow(_a, 3.0) + pow(_b, 3.0);
            if (_possibleNearest &gt; originalNumber) _a--;
            else if (_possibleNearest &gt; _neareast &amp;&amp; _possibleNearest != originalNumber) _neareast = _possibleNearest, _b++;
            else _b++;
        } while (_b &lt;= _s);
        return _neareast;
    } else {
        return MAXFLOAT;
    }
}


random test values:


99998 returns 99937 (= 333 + 403) (runtime O(36))
4105 returns 4104 (= 163 + 23) (runtime O(17))
1023 returns 1008 (= 103 + 23) (runtime O(11))
999 returns 945 (= 93 + 63) (runtime O(6))
216 returns 189 (= 53 + 43) (runtime O(4))
3 returns 2 (= 13 + 13) (runtime O(1))




explanation

let us get the two essential conditions from the OP


y &lt; x > 1;
y can be expressed with a3 + b3;
where x, y ∈ ℕ, a, b ∈ ℕ+ and a > 0, b > 0 (that last condition obviously has to be satisfied);




#1

we know 13 + 13 &lt; x &lt; (x+1)1/3 + (x+1)1/3, therefore the actual smaller value also must be in this interval.

if we can build a simple (x+1)1/3 by (x+1)1/3 matrix which holds every possible combination of sums of cubes, that matrix must contain the value we are chasing.


  COMMENT: after certain number of iterations (maximum number of iterations: ((x+1)1/3)2) the requested nearest smaller value can be extracted from that massive interval via e.g. brutal-force algorithms, but we are looking for a much efficient solution than that.


#2

we know the already the addition is commutative operand, so a+b=b+a, so we can drop the part under the diagonal of the matrix, so we can stop the iteration later when we reach the column s = (x/2)1/3. the s is rounded down to the nearest natural, s ∈ ℕ.

#3

the possible values are at certain locations in the half matrix, the possible elements are on an exponential curve, that helps to establish the actual logic of the iterations.

we need to find where this curve enters the matrix, and we walk through the values of the matrix what the curve intersects.

the enter row index is the whole part of a = x1/3 and the column index is the whole part of the b = (x - a3)1/3.

we know:


a > s > b is always true, therefore:
x > a3 + b3; that value also can be the possible nearest smaller, which we called y.
x &lt; (a+1)3 + (b+1)3;
we don't know the relation between x and a3 + (b+1)3; that is what we will find out:


let b = b + 1 and check what we have got:

if the x > a3 + b3 > y, that is a another possible nearest smaller; if not, we ignore it;

if the x = a3 + b3, that is the same as input, we ignore it, according to the original y &lt; x condition;

if the x &lt; a3 + b3, that value is greater than the original number, so we ignore it; because the a > s > b and x ≧ 2s3 statements are always true, therefore x ≧ (a-1)3 + b3 will be true as well, so we can let a = a - 1 and start the next iteration with the new a, b values.

the iteration stops when the b reaches the intersection of the matrix diagonal and the exponential curve, that value was calculated above as s; so if we reach the intersection point, we can be sure that we have already checked all possible nearest smaller values which the matrix holds; and during making the iterations we always kept the largest one as y, thus when we stop the algorithm, the y will hold the only nearest smaller value.