Decompose a number into triangles

Question

Given an integer n, decompose it into a sum of maximal triangular numbers (where T_m represents the mth triangular number, or the sum of the integers from 1 to m) as follows:

• while n> 0,

  • find the largest possible triangular number T_m such that T_m ≤ n.

  • append m to the triangular-decomposition representation of n.

  • subtract T_m from n.

For example, an input of 44 would yield an output of 8311, because:

• 1+たす2+たす3+たす4+たす5+たす6+たす7+たす8 =わ 36 < 44, but 1+たす2+たす3+たす4+たす5+たす6+たす7+たす8+たす9 =わ 45> 44.

  • the first digit is 8; subtract 36 from 44 to get 8 left over.

• 1+2+3 = 6 < 8, but 1+2+3+4 = 10> 8.

  • the second digit is 3; subtract 6 from 8 to get 2 left over.

• 1 < 2, but 1+2 = 3> 2.

  • the third and fourth digits must be 1 and 1.

Use the digits 1 through 9 to represent the first 9 triangular numbers, then use the letters a through z (can be capitalized or lowercase) to represent the 10th through 35th triangular number. You will never be given an input that will necessitate the use of a larger "digit".

The bounds on the input are 1 ≤ n < 666, and it will always be an integer.

All possible inputs and outputs, and some selected test cases (listed as input, then output):

1 1
2 11
3 2
4 21
5 211
6 3
100 d32
230 k5211
435 t
665 z731

An output of ∞ for an input of -1/12 is not required. :)

• user75200: But does an input of ∞ need to have an output of ∞?

Answer 1

JavaScript (ES6), 52 bytes

f=(n,t=0)=>t<n?f(n-++t,t):t.toString(36)+(n?f(n):'')

How?

Rather than explicitly computing T_i = 1 + 2 + 3 + ... + i, we start with t = 0 and iteratively subtract t + 1 from n while t < n, incrementing t at each iteration. When the condition is not fulfilled anymore, a total of T_t has been subtracted from n and the output is updated accordingly. We repeat the process until n = 0.

Below is a summary of all operations for n = 100.

 n | t | t < n | output
----+----+-------+--------
100 | 0 | yes | ""
 99 | 1 | yes | ""
 97 | 2 | yes | ""
 94 | 3 | yes | ""
 90 | 4 | yes | ""
 85 | 5 | yes | ""
 79 | 6 | yes | ""
 72 | 7 | yes | ""
 64 | 8 | yes | ""
 55 | 9 | yes | ""
 45 | 10 | yes | ""
 34 | 11 | yes | ""
 22 | 12 | yes | ""
 9 | 13 | no | "d"
----+----+-------+--------
 9 | 0 | yes | "d"
 8 | 1 | yes | "d"
 6 | 2 | yes | "d"
 3 | 3 | no | "d3"
----+----+-------+--------
 3 | 0 | yes | "d3"
 2 | 1 | yes | "d3"
 0 | 2 | no | "d32"

Test cases

f=(n,t=0)=>t<n?f(n-++t,t):t.toString(36)+(n?f(n):'')
console.log(f(1)) // 1
console.log(f(2)) // 11
console.log(f(3)) // 2
console.log(f(4)) // 21
console.log(f(5)) // 211
console.log(f(6)) // 3
console.log(f(100)) // d32
console.log(f(230)) // k5211
console.log(f(435)) // t
console.log(f(665)) // z731

Answer 2

Jelly, (削除) 18 (削除ここまで) 17 bytes

Ḥ‘1⁄2+.Ḟ©ịØB2®cạμ1¿

This is a monadic link that prints to STDOUT. It's return value is 0 and should be ignored.

Try it online!

Answer 3

dc, 74 bytes

?sa[2k_1K/1 4/la2*+v+0k1/dlardd*+2/-sadd10<t9>ula0<s]ss[87+P]st[48+P]sulsx

This is awful.

?sa stores the input
[2k sets precision to 2 so dc doesn't truncate 1/4
_1K/1 4/la2*+v+ uses the quadratic formula to find k, the next value to print
0k1/d truncates k to an integer
lardd*+2/-sa subtracts kth triangular number from the input 
dd10<t9>u determines whether to print k as a letter or a digit 
la0<s]ss loops when a is greater than 0
[87+P]st prints k as a letter
[48+P]su prints k as a digit (not p, as that leaves a trailing newline)
lsx starts the main loop

Answer 4

JavaScript (ES6), (削除) 61 (削除ここまで) 57 bytes

Saved 4 bytes thanks to @Arnauld

f=(n,p=q=0)=>n?p-~q>n?q.toString(36)+f(n-p):f(n,++q+p):''

• Arnauld: I had f=(n,t=0)=>n?t+1>n?t.toString(36)+f(n):f(n-++t,t):1
• ETHproductions: @Arnauld Oh wow, that's way better. You should post it yourself...
• Arnauld: Alright. In your version, would it be safe to do f=(n,p=q=0) and f(n,++q+p)?

Answer 5

Java 7, 81 bytes

int i=0;String c(int n){return i<n?c(n-++i):Long.toString(i,36)+(n>(i=0)?c(n):"");}

Port from @Arnauld's amazing JavaScript (ES6) answer.
My own approach was almost 2x as long..

Try it here.

Explanation:

int i=0; // Temp integer `i` (on class level)
String c(int n){ // Method with integer parameter and String return-type
 return i<n? // If `i` is smaller than the input integer
 c(n-++i) // Return a recursive call with input minus `i+1` (and raise `i` by 1 in the process)
 : // Else:
 Long.toString(i,36)+ // Return `i` as Base-36 +
 (n>(i=0)? // (If the input integer is larger than 0 (and reset `i` to 0 in the process)
 c(n) // Recursive call with the input integer
 : // Else:
 ""); // an empty String)
} // End of method

Answer 6

Retina, (削除) 115 (削除ここまで) (削除) 108 (削除ここまで) (削除) 38 (削除ここまで) 34 bytes

.+
$*¶
(\G¶|¶1円)+
01ドル
+T`_w¶`w_`.¶

[Try it online!] (Includes test suite) Uses uppercase letters. Edit: Saved (削除) 70 (削除ここまで) 74 bytes by shamelessly adapting @MartinEnder's answer to Is this number triangular? Explanation: The number is converted into unary, then the largest possible triangular number is repeatedly matched until the number is exhausted. Each match is then converted into base 36.

Answer 7

PHP, 74 Bytes

for(;$n=&$argn;$t.=$i>10?chr($i+86):$i-1)for($i=0;$n>=++$i;)$n-=$i;echo$t;

Online Version

Answer 8

R, 87 bytes

Originally, I tried to preset the possible Triangular numbers. This led to this code with 105 bytes:

pryr::f(n,{l=cumsum(1:35)
k=''
while(n){y=tail(which(l<=n),1)
n=n-l[y]
k=paste0(k,c(1:9,letters)[y])}
k})

This required more indexing so I tried the methodology from @Arnauld to reduce the bytes down to 87.

pryr::f(n,{k='';while(n){t=0;while(t<n){t=t+1;n=n-t};k=paste0(k,c(1:9,letters)[t])};k})

Both codes made use of the preset letters, since their I couldn't find a short way to convert to base 36.