15
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ But does an input of need to have an output of ∞? \$\endgroup\$ – user75200 Oct 26 '17 at 9:22
8
\$\begingroup\$

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 Ti = 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 Tt 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

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Jelly, 18 17 bytes

Ḥ‘½+.Ḟ©ịØB2®cạµ¹¿

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

Try it online!

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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):''
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ I had f=(n,t=0)=>n?t+1>n?t.toString(36)+f(n):f(n-++t,t):1 \$\endgroup\$ – Arnauld May 2 '17 at 0:37
  • \$\begingroup\$ @Arnauld Oh wow, that's way better. You should post it yourself... \$\endgroup\$ – ETHproductions May 2 '17 at 0:39
  • 1
    \$\begingroup\$ Alright. In your version, would it be safe to do f=(n,p=q=0) and f(n,++q+p)? \$\endgroup\$ – Arnauld May 2 '17 at 0:58
  • \$\begingroup\$ @Arnauld Yes, thanks! \$\endgroup\$ – ETHproductions May 2 '17 at 1:25
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Retina, 115 108 38 34 bytes

.+
$*¶
(\G¶|¶\1)+
0$1
+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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\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.