Find the nearest (small) number x where x can be represented by sum of cubes
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.