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.

• fireflame241: Sandbox full of pebbles.
• geokavel: Thematically related: codegolf.stackexchange.com/questions/95231/natural-pi-0-rock
• Martin Ender: OEIS A061336
• Martin Ender: Not to be confused with OEIS A057945 (the first difference occurs for n = 12).

Answer 1

Retina, (削除) 57 (削除ここまで) 49 bytes

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

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

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

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

• Erik the Outgolfer: Darn Frobenius solve atom it beat my normal Jelly solution by 6 whole bytes :(
• miles: @EriktheOutgolfer I need to finish it and make a pull for it.

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

Jelly, 15 bytes

0rSƤṗ8S=\Ðf8ḢTL

Try it online!

Answer 6

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 = x2 (n itself is triangular)
• or x> 0 and y> 0 such that 8n+2 = x2+y2 (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 x2 + y2 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)))

Answer 7

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 8

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