Three triangular numbers

Question

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 and an entry at OEIS, 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, so standard loopholes apply. May the shortest answer in bytes win!

Answer 1

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!

Answer 2

Python 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!

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 3

Jelly, 12 bytes

0r+\œċ3S=¥Ðf

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 4

Brachylog, 13 bytes

⟦⟦ᵐ+ᵐj₃⊇Ṫ.+?∧

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 5

MATL, 18 bytes

Q:qYs3Z^t!sG=fX<Y)

This outputs the first result in lexicographical order.

Try it at MATL Online!

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 6

Retina, 63 59 bytes

.+
$*
^((^1|1\2)*)((1(?(4)\4))*)((1(?(6)\6))*)$
$.1 $.3 $.5

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 7

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 8

Python 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!

Thanks to @WheatWizard for saving 12 bytes!

Answer 9

PHP, 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!

Answer 10

Mathematica, 63 bytes

(t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&]‌​)&

Answer 11

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 12

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!

Answer 13

R, 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!

Answer 14

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.

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 15

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 16

Pyth, 19 bytes

I am so out of practise with Pyth, it's untrue :/

hfqQsT.C*3+0msSdSQ3

Try it out here.

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 17

Ruby 61 57 55 bytes

Inspired by Lynn's Python answer. 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!

Answer 18

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>

Answer 19

J, 36 bytes

((2!1+$@]#:0({I.@,)=)]+/+/~)2!1+i.,]

Try it online!