15
Given an integer n, decompose it into a sum of maximal triangular numbers (where Tm 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 Tm such that Tm ≤ n.
append m to the triangular-decomposition representation of n.
subtract Tm 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. :)
But does an input of ∞ need to have an output of ∞?
– user75200 – 2017-10-26T09:22:15.577