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;

}

Calculating the number of tetrahedrals required to represent an integer in Java using dynamic programming

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

public static Integer[] 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.toArray(new Integer[tetraNumList.size()]);

}

Initializing the arrays:

Integer[] tetrahedrals = computeTetrahedralNumbers(n);

/**

* Each cell C[i,j] equals to the number of tetrahedrals required to represent

* the integer j,taking into consideration the tetrahedrals from the

* first till the i-th.

*/

C = new int[tetrahedrals.length][n+1];

for(int i = 0; i    C[i][0] = 0;

}

/**

* Each cell of the first row is initialized with the value of its

* column since 1 is a tetrahedral and so each integer can be

* represented by a sum of ones.

*/

for (int j = 1; j < n+1; j++) {
    C[0][j]=j;

}

Calculating the number of tetrahedrals required to represent an integer:

/**

* Utilizes the array C from the first column till the n-th.

* Each utilized cell is either assigned the value of the cell above it (when

* the integer it represents is smaller than the maximum tetrahedral that can

* be used-since that tetrahedral obviously cant be taken into consideration

* because the result would be bigger than the target) or the minimum value

* between the cell above it and the number of tetrahedrals required to

* represent the integer n-(maximum allowed tetrahedral) plus one (so the maximum

* allowed tetrahedral is taken into consideration).

*

* When the method is finished,the first n+1 cells of the last row contain

* the minimum number of tetrahedrals required to represent the integers from 0 to n

* and the first n+1 columns contain the process done for that calculation.

*

* If n=number of tetrahedrals smaller than the limit and W=number of integers

* the time and space complexity is pseudo-polynomial-O(nW).The number of integers

* (10000) can be represented with 14 bits and if it gets doubled,15 bits will be

* needed whereas the number of operations will be at least doubled(since an

* increase at the number of integers also increases the available tetrahedrals)

* so when the input is increased by one bit,the complexity is exponential

* if the input is seen as bits and pseudo-polynomial if seen as number.If

* the number of tetrahedrals is doubled,the array will have doubled amount of

* rows(double the space) and the number of operations will be doubled too,

* so complexity will be considered polynomial.

*

*

* @param n

* @return the number of tetrahedrals required to represent n

*/



public int computeTetrahedralSumCount(int n) {

    for (int i = 1; i < C.length; i++) {
        for (int j = 1; j <= n; j++) {
//could be avoided under the

//assumption that the method has been called for all the integers

//before the n-th and the array is already correct till the n-th

//column and set j=n without looping

            if(j                C[i][j]=C[i-1][j];

            }else{

                C[i][j]=Math.min(C[i-1][j], 1+C[i][j-tetrahedrals[i]]);

            }

        }

    }

    return C[C.length-1][n];

}