[Question]
  [
**Closed**. This question needs [details or clarity](/help/closed-questions). It is not currently accepting answers.
 
 
---
**Want to improve this question?** Add details and clarify the problem by [editing this post](/posts/132834/edit).
Closed 6 years ago.
[Improve this question](/posts/132834/edit) 
### Description
There have been quite a few other challenges concerning these numbers before, and I hope this one is not among them.
The *n* th triangular number equals the sum of all natural numbers up to *n*, simple stuff. There are a [wikipedia page](https://en.wikipedia.org/wiki/Triangular_number) and an [entry at OEIS](https://oeis.org/A000217), for those who wish to inform themselves further.
Now, Gauss found out that every natural number may be expressed as a sum of three triangular numbers (these include `0`), and it is fine to have one number more than once, e.g. `0 + 1 + 1 = 2`.
### Challenge
Your task is to write a program or function, given a natural number (including `0`), prints three triangular numbers that sum up to the argument. You may print the numbers separeted by spaces, as an array, or by another method you like. However, it is **forbidden** to use any builtin functions to directly get an array, a range or any other form of collection containing a list of triangular numbers (for instance a single atom that yields the range).
### Test cases
```
9 -> 6 + 3 + 0 or 3 + 3 + 3
12 -> 6 + 6 + 0 or 6 + 3 + 3 or 10 + 1 + 1
13 -> 6 + 6 + 1
1 -> 1 + 0 + 0
0 -> 0 + 0 + 0
```
Note: If there is more than one possible combination, you may print any or all, but you must print any combination only once, eliminating all combinations that are a result of rearranging other combinations.
I'd really appreciate a try-it link and an explanation, I really love to see how you solve the problem ;)
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so standard loopholes apply. May the shortest answer in bytes win!
  
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 10 bytes
Code:
```
ÝηO3ãʒOQ}¬
```
Explanation:
```
Ý             # Compute the range [0 .. input]
 η            # Get the prefixes
  O           # Sum each prefix to get the triangle numbers
   3ã         # Cartesian repeat 3 times
     ʒ  }     # Keep elements that
      OQ      #   have the same sum as the input
         ¬    # Retrieve the first element
```
Uses the **05AB1E** encoding. [Try it online!](https://tio.run/##MzBNTDJM/f//8Nxz2/2NDy8@Nck/sPbQmv//LQE "05AB1E – Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), 99 bytes
```
from random import*
n=input()
while 1:b=sample([a*-~a/2for a in range(n+1)]*3,3);n-sum(b)or exit(b)
```
[Try it online!](https://tio.run/##FYtLDkAwFAD3TtFlW0R8VsRJxOKJ4iX62lQFG1evWs0sZuzjN0NVCIszmjmgOQK1Nc7LhHoke3oukmvDXbGynfoDtN0VH0DmLxTVYhwDhvSvq@KUlmKUdVaLjvLj1HwSMVA3@mghNB8 "Python 2 – Try It Online")
I'm pretty amazed this is shorter than `itertools` or a triple list comprehension! It (eventually) spits out a random answer every time you run it.
Two 102s:
```
n=input();r=[a*-~a/2for a in range(n+1)];print[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]
def f(n):r=[a*-~a/2for a in range(n+1)];return[(a,b,c)for a in r for b in r for c in r if a+b+c==n][0]
```
itertools looks to be 106:
```
from itertools import*;lambda n:[x for x in product([a*-~a/2for a in range(n+1)],repeat=3)if sum(x)==n][0]
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 12 bytes
```
0r+\œċ3S=¥Ðf
```
[Try it online!](https://tio.run/##y0rNyan8/9@gSDvm6OQj3cbBtoeWHp6Q9v9w@6OmNUcnPdw5A0hH/v9vqWNopGNorGOoYwAA "Jelly – Try It Online")
## How it works
```
0r+\œċ3S=¥Ðf   input: n
0r             [0 1 ... n]
  +\           cumsum
    œċ3        combinations of 3 elements, with repetition
          Ðf   filter on
       S          sum
        =         equals n
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 13 bytes
```
⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/r//9H8ZUD0cOsEbSDOetTU/Kir/eHOVXra9o86lv//b/k/CgA "Brachylog – Try It Online")
## How it works
```
⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧  input: n
⟦              [0 1 ... n]
 ⟦ᵐ            [[0] [0 1] [0 1 2] ... [0 1 ... n]]
   +ᵐ          [0 1 3 ... n(n+1)/2]
     j₃        [0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2 0 1 3 ... n(n+1)/2]
       ⊇       is a superset of
        Ṫ      a list of three elements 
         .     which is the output
          +?   which sums up to be the input
```
[Answer]
## Haskell, ~~66~~ 59 bytes
Thanks for allowing to output all solutions, that was fascinating distraction!
I was so happy to not need to extract one solution and be able to just give them all that I didn't notice the cost that comes from avoiding permuted solutions. @Lynn's remark explained that to me and let me save 7 bytes.
```
f n|l<-scanl(+)0[1..n]=[(a,b,c)|c<-l,b<-l,a<-l,a+b+c==n]!!0
```
This binds more than enough triangular numbers to `l` and checks all combinations.
[Answer]
# [Retina](https://github.com/m-ender/retina), ~~63~~ 59 bytes
```
.+
$*
^((^1|1\2)*)((1(?(4)\4))*)((1(?(6)\6))*)$
$.1 $.3 $.5
```
[Try it online!](https://tio.run/##K0otycxL/K@q4Z7wX0@bS0WLK05DI86wxjDGSFNLU0PDUMNew0QzxkQTzjPTjDED8VS4VPQMFVT0jIHY9P9/Sy5DIy5DYy5DLgMA "Retina – Try It Online") Link includes test cases. `(1(?(1)\1))*` is a generalised triangular number matcher, but for the first triangular number we can save a few bytes by using `^` for the initial match.
[Answer]
# [MATL](https://github.com/lmendo/MATL), 18 bytes
```
Q:qYs3Z^t!sG=fX<Y)
```
This outputs the first result in lexicographical order.
Try it at [**MATL Online!**](https://matl.io/?code=Q%3AqYsOh3Z%5Et%21sG%3DfX%3CY%29&inputs=13&version=20.2.0)
### Explanation
```
Q     % Implicitly input n. Add 1
:     % Range (inclusive, 1-based): gives [1 2 ... n+1]
q     % Subtract 1 (element-wise): gives [0 1 ... n]
Ys    % Cumulative sum
3Z^   % Cartesian power with exponent 3. Gives a matrix where each row is a
      % Cartesian tuple
t     % Duplicate
!s    % Sum of each row
G=    % Does each entry equal the input?
f     % Find indices that satisfy that condition
X<    % Minimum
Y)    % Use as row index into the Cartesian power matrix. Implicitly display
```
[Answer]
# [PHP](https://php.net/), 351 bytes
```
$r=[];function f($a=[],$c=0){global$argn,$t,$r;if($c<3){$n=$argn-array_sum($a);$z=array_filter($t,$f=function($v)use($n,$c){return$v>=$n/(3-$c)&&$v<=$n;});foreach($z as$v){$u=array_merge($a,[$v]);if(($w=$n-$v)<1){if(!$w){$u=array_pad($u,3,0);sort($u);if(!in_array($u,$r)){$r[]=$u;}}}else f($u,$c+1);}}}for($t=[0];$argn>$t[]=$e+=++$i;);f();print_r($r);
```
[Try it online!](https://tio.run/##TZDdaoRADIXv@xS7S1gmqFQRejPO9kFEZGrHH3BHiTMuXfHZbbQt9DIn5zucZGzHLXsf2/EFNDVWXZK3i9yAVF7I2tvKdYM91QI0CyFUKsal6YcP3R/2EFwIJDs2VFmKC1h16JEm0l/l5O9MooSn@hHqrneGxE7V6i9ewIx@MgI4rsKFjPNkYb4psK8ijVi7XmHOeJQrynogo6tWwPOkJyYX8L/hd0MNp@gwh7nAvZSAB1MRu7IEFxbO8PgHjPpTgA/TMEY5DeR4OLBzZ8vDsW@BkBHKCwVerutq@snsD@FNFSS4S1yJT1J5XMjj@hu43W4CFQTQSe4sUI7UWVeykVBu2zc "PHP – Try It Online")
[Answer]
# [Python 3](https://docs.python.org/3/), 119 bytes
```
lambda n:[l for l in combinations_with_replacement([(t**2+t)/2for t in range(n)],3)if sum(l)==n]
from itertools import*
```
[Try it online!](https://tio.run/##FcxBCoMwEEDRfU8xyyQVSnVXyEmsSLRJHUhmwjil9PSpbv7u/frTjWloyT9bDmV5BaDHmCGxQAYkWLksSEGRaZ@/qNssseawxhJJzWjUuf6q9tafQk8hgd7RkJ26wWKC/VNMtt7TdEnCBVCjKHPeAUtlUdeq4LG69x2ko9a2Pw "Python 3 – Try It Online")
**Thanks to @WheatWizard for saving 12 bytes!**
[Answer]
# C/C++ - 197 bytes
```
#include<stdio.h>
#define f(i,l,u) for(int i=l;i<=u;i++)
int t(int n){return n>1?n+t(n-1):n;}
int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}
```
Blow by blow:
```
#include<stdio.h>
```
Needed for printf. Could be elided for certain versions of C
```
#define f(i,l,u) for(int i=l;i<=u;i++)
```
Space saving for loop.
```
int t(int n){return n>1?n+t(n-1):n;}
```
Recursive triangle evaluator.
```
int c(int n){f(a,0,n)f(b,a,n)f(c,b,n)if(t(a)+t(b)+t(c)==n)return printf("%d %d %d\n",t(a),t(b),t(c));}
```
This guy does the heavy lifting. Three nested for loops iterate a, b, c from 0 to n, note that b and c each iterate from the previous value up to n. It's not strictly necessary to trim iteration like that since the `return` coming in a minute solves the "duplicate" problem.
At the inner level, if the sum of the three triangle numbers `==` the desired value, print the triangles and return.
You can legally remove the `return` keyword and convert the return type of c to void to save a few more bytes and print all possible solutions. It is for this reason that iterations are limited, if all loops ran from `0` to `n` it would cause duplicates.
[Answer]
# Mathematica, 63 bytes
```
(t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&]‌​)&
```
[Answer]
# [CJam](https://sourceforge.net/p/cjam), 26 bytes
```
{_),[{\_@+}*]3m*_{:+}%@#=}
```
Port of my MATL answer. This is an anonymous block that expects the input on the stack and replaces it by the output array.
[**Try it online!**](https://tio.run/##S85KzP1vaPy/Ol5TJ7o6Jt5Bu1Yr1jhXK77aSrtW1UHZtvZ/XcF/AA "CJam – Try It Online")
[Answer]
# [R](https://www.r-project.org/), 66 bytes
```
n=scan();b=expand.grid(rep(list(cumsum(0:n)),3));b[rowSums(b)==n,]
```
Brute force algorithm; reads `n` from stdin and returns a dataframe where each row is a combination of 3 triangular numbers that add up to `n`. If necessary, I can return only the first row for +4 bytes.
[Try it online!](https://tio.run/##K/r/P8@2ODkxT0PTOsk2taIgMS9FL70oM0WjKLVAIyezuEQjuTS3uDRXw8AqT1NTx1gTqC66KL88GCiqkaRpa5unE/vf@D8A "R – Try It Online")
[Answer]
# Java 8, 164 bytes
```
n->{int t[]=new int[n+1],i=0,j=0;for(;i<=n;)if(Math.sqrt(8*i+++1)%1==0)t[j++]=i-1;for(int a:t)for(int b:t)for(int c:t)if(a+b+c==n)return new int[]{c,b,a};return t;}
```
**Explanation:**
[Try it here.](https://tio.run/##pZDBbsMgDIbvfQouk2AkKNku6xiT9gDtpccqB0LJRpY6GXE6VVGePSNpKu3cSiB@jD/j36U@6bhuLJSH79FUum3JRjvoV4Q4QOsLbSzZTtc5sM@IoeEkwGSIDWGH1aJGZ8iWAFFkhPi9n1JCsgL7O2PA0yxyKolKlcii9lS6NwWSuYJuNH6J9scjfXl0nPOUPaRKJQz3JeeZcnE6A1NF/YrsqvN/2gQdKmmec6MUMG@x80Cun2e9ifJID3KJoxxGeem86fIqdL4YONXuQI7BPt2hd/AZ3Gp28b47t2iPou5QNOEJK6BlGJ3o0FXiw3t9bgXWF4yCMHTN2DyiG9D06Q72@Q72djRZ0GE1jH8)
```
n->{                     // Method with int parameter and int-array return-type
  int t[]=new int[n+1],  //  Create an int-array to store triangular numbers
      i=0,j=0;           //  Two index-integers
  for(;i<=n;)            //  Loop (1) from 0 to `n` (inclusive)
    if(Math.sqrt(8*i+++1)%1==0) 
                         //   If `i` is a triangular number
      t[j++]=i-1;        //    Add it to array `t`
                         //  End of for-loop (1) (implicit / single-line body)
  for(int a:t)           //  Loop (2) over the triangular numbers
    for(int b:t)         //   Inner loop (3) over the triangular numbers
      for(int c:t)       //    Inner loop (4) over the triangular numbers
        if(a+b+c==n)     //     If the three triangular numbers sum equal the input
          return new int[]{c,b,a};
                         //      Return these three triangular numbers as int-array
                         //    End of loop (4) (implicit / single-line body)
                         //   End of loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  return t;              //  Return `t` if no sum is found (Java methods always need a
                         //  return-type, and `t` is shorter than `null`;
                         //  since we can assume the test cases will always have an answer,
                         //  this part can be interpret as dead code)
}                        // End of method
```
[Answer]
# JavaScript, 108 bytes
```
r=[],i=a=b=0
while(a<=x)r.push(a=i++*i/2)
for(a=0;a<3;){
b=r[i]
if(b<=x){
x-=b
a++
console.log(b)}
else i--}
```
### Explanation
`x` represents the input
`while(a<=x)r.push(a=i++*i/2)` Creates an array of all triangular numbers up to x
The `for` loop prints the highest triangular number less than `x`, then subtracts that number from `x`, for three iterations. (basically a greedy algorithm)
[Answer]
# Pyth, 19 bytes
I am *so* out of practise with Pyth, it's untrue :/
```
hfqQsT.C*3+0msSdSQ3
```
Try it out [here](https://pyth.herokuapp.com/?code=hfqQsT.C%2a3%2B0msSdSQ3&input=13&debug=0).
```
hfqQsT.C*3+0msSdSQ3  Implicit: Q=input()
                SQ   Range 1-n
            m        Map the above over d:
              Sd       Range 1-d
             s         Sum the above
                     Yields [1,3,6,10,...]
          +0         Prepend 0 to the above
        *3           Triplicate the above
      .C          3  All combinations of 3 of the above
 f                   Filter the above over T:
    sT                 Where sum of T
  qQ                   Is equal to input
h                    Take the first element of that list
```
[Answer]
# [J](http://jsoftware.com/), 36 bytes
```
((2!1+$@]#:0({I.@,)=)]+/+/~)2!1+i.,]
```
[Try it online!](https://tio.run/##y/r/P03B1kpBQ8NI0VBbxSFW2cpAo9pTz0FH01YzVltfW79OEySTqacTy8WVmpyRr6BhnaapZKAQq2CpYGikYGisYKhg8P8/AA "J – Try It Online")
[Answer]
# Ruby ~~61~~ ~~57~~ 55 bytes
Inspired by Lynn's Python [answer](https://codegolf.stackexchange.com/a/132852/65905). It generates random triplets until the desired sum is achieved:
```
->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}
```
It requires Ruby 2.4. In Ruby 2.3 and older, it's a syntax error, and `Range#sum` isn't defined. This longer version (64 bytes) is needed for Ruby 2.3:
```
->n{x=Array.new(3){(a=rand(n+1))*-~a/2}until x&.inject(:+)==n;x}
```
Here's a small test:
```
f=->n{x=Array.new 3{(0..rand(n+1)).sum}until x&.sum==n;x}
# => #<Proc:0x000000018aa5d8@(pry):6 (lambda)>
f[0]
# => [0, 0, 0]
f[13]
# => [0, 3, 10]
f[5]
# => [3, 1, 1]
f[27]
# => [21, 3, 3]
f[27]
# => [0, 21, 6]
f[300]
# => [3, 21, 276]
```
[Try it online with Ruby 2.3!](https://tio.run/##KypNqvyfZvtf1y6vusLWsagosVIvL7Vcw1izWiPRtigxL0UjT9tQU1NLty5R36i2NK8kM0ehQk0vMy8rNblEw0pb09Y2z7qi9n@BQlq0Qaw1iDKEUkYQ2sg89j8A "Ruby – Try It Online")
[Answer]
# Javascript (ES6), 108 bytes - fixed
Takes an integer as an input, outputs an array `[a, b, c]` containing a sorted list of triangle numbers `a + b + c = x`, where `a` is the largest triangle number less than or equal to the input, and `b` is the largest triangle number less than or equal to the input minus `a`.
```
x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k}
```
## Explanation
```
x=>{
    t=[0],                               // initialize an array of triangle numbers
    t.f=t.forEach,                       // copy forEach method into t.f,
                                         // saves a net of 4 bytes
    i=j=k=0;
    for(;j<x;t[i]=j+=i++);               // populate t with all triangle numbers that
                                         // we could possibly need
    t.f(                                 // loop over all t
        a=>t.f(                          // loop over all t
            b=>t.f(                      // loop over all t
                c=>a+b+c==x?k=[a,b,c]:0  // if a+b+c = x, set k = [a,b,c], else noop
                                         // using a ternary here saves 1 byte vs
                                         // if statement
                                         // iterating over t like this will find all
                                         // permutations of [a,b,c] that match, but
                                         // we will only return the last one found,
                                         // which happens to be sorted in descending order
            )
        )
    );
    return k
}
```
```
const F = x=>{t=[0],t.f=t.forEach,i=j=k=0;for(;j<x;t[i]=j+=i++);t.f(a=>t.f(b=>t.f(c=>a+b+c==x?k=[a,b,c]:0)));return k};
$('#output').hide();
$('#run').click(() => {
  const x = parseInt($('#input').val(), 10);
  if (x >= 0) {
    $('#input').val(x);
    const values = F(x);
    $('#values').text(values.join(', '));
    $('#output').show();
  }
  else {
    $('#output').hide();
    alert('You must enter a positive integer');
  }
});
```
```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
Enter a value: <input type="text" id="input" />
<br />
<button id="run">Get triangle numbers</button>
<br />
<span id="output">Triangle numbers are: <span id="values"></span></span>
```
]