8
\$\begingroup\$

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 , so the shortest code in each language wins.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You don't need group 1 in the second stage, and neither group 1 nor 3 in the third stage. \$\endgroup\$ – Martin Ender Sep 8 '17 at 10:44
  • \$\begingroup\$ And then ((?(2)1\2|1)) can be shortened to (1(?(2)\2)). \$\endgroup\$ – Martin Ender Sep 8 '17 at 10:55
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Sep 8 '17 at 10:59
  • \$\begingroup\$ @MartinEnder That last version makes my brain ache, but I was able to use your second comment for my linked answer, which was nice. \$\endgroup\$ – Neil Sep 8 '17 at 12:28
  • \$\begingroup\$ I think the last one is actually simpler than even the standard approach because it doesn't have the weird conditional forward reference. \$\endgroup\$ – Martin Ender Sep 8 '17 at 12:30
1
\$\begingroup\$

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

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
\$\endgroup\$
  • \$\begingroup\$ Darn Frobenius solve atom it beat my normal Jelly solution by 6 whole bytes :( \$\endgroup\$ – Erik the Outgolfer Sep 8 '17 at 10:57
  • \$\begingroup\$ @EriktheOutgolfer I need to finish it and make a pull for it. \$\endgroup\$ – miles Sep 8 '17 at 16:18
1
\$\begingroup\$

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

Jelly, 15 bytes

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

Try it online!

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

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

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

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

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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