javaalgorithmmathnumberstriangular

Find max matching 3 Triangular numbers

It's well known that any positive number can be expressed through at most 3 Triangular numbers. ( https://oeis.org/A000217 )

Example:

11 := 10 + 1

12 := 10 + 1 + 1

13 := 10 + 3

14 := 10 + 3 + 1

15 := 15

I am searching the representation of the positive number n through at most 3 possible Triangular summands. There can exist more than one representation of n. I am interested in the one with the greatest summands.

Is there a more effective way than 2 decreasing for and 1 increasing for loops to find the summands?

public void printMaxTriangularNumbers(int n){
  int[] tri = createTriangularNumbers(1000);

  lbl: for(int i = tri.length-1; ; i--){
    int tmp = n - tri[i];
    if(tmp == 0){
      System.out.println(tri[i]);
      break;
    }
    for(int j=i; j>0; j--){
      int tmp2 = tmp - tri[j];
      if(tmp2 ==0){
        System.out.println(tri[i]);
        System.out.println(tri[j]);
        break lbl;
      }
      for(int k=1; k <= j;k++){
        if(tmp2 - tri[k] == 0){
          System.out.println(tri[i]);
          System.out.println(tri[j]);
          System.out.println(tri[k]);
          break lbl;
        }
      }
    }
  }
}

public int[] createTriangularNumbers(int n){
  int[] out = new int[n+1];
  for(int i=1,sum=0; i<=n;i++){
    out[i] = sum += i;
  }
  return out;
}
Solution

  • As far as I can see, there is no direct formula. An algorithm is needed. For instance, a greedy method does not work. Take for example the value 90:

    So I would propose a recursive/backtracking algorithm, where each recursive call deals with one summand only. Each level in the recursion takes first the highest possible triangular number, but if the recursive call fails, it will go for the second largest and dive into recursion again, until there is an acceptable sum.

    We can use the formula mentioned at maths.stackexchange.com:

    Let Tm be the largest triangular number less than or equal to c. You can actually get an explicit formula for m, namely: enter image description here

    Here is a snippet that implements the recursion. When running it, you can introduce a value, and the triangular summands will be produced for it.

    function getTriangularTerms(n, maxTerms) {
    if (maxTerms === 0 && n > 0) return null; // failure: too many terms
    if (n == 0) return []; // Ok! Return empty array to which terms can be prepended
    // Allow several attempts, each time with a
    //   lesser triangular summand:
    for (let k = Math.floor((Math.sqrt(1+8*n) - 1) / 2); k >= 1; k--) {
        let term = k * (k+1)/2;
        // Use recursion
        let result = getTriangularTerms(n - term, maxTerms - 1);
        // If result is not null, we have a match
        if (result) return [term, ...result]; // prepend term
    }
}

// I/O handling
let input = document.querySelector("input");
let output = document.querySelector("span");

(input.oninput = function () { // event handler for any change in the input
    let n = input.value;
    let terms = getTriangularTerms(n, 3); // allow 3 terms max.
    output.textContent = terms.join("+");
})(); // execute also at page load.
    Enter number: <input type="number" value="14"><br>
Terms: <span></span>