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\$

closed as unclear what you're asking by Peter Taylor, Wheat Wizard, Rɪᴋᴇʀ, Stephen, xnor Jul 18 '17 at 9:02

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ For 12 you can also do 1 + 1 + 10. \$\endgroup\$ – Erik the Outgolfer Jul 17 '17 at 12:59
  • 1
    \$\begingroup\$ @steenbergh a won't always be a triangular number \$\endgroup\$ – Felipe Nardi Batista Jul 17 '17 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\$ – Peter Taylor Jul 17 '17 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\$ – Peter Taylor Jul 17 '17 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 '17 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\$
  • \$\begingroup\$ Ahhh... Yep; that'd do it. \$\endgroup\$ – Magic Octopus Urn Jul 17 '17 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\$
  • \$\begingroup\$ +1 for random output. :) I'm also surprised that gives the shortest solution (thus far). \$\endgroup\$ – Kevin Cruijssen Jul 17 '17 at 14:41
  • \$\begingroup\$ Thank you very much for the method. The corresponding Ruby code has 57 bytes. \$\endgroup\$ – Eric Duminil Jul 17 '17 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\$
  • \$\begingroup\$ Please consider adding an explanation.. =) \$\endgroup\$ – racer290 Jul 17 '17 at 12:58
  • 2
    \$\begingroup\$ @racer290 done. \$\endgroup\$ – Leaky Nun Jul 17 '17 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\$

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\$
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\$
  • \$\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 '17 at 18:48
  • \$\begingroup\$ @Lynn You're right of course, I got distracted. Thanks! \$\endgroup\$ – Christian Sievers Jul 17 '17 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\$
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\$
  • \$\begingroup\$ Your map (and perhaps your filter) can be written shorter as a list comprehension. \$\endgroup\$ – Wheat Wizard Jul 17 '17 at 14:44
  • \$\begingroup\$ Here's a TIO of the changes implemented. \$\endgroup\$ – Wheat Wizard Jul 17 '17 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 Vogeli Jul 17 '17 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 '17 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 Vogeli Jul 17 '17 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\$
  • \$\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\$ – numbermaniac Jul 18 '17 at 8:48
  • \$\begingroup\$ Great, I'll edit \$\endgroup\$ – J42161217 Jul 18 '17 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\$
  • \$\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 '17 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\$
  • \$\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 '17 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 '17 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 '17 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\$
  • \$\begingroup\$ You're not explaining the most interesting part: why is x-m-n a triangular number, i.e. why does this work? \$\endgroup\$ – Christian Sievers Jul 17 '17 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 '17 at 23:44
  • \$\begingroup\$ Fixed now, less happy with this solution <;o( but at least it works. \$\endgroup\$ – asgallant Jul 18 '17 at 16:42

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