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];

}

Definite integrals calculation in Java

IntegralApproximations.java

A class containing methods to calculate definite integrals and error margins.

Supports:

• Trapezoidal rule
• Simpson's rule

Example: Calculating the integral of sine in [0,pi/2] using 2 strips.

int n = 2;

double[] x = new double[n + 1];

double[] y = new double[n + 1];

x[0] = 0.28559933214452704;

x[1] = 0.8567979964335803;

x[2] = 1.4279966607226338;

for (int i = 0; i < n + 1; i++) {

    y[i] = (double) Math.round(Math.sin(x[i]) * 1000000) / 1000000;

}

System.out.println("Trapezoidal approximation : " + trapezoidal(x, y));

System.out.println("Simpson approximation     : " + simpson(x, y));

Calculating the error

double e1, e2;

double[] xe = new double[199];

double[] ye = new double[199];

double start = 0;

double dif = x[0] / 198;

for (int i = 0; i < 199; i++) {

    xe[i] = start;

    start += dif;

    ye[i] = Math.sin(xe[i]);

}

e1 = simpson(xe, ye) + simpError(x[0], 198, Math.sin(x[0]));

start = x[2];

dif = ((Math.PI / 2) - x[2]) / 198;

for (int i = 0; i < 199; i++) {

    xe[i] = start;

    start += dif;

    ye[i] = Math.sin(xe[i]);

}

e2 = simpson(xe, ye) + simpError(Math.PI / 2 - x[2], 198, 1);

System.out.println("Maximum theoretical error (trapezoidal) : " + (e1 + e2 + trapError(x[2] - x[0], n, Math.sin(x[2]))));

System.out.println("Actual error (trapezoidal) : " + (1 - trapezoidal(x, y)));

System.out.println("Maximum theoretical error (simpson)     : " + (e1 + e2 + simpError(x[2] - x[0], n, Math.sin(x[2]))));

System.out.println("Actual error (simpson)     : " + (1 - simpson(x, y)));

Output

Trapezoidal approximation : 0.7948383637221537

Simpson approximation     : 0.8176811695057372

Maximum theoretical error (trapezoidal) : 0.21356634499073798

Actual error (trapezoidal) : 0.20516163627784634

Maximum theoretical error (simpson)     : 0.18349059382360064

Actual error (simpson)     : 0.18231883049426278

Simpson's rule in Java

Wikipedia

Calculating the integral:

/**

*

* @param x ascending order,odd number of points

* @param y

* @return

*/

static public double simpson(double[] x, double[] y) {

    double s1 = 0, s2 = 0;

    double dif = x[x.length - 1] - x[0];

    int n = x.length - 1;

    if (n % 2 != 0) {

        throw new IllegalArgumentException();

    }

    for (int i = 1; i <= (n * 0.5) - 1; i++) {

        s1 += y[2 * i];

    }

    s1 *= 2;

    for (int i = 1; i <= n * 0.5; i++) {

        s2 += y[(2 * i) - 1];

    }

    s2 *= 4;

    return ((dif / (3 * n)) * (y[0] + y[n] + s1 + s2));



}

Calculating the maximum theoretical error:

/**

*

* @param dif total length of the strips

* @param n number of strips

* @param max max value of the 4nd derivative

* @return

*/

static public double simpError(double dif, int n, double max) {

    return ((Math.pow(dif, 5) / (180 * n * n * n * n)) * max);

}

This is part of the Definite Integral Approximations project.

Trapezoidal rule in Java

Wikipedia

Calculating the integral:

/**

*

* @param x ascending order

* @param y

* @return

*/

static public double trapezoidal(double[] x, double[] y) {

    double s = 0;

    double dif = x[x.length - 1] - x[0];

    int n = x.length - 1;

    for (int i = 1; i <= n - 1; i++) {

        s += y[i];

    }

    s *= 2;

    return (dif / (2 * n)) * (y[0] + y[n] + s);

}

Calculating the maximum theoretical error:

/**

*

* @param dif total length of the strips

* @param n number of strips

* @param max max value of the 2nd derivative

* @return

*/

static public double trapError(double dif, int n, double max) {

    return ((Math.pow(dif, 3) / (12 * n * n)) * max);

}

This is part of the Definite Integral Approximations project.