19
\$\begingroup\$

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

\$\endgroup\$
12
  • 1
    \$\begingroup\$ For 12 you can also do 1 + 1 + 10. \$\endgroup\$ Jul 17, 2017 at 12:59
  • 1
    \$\begingroup\$ @steenbergh a won't always be a triangular number \$\endgroup\$ Jul 17, 2017 at 13:28
  • 3
    \$\begingroup\$ I can parse "builtin functions to directly get an array, a range or any other form of collection containing a list of triangular numbers" in two ways, but neither of them makes sense. The first prohibits all builtins which directly get an array, but that seems to prohibit all use of arrays in every language I know; the other prohibits builtins to "directly get ... a range ... containing a list of triangular numbers", but I don't know what that would mean. \$\endgroup\$ Jul 17, 2017 at 13:38
  • 2
    \$\begingroup\$ So built-in functions which take an argument n and return a list of the first n triangle numbers are permitted? That feels rather targetted against some specific language, although I don't know which. \$\endgroup\$ Jul 17, 2017 at 13:49
  • 4
    \$\begingroup\$ I urge you to lift this restriction. I promise you it won't improve the inter-language answer quality or fairness in the way you think. \$\endgroup\$
    – Lynn
    Jul 17, 2017 at 13:51

19 Answers 19

8
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ Ahhh... Yep; that'd do it. \$\endgroup\$ Jul 17, 2017 at 14:18
7
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ +1 for random output. :) I'm also surprised that gives the shortest solution (thus far). \$\endgroup\$ Jul 17, 2017 at 14:41
  • \$\begingroup\$ Thank you very much for the method. The corresponding Ruby code has 57 bytes. \$\endgroup\$ Jul 17, 2017 at 17:20
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Please consider adding an explanation.. =) \$\endgroup\$
    – racer290
    Jul 17, 2017 at 12:58
  • 2
    \$\begingroup\$ @racer290 done. \$\endgroup\$
    – Leaky Nun
    Jul 17, 2017 at 13:00
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Isn’t dropping the a>=b,b>=c conditions and just suffixing !!0 to your code also a valid answer? Outputting all solutions doesn’t really help you here. \$\endgroup\$
    – Lynn
    Jul 17, 2017 at 18:48
  • \$\begingroup\$ @Lynn You're right of course, I got distracted. Thanks! \$\endgroup\$ Jul 17, 2017 at 22:59
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
5
  • \$\begingroup\$ Your map (and perhaps your filter) can be written shorter as a list comprehension. \$\endgroup\$
    – Wheat Wizard
    Jul 17, 2017 at 14:44
  • \$\begingroup\$ Here's a TIO of the changes implemented. \$\endgroup\$
    – Wheat Wizard
    Jul 17, 2017 at 14:48
  • \$\begingroup\$ @WheatWizard thanks for the idea, I can't believe I didn't think of a list comprehension for the map \$\endgroup\$
    – Chase
    Jul 17, 2017 at 14:50
  • \$\begingroup\$ Filter objects are perfectly valid output, but if you want to output a list you can use a splat like so [*filter(...)] \$\endgroup\$
    – Wheat Wizard
    Jul 17, 2017 at 14:51
  • 1
    \$\begingroup\$ What I had tried was (x,y,z) for x,y,z in... which is longer than your l for l in... which likely accounts for that difference. \$\endgroup\$
    – Chase
    Jul 17, 2017 at 14:52
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 63 bytes

(t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&]‌​)&
\$\endgroup\$
2
  • \$\begingroup\$ With infix syntax and that whack way of getting First that saves a whopping 2 bytes, (t=#;#&@@Select[Table[i(i+1)/2,{i,0,t}]~Tuples~{3},Tr@#==t&])& for 62 bytes. \$\endgroup\$ Jul 18, 2017 at 8:48
  • \$\begingroup\$ Great, I'll edit \$\endgroup\$
    – ZaMoC
    Jul 18, 2017 at 8:54
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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)

\$\endgroup\$
1
  • \$\begingroup\$ You've got the same problem I do: by taking the biggest triangle number <= x at each step, you aren't guaranteed to have a triangle number for your 3rd place. Check your output for x = 103: 91 + 10 + 1 = 102 \$\endgroup\$
    – asgallant
    Jul 18, 2017 at 16:25
0
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ You could possibly save a byte by leaving out the selector for the first list element because you are allowed to print all possible solutions too. \$\endgroup\$
    – racer290
    Jul 17, 2017 at 15:56
  • \$\begingroup\$ @racer290 Even better, though the results will be in the form [[a,b,c],[d,e,f]] - would that be ok? \$\endgroup\$
    – Sok
    Jul 17, 2017 at 15:57
  • \$\begingroup\$ @racer290 Actually, no, filtering the duplicates would not be free by the looks of things, so it wouldn't be any shorter :c \$\endgroup\$
    – Sok
    Jul 17, 2017 at 15:58
0
\$\begingroup\$

J, 36 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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>

\$\endgroup\$
3
  • \$\begingroup\$ You're not explaining the most interesting part: why is x-m-n a triangular number, i.e. why does this work? \$\endgroup\$ Jul 17, 2017 at 23:03
  • \$\begingroup\$ Well dangit, turns out it isn't guaranteed. All of the test cases I used just happened to produce a valid triplet of triangle numbers. Back to the drawing board. \$\endgroup\$
    – asgallant
    Jul 17, 2017 at 23:44
  • \$\begingroup\$ Fixed now, less happy with this solution <;o( but at least it works. \$\endgroup\$
    – asgallant
    Jul 18, 2017 at 16:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.