Finding all the integers [1,10,000,000] that can't be represented by a sum of 1,2,3,4 tetrahedrals in Java

Time complexity of the method main method is less than O(n²) and space complexity is O(n).

Initializing:

List tetraNumb = th.computeTetrahedralNumbers(limit);

Collections.sort(tetraNumb);

List tetraNumbPair = th.computeTetrahedralNumberPairs(tetraNumb, limit);

Collections.sort(tetraNumbPair);

List result = execute(tetraNumList, tetraNumPairList, limit);

Computing all the tetrahedral numbers that are smaller than the given threshold:

public List computeTetrahedralNumbers(double limit){

    List tetraNumList = new ArrayList();

    int i = 1;

    int tetra_N = 0;

    while (tetra_N <= limit){
        int tri_N = 0, n;

        tetra_N = 0;

        for (n = 1; n <= i; n++) {
            tri_N += n;

            tetra_N += tri_N;

        }

        if(tetra_N <= limit){
            tetraNumList.add(tetra_N);

        }

        i++;

    }

    return tetraNumList;

}

Creating a list cthat contains the sum of tetrahedral pairs smaller than a threshold:

/**

* Creates the list that contains the sum of tetrahedral pairs smaller than the limit.

* To do so,it checks the pairs between each number and the rest(including itself) until

* the pair's summation is larger than the limit,in which case the iteration

* continues with the next tetrahedral which is paired at most till the position

* the previous check stopped.

* The space complexity is O(n^(2/3)) and the time complexity is O(n^2)

* @param tetraNumList all the tetrahedral numbers smaller than the limit,sorted

* @param limit the tetrahedral threshold

* @return unsorted list of tetrahedral pairs

*/

public List computeTetrahedralNumberPairs(List tetraNumList, double limit) {

    List pairs = new ArrayList<>();

    int max = tetraNumList.size();

    int i, j;

    int sum;

for (i = 0; i < tetraNumList.size(); i++) {//cost: O(n^1/3)

for (j = 0; j < max; j++) {//worst case cost: O(n^1/3)

    sum = tetraNumList.get(i) + tetraNumList.get(j);

    if (sum < limit) {
        if (!pairs.contains(sum)) {

            pairs.add(sum);

        }

    } else {



// there is no need to continue since the array is sorted so

// all the following summations will be larger than the limit

// and also the next loop doesn't have to check beyond this

// index, making the time complexity definitely smaller than

// n*n



        max = j;

        break;

    }

}

}

return pairs;

}

The main method (execute) :

/**

* For each integer i bigger/equal than 1 and smaller/equal than the upper

* limit checks if i is:

*      -tetrahedral (cost O(logn))

*      -summed pair of tetrahedrals (cost O(logn))

*      -summed triplet of tetrahedrals (cost O((n^1/3)logn))

*      -summed quartet of tetrahedrals (cost O((n^2/3)logn))

* If all these condition are false,the number is part of the final result

*/

public List execute(List tetraNumb, List tetraNumbPair, int limit) {

    List nonTetra = new ArrayList<>();

    for (int i = 1; i <= limit; i++) { 
        if(Collections.binarySearch(tetraNumb, i) >= 0){

            continue;

        }

        if(Collections.binarySearch(tetraNumbPair, i) >= 0){

            continue;

        }

        if(searchOnTripletTetrahedrals(tetraNumb, tetraNumbPair, i) >= 0){

            continue;

        }

        if(searchOnQuartetTetrahedrals(tetraNumbPair, i) >= 0){

            continue;

        }

        nonTetra.add(i);

    }

    return nonTetra;

}

Searching on triplet and quartet tetrahedrals:

/**

* For each integer i bigger/equal than 1 and smaller/equal than the upper

* limit checks if i is:

*      -tetrahedral (cost O(logn))

*      -summed pair of tetrahedrals (cost O(logn))

*      -summed triplet of tetrahedrals (cost O((n^1/3)logn))

*      -summed quartet of tetrahedrals (cost O((n^2/3)logn))

* If all these condition are false,the number is part of the final result

*/

public List execute(List tetraNumb, List tetraNumbPair, int limit) {

    List nonTetra = new ArrayList<>();

    for (int i = 1; i <= limit; i++) { 
        if(Collections.binarySearch(tetraNumb, i) >= 0){

            continue;

        }

        if(Collections.binarySearch(tetraNumbPair, i) >= 0){

            continue;

        }

        if(searchOnTripletTetrahedrals(tetraNumb, tetraNumbPair, i) >= 0){

            continue;

        }

        if(searchOnQuartetTetrahedrals(tetraNumbPair, i) >= 0){

            continue;

        }

        nonTetra.add(i);

    }

    return nonTetra;

}





/**

* For each tetrahedral number (tn),smaller than the target, attempts to find,using

* binary search on tetraNumPairList, a number tp=target-tn which is a triplet of

* tetrahedral sum.

* Space complexity is insignificant and time complexity is O((n^1/3)logn) since

* the number of tetrahedral numbers is O(n^1/3) and the cost of binary search is O(logn)

* @param tetraNumList the sorted list of tetrahedrals

* @param tetraNumPairList the sorted list of summed pairs of tetrahedrals

* @param num the target number for which the method is called

* @return positive if found, negative if not

*/

public int searchOnTripletTetrahedrals(List tetraNumList, List tetraNumPairList, int num) {

    int i, found, searchQ;

for (i = 0; i < tetraNumList.size(); i++) {//cost: O(n^1/3)

    searchQ = num - tetraNumList.get(i);

    if (searchQ > 0) {

if ((found = Collections.binarySearch(tetraNumPairList, searchQ)) >= 0) {//cost:O(log(n^2/3))

    return found;

}

} else {



// since the array is sorted and the tetrahedral numbers are positive

// it is impossible to find a solution after this index



    return -1;

}

}

return -1;

}





/**

* For each summed pair of tetrahedrals tp1,smaller than the target,attempts to

* find,using binary search on tetraNumPairList, a quartet  of tetrahedral sum

* tp2=target-tp1.

* Space complexity is insignificant and time complexity is O((n^2/3)logn) since

* the number of summed pairs of tetrahedral numbers is O(n^2/3) and the cost

* of binary search is O(logn)

* @param tetraNumPairList the sorted list of summed pairs of tetrahedrals

* @param num the target number for which the method is called

* @return positive if found, negative if not

*/

public int searchOnQuartetTetrahedrals(List tetraNumPairList, int num) {

    int i, found, searchQ;

for (i = 0; i < tetraNumPairList.size(); i++) {//cost: O(n^2/3)

    searchQ = num - tetraNumPairList.get(i);

    if (searchQ > 0) {

if ((found = Collections.binarySearch(tetraNumPairList, searchQ)) >= 0) {//cost:O(log(n^2/3))

    return found;

}

} else {



// since the array is sorted and the tetrahedral numbers are positive

// it is impossible to find a solution after this index



    return -1;

}

}

return -1;

}