Piles and Piles of Pebbles

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?

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 , so the shortest code in each language wins.

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.

• You don't need group 1 in the second stage, and neither group 1 nor 3 in the third stage. – Martin Ender Sep 8 '17 at 10:44
• And then ((?(2)1\2|1)) can be shortened to (1(?(2)\2)). – Martin Ender Sep 8 '17 at 10:55
• Actually, it's another three byte shorter to do something weird like this: ^((?<2>)(1\2)+){2}$. Or ^(()(?<2>1\2)+){2}$ if you prefer. – Martin Ender Sep 8 '17 at 10:59
• @MartinEnder That last version makes my brain ache, but I was able to use your second comment for my linked answer, which was nice. – Neil Sep 8 '17 at 12:28
• I think the last one is actually simpler than even the standard approach because it doesn't have the weird conditional forward reference. – Martin Ender Sep 8 '17 at 12:30

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 *)


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  • Darn Frobenius solve atom it beat my normal Jelly solution by 6 whole bytes :( – Erik the Outgolfer Sep 8 '17 at 10:57 • @EriktheOutgolfer I need to finish it and make a pull for it. – miles Sep 8 '17 at 16:18 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 }  Jelly, 15 bytes 0rSƤṗ⁸S⁼¥Ðf⁸ḢTL  Try it online! JavaScript (ES6), 7563 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))) 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  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