Piles and Piles of Pebbles

Question

My job is stacking pebbles into triangular piles. I've only been doing this for a century and it is already pretty boring. The worst part is that I label every pile. I know how to decompose pebbles into piles of maximal size, but I want to minimize the number of piles. Can you help?

Task

Given an integer, decompose it into the minimum number of triangular numbers, and output that minimum number.

Triangular Numbers

A triangular number is a number which can be expressed as the sum of the first n natural numbers, for some value n. Thus the first few triangular numbers are

1 3 6 10 15 21 28 36 45 55 66 78 91 105

Example

As an example, let's say the input is 9. It is not a triangular number, so it cannot be expressed as the sum of 1 triangular number. Thus the minimum number of triangular numbers is 2, which can be obtained with [6,3], yielding the correct output of 2.

As another example, let's say the input is 12. The most obvious solution is to use a greedy algorithm and remove the largest triangular number at a time, yielding [10,1,1] and an output of 3. However, there is a better solution: [6,6], yielding the correct output of 2.

Test Cases

in out
1 1
2 2
3 1
4 2
5 3
6 1
7 2
8 3
9 2
10 1
11 2
12 2
13 2
14 3
15 1
16 2
17 3
18 2
19 3
20 2
100 2
101 2
5050 1

Rules

• The input integer is between 1 and the maximum integer of your language.
• I can emulate any language with my pebbles, and I want your code as small as possible because I have nothing but pebbles to keep track of it. Thus this is code-golf, so the shortest code in each language wins.

Answer 1

Retina, 57 49 bytes

.+
$*
(^1|1\1)+$
1
(^1|1\1)+(1(?(2)\2))+$
2
11+
3

Try it online! Based on my answer to Three triangular numbers. Change the third line to ^(^1|1\1)*$ to support zero input. Edit: Saved 8 (but probably should be more) bytes thanks to @MartinEnder.

Answer 2

Mathematica, 53 bytes

Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&

This code is very slow. If you want to test this function, use the following version instead:

Min[Plus@@@Table[$($+1)/2,{$,√#+1}]~FrobeniusSolve~#]&

Try it on Wolfram Sandbox

Explanation

Min[Plus@@@Table[$($+1)/2,{$,#+1}]~FrobeniusSolve~#]&  (* input: n *)

           Table[$($+1)/2,{$,#+1}]                     (* Generate the first n triangle numbers *)
                                  ~FrobeniusSolve~#    (* Generate a Frobenius equation from the *)
                                                       (* triangle numbers and find all solutions. *)
    Plus@@@                                            (* Sum each solution set *)
Min                                                    (* Fetch the smallest value *)

Answer 3

Jelly (fork), 9 bytes

æFR+\$S€Ṃ

This relies on a fork where I implemented an inefficient Frobenius solve atom. Can't believe it's already been a year since I last touched it.

Explanation

æFR+\$S€Ṃ  Input: n
æF         Frobenius solve with
     $     Monadic chain
  R          Range, [1, n]
   +\        Cumulative sum, forms the first n triangle numbers
      S€   Sum each
        Ṃ  Minimum

Answer 4

R, 69 58 bytes

function(n)3-n%in%(l=cumsum(1:n))-n%in%outer(c(0,l),l,"+")

Try it online!

Explanation:

function(n){
 T <- cumsum(1:n)             # first n triangular numbers  [1,3,6]
 S <- outer(c(0,T),T,"+")     # sums of the first n triangular numbers,
                              # AND the first n triangular numbers [1,3,6,2,4,7,4,6,9,7,9,12]
 3 - (n %in% S) - (n %in% T)  # if n is in T, it's also in S, so it's 3-2: return 1
                              # if n is in S but not T, it's 3-1: return 2
                              # if n isn't in S, it's not in T, so 3-0: return 3
}

Answer 5

Kotlin, 176 154 bytes

Submission

{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

Beautified

{
    // Make a mutable copy of the input
    var l=it
    // Keep track of the number of items removed
    var n=0
    // While we still need to remove pebbles
    while (l > 0) {
        // Increase removed count
        n++
        // BEGIN: Create a list of triangle numbers
        val r= mutableListOf(1)
        var t = 3
        var i = 3
        while (t<= l) {
            // Add the number to the list and calculate the next one
            r.add(t)
            t+=i
            i++
        }
        // END: Create a list of triangle numbers
        // Get the fitting pebble, or the biggest one if none fit or make a perfect gap
        l -= r.lastOrNull {l==it|| r.contains(l-it)} ?: r[0]
    }
    //Return the number of pebbles
    n
}

Test

var r:(Int)->Int =
{var l=it
var n=0
while(l>0){n++
val r=mutableListOf(1)
var t=3
var i=3
while(t<=l){r.add(t)
t+=i
i++}
l-=r.lastOrNull{l==it|| r.contains(l-it)}?:r[0]}
n}

data class TestData(val input:Int, val output:Int)

fun main(args: Array<String>) {
    val tests = listOf(
            TestData(1,1),
            TestData(2,2),
            TestData(3,1),
            TestData(4,2),
            TestData(5,3),
            TestData(6,1),
            TestData(7,2),
            TestData(8,3),
            TestData(9,2),
            TestData(10,1),
            TestData(11,2),
            TestData(12,2),
            TestData(13,2),
            TestData(14,3),
            TestData(15,1),
            TestData(16,2),
            TestData(17,3),
            TestData(18,2),
            TestData(19,3),
            TestData(20,2),
            TestData(100,2),
            TestData(101,2),
            TestData(5050,1)
    )
    tests.map { it to r(it.input) }.filter { it.first.output != it.second }.forEach { println("Failed for ${it.first}, output ${it.second} instead") }
}

TryItOnline

Answer 6

MATL, 15 bytes

`G:Ys@Z^!XsG-}@

Try it online!

Explanation

`         % Do...while
  G:      %   Push range [1 2 3 ... n], where n is the input
  Ys      %   Cumulative sum: gives [1 3 6 ... n*(n+1)/2]
  @Z^     %   Cartesian power with exponent k, where k is iteration index
          %   This gives a k-column matrix where each row is a Cartesian tuple
  !Xs     %   Sum of each row. Gives a column vector
  G-      %   Subtract input from each entry of that vector. This is the loop 
          %   condition. It is truthy if it only contains non-zeros
}         % Finally (execute before exiting the loop)  
  @       %   Push iteration index, k. This is the output
          % End (implicit). Proceeds with next iteration if the top of the
          % stack is truthy

Answer 7

Jelly, 15 bytes

0rSƤṗ⁸S⁼¥Ðf⁸ḢTL

Try it online!

Answer 8

JavaScript (ES6), 75 63 61 bytes

f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

How?

We use the following properties:

• According to Fermat polygonal number theorem, any positive integer can be expressed as the sum of at most 3 triangular numbers.
• A number t is triangular if and only if 8t+1 is a perfect square (this can easily be proven by solving t = n(n+1) / 2).

Given a positive integer n, it's enough to test whether we can find:

• x > 0 such that 8n+1 = x² (n itself is triangular)
• or x > 0 and y > 0 such that 8n+2 = x²+y² (n is the sum of 2 triangular numbers)

If both tests fail, n must be the sum of 3 triangular numbers.

f = (n, x = y = 0) =>                 // given n and starting with x = y = 0
  y < n + 2 ?                         // if y is less than the maximum value:
    x * x + y * y - 8 * n - 2 + !y ?  //   if x² + y² does not equal 8n + 2 - !y:
      f(                              //     do a recursive call with:
        n,                            //       - the original input n
        x < n + 2 ? x + 1 : ++y       //       - either x incremented or
      )                               //         y incremented and x set to y
    :                                 //   else:
      2 - !y                          //     return either 1 or 2
  :                                   // else:
    3                                 //   return 3

Test cases

f=(n,x=y=0)=>y<n+2?x*x+y*y-8*n-2+!y?f(n,x<n+2?x+1:++y):2-!y:3

;[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 100, 101, 5050 ]
.forEach(n => console.log(n + ' --> ' + f(n)))