# Question
Title: Relations between interval and semitones
Output this table:

|  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| -2\* | -1\* | - | 0 | - | 1 | 2 |
| -1\* | 0 | 1 | - | 2 | 3 | 4 |
| 1 | 2 | 3 | - | 4 | 5 | 6 |
| 3 | 4 | - | 5 | - | 6 | 7 |
| 5 | 6 | - | 7 | - | 8 | 9 |
| 6 | 7 | 8 | - | 9 | 10 | 11 |
| 8 | 9 | 10 | - | 11 | 12 | 13 |
| 10 | 11 | - | 12 | - | 13 | 14 |

* You can output one string with two types of split, 1D string array with one type of split, or 2D string array
* If your language support mixed type then you can fill numbers in number cells(but not `-1*` and `-2*`)
* If your number type has one value `-` then you can use it in `-` cells. Otherwise they should be text `-`.
* This table comes from here but I removed 1st row and 1st column
* Shortest code wins

# Answer
# JavaScript (ES6), 90 bytes

Returns a single string, using commas and line feeds as delimiters.

```
f=(n=7)=>~n--?[..."0024200"].map(j=>4-(n&2)&j?'-':v+["**"[++v+1]],v=34-n*7>>2)+`
`+f(n):''

```

Try it online!

Or **78 bytes** without the asterisks:

```
f=(n=7)=>~n--?[..."0024200"].map(j=>4-(n&2)&j?'-':v++,v=34-n*7>>2)+`
`+f(n):''

```

Try it online!

### How?

We iterate from \\$n=6\\$ to \\$n=-1\\$. The starting value of each row can be obtained with:

$$v\_n=\left\lfloor\frac{1}{4}(34-7n)\right\rfloor$$

There are 2 distinct row patterns:

$$\begin{cases}\[v\_n,v\_n+1,\varnothing,v\_n+2,\varnothing,v\_n+3,v\_n+4\]&n\in\\{-1,2,3,6\\}\\ \[v\_n,v\_n+1,v\_n+2,\varnothing,v\_n+3,v\_n+4,v\_n+5\]&n\in\\{0,1,4,5\\}\end{cases}$$

We can just test the penultimate bit of \\$n\\$ to distinguish them. We generate \\$2\\$ if it's set or \\$4\\$ otherwise and do a bitwise AND with the digit from the lookup string `"0024200"` according to its position.
> 5 votes

# Answer
# Raku, 96 bytes

```
{map ->\i,\j {{j-3,j-2,$_&&j-1,!$_&&j-1,$_&&j,j+$_,j+1+$_}((153+>i)%%2)},<1 2 4 6 8 9 11 13>.kv}

```

Returns the output as a 2D list with `False` for the blanks.

Try it online!
> 4 votes

# Answer
# Charcoal, ~~47~~ ~~39~~ 37 bytes

```
Ｅ⁸Ｅ⁺Σ…68ι⊕Ｅ⁷Σ…432234λ⎇﹪λ⁴⁺⊖⊖÷λ⁴…*‹λ⁸-

```

Try it online! Link is to verbose version of code. Outputs a Charcoal array, i.e. each element on its own line and each row double-spaced from the previous. Explanation:

```
 ⁸                                      Literal integer `8`
Ｅ                                       Map over implicit range
           ⁷                            Literal integer `7`
          Ｅ                             Map over implicit range
              432234                    Literal string `432234`
             …                          Truncated to length
                    λ                   Current column
            Σ                           Digital sum
         ⊕                              Vectorised increment
   ⁺                                    Vectorised add
      68                                Literal string `68`
     …                                  Extended to length
        ι                               Current row
    Σ                                   Digital sum
  Ｅ                                     Map over list
                       λ                Inner value
                      ﹪                 Modulo
                        ⁴               Literal integer `4`
                     ⎇                  If divisible then
                                    -   Literal string `-` otherwise
                             λ          Current value
                            ÷           Integer divided by
                              ⁴         Literal integer `4`
                           ⊖            Incremented
                          ⊖             Incremented
                         ⁺              Concatenated with
                                *       Literal string `*`
                               …        Truncated to length
                                  λ     Current value
                                 ‹      Is less than
                                   ⁸    Literal integer `8`

```

The program works by generating the following table, where the headers are generated from a list of differences:

| + | 1 | 5 | 8 | 10 | 12 | 15 | 19 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 1 | 5 | 8 | 10 | 12 | 15 | 19 |
| 6 | 7 | 11 | 14 | 16 | 18 | 21 | 25 |
| 14 | 15 | 19 | 22 | 24 | 26 | 29 | 33 |
| 20 | 21 | 25 | 28 | 30 | 32 | 35 | 39 |
| 28 | 29 | 33 | 36 | 38 | 40 | 43 | 47 |
| 34 | 35 | 39 | 42 | 44 | 46 | 49 | 53 |
| 42 | 43 | 47 | 50 | 52 | 54 | 57 | 61 |
| 48 | 49 | 53 | 56 | 58 | 60 | 63 | 67 |

Multiples of `4` are replaced with `-` while the remaining numbers are integer divided by `4` and then decremented twice, appending a `*` if this reduces them below zero.
> 3 votes

# Answer
# 05AB1E, 47 bytes

```
6L3-D>3FDÌ}D>DÌDÌ)εƵqbNèi¨Ƶ;S£ë3ô}'-.ý˜εD0‹i'*«

```

Try it online.

**Explanation:**

```
6L             # Push list [1,2,3,4,5,6]
  3-           # Decrease each by 3: [-2,-1,0,1,2,3]
D>             # Duplicate it, and increase each by 1
3F  }          # Loop 3 times:
  DÌ           #  Duplicate the top list, and increase each by 2
D>DÌDÌ         # Three more duplicates with +1, +2, and +2 respectively again
)              # Wrap all lists on the stack into a list
 ε             # Map over each inner list:
  Ƶq           #  Push compressed integer 153
    b          #  Convert it to binary: 10011001
     Nè        #  Index the current map-index into it
       i       #  If this is 1:
        ¨      #   Remove the last item of the list
         Ƶ;    #   Push compressed integer 212
           S   #   Convert it to a list: [2,1,2]
            £  #   Split the list into parts of that size: [[a,b],[c],[d,e]]
       ë       #  Else:
        3ô     #   Split the list into triplets: [[a,b,c],[d,e,f]]
       }       #  After the if-else:
        '-.ý  '#  Intersperse the list of sub-lists with "-" delimiter
            ˜  #  And flatten it to a single list again
  ε            #  Map over each inner value:
   D           #   Duplicate the current value
    0‹i        #   Pop the copy, and if it's a negative integer:
       '*«    '#    Append a "*"
               # (after which the matrix is output implicitly as result)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `Ƶq` is `153` and `Ƶ;` is `212`.
> 1 votes

# Answer
# Python 3, ~~222~~ 216 bytes

```
r=[];z=(0,3,4,7);m=-1
for i in range(8):
	r.append([]);s=i*2-(i+1)//4
	for q in range(7):d=q-3-int(q>3)+int(q<2 and i in z);r[m]+=[s+d];r[m][m]="-"if(q in(2,4)and i in z)or q==3 and i in(1,2,5,6)else r[m][m]
print(r)

```

Try it online!
> 1 votes

# Answer
# Python 3, 76 bytes

```
n=0
for r in b"(($"*2:n+=-4|r;print([r%c*'-'or(n:=n+1)for c in b""])

```

Try it online!

This prints each row as its own list. The two bytestrings contain unprintable characters -- here's the code with their ASCII values shown:

```
n=0
for r in[21,40,40,36]*2:n+=-4|r;print([r%c*'-'or(n:=n+1)for c in[1,1,5,3,5,1,1]])

```

Try it online!

The `r`'s in `[21,40,40,36]*2` correspond to the 8 rows, and the `c`'s in `[1,1,5,3,5,1,1]` to the 7 columns. They are chosen to make a "modulo table" producing the positions of the dashes, with a dash where `r%c==1` and `r%c==0` elsewhere.

```
           c
     1 1 5 3 5 1 1
r  %--------------
21 | 0 0 1 0 1 0 0
40 | 0 0 0 1 0 0 0
40 | 0 0 0 1 0 0 0
36 | 0 0 1 0 1 0 0
21 | 0 0 1 0 1 0 0
40 | 0 0 0 1 0 0 0
40 | 0 0 0 1 0 0 0
36 | 0 0 1 0 1 0 0

```

Each non-dash position is filled with the number `n`, which is first incremented. Changes to `n` persist between rows, so before the start of each row we decrease `n` from the end of the previous row by substracting either 3 or 4, noting that it will increment by 1 before the first value is produced.

These deltas are encoded per-row by the `r`'s as `-4|r`, which produces `[-4,-3,-3,-3,-4,-3,-3,-3]`. Because this pattern repeats in 2 blocks of 4 for the 8 rows, as did the dash pattern, we write the `r`'s list as a four-entry list repeated twice, saving bytes.

Here are all the properties we needed the hardcoded `r`'s and `c`'s to satisfy:

```
-4|21 == -3
-4|40 == -4
-4|36 == -4

 21%5 == 36%5 == 1
 40%3 == 1
 21%1 == 40%1 == 36%1 == 40%5 == 21%3 == 36%3 == 0

```

I found these with a brute-force search, and many other options were possible.
> 0 votes

# Answer
# Scala, 145 bytes

Port of @xnor's Python answer in Scala.

---

Golfed version. Try it online!

```
var n=0;for(r<-Seq(21,40,40,36)++Seq(21,40,40,36)){n+= -4|r;println(Seq(1,1,5,3,5,1,1).map(c=>if(r%c==0){n+=1;n.toString}else"-").mkString(","))}

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    var n = 0
    val rs = List(21, 40, 40, 36) ++ List(21, 40, 40, 36)
    val cs = List(1, 1, 5, 3, 5, 1, 1)

    for (r <- rs) {
      n += -4 | r
      val result = cs.map { c =>
        if (r % c == 0) {
          n += 1
          n.toString
        } else "-"
      }
      println(result.mkString(", "))
    }
  }
}

```
> 0 votes

---
Tags: code-golf, kolmogorov-complexity, music
---


title: Interactive Maze Solver

text:
# Question
Title: Interactive Maze Solver
Bob got kidnapped and is stuck in a maze. Your job is to help him find a way out. But since it is a very dark and scary maze, he can't see anything. He can only feel walls when he runs in to it, and knows when he has found the exit, but doesn't know anything more that.

Since he has to run your program by memory, it has to be as short as possible.

*Note: I took this problem from http://acmgnyr.org/year2016/problems.shtml, but adapted it slightly, and wrote the judge program/test cases myself.*

# Specification

* This is an interactive problem, so you program will output moves to stdout, and take in responses from stdin.
* Your program can output one of the moves `right`, `left`, `down`, `up`.
* It will then get as input one of the following:
    + `wall` \- this means that Bob has hit a wall. Bob will stay in the same place.
    + `solved` \- Bob has found the exit! Your program should now also exit without printing anything else.
    + `ok` \- Bob was able to move in the given direction.
* If the maze has no exit, your program should output `no exit` to let Bob know that he should give up. Your program should then exit without printing anything else.
* Since Bob is in a hurry to get out, your program should not make any extraneous moves. In other words, **your program is not allowed to move in the same direction from the same square twice**.
* This is , so shortest program wins!

# Examples

In the following examples, `S` is the starting square, `X` is the exit, `#` is a wall, and spaces are valid squares. Since there is no single correct answer, these are just example runs of a solution. Also note that the drawings of the maze are just there for you to see, and your program will not get them as input.

```
########
#S     #
###### #
     # #
     #X#

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              solved

#####
# S #
#####

right
              ok
right
              wall
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              wall
left
              wall
right
              ok
no exit
              solved

###############################
#S                            #
##############       ###      #
             #       #X#      #
             #                #
             ##################

right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              ok
right
              wall
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              ok
down
              ok
down
              ok
down
              wall
left
              ok
down
              wall
up
              ok
up
              ok
left
              wall
down
              ok
left
              wall
down
              ok
left
              ok
down
              wall
up
              wall
left
              ok
down
              wall
up
              solved

```

# Checker Program

* I have written a solution checker in Python. You can find it at https://gist.github.com/Maltysen/f0186019b3aa3812d812f8bb984fee19.
* Run it like `python mazechecker.py ./mazesolver`.
* It will test your program on all the mazes in a folder called `mazes`.
* The mazes are in separate files in the same format from above.
* It checks all the conditions listed above, and notifies you if your solution violates any.
* You can have it print additional diagnostic info with `python mazechecker.py -d ./mazesolver`.
* You can find a zipped `mazes` folder here. You can also add your own to it if you want.

# Answer
# JavaScript (ES6),  ~~180~~  174 bytes

Uses `prompt()` to output the direction and retrieve the result.

```
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])

```

Try it online! (with automated I/O)

### Interactive snippet

***WARNING**: this code will display a prompt() dialog until 'solved' is entered or the function figures out that there's no exit at all.*

```
(
_=>(g=p=>[...'012301234'].some((d,i)=>g[p]>>d&1|i<4&g[P=[p[0]+(d-2)%2,p[1]+~-d%2]]>0?0:(r=prompt('up/left/down/right/no exit'.split`/`[g[p]|=1<<d,d]))<'s'?g(P):r<'t'))([0,0])
)()
```

### Commented

```
_ => (                      // anonymous function taking no argument
  g = p =>                  // g = recursive function taking the current position p = [x, y]
    [ ...'0123',            // i<4  : try to move on squares that haven't been visited yet
      ...'0123',            // 3<i<8: try to go back to where we initially came from
      ...'4'                // i=8  : if everything failed, there must be no exit
    ].some((d, i) =>        // for each direction d at index i:
      g[p] >> d & 1         //   if this direction was already tried at this position
      | i < 4 &             //   or i is less than 4 and
      g[P = [               //   the square at the new position P = [X, Y] with:
        p[0] + (d - 2) % 2, //     X = x + dx[d]
        p[1] + ~-d % 2      //     Y = y + dy[d]
      ]] > 0 ?              //   was already visited:
        0                   //     abort
      : (                   //   else:
        r = prompt(         //     output the direction:
          [ 'up',           //       0 = up
            'left',         //       1 = left
            'down',         //       2 = down
            'right',        //       3 = right
            'no exit'       //       4 = no exit
          ][                //
            g[p] |= 1 << d, //       mark this direction as used
            d               //       d = actual index of the string to output
          ]                 //     r = result of prompt()
        )                   //
      ) < 's' ?             //     if r = 'ok':
        g(P)                //       do a recursive call at the new position
      :                     //     else:
        r < 't'             //       yield true if r = 'solved' or false if r = 'wall'
    )                       // end of some()
)([0, 0])                   // initial call to g at (0, 0)

```
> 7 votes

# Answer
# Python3, 408 bytes:

```
E=enumerate;P=print
def f(m):
 q,d=[(x,y)for x,r in E(m)for y,s in E(r)if'S'==s],{}
 while q:
  x,y=q.pop(0)
  for M,X,Y in[('up',-1,0),('down',1,0),('left',0,-1),('right',0,1)]:
   if 0<=(j:=x+X)<len(m)and 0<=(k:=y+Y)<len(m[0])and(j,k)not in(V:=d.get((x,y),[])):
    C=m[j][k]
    if'X'==C:P(M+' solved');return
    elif'#'==C:P(M+' wall')
    else:print(M+' ok');q+=[(j,k)];d[(x,y)]=V+[(j,k)]
 P('no exit')

```

Try it online!
> 0 votes

---
Tags: code-golf, puzzle-solver, maze, interactive
---


title: Balanced Ternary Converter

text:
# Question
Title: Balanced Ternary Converter
Credits for the challenge idea go to @AndrewPiliser. His original proposal in the sandbox was abandoned and since he has not been active here for several months, I have taken over the challenge.

**Balanced ternary** is a non-standard numeral system. It is like ternary in that the digits increase in value by a factor of 3 as you go further to the left - so `100` is `9` and `1001` is 28.

However, instead of having values of 0, 1 and 2, **the digits have values of -1, 0, and 1**. (You can still use this to express any integer.)

For this challenge, the digit meaning `+1` will be written as `+`, `-1` will be written as `-`, and `0` is just `0`. Balanced ternary does not use the `-` symbol in front of numbers to negate them like other numeral systems do - see examples.

**Your task is to write a complete program which takes a 32-bit decimal signed integer as input and converts it to balanced ternary.** No built-in base conversion functions of any sort are allowed (Mathematica probably has one...). Input can be on standard input, command-line arguments, etc.

Leading zeroes may be present in input but not in output, unless the input is `0`, in which case the output should also be `0`.

## Examples

These are conversions from balanced ternary to decimal; you will have to convert the other way.

```
+0- = 1*3^2 + 0*3^1 + -1*3^0 = 9 + 0 + -1 = 8
+-0+ = 1*3^3 + -1*3^2 + 0*3^1 + 1*3^0 = 27 + -9 + 0 + 1 = 19
-+++ = -1*3^3 + 1*3^2 + 1*3^1 + 1*3^0 = -27 + 9 + 3 + 1 = -14

```

# Answer
## Python 2: 58 chars

```
n=input()
s=""
while n:s="0+-"[n%3]+s;n=-~n/3
print s or 0

```

Generates the balanced ternary digit-by-digit from the end. The last digit is given by the residue `n%3` being `-1`,`0`, or `+1`. We then remove the last digit and divide by 3 using Python's floor-divide `n=(n+1)/3`. Then, we proceed recursively with the new last digit until the number is 0.

A special case is needed for the input `0` to give `0` rather than the empty string.

---

The specs don't allow this, but if one could write a function instead of a program and output the empty string for 0, a 40 char solution would be possible.

```
g=lambda n:n and g(-~n/3)+"0+-"[n%3]or""

```
> 23 votes

# Answer
# Pyth, ~~71~~ ~~24~~ 23

```
L?+y/hb3@"0+-"%b3bk|yQ0

```

This is a recursive solution, based on @xnor's 40 character recursive function. `y` constructs the baanced ternary of the input, by finding the last digit using the mod 3 index, and then uses the fact that the rest of the digits are equal to the balanced ternary for (n+1)/3, using floored division. Then, it calls the function, returning the result, or 0 if the input is 0.

Try it here.
> 6 votes

# Answer
# CJam, 24 bytes

I came up with this independently and I think this is, most probably, the only way to handle this.

```
li{_3%"0+-"=\_g+3/}h;]W%

```

Algorithmically, its similar to xnor's answer.

Try it online here

**How it works**:

```
li{               }h                 "Read input, convert to integer and run the code block"
                                     "until stack has 0 on top";
   _3%                               "Copy and get modulus 3";
      "0+-"=                         "Take the correct character based on the above modulus";
            \_g+                     "Swap, copy and take signum of the number and add"
                                     "that to it, incrementing the number if positive,"
                                     "decrementing otherwise";
                3/                   "Integer divide by 3 and continue until 0";
                    ;]               "Pop the residual 0 and wrap everything in array";
                      W%             "Reverse to get in binary format (right handed)";

```
> 6 votes

# Answer
# JavaScript (E6) 68

A complete program, as requested, with I/O via popup. The core is the R function, 49 bytes.

Not so different from the other recursive solutions, I guess. Taking advantage of the automatic conversion between string and number to avoid a special case for "0"

```
 alert((R=(n,d=(n%3+3)%3)=>n?R((n-d)/3+(d>1))+'0+-'[d]:'')(prompt()))

```

**Test** in FireFox/FireBug console, using just the R function

```
['0','8','19','-14','414'].map(x =>x +': '+R(x))

```

*Output*

```
["0: 0", "8: +0-", "19: +-0+", "-14: -+++", "414: +--0+00"]

```
> 6 votes

# Answer
# Mathematica, 54 characters

Similar to xnor's recursion

Unicode symbols are used to replace `Floor`,`Part`,`!=`

```
If[(t=⌊(#+1)/3⌋)≠0,#0@t,""]<>{"0","+","-"}〚#~Mod~3+1〛&

```

## Output

Stored as `f` for brevity and written without unicode incase you can't view

```
f=If[(t=Floor[(#+1)/3])!=0,#0@t,""]<>{"0","+","-"}[[#~Mod~3+1]]&
f /@ {8, 19, -14, 414} // Column

+0-
+-0+
-+++
+--0+00

```
> 5 votes

# Answer
# Mathematica - ~~157~~ ~~154~~ ~~146~~ 128

The golfed version:

```
f=(s="";n=#;i=Ceiling@Log[3,Abs@#]~Max~0;While[i>=0,s=s<>Which[n>=(1+3^i)/2,n-=3^i;"+",n>-(1+3^i)/2,"0",1>0,n+=3^i;"-"];i--];s)&

```

And with indentation for legibility:

```
f = (s = ""; n = #; i = Ceiling@Log[3, Abs@#]~Max~0;
 While[i >= 0,
  s = s<>Which[
   n >= (1 + 3^i)/2, n -= 3^i; "+",
   n > -(1 + 3^i)/2, "0",
   1 > 0, n += 3^i; "-"
  ];
 i--];
s)&

```

Usage:

```
f[414]

```

Output:

```
+--0+00

```

Many thanks to Martin Büttner in reducing the number of characters.
> 3 votes

# Answer
# GNU sed, 236 bytes

```
/^0/bV
:
s/\b9/;8/
s/\b8/;7/
s/\b7/;6/
s/\b6/;5/
s/\b5/;4/
s/\b4/;3/
s/\b3/;2/
s/\b2/;1/
s/\b1/;0/
s/\b0//
/[^;-]/s/;/&&&&&&&&&&/g
t
y/;/1/
:V
s/111/3/g
s/3\b/3:/
s/311/33!/
s/31/3+/
y/3/1/
tV
s/1/+/
y/1:/!0/
/-/{s/-//
y/+!/!+/
}
y/!/-/

```

Try it online!

# Explanation

The first half of the code (less the first line) translates decimal to unary and comes straight from "Tips for golfing in sed." Then it translates unary to balanced ternary one trit at a time, which I'll demonstrate by working an example manually.

Before the final output, the ternary digits `-`, `0`, and `+` are represented by `!`, `:`, and `+`, respectively.

For an interesting result, we start with `-48`, which has been converted to unary (with the `-` intact). To calculate the first (right-most) trit, we have to calculate the remainder of 48÷3. We can do this by replacing the `111`s with `3`s:

```
-111111111111111111111111111111111111111111111111 │ s/111/3/g
# => -3333333333333333

```

48÷3 has no remainder, so no `1`s remain, and we know our first trit is `:` (for 0), so we replace it:

```
-3333333333333333 │ s/3\b/3:/
# => -3333333333333333:

```

Now we have our "ones place," so we know the remaining `3`s represent the threes place. To keep the math working we have to divide them by 3, i.e. replace them with `1`s:

```
-3333333333333333: │ y/3/1/
# => -1111111111111111:

```

Let's double-check our math: We have 16 (unary `1111111111111111`) in the threes place and zero (`:`) in the ones place. That's 3✕16 + 1✕0 = 48. So far so good.

Now we start again. Replace `111`s with `3`s:

```
-1111111111111111: │ s/111/3/g
# => -333331:

```

This time our remainder is `1`, so we put `+` in the threes place and replace the remaining `3`s with `1`s:

```
-333331: │ s/31/3+/; y/3/1/
# => -11111+:

```

Sanity check time: We have a 5 (unary `11111`) in the nines place, 1 (`+`) in the threes place, and 0 (`:`) in the ones place: 9✕5 + 3✕1 + 1✕0 = 48. Great! Again we replace the `111`s with `3`s:

```
-11111+: │ s/111/3/g
# => -311+:

```

This time our remainder is 2 (`11`). That takes up two trits (`+!`), which means we have a carry. Just like in decimal arithmetic that means we take the rightmost digit and add the rest to the column to the left. In our system, that means we put `!` in the nines place and add another three to its left, then replace all of the `3`s with `1`s to represent the 27s place:

```
-311+: │ s/311/33!/; y/3/1/
# => -11!+:

```

Now we don't have any 3s left, so we can replace any remaining unary digits with their corresponding trits. Two (`11`) is `+!`:

```
-11!+: │ s/11/+!/
# => -+!!+:

```

In the actual code this is done in two steps, `s/1/+/` and `y/1:/!0/`, to save bytes. The second step also replaces `:`s with `0`s, so it actually does this:

```
-11!+: │ s/1/+/; y/1:/+0/
# => -+!!+0

```

Now we check if we have a negative number. We do, so we have to get rid of the sign and then invert each trit:

```
-+!!+0 │ /-/ { s/-//; y/+!/!+/; }
# => !++!0

```

Finally, we replace `!`s with `-`s:

```
!++!0 │ y/!/-/
# => -++-0

```

That's it!
> 3 votes

# Answer
# Clojure, 172 bytes

`(let[s "0+-"](loop[x(Integer.(read-line))xs '()](if(= 0 x)(println(apply str xs))(let[y(mod x 3)x(int (Math/floor(/ x 3.0)))](recur(if(= y 2)(inc x)x)(cons(get s y)xs))))))`

Readable version:

```
(let [s "0+-"]
  (loop [x  (Integer. (read-line))
         xs '()]
    (if (= 0 x)
      (apply str xs)
      (let [y (mod x 3)
            x (int (Math/floor (/ x 3.0)))]
        (recur (if (= y 2) (inc x) x) (cons (get s y) xs))))))

```
> 3 votes

# Answer
# Stax, 17 bytes

```
ë1·âΓM¿├>Ö≥Er☺à┤3

```

Run and debug it

Shortest answer so far, but should be easily beaten by some golfing languages. The algorithm is the same as @xnor's Python answer.

ASCII equivalent:

```
z{"0+-";3%@+,^3/~;wr

```
> 2 votes

# Answer
# JavaScript 108 102 (ES6, no recursive calls)

```
t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v="0+-"[r=(a%3+3)%3]+v,2==r&&++a,a=a/3|0;return v}

```

Original entry at 108

```
t=a=>{v="";if(0==a)v="0";else for(a=(N=0>a)?-a:a;a;)v=(N?"0-+":"0+-")[r=a%3]+v,2==r&&++a,a/=3,a|=0;return v}

```

Not as fancy as @edc65's answer... I'd appreciate any help reducing this further...
> 1 votes

# Answer
# Clojure, 242 bytes

```
#(clojure.string/join""(map{1"+"0"0"-1"-"}(loop[x(vec(map read-string(clojure.string/split(Integer/toString % 3)#"")))](let[y(.indexOf x 2)](if(< y 0)x(let[z(assoc x y -1)](recur(if(= y 0)(vec(cons 1 z))(assoc z(dec y)(inc(x(dec y))))))))))))

```

Is this the longest Clojure answer so far?

Ungolfed (with comments):

```
(use '[clojure.string :only (split join)]);' (Stupid highlighter)
; Import functions

(defn ternary [n]
  (join ""
  ; Joins it all together
    (map {1 "+" 0 "0" -1 "-"}
    ; Converts 1 to +, 0 to 0, -1 to -
      (loop [x (vec (map read-string (split (Integer/toString n 3) #"")))]
      ; The above line converts a base 10 number into base 3,
      ; and splits the digits into a list (8 -> [2 2])
        (let [y (.indexOf x 2)]
        ; The first occurrence of 2 in the list, if there is no 2,
        ; the .indexOf function returns -1
          (if (< y 0) x
          ; Is there a 2? If not, then output the list to
          ; the map and join functions above.
            (let [z (assoc x y -1)]
            ; Converts where the 2 is to a -1 ([2 2] -> [-1 2])
              (recur
                (if (= y 0) (vec (cons 1 z))
                  ; If 2 is at the 0th place (e.g. [2 2]),
                  ; prepend a 1 (e.g. [-1 2] -> [1 -1 2])
                  (assoc z (dec y) (inc (x (dec y)))))))))))))
                  ; Else increment the previous index
                  ; (e.g. [1 -1 2] -> [1 0 -1])

```
> 1 votes

# Answer
# 8th, ~~179~~ ~~171~~ 167 characters

Here it is a complete program in 8th which takes a decimal signed integer as input and converts it to balanced ternary

```

: f "" swap repeat dup 3 n:mod ["0","+","-"] swap caseof rot swap s:+ swap dup n:sgn n:+ 3 n:/mod nip while drop s:rev ;
"? " con:print 16 null con:accept >n
f cr . cr

```

**Test**

```

? 414
+--0+00

```

The first time the program asks for a number to convert (as required). Then, it is possible to invoke the word `f` to convert more numbers as in the following line:

```

[ 8 , 19 , -14 , ] ( nip dup . space f . cr ) a:each drop

```

**Output**

```

8 +0-
19 +-0+
-14 -+++

```

**Code explanation**

```

"? " con:print 16 null con:accept >n

```

This is the code for input handling. The core of the code is inside the word `f`. Away from the *golf course* I would have used the word `>bt` instead of `f`. Here it is an ungolfed version of `f` (with comments):

```

: f \ n -- s
    ""   \ used for the first symbol concatenation
    swap \ put number on TOS to be used by loop
    repeat
        dup
        3 n:mod      \ return the remainder of the division by 3
        [ "0" , "+" , "-" , ]
        swap caseof  \ use remainder to take proper symbol
        rot          \ put previous symbol on TOS
        swap         \ this is required because "" should come first
        s:+          \ concatenate symbols
        swap         \ put number on TOS
        dup
        n:sgn n:+    \ add 1 if positive or add -1 if negative
        3 n:/mod nip \ put quotient only on TOS
    while drop
    s:rev            \ reverse the result on TOS
;

```
> 1 votes

# Answer
# Brainfuck, ~~406~~ ~~340~~ 335 bytes

code (with added newlines for readability):

```
-[+>+[+<]>+]>-<,[->->+<<]+>[[-]<->]<[>>,<]>[<]>>>>++<<<[>-[<->-----]<+++>>>[>]>>++>++<<<<[[->>+>>+<<<<]<]>>>++>++<
[[-<<<<<+>>>>>]<<<<+++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]->[-]-->+[+[-<<+>>]>]>>]<<<<<<[[->>>+<<<]<]>,]
<<[>>>>>[[-<->]>]<<[++++<]<]>>>>>[>]+[<--[>->]>[-<+>]<]<<++>+<[>-]>[-<++>>]<<[>>--[<+>++++++]<<---[>++<++[>+++<-]]>.[-]<<]

```

Takes input as decimal string with an optional leading `-` This is my first non-trivial Brainfuck program so there is certainly room for improvement.

Try it online

Commented version of code:

```
-[+>+[+<]>+]>-  constant 45
<,[->->+<<]+>[[-]<->]<[>>,<]>[<]> remember sign
>>>++<<< load 2 in cell 3
[ while input is not EOF
>-[<->-----]<+++ subtract 48 (ascii 0) from input
>>>[>]>>++>++<<<<[[->>+>>+<<<<]<]>>>++>++<  multiply by 10 (add number to shifted copy)
[  add next digit and handle carries
[-<<<<<+>>>>>]
<<<<+++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]
->[-]-->+[+[-<<+>>]>]>>
]
<<<<<<[[->>>+<<<]<]>
,] reset to start of loop
<<[>>>>>[[-<->]>]<<[++++<]<] flip number if negative
>>>>>[>]+[<--[>->]>[-<+>]<]<<++ strip leading zeros
>+<[>-]>[-<++>>]<< ensure zero is printed
[ print the number
  >>--[<+>++++++]< load 43 (char code of plus)
  <---[>++<++[>+++<-]]>.[-]<<
]

```
> 1 votes

# Answer
## Java, ~~327~~ 269 characters

My first try in code golfing. I don't know any of those really short languages, so here's a solution in Java. I'd appreciate advice to further shorten it.

```
import java.util.*;class a{public static void main(String[] h){int i=Integer.parseInt(new Scanner(System.in).nextLine());String r="";while(i!=0){if(i%3==2||i%3==-1){r="-"+r;}else if(i%3==1||i%3==-2){r="+"+r;}else{r="0"+r;}i=i<0?(i-1)/3:(i+1)/3;}System.out.println(r);}}

```

Try it here : http://ideone.com/fxlBBb

**EDIT**

Replaced `BufferedReader` by `Scanner`, allowing me to remove `throws` clause, but had to change import (+2 chars). Replaced `Integer` by `int`. Unfortunately, program won't compile if there isn't `String[] h` in `main`.
> 0 votes

# Answer
# JavaScript (ES6), 51 bytes

```
v=>[...v].map(x=>t=3*t+((+x!=+x)?(x+1)-0:0),t=0)&&t

```

Loop through characters. First multiply previous total times 3, then if isNaN(character) is true, convert the string (character + "1") to a number and add it, otherwise zero.
> 0 votes

# Answer
# Stax, 14 bytes

```
ü♣ê⌠yù∞♪♦X=/ƒ├

```

Run and debug it
> 0 votes

# Answer
# 05AB1E, 20 bytes

```
ΔYÝ<ÀÅв3βÊ½¾}…0+-ÅвJ

```

Try it online!
> 0 votes

# Answer
# APL(NARS), 26 chars, 52 bytes

```
{+/(3*¯1+⍳≢⍵)×¯2+⌽'-0+'⍳⍵}

```

test:

```
  h←{+/(3*¯1+⍳≢⍵)×¯2+⌽'-0+'⍳⍵}
  h '+0-'
8
  h '+-0+'
19
  h '-+++'
¯14
  h ,'-'
¯1
  h ,'0'
0
  h ,'+'
1

```

possible it could be less if ⊥ is used but it is forbidden...
> 0 votes

# Answer
# Python 3, 66

Python 2 answer from xnor, ported to Python 3. Note that official support for Python 2 ceases on January 1 2020.

```
n=eval(input())
s=""
while n:s="0+-"[n%3]+s;n=-~n//3
print(s or 0)

```
> 0 votes

# Answer
# Raku (Perl 6) (rakudo), ~~52~~ 53 bytes

```
{.&(my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''})||0}

```

Attempt This Online!

## Explanation

```
{.&(my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''})||0}
    my&g={$_??g(-+^$_ div 3)~ <0 + ->[$_%3]!!''}      # g returns '' for 0
              g(-+^$_ div 3)                          # g(($_ + 1) div 3)
 .&(                                           )      # call g($_)
                                                ||0   # if this is falsy, then return 0

```
> 0 votes

---
Tags: code-golf, math, number, base-conversion
---


title: How does the square end?

text:
# Question
Title: How does the square end?
In base-10, all perfect squares end in \\$0\\$, \\$1\\$, \\$4\\$, \\$5\\$, \\$6\\$, or \\$9\\$.

In base-16, all perfect squares end in \\$0\\$, \\$1\\$, \\$4\\$, or \\$9\\$.

Nilknarf describes why this is and how to work this out very well in this answer, but I'll also give a brief description here:

When squaring a base-10 number, \\$N\\$, the "ones" digit is not affected by what's in the "tens" digit, or the "hundreds" digit, and so on. Only the "ones" digit in \\$N\\$ affects the "ones" digit in \\$N^2\\$, so an easy (but maybe not golfiest) way to find all possible last digits for \\$N^2\\$ is to find \\$n^2 \mod 10\\$ for all \\$0 \le n \< 10\\$. Each result is a possible last digit. For base-\\$m\\$, you could find \\$n^2 \mod m\\$ for all \\$0 \le n \< m\\$.

Write a program which, when given the input \\$N\\$, outputs all possible last digits for a perfect square in base-\\$N\\$ (without duplicates). You may assume \\$N\\$ is greater than \\$0\\$, and that \\$N\\$ is small enough that \\$N^2\\$ won't overflow (If you can test all the way up to \\$N^2\\$, I'll give you a finite amount of brownie points, but know that the exchange rate of brownie points to real points is infinity to one).

Tests:

```
 Input -> Output
 1     -> 0
 2     -> 0,1
 10    -> 0,1,5,6,4,9
 16    -> 0,1,4,9
 31    -> 0,1,2,4,5,7,8,9,10,14,16,18,19,20,25,28
 120   -> 0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105

```

this is , so standard rules apply!

(If you find this too easy, or you want a more in-depth question on the topic, consider this question: Minimal cover of bases for quadratic residue testing of squareness).

# Answer
# Jelly, 5 bytes

```
R²%³Q

```

Try it online!

### Explanation

```
R²%³Q   Main link, argument: n

R       Range from 1 to n
 ²      Square each
  %³    Mod each by n
    Q   Deduplicate

```
> 9 votes

# Answer
# Google Sheets, ~~52~~ ~~51~~ 47 bytes

```
=ArrayFormula(Join(",",Unique(Mod(Row(A:A)^2,A1

```

Saved 4 bytes thanks to Taylor Scott

Sheets will automatically add 4 closing parentheses to the end of the formula.

It doesn't return the results in ascending order but it does return the correct results.
> 22 votes

# Answer
# Swift, ~~47 35~~ 32\* bytes

* *-3 thanks to @Alexander.*

*Possibly the first time in history Swift ~~ties~~ beats Python?*

```
{m in Set((0..<m).map{$0*$0%m})}

```

**Try it online!**

---

# Explanation

* `(0..<m).map{}` \- Iterates through the range `[0...m)` and map the following results:
* `$0*$0%m` \- The square of each integer modulo the base `m`.
* `Set(...)` \- Removes the duplicates.
* `m in` \- Assigns the base to a variable `m`
> 8 votes

# Answer
# 05AB1E, 5 bytes

```
Lns%ê

```

Try it online! or as a Test Suite

```
L     # Range 1 .. input
 n    # Square each
  s%  # Mod by input
    ê # Uniquify (also sorts as a bonus)

```
> 7 votes

# Answer
# APL (Dyalog Unicode), 6 bytes

```
∪⊢|⍳×⍳

```

Try it online!

Explanation:

```
∪⊢|⍳×⍳
   ⍳×⍳    ⍝ square every number in range from 1 to ⍵
 ⊢|       ⍝ modulo ⍵
∪         ⍝ unique elements

```
> 5 votes

# Answer
# Japt, ~~7~~ 6 bytes

```
Ç²%UÃâ

```

Test it

1 byte saved thanks to Oliver

---

## Explanation

Implicit input of integer `U`.

```
Ç   Ã

```

Create an array of integers from `0` to `U-1`, inclusive and pass each though a function.

```
²

```

Square.

```
%U

```

Modulo `U`.

```
â

```

Get all unique elements in the array and implicitly output the result.
> 4 votes

# Answer
# Pyth, 6 bytes

```
{%RQ*R

```

Try it online

### How it works

```
{%RQ*RdQ    implicit variables
       Q    autoinitialized to eval(input())
    *R      over [0, …, Q-1], map d ↦ d times
      d         d
 %R         map d ↦ d modulo
   Q            Q
{           deduplicate

```
> 4 votes

# Answer
# Python 3, ~~40~~ ~~39~~ 37 bytes

*-1 byte thanks to Mr. Xcoder. -2 bytes thanks to Business Cat.*

```
lambda m:[*{n*n%m for n in range(m)}]

```

Try it online!
> 3 votes

# Answer
# Brachylog, ~~10~~ 9 bytes

```
>ℕ^₂;?%≜ᶠ

```

Try it online!

### Explanation

```
       ≜ᶠ       Find all numbers satisfying those constraints:
    ;?%           It must be the result of X mod Input where X…
  ^₂              …is a square…
>ℕ                …of an integer in [0, …, Input - 1]

```
> 3 votes

# Answer
# C#, 63 bytes

```
using System.Linq;m=>new int[m].Select((_,n)=>n*n%m).Distinct()

```

Try it online!
> 3 votes

# Answer
## JavaScript (ES6), 52 bytes

```
f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

```

### Test cases

```
f=(m,k=m,x={})=>k?f(x[k*k%m]=m,k-1,x):Object.keys(x)

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))
```

---

## Non-recursive version, ~~60~~ 58 bytes

*Saved 2 bytes thanks to @ThePirateBay*

```
m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

```

### Test cases

```
let f =

m=>(a=[...Array(m).keys()]).filter(v=>a.some(n=>n*n%m==v))

;[1, 2, 10, 16, 31, 120]
.map(m => console.log(m + ' -> ' + f(m)))
```
> 3 votes

# Answer
# Actually, 11 bytes

```
;╗r⌠²╜@%⌡M╔

```

Try it online!

Explanation:

```
;╗r⌠²╜@%⌡M╔
;╗           store a copy of m in register 0
  r          range(m)
   ⌠²╜@%⌡M   for n in range:
    ²          n**2
     ╜@%       mod m
          ╔  remove duplicates

```
> 2 votes

# Answer
# Haskell, 45 bytes

```
import Data.List
f m=nub[n^2`mod`m|n<-[0..m]]

```

-4 bytes from Anders Kaseorg

Try it online!
> 2 votes

# Answer
# CJam, 12 bytes

```
{_,_.*\f%_&}

```

Anonymous block accepting a number and returning a list.

Try it online!

### Explanation

```
_,          Copy n and get the range [0 .. n-1]
  _.*       Multiply each element by itself (square each)
     \f%    Mod each by n
        _&  Deduplicate

```
> 2 votes

# Answer
# MATL, ~~6~~ 5 bytes

-1 byte thanks to @LuisMendo

```
:UG\u

```

Try it online!
> 2 votes

# Answer
# AWK, ~~44~~ ~~43~~ 40 bytes

```
{for(;i++<$0;)if(!a[j=i*i%$0]++)print j}

```

I managed to cut off 3 bytes after revisiting this old answer.

Step by step:

```
{
for(;i++<$0;)        For all numbers less of equal to the input...

if(!a[j=i*i%$0]++)   Increments the element j of the array a.
                     j is the last digit of each i*i.
                     If the element a[j] is being incremented
                     for the first time (a[j]++ returns 0,
                     so negating it (!a[j]++) returns 1)...

print j              Prints j.
}

```

Try it online!

### Former answer (43 bytes)

```
{for(;i++<$0;)a[i*i%$0];for(j in a)print j}

```

Edit: Incrementing the `i` variable during the `for` condition saved one more byte.

Step by step:

```
{
for(;               # starts the loop with no previous statement.
    i++<$0;)        # loops while _i_ is less than the input ($0).
                    # also increments 1 to the _i_ variable after
                    # it is evaluated.

    a[i*i%$0];      # fiat the _i*i%$0_ element of the _a_ array!
                    # by only stating _array[element]_, the element exists.
                    # i*i%$0 means: i squared (mod $0), i.e., the last digit.

for(j in a)         # for every element _j_ existing in the _a_ array,
    print j         # prints the element _j_
}

```

Try it online!
> 2 votes

# Answer
# Scala, ~~32~~ 30 bytes

Simple use of the *easy tip* from OP.

```
(0 to n-1).map(x=>x*x%n).toSet

```

Try it online!

-2 bytes thanks to @MrXcoder, with priorities (no need for `()` around `*` operation)

Wondering: is this possible to *implicitly* tell the compiler to understand things like `(0 to n-1)map(x=>x*x%n)toSet` (without having to `import scala.language.postfixOps`)?
> 1 votes

# Answer
# Octave, 27 bytes

```
@(n)unique(mod((1:n).^2,n))

```

Try it online!
> 1 votes

# Answer
# Mathematica, 30 bytes

```
Union@Table[Mod[i^2,#],{i,#}]&

```

Try it online!
> 1 votes

# Answer
## JavaScript (ES6), 48 bytes

```
f=
n=>[...new Set([...Array(n)].map((_,i)=>i*i%n))]
```

```
<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>
```

43 bytes if returning a `Set` instead of an array is acceptable.
> 1 votes

# Answer
# Ruby, ~~31~~ 30 bytes

```
->m{(0..m).map{|n|n*n%m}.uniq}

```

Try it online!
> 1 votes

# Answer
# Haskell, 44 bytes

```
f m=[k|k<-[0..m],or[mod(n^2)m==k|n<-[0..m]]]

```

Try it online!
> 1 votes

# Answer
# Perl 6, 19 bytes

```
{set (^$_)»²X%$_}

```

Test it

## Expanded:

```
{ # bare block lambda with implicit param ｢$_｣

  set        # turn the following into a Set (shorter than ｢unique｣)

      (
        ^$_  # a Range upto (and excluding) ｢$_｣
      )»²    # square each of them (possibly in parallel)

    X%       # cross modulus the squared values by

      $_     # the input
}

```
> 1 votes

# Answer
# Whispers v2, 71 bytes

```
> Input
>> [1)
>> L²
>> L%1
>> Each 3 2
>> Each 4 5
>> {6}
>> Output 7

```

Try it online!

The TIO Footer simply sorts the output, remove it to see the unsorted set.
> 1 votes

# Answer
# K (ngn/k), ~~11~~ 10 bytes

```
{?x!*/&=x}

```

Try it online!

* `&=x` generate a list containing `(0..x; 0..x)`
* `*/` multiply the two items of the list together
* `x!` mod the result by `x`
* `?` (implicitly) return the distinct last digits
> 1 votes

# Answer
# Vyxal, 5 bytes

```
ɾ²$%U

```

Try it Online!

```
ɾ     # 1...n
 ²    # Each squared
   %  # Modulo...
  $   # input
    U # Uniquify the result

```
> 1 votes

# Answer
# Nibbles, 5 bytes

```
`$.,$%^$~@

```

Attempt This Online!

```
`$ Deduplicate
.   map
,    range
$     input
%    mod
^     power
$      it
~      2
@     input

```
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
L²ŒU

```

Try it online!

#### Explanation

```
L²ŒU  # Implicit input
L     # Push [0..input)
 ²    # Square each value
  Œ   # Mod by input
   U  # Uniquify
      # Implicit output

```
> 1 votes

# Answer
# Retina, 70 bytes

```
.+
$*

;$`¶$`
1(?=.*;(.*))|;1*
$1
(1+)(?=((.*¶)+\1)?$)

D`1*¶
^|1+
$.&

```

Try it online! Warning: Slow for large inputs. Slightly faster 72-byte version:

```
.+
$*

$'¶$';
1(?=.*;(.*))|;1*
$1
+s`^((1+)¶.*)\2
$1
^1+

D`1*¶
^|1+
$.&

```

Try it online!
> 0 votes

# Answer
# Clojure, 40 bytes

```
#(set(map(fn[x](mod(* x x)%))(range %)))

```
> 0 votes

# Answer
# Pyth, 13 bytes

```
VQ aY.^N2Q){Y

```

Try online.

Lame attempt at explaining:

```
VQ               for N in [0 .. input-1]
                   blank space to supress implicit print inside the loop
     .^N2Q         N ^ 2 % input
   aY              append that to Y, which is initially an empty list
          )      end for
           {Y    deduplicate and implicit print

```

To sort the output, insert an `S` on any side of the `{`

I think there should be a shorter way...
> 0 votes

# Answer
# Python 2, 59 bytes

```
t=int(input())
print list(set([(i*i)%t for i in range(t)]))

```

Try it online!
> 0 votes

# Answer
# PowerShell, 35 bytes

```
0..($n="$args")|%{$_*$_%$n}|sort -u

```

Try it online!
> 0 votes

# Answer
# , 28 bytes

```
unique((1:(n<-scan()))^2%%n)

```

Try it online!
> 0 votes

# Answer
# 8th, ~~138~~ 131 bytes

**Code**

```
[] swap dup >r ( 2 ^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip

```

**Explanation**

`[]` \- Create output array

`swap dup >r` \- Save input for later use

`( 2 ^ r@ n:mod a:push ) 1 rot loop` \- Compute square end

`rdrop` \- Clean r-stack

`' n:cmp a:sort` \- Sort output array

`' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip` \- Get rid of consecutive duplicates from array

**SED** (Stack Effect Diagram) is: `a -- a`

**Usage and example**

```
: f [] swap dup >r ( 2 n:^ r@ n:mod a:push ) 1 rot loop rdrop ' n:cmp a:sort ' n:cmp >r -1 a:@ swap ( tuck r@ w:exec ) a:filter rdrop nip ;

ok> 120 f .
[0,1,4,9,16,24,25,36,40,49,60,64,76,81,84,96,100,105]

```
> 0 votes

# Answer
# Java (OpenJDK 8), ~~86~~ 77 bytes

```
n->java.util.stream.IntStream.range(1,n+1).map(a->a*a%n).distinct().toArray()

```

Try it online!
> 0 votes

# Answer
# PHP, 53 bytes

```
for(;$i<$t=$argv[1];)$a[$z=$i++**2%$t]++?:print"$z
";

```

Loop from 0 to the input number, using the `n^2 mod base` formula to mark numbers that have been used. It goes to that position in an array, checking if it's been incremented and outputting it if it hasn't. It then increments it afterwards so duplicate values don't get printed.

Try it online!
> 0 votes

# Answer
# Perl 5 `-MList::Util=uniq -na`, 32 bytes

```
say for uniq map$_**2%"@F",0..$_

```

Try it online!
> 0 votes

# Answer
# Pari/GP, 25 bytes

```
n->Set([x^2%n|x<-[1..n]])

```

Try it online!
> 0 votes

# Answer
# Prolog (SWI), 49 bytes

```
N+X:-setof(K,A^(between(0,N,A),K is A^2mod N),X).

```

Try it online!

Creates a set of values from `K=(A^2)%N`, where `0<=A<=N`.
> 0 votes

# Answer
# Pyt, 7 bytes

```
Đř²⇹%Ụş

```

Try it online!

```
Đ            implicit input (n); Đuplicate on stack
 ř           řangify (push [1,2,...,n])
  ²          square
   ⇹%        modulo n
     Ụş      get Ụnique elements and şort in ascending order; implicit print

```
> 0 votes

# Answer
# Thunno `D`, \\$ 6 \log\_{256}(96) \approx \\$ 4.94 bytes

```
R2^$ZU

```

Attempt This Online!

## Thunno, \\$ 7 \log\_{256}(96) \approx \\$ 5.76 bytes

```
DR2^$ZU

```

Attempt This Online!

#### Explanation

```
DR2^$ZU  # Implicit input
DR       # Duplicate and get range(input)
  2^     # Square each number
    $    # Mod by the input
     ZU  # Uniquify
         # Implicit output

```
> 0 votes

# Answer
# JavaScript, 45 bytes

```
n=>(g=x=>x?g(g[x*x%n]=x-1):Object.keys(g))(n)

```

Try it online!

## 40 bytes

With output as an array that could contain multiple empty items.

```
n=>(g=x=>x?g(x-1,a[y=x*x%n]=y):a)(a=[n])

```

Try it online!
> 0 votes

# Answer
# , 10 bytes

```
~.@:|2^~i.

```

Attempt This Online!

```
~.@:|2^~i.
        i.  NB. range [0..n)
     2^~    NB. square
  @:        NB. then
~.          NB. uniquify

```
> 0 votes

---
Tags: code-golf, number-theory, abstract-algebra
---


title: Sign that word!

text:
# Question
Title: Sign that word!
# What is a Word Signature?

The signature of a word are all of it's letters put in order - the signatures of `this`, `hist` and `hits` are all `hist`.

# The Challenge

Write a program program should ask for an input, then print out the signature of that word. So an example program run might look like this:

```
Give me a string: this
The signature signature of 'this' is hist.

```

There is no required interaction, as long as it takes an input and prints the signature, it is OK.

# Scoring

The program with the smallest byte count wins!

# Leaderboard

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
var QUESTION_ID=54945;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table><table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
```

**Challenged Finished!**

**WINNER: jimmy23013**

# Answer
# GolfScript, 1 byte

```
$

```

Yes, only 1 byte.

Try it here.
> 50 votes

# Answer
# C (with x86), 61 bytes

```
s[];main(){qsort(s,read(0,s,99),1,"YXZQQQ\x8a\x00*\x02\x0f\xbe\xc0\xc3");puts(s);}

```

That string contains raw bytes, not actual `\x..` codes, and it's a *raw machine code callback* passed to `qsort`. Works on x86 only:

```
59         pop   ecx
58         pop   eax
5a         pop   edx
51         push  ecx
51         push  ecx
51         push  ecx
8a 00      mov   al,  BYTE PTR [eax]
2a 02      sub   al,  BYTE PTR [edx]
0f be c0   movsx eax, al
c3         ret

```

Which is essentially:

```
int func(char *a, char *b) { return *a - *b; }

```

See p6-7 of this pamphlet in Japanese by shinh.
> 26 votes

# Answer
# Stuck, 4 bytes

```
sc$d

```

This language was documented on the wiki just yesterday! Mmm, fresh esolangs.
> 20 votes

# Answer
# Stuck, 5 Bytes

I finally get to use my language, Stuck! :D

```
s$""j

```

This takes an input via stdin, sorts, joins, and implicitly prints. This did give me some ideas for changes though.

**Edit:** Oh wow, someone already posted and beat me in my own language!
> 19 votes

# Answer
# GOTO++, ~~432~~ 430 bytes

GOTO++ project site.

```
niveaugourou 0
s=ENTRETONTEXTE()
§2 a=LeCaracNumero()&s *(1)
n=*(1)
costaud i=*(2)/&i infeg NombreDeLettres(&s)/i=+*(1)
b=LeCaracNumero()&s &i
GOTONULPOURLESNULS %1 }&b inf &a{
a=&b
n=&i
§1 faiblard
GOTOPRINTDUTEXTE()&a
t=PrendsUnMorceau()&s *(0) &n
u=PrendsUnMorceau()&s }&n+*(1){ *(0)
e=BOITEAPINGOUINS()&t &u
s=Marijuana()&e «»
GOTONONNULPOURLESNULS %3 }NombreDeLettres(&s) eg *(1){
GOTOPASMALIN %2
§3 GOTOPRINTDUTEXTE()&s

```

Not sure why I inflicted this to myself, but I did
> 16 votes

# Answer
# gs2, 1 byte

```
/

```

Same as the GolfScript answer, but gs2 uses a different operator for sorting.
> 13 votes

# Answer
# Perl, 18 bytes

```
print sort<>=~/./g

```

Thanks to Dom Hastings for helping me save 3 bytes.
> 10 votes

# Answer
# Haskell, 35 bytes

```
import Data.List;main=interact sort

```
> 7 votes

# Answer
# C#, ~~114~~ 110 characters

Takes input from a command line argument. Not a very short program, but well... it's C#. :P

```
namespace System.Linq{class P{static void Main(string[]a){Console.Write(string.Concat(a[0].OrderBy(x=>x)));}}}

```

Thanks to Abbas for saving 4 bytes!
> 6 votes

# Answer
## Pyth, 2 bytes

```
Sw

```

DEMO HERE.
Details-

```
S - for sorting
w - Python 3's input()

```
> 6 votes

# Answer
# J, 3 bytes

```
/:~

```

For example: `/:~'this'`
> 6 votes

# Answer
# Brainfuck, 40 bytes

```
,[>>+>>,]<<[[<<]>>[-[<]>>[.<<->]>+>>]<<]

```

This uses the counting sort algorithm, which makes this an **O(n)** solution.

The code requires a left-infinite or wrapping tape of 8 bit cells. Try it online!

### How it works

```
,          Read a char from STDIN.
[          While the byte under the pointer (last read char) is non-zero:
  >>+        Move the pointer two steps to the right and increment.
  >>,        Move the pointer two steps to the right and read a char.
]
<<         Move the pointer two steps to the left.

           If the input was "sort", the tape now contains the following:
           0 0 115 0 1 0 111 0 1 0 114 0 1 0 116 0 1 0 0
                                                   ^

[          While the byte under the pointer is non-zero:
  [<<]       Advance two steps to the left until a null byte is encountered.
  >>         Advance two steps to the right.

             This will place the pointer on the first input character.

  [          While the byte under the pointer is non-zero:
    -          Decrement.
    [<]        Move the pointer to the left until a null byte is encountered.
    >>         Move the pointer two steps to the right.

               If the decremented character is non-zero, [<] will move to the
               null byte before it, so >> brings the pointer to the null byte
               after it. If the decremented character is zero, [<] is a no-op, so
               >> advances two steps to the right, to a non-zero byte.

    [          While the byte under the pointer is non-zero:
      .          Print the char under the pointer.
      <<-        Move the pointer two steps to the left and decrement.
      >          Move the pointer to the right.
    ]

               If the decremented character gave zero, this will print the value
               of the accumulator after it, and decrement the character once more
               to make it non-zero, then place the pointer to the right of the
               character, thus exiting the loop.

    >+         Move the pointer to the right and increment.

               This increments the accumulator each time an input character is
               decremented.

    >>         Move the pointer two steps to the right.

               This moves the pointer to the next character.
  ]
  <<         Move the pointer two steps to the left.

             This moves the pointer to the accumulator of the last character.
]

             After 255, th accumulator wraps around to 0, and the loop ends.

```
> 6 votes

# Answer
# CJam, 2 bytes

```
l$

```

Reads a line of input (`l`) and sorts it (`$`).
> 5 votes

# Answer
## Coreutils, 24 23

```
fold -w1|sort|tr -d \\n

```
> 4 votes

# Answer
## Python 3, 31 Bytes

```
print("".join(sorted(input())))

```
> 4 votes

# Answer
# Ruby, 17 bytes

```
$><<$<.chars.sort

```
> 4 votes

# Answer
# Java 8, 119 bytes

This is basically only competitive with the C# answer, because, well, Java.

(At least this beats GOTO++. Not really an accomplishment...)

```
class C{public static void main(String[]s){s=s[0].split("");java.util.Arrays.sort(s);System.out.print("".join("",s));}}

```

*Thanks to ProgramFOX for saving 1 byte, rink.attendant for saving 2 bytes.*
> 4 votes

# Answer
# Ostrich, 2 bytes

```
G$

```

In Ostrich `G` reads a line of input from STDIN and `$` sorts it.
> 4 votes

# Answer
## JavaScript (ES6), 32 bytes

Demo only works in Firefox and Edge at time of writing, as Chrome/Opera does not support ES6 by default:

Edit: I didn't look at the answers prior to posting but now I realize it's pretty much the exact same as the one by NinjaBearMonkey.

```
f=x=>alert([...x].sort().join``)
```

```
<form action=# onsubmit='f(document.getElementById("I").value);return false;'>
  <input type=text pattern=\w+ id=I>
  <button type=submit>Sort letters</button>
</form>
```
> 3 votes

# Answer
# Julia, 21 bytes

```
s->join(sort([s...]))

```

And for fun, here's how you might do it without using an inbuilt sorting function, for 53 bytes:

```
f=s->s>""?(k=indmax(s);f(s[k+1:end]s[1:k-1])s[k:k]):s

```
> 3 votes

# Answer
# SWI-Prolog, 34 bytes

```
a(X):-msort(X,Y),writef("%s",[Y]).

```

Called as such:`a(`this`).`
> 2 votes

# Answer
# Scala, 21 bytes

```
print(args(0).sorted)

```

run from command line example:

```
$ scala -e "print(args(0).sorted)" this
hist

```
> 2 votes

# Answer
# Powershell, ~~44~~ 37 Bytes

```
-join((Read-Host).ToCharArray()|sort)

```
> 2 votes

# Answer
# JavaScript, 34 bytes

```
alert([...prompt()].sort().join``)

```

The reason this is so long is that JavaScript can only sort arrays, so the string must be split into an array, sorted, and then joined back into a string. This is ECMAScript 6; the equivalent in ES5 is:

```
alert(prompt().split('').sort().join(''))

```
> 2 votes

# Answer
# Python 2, 33 32 bytes

```
print`sorted(raw_input())`[2::5]

```

Heavily inspired by @Kamehameha's answer. Converted to python 2. Can't golf much more.
> 1 votes

# Answer
# APL, 7 characters

Doesn't work on ngn-apl for me, but should work in theory:

```
X[⍋X←⍞]

```

reads a line from standard input, which is assigned to `X`. `⍋X` is the indices of `X` which yield an ascending order, and `X[...]` actually sorts `X` by these indices.
> 1 votes

# Answer
# JavaScript, 54 bytes

call js file with node

```
console.log(process.argv[2].split('').sort().join(''))

```
> 1 votes

# Answer
# Nim, ~~102~~ ~~101~~ ~~79~~ 73 bytes

```
let s=stdin.readAll
for i in 1..'~':
 for j in s:(if i==j:stdout.write j)

```

Still learning Nim and working out golf tricks. Apparently it's better *not* to use the builtin `sort`, which would require a lot of imports (thanks @Mauris)
> 1 votes

# Answer
## Matlab, ~~13~~ 5 bytes

The code simply defines a function handle to the `sort` function:

```
@sort

```

To call it, use `ans('this')`, where `'this'` represents the input string (thanks to Alex A. and Stewie Griffin):

```
>> @sort
ans =
    @sort
>> ans('this')
ans =
hist

```
> 1 votes

# Answer
# Processing, 40 bytes

```
print(join(sort(args[0].split("")),""));

```
> 1 votes

# Answer
# jq, 20 bytes

```
explode|sort|implode

```

try it here
> 1 votes

# Answer
## PowerShell, 27 bytes

```
%{([char[]]$_|sort)-join''}

```
> 1 votes

# Answer
# PHP, 47 bytes

```
$a=str_split($argv[1]);asort($a);echo join($a);

```
> 1 votes

# Answer
# C++, 135 bytes

```
#include <iostream>
#include <string>
#include <algorithm>
main(){std::string s;std::cin>>s;std::sort(s.begin(),s.end());std::cout<<s;}

```

http://coliru.stacked-crooked.com/a/7c9d5c37c2783a23

I payed for what I used :P
> 1 votes

# Answer
# pb (INVALID), 179 bytes

```
^w[B!0]{w[B!0]{>}<t[B]^b[T]vb[0]<[X]<vb[B+1]^>}^w[B!0]{w[B!0]{>}<t[B]b[0]<[X]v[T+2]w[B!0]{>}b[T]<[X]^[Y+2]}vv<w[B!0]{>vw[B=0]{v}w[B!0]{>}<t[B]b[0]^[Y]<[X]w[B!0]{>}b[T]<[X]<b[B-1]}

```

Answers on this site are only considered valid if the language they're written in was available (e.g. there was an interpreter) at the time the question was posted. I didn't finish pb's interpreter until the day after, so this answer is just for fun and is ineligible to win (not that it was going to). That's also why I formatted the header of this answer incorrectly; I don't want to show up in the leaderboard snippet :)

Here's the code with comments, though I'm not sure they'll be helpful to anyone trying to decipher this. I just wrote them to keep my thoughts straight while writing the program, so they're kind of redundant and all over the place.

```
^w[B!0]{                     # while there's something at (0, -1)
    w[B!0]{>}<t[B]^b[T]vb[0] # move last byte of input up by 1
    <[X]<v                   # go to (-1, 0)
    b[B+1]                   # increase by 1
    ^>}                      # restart loop
^w[B!0]{                     # while there's something at (0, -2)
    w[B!0]{>}<t[B]b[0]       # save last byte of input and erase it
    <[X]                     # go to (0, -2)
    v[T+2]                   # go down T+2
    w[B!0]{>}b[T]            # go right until there's nothing there. write T
    <[X]^[Y+2]}              # restart loop
vv<w[B!0]{                   # while there's something at (-1, 0)
    >vw[B=0]{v}              # go down the X=0 column until you find something
    w[B!0]{>}<t[B]b[0]       # save the rightmost thing and erase it
    ^[Y]<[X]w[B!0]{>}b[T]    # add the thing you got to Y=0, to be outputted
    <[X]<b[B-1]}             # decrease (-1, 0) by 1 and repeat loop

```
> 1 votes

# Answer
## Ruby, 23 bytes

```
puts gets.chars.sort*''

```

Splits string by empty regexp, sorts array, joins array. Thanks to @MartinBüttner for 6 bytes :D
> 1 votes

# Answer
# Brainfuck, 140 bytes

Probably not the winning post, but still it was fun :)

```
----------[++++++++++>>,----------]<<[[<<]>>>>[[<<[[-<+>]>>>+<<<]<[->+<]>>>>[-<-<+<->>>>>+<<]>>-[+<<<[-<<+>>]>>>]<<<]<[-<+>>+<]>>>]<<.[-]<<]

```

Explanation:

Program loads whole line and performs bubble sort. After each sort iteration prints and removes last character. It's always the smallest one, because bubble sort guarantees, that after every iteration the lowest value is in the end. Stops after removal of all characters.

```
#read line
----------[++++++++++>>,----------]<<

#MEMORY MODEL OF WHOLE PROGRAM:
# 0|0|?|0|?|0|?|0|?|0|0
#     C   C   C   C
# C-character from input

#iterate if there are characters
[
    #go to first letter
    [<<]>>

    #MEMORY MODEL OF TWO SORTED CHARACTERS:
    # 0|?|0|?|0|?|0|?
    # S L M R F   G
    # S - swap of left during left 0 check
    # L - left character
    # M - middle, difference between left and right
    # R - right character
    # F - flag, set if left was not 0
    # G - next flag, set if left was 0

    #sort two characters if there are at least two
    >>[
        #while right is not 0
        [
            #if left is not 0
            <<[[-<+>]
                #set flag
                >>>+<<<
            #clean up after left's 0 check
            ]<[->+<]>

            #if flag is set, so left is not 0
            >>>[-
                #move 1 from left and right to the middle
                <-<+<->>>
                #set next flag
                >>+<<
            ]

            #if next flag is not set, so left was 0
            >>-[+
                #transfer right to left
                <<<[-<<+>>]>>>
            ]

        #while right is not 0
        <<<]

        #distribute middle to left and right
        <[-<+>>+<]>

    #end if it was the last character
    >>]
    #write and clear last character
    <<.[-]
#end if no more characters
<<]

```
> 1 votes

# Answer
# 05AB1E, 1 byte

```
{

```

Try it online or verify a few more test cases.

Also works in 05AB1E (legacy) or 2sable, which are older versions of 05AB1E.

**Explanation:**

```
{  # Sort the characters of the (implicit) input-string
   # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Idris, 46 bytes

```
main:IO();main=putStr$pack$sort$unpack!getLine

```
> 0 votes

# Answer
# Lua, 79 bytes

```
t=table for c in({...})[1]:gmatch"."do t:insert(c)end t:sort()print(t:concat())

```

Obviously, I could save a few bytes if the string was already in a variable (say, `s`):

```
t=table for c in s:gmatch"."do t:insert(c)end t:sort()print(t:concat())

```
> 0 votes

# Answer
# Bash + coreutils (49 bytes)

Bash was not yet submitted, here is a script (needs to be in a file, as it recurses):

```
[ $1 ]&&(echo ${1::1};$0 ${1:1})|sort|tr -d '\n'

```

I just recursively output head, call the script with the tail of the word in order to split the input word (`$1`) to single chars and then use `sort` util.

However I believe a shorter solution using bash+coreutils exists... Any ideas?
> 0 votes

# Answer
# Lua, 91 bytes

```
a=table t={}for c in arg[1]:gmatch(".") do t[#t+1]=c end a.sort(t)print(a.concat(t))

```

Lua has no string sort function or split/explode function, so it was a struggle
> 0 votes

# Answer
# Clojure, 35 Bytes

```
(print(apply str(sort(read-line))))

```

This will prompt the user for input, sort the characters, rejoin them back into a string and print it.

However, we can make it 3 bytes smaller if we allow the result to include quotations:

```
(pr(apply str(sort(read-line))))

```

`pr` is a debugging tool that prints the object it's given rather than its contents, so instead of showing `hist` in the console, it will show `"hist"`.
> 0 votes

# Answer
# **C++, 101 Bytes**

```
#include<bits/stdc++.h>
using namespace std;main(){string s;cin>>s;sort(s.begin(),s.end());cout<<s;}

```
> 0 votes

# Answer
# Thunno, 2 bytes

```
z:

```

Attempt This Online!

Output as a list of characters. Add the `J` flag if you want a string.
> 0 votes

# Answer
# Thunno 2, 1 byte

Try it online!

Built-in for "sort".
> 0 votes

---
Tags: code-golf, string, sorting, word
---


title: Up go the bits!

text:
# Question
Title: Up go the bits!
Given an integer N perform the following steps: (using 9 as an example).

1. Receive input N. (`9`)
2. Convert N from base10 to base2. (`1001`)
3. Increase every bit by 1. (`2112`)
4. Treat the result as base3 and convert it back to base10. (`68`)
5. Return/Output the result.

---

## Input

May be received in any reasonable number format.
You only need to handle cases where N \> 0.

---

## Output

Either return as a number or string, or print to `stdout`.

---

## Rules

* This is , the shortest code in bytes wins.
* Default loopholes are forbidden.

---

## Test Cases

```
1 -> 2
2 -> 7
5 -> 23
9 -> 68
10 -> 70
20 -> 211
1235 -> 150623
93825 -> 114252161

```

# Answer
# Python 2, 31 bytes

```
f=lambda n:n and 3*f(n/2)+n%2+1

```

Try it online!
> 15 votes

# Answer
# JavaScript (Node.js), 23 bytes

```
f=x=>x&&x%2+1+3*f(x>>1)

```

Try it online!
> 11 votes

# Answer
# Java (JDK 10), 44 bytes

```
long n(long x){return x<1?0:x%2+1+3*n(x/2);}

```

Try it online!
> 9 votes

# Answer
# Jelly, 4 bytes

```
B‘ḅ3

```

Try it online!
> 6 votes

# Answer
# Java 10, ~~81~~ 52 bytes (Base conversion)

```
n->n.toString(n,2).chars().reduce(0,(r,c)->r*3+c-47)

```

Try it online.

-29 bytes thanks to *@Holger*.

**Explanation:**

```
n->{                         // Method with Long as both parameter and return-type
  n.toString(n,2)            //  Convert the input to a Base-2 String
  .chars().reduce(0,(r,c)->  //  Loop over its digits as bytes
    r*3+c-47)                //  Multiply the current result by 3, and add the digit + 1
                             //  (which is equal to increasing each digit by 1,
                             //  and then converting from Base-3 to Base-10)

```

---

# Java 10, ~~171~~ ~~167~~ ~~151~~ ~~150~~ 149 bytes (Sequence)

```
n->{int t=31-n.numberOfLeadingZeros(n);return a(t+1)+b(n-(1<<t));};int a(int n){return--n<1?n+2:3*a(n)+1;}int b(int n){return n<1?0:n+3*b(n/=2)+n*2;}

```

-16 bytes thanks to *@musicman523*, changing `(int)Math.pow(2,t)` to `(1<<t)`.
-1 byte thanks to *@Holger*, changing `(int)(Math.log(n)/Math.log(2))` to `31-n.numberOfLeadingZeros(n)`.

Try it online.

**Explanation:**

```
n->{                         // Method with Integer as both parameter and return-type
  int t=31-n.numberOfLeadingZeros(n);
                             //  2_log(n)
  return a(t+1)              //  Return A060816(2_log(n)+1)
         +b(n-(1<<t));}      //   + A005836(n-2^2_log(n))

// A060816: a(n) = 3*a(n-1) + 1; a(0)=1, a(1)=2
int a(int n){return--n<1?n+2:3*a(n)+1;}

// A005836: a(n+1) = 3*a(floor(n/2)) + n - 2*floor(n/2).
int b(int n){return n<1?0:n+3*b(n/=2)+n*2;}

```

When we look at the sequence:

```
2,  7,8,  22,23,25,26,  67,68,70,71,76,77,79,80,  202,203,205,206,211,212,214,215,229,230,232,233,238,239,241,242, ...

```

We can see multiple subsequences:

```
A053645(n):
0,  0,1,  0,1,2,3,  0,1,2,3,4,5,6,7,  0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,  ...

A060816(A053645(n)):
2,  7,7,  22,22,22,22,  67,67,67,67,67,67,67,67,  202,202,202,202,202,202,202,202,202,202,202,202,202,202,202,  ...

A005836(A053645(n)+1)
0,  0,1,  0,1,3,4,  0,1,3,4,9,10,12,13,  0,1,3,4,9,10,12,13,27,28,30,31,36,37,39,40,  ...

```

So the sequence being asked is:

```
A060816(A053645(n)) + A005836(A053645(n)+1)

```

---

I suck at finding patterns, so I'm proud of what I found above.. Having said that, *@user202729* found a better and shorter approach in Java within a few minutes.. :'(
> 6 votes

# Answer
# 05AB1E, 5 bytes

```
b€>3β

```

Try it online!

```
b       binary
 €>     increment each
   3β   base 3

```

---

# 05AB1E, 5 bytes

```
2в>3β

```

Try it online!
> 6 votes

# Answer
# , 7 bytes

```
3#.1+#:

```

Try it online!

Thanks Galen Ivanov for -4 bytes! I really need to improve my J golfing skill...
> 6 votes

# Answer
# , ~~55~~ 43 bytes

```
function(n)(n%/%2^(x=0:log2(n))%%2+1)%*%3^x

```

Try it online!

Uses the standard base conversion trick in R, increments, and then uses a dot product with powers of `3` to convert back to an integer.

Thanks to @user2390246 for dropping 12 bytes!
> 6 votes

# Answer
# APL (Dyalog), 10 bytes

```
3⊥1+2⊥⍣¯1⊢

```

Try it online!

```
    2⊥⍣¯1  binary
  1+       go guess
3⊥         base 3

```
> 5 votes

# Answer
# Brachylog, 7 bytes

```
ḃ+₁ᵐ~ḃ₃

```

Try it online!

### Explanation

Not that you really need one, but…

```
ḃ            To binary
 +₁ᵐ         Map increment
    ~ḃ₃      From ternary

```
> 4 votes

# Answer
# Ruby, 27 bytes

```
f=->x{x>0?x%2+1+3*f[x/2]:0}

```

Try it online!
> 4 votes

# Answer
# Python 2, ~~56~~ 55 bytes

```
lambda n:int(''.join('12'[c>'0']for c in bin(n)[2:]),3)

```

Try it online!
> 3 votes

# Answer
# Attache, 19 bytes

```
FromBase&3@1&`+@Bin

```

Try it online!

This is a composition of three functions:

* `FromBase&3`
* `1&`+`
* `Bin`

This first converts to binary (`Bin`), increments it (`1&`+`), then converts to ternary (`FromBase&3`).

## Alternatives

Non-pointfree, 21 bytes: `{FromBase[Bin!_+1,3]}`

Without builtins, 57 bytes: `Sum@{_*3^(#_-Iota!_-1)}@{If[_>0,$[_/2|Floor]'(1+_%2),[]]}`
> 3 votes

# Answer
# Retina 0.8.2, 36 bytes

```
.+
$*
+`^(1+)\1
$1;1
^
1
+`1;
;111
1

```

Try it online! Explanation:

```
.+
$*

```

Convert from decimal to unary.

```
+`^(1+)\1
$1;1

```

Repeatedly divmod by 2, and add 1 to the result of the modulo.

```
^
1

```

Add 1 to the first digit too.

```
+`1;
;111

```

Convert from unary-encoded base 3 to unary.

```
1

```

Convert to decimal.
> 3 votes

# Answer
# Japt, 6 bytes

```
¤cÄ n3
¤      // Convert the input to a base-2 string,
 c     // then map over it as charcodes.
  Ä    // For each item, add one to its charcode
       // and when that's done,
    n3 // parse the string as a base 3 number.

```

Takes input as a number, outputs a number.

Try it online!
> 3 votes

# Answer
# MATL, ~~12~~ ~~7~~ 6 bytes

```
BQ3_ZA

```

Try it online!

Saved **5** bytes thanks to Giuseppe and another one thanks to Luis Mendo.

Old 7 byte answer:

```
YBQc3ZA

```

Try it online!

### Explanation:

```
YB        % Convert to binary string
  Q       % Increment each element
   c      % Convert ASCII values to characters
    3     % Push 3
     ZA   % Convert from base 3 to decimal.

```

---

Old one for 12 bytes:

```
BQtz:q3w^!Y*

```

Try it online!

Oh my, that was messy... So is this: \`BQ3GBn:q^!Y\*.

### Explanation:

```
               % Implicit input
B              % Convert to binary vector
 Q             % Increment all numbers
  t            % Duplicate
   z           % Number of element in vector
    :          % Range from 1 to that number
     q         % Decrement to get the range from 0 instead of 1
      3        % Push 3
       w       % Swap order of stack
        ^      % Raise 3 to the power of 0, 1, ...
         !     % Transpose
          Y*   % Matrix multiplication
               % Implicit output

```
> 3 votes

# Answer
# C# (Visual C# Compiler), 128 bytes

```
using System;using System.Linq;i=>{int z=0;return Convert.ToString(i,2).Reverse().Select(a=>(a-47)*(int)Math.Pow(3,z++)).Sum();}

```

Try it online!

I am counting `System` because i use `Convert` and `Math`.
> 3 votes

# Answer
# Python 2, ~~56~~ 54 bytes

```
lambda i:int(''.join(`int(x)+1`for x in bin(i)[2:]),3)

```

Try it online!
> 2 votes

# Answer
## PHP, 84 64 Bytes

Try it online!!

**ORIGINAL Code**

```
function f($n){$b=decbin($n);echo base_convert($b+str_repeat('1',strlen($b)),3,10);}

```

Try it online!!

**Thanks to Cristoph**, less bytes if ran with php -R

```
function f($n){echo base_convert(strtr(decbin($n),10,21),3,10);}

```

**Explanation**

```
function f($n){
$b=decbin($n);                    #Convert the iteger to base 2
echo base_convert(                  #base conversion PHP function
    $b+str_repeat('1',strlen($b)),  #It adds to our base 2 number
    3,                              #a number of the same digits length
    10);                            #with purely '1's
}

```
> 2 votes

# Answer
# C, ~~32~~ 27 bytes

```
n(x){x=x?x%2+1+3*n(x/2):0;}

```

Based on user202729's Java answer. Try it online here. Thanks to Kevin Cruijssen for golfing 5 bytes.

Ungolfed version:

```
n(x) { // recursive function; both argument and return type are implicitly int
    x = // implicit return
    x ? x % 2 + 1 + 3*n(x/2) // if x != 0 return x % 2 + 1 + 3*n(x/2) (recursive call)
    : 0; // else return 0
}

```
> 2 votes

# Answer
# Octave with the communication toolbox, ~~33~~ 32 bytes

```
@(x)(de2bi(x)+1)*3.^(0:log2(x))'

```

Try it online!

Converts the input to a binary vector using `de2bi`, and incrementing all numbers. Does matrix multiplication with a vertical vector of **3** raised to the appropriate powers: `1, 3, 9, ...`, thus getting the sum without an explicit call to `sum`.
> 2 votes

# Answer
# Husk, 5 bytes

```
B3m→ḋ

```

Try it online!

### Explanation

```
B3m→ḋ
    ḋ  Convert to base 2
  m→   Map increment
B3     Convert from base 3

```
> 2 votes

# Answer
# CJam, 8 bytes

```
ri2b:)3b

```

Try it online!

### Explanation

```
ri   e# Read input as an integer
2b   e# Convert to base 2. Gives a list containing 0 and 1
:)   e# Add 1 to each number in that list
3b   e# Convert list from base 3 to decimal. Implicitly display

```
> 2 votes

# Answer
# Brain-Flak, 74 bytes

```
({<>(())<>({<({}[()])><>([{}]())<>})}(<>)){{}((({})()){}{}[{}])([][()])}{}

```

Try it online!

## "Readable" version

```
({<>(())<>
  ({
    <({}[()])>
    <>
    ([{}]())
    <>
  })
}
# At this point we have a inverted binary string on the stack
(<>)
)
{
  {}
  (
    (({})()){}{}[{}]
  )
  ([][()])
}{}

```
> 2 votes

# Answer
# Ruby, 28 bytes

```
f=->x{x>0?x%2+3*f[x>>1]+1:0}

```

black magic, no idea how it works

Try it online!
> 2 votes

# Answer
# Whitespace, 117 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_number][T    T   T   _Retrieve][N
S S S N
_Create_Label_OUTER_LOOP][S N
S _Duplicate][S S S T   S N
_Push_2][T  S T T   _Modulo][S S S T    N
_Push_1][T  S S S _Add][S N
T   _Swap][S S S T  S N
_Push_2][T  S T S _Integer_division][S N
S _Duplicate][N
T   S N
_If_0_jump_to_Label_INNER_LOOP][N
S N
S N
_Jump_to_Label_OUTER_LOOP][N
S S N
_Create_Label_INNER_LOOP][S S S T   T   N
_Push_3][T  S S N
_Multiply][T    S S S _Add][S N
T   _Swap][S N
S _Duplicate][N
T   S T N
_If_0_jump_to_Label_PRINT_AND_EXIT][S N
T   _Swap][N
S N
N
_Jump_to_Label_INNER_LOOP][N
S S T   N
_Create_Label_PRINT_AND_EXIT][S N
T   _Swap][T    N
S T _Output_integer_to_STDOUT]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

### Explanation in pseudo-code:

I first converted the recursive function `int f(int n){return n<1?0:n%2+1+3*f(n/2);}` to its iterative form (in pseudo-code):

```
Integer n = STDIN as integer
Add starting_value 0 to the stack
function OUTER_LOOP:
  while(true){
    Add n%2+1 to the stack
    n = n/2
    if(n == 0):
      Jump to INNER_LOOP
    Else:
      Jump to next iteration OUTER_LOOP

function INNER_LOOP:
  while(true){
    n = 3*n
    n = n + Value at the top of the stack (the ones we calculated with n%2+1)
    Swap top two items
    Check if the top is now 0 (starting value):
      Jump to PRINT_AND_EXIT
    Else:
      Swap top two items back
      Jump to next iteration INNER_LOOP

function PRINT_AND_EXIT:
  Swap top two items back
  Print top to STDOUT as integer
  Exit program with error: Exit not defined

```

And I then implemented this iterative approach in the stack-based language Whitespace, using it's default stack.

### Example runs:

**Input: `1`**

```
Command    Explanation                   Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                        [0]
SNS        Duplicate top (0)             [0,0]
SNS        Duplicate top (0)             [0,0,0]
TNTT       Read STDIN as integer         [0,0]           {0:1}   1
TTT        Retrieve                      [0,1]           {0:1}
NSSSN      Create Label OUTER_LOOP       [0,1]           {0:1}
 SNS       Duplicate top (1)             [0,1,1]         {0:1}
 SSSTSN    Push 2                        [0,1,1,2]       {0:1}
 TSTT      Modulo top two (1%2)          [0,1,1]         {0:1}
 SSSTN     Push 1                        [0,1,1,1]       {0:1}
 TSSS      Add top two (1+1)             [0,1,2]         {0:1}
 SNT       Swap top two                  [0,2,1]         {0:1}
 SSSTSN    Push 2                        [0,2,1,2]       {0:1}
 TSTS      Int-divide top two (1/2)      [0,2,0]         {0:1}
 SNS       Duplicate top (0)             [0,2,0,0]       {0:1}
 NTSN      If 0: Go to Label INNER_LOOP  [0,2,0]         {0:1}
 NSSN      Create Label INNER_LOOP       [0,2,0]         {0:1}
  SSSTTN   Push 3                        [0,2,0,3]       {0:1}
  TSSN     Multiply top two (0*3)        [0,2,0]         {0:1}
  TSSS     Add top two (2+0)             [0,2]           {0:1}
  SNT      Swap top two                  [2,0]           {0:1}
  SNS      Duplicate top (0)             [2,0,0]         {0:1}
  NTSTN    If 0: Jump to Label PRINT     [2,0]           {0:1}
  NSSTN    Create Label PRINT            [2,0]           {0:1}
   SNT     Swap top two                  [0,2]           {0:1}
   TNST    Print top to STDOUT           [0]             {0:1}           2
                                                                                error

```

Try it online (with raw spaces, tabs and new-lines only).
Stops with error: Exit not defined.

**Input: `4`**

```
Command    Explanation                   Stack           Heap    STDIN   STDOUT   STDERR

SSSN       Push 0                        [0]
SNS        Duplicate top (0)             [0,0]
SNS        Duplicate top (0)             [0,0,0]
TNTT       Read STDIN as integer         [0,0]           {0:4}   4
TTT        Retrieve                      [0,4]           {0:4}
NSSSN      Create Label OUTER_LOOP       [0,4]           {0:4}
 SNS       Duplicate top (4)             [0,4,4]         {0:4}
 SSSTSN    Push 2                        [0,4,4,2]       {0:4}
 TSTT      Modulo top two (4%2)          [0,4,0]         {0:4}
 SSSTN     Push 1                        [0,4,0,1]       {0:4}
 TSSS      Add top two (0+1)             [0,4,1]         {0:4}
 SNT       Swap top two                  [0,1,4]         {0:4}
 SSSTSN    Push 2                        [0,1,4,2]       {0:4}
 TSTS      Int-divide top two (4/2)      [0,1,2]         {0:4}
 SNS       Duplicate top (2)             [0,1,2,2]       {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,2]         {0:4}
 NSNSN     Jump to Label OUTER_LOOP      [0,1,2]         {0:4}
 SNS       Duplicate top (2)             [0,1,2,2]       {0:4}
 SSSTSN    Push 2                        [0,1,2,2,2]     {0:4}
 TSTT      Modulo top two (2%2)          [0,1,2,0]       {0:4}
 SSSTN     Push 1                        [0,1,2,0,1]     {0:4}
 TSSS      Add top two (0+1)             [0,1,2,1]       {0:4}
 SNT       Swap top two                  [0,1,1,2]       {0:4}
 SSSTSN    Push 2                        [0,1,1,2,2]     {0:4}
 TSTS      Int-divide top two (2/2)      [0,1,1,1]       {0:4}
 SNS       Duplicate top (1)             [0,1,1,1,1]     {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,1,1]       {0:4}
 NSNSN     Jump to Label OUTER_LOOP      [0,1,1,1]       {0:4}
 SNS       Duplicate top (1)             [0,1,1,1,1]     {0:4}
 SSSTSN    Push 2                        [0,1,1,1,1,2]   {0:4}
 TSTT      Modulo top two (1%2)          [0,1,1,1,1]     {0:4}
 SSSTN     Push 1                        [0,1,1,1,1,1]   {0:4}
 TSSS      Add top two (1+1)             [0,1,1,1,2]     {0:4}
 SNT       Swap top two                  [0,1,1,2,1]     {0:4}
 SSSTSN    Push 2                        [0,1,1,2,1,2]   {0:4}
 TSTS      Int-divide top two (1/2)      [0,1,1,2,0]     {0:4}
 SNS       Duplicate top (0)             [0,1,1,2,0,0]   {0:4}
 NTSN      If 0: Go to Label INNER_LOOP  [0,1,1,2,0]     {0:4}
 NSSN      Create Label INNER_LOOP       [0,1,1,2,0]     {0:4}
  SSSTTN   Push 3                        [0,1,1,2,0,3]   {0:4}
  TSSN     Multiply top two (0*3)        [0,1,1,2,0]     {0:4}
  TSSS     Add top two (2+0)             [0,1,1,2]       {0:4}
  SNT      Swap top two                  [0,1,2,1]       {0:4}
  SNS      Duplicate top (1)             [0,1,2,1,1]     {0:4}
  NTSTN    If 0: Jump to Label PRINT     [0,1,2,1]       {0:4}
  SNT      Swap top two                  [0,1,1,2]       {0:4}
  NSNN     Jump to Label INNER_LOOP      [0,1,1,2]       {0:4}
  SSSTTN   Push 3                        [0,1,1,2,3]     {0:4}
  TSSN     Multiply top two (2*3)        [0,1,1,6]       {0:4}
  TSSS     Add top two (1+6)             [0,1,7]         {0:4}
  SNT      Swap top two                  [0,7,1]         {0:4}
  SNS      Duplicate top (1)             [0,7,1,1]       {0:4}
  NTSTN    If 0: Jump to Label PRINT     [0,7,1]         {0:4}
  SNT      Swap top two                  [0,1,7]         {0:4}
  NSNN     Jump to Label INNER_LOOP      [0,1,7]         {0:4}
  SSSTTN   Push 3                        [0,1,7,3]       {0:4}
  TSSN     Multiply top two (7*3)        [0,1,21]        {0:4}
  TSSS     Add top two (1+21)            [0,22]          {0:4}
  SNT      Swap top two                  [22,0]          {0:4}
  SNS      Duplicate top (0)             [22,0,0]        {0:4}
  NTSTN    If 0: Jump to Label PRINT     [22,0]          {0:4}
  NSSTN    Create Label PRINT            [22,0]          {0:4}
   SNT     Swap top two                  [0,22]          {0:4}
   TNST    Print top to STDOUT           [0]             {0:4}           22
                                                                                error

```

Try it online (with raw spaces, tabs and new-lines only).
Stops with error: Exit not defined.
> 2 votes

# Answer
# Vyxal, 4 bytes

```
b›3β

```

Try it Online!

```
b    # Binary
 ›   # Increment
  3β # From base 3

```
> 2 votes

# Answer
# Add++, 14 bytes

```
L,BBu1€+B]3$Bb

```

Try it online!
> 1 votes

# Answer
# Japt, 7 bytes

```
¤£°XÃn3

```

Try it here
> 1 votes

# Answer
# Stax, 7 bytes

```
É¥ê4¼⌐○

```

Run and debug it

This one is pretty straightforward. After unpacking, and commenting, the program looks like this.

```
:B  Convert to bits
{^m Increment each
3|b Base-3 convert

```
> 1 votes

# Answer
# Haskell, 32 bytes

```
f 0=0
f a=1+mod a 2+3*f(div a 2)

```

Try it online!
> 1 votes

# Answer
# Pyth, 8

```
ihMjQ2 3

```

How to eliminate the space and make the `Q` implicit?

Pyth online.
> 1 votes

# Answer
# Perl 5, 36 bytes

```
$\+=(1+$_%2)*3**$b++,$_>>=1while$_}{

```

Try it online!
> 1 votes

# Answer
# dc, 66 bytes

```
[2~rd0<B]dsBxz1-si[1+z:tz0<T]dsTx0dsj[ljd1+dsj;tr3r^*+ljli>M]dsMxp

```

Try it online!

`[2~rd0<B]dsBx` is a macro that uses `dc`'s quotient/remainder integer division, `~` to continuously break divide by two, breaking *n* down to individual binary bits on the stack. It will always leave one extra zero, so we subtract one from the stack depth and store this total length in `i` with `z1-si`.

`[1+z:tz0<T]dsTx` is a macro that adds one to whatever is on the stack, and then pops that value, storing it at index(stack depth) in array `t`. This basically means that if we started with the binary `1101`, `t` now holds `2, 1, 2, 2`, assuming 1-indexing. `0dsj` puts a zero on the stack so we don't get a stack empty error when we do our first addition, and it stores a zero in register `j` as well.

`[ljd1+dsj;tr3r^*+ljli>M]dsMx` is, unfortunately, a lot of counter nonsense. We need register `j` for two things - pull element `(j+1)` from array `t`, and multiply it by `3^j`. We start macro `M` by putting `j` on the stack and duplicating it. We increment the new copy, duplicate it, and store it back into `j`. With the copy of `(j+1)` we left behind, we pull from array `t`. Swap so that our original `j` is at the top of the stack, do the necessary base-three math with `3r^*`, add this 'bit' to our total, and then compare `j` with `i` to see if we still have more 'bits' to do. At the very end, we `p`rint.
> 1 votes

# Answer
# Excel, 54 bytes

```
=DECIMAL(SUBSTITUTE(SUBSTITUTE(BASE(A1,2),1,2),0,1),3)

```

A fairly straightforward translation of the problem. Takes input from A1. I tried some cuter things with bit math like

```
=SUM(IF(ROW(1:31)<LOG(A1,2)+1,POWER(3,ROW(1:31)-1)*(1+MOD(BITRSHIFT(A1, ROW(1:31)-1),2))))

```

because nesting SUBSTITUTE always feels wasteful, but couldn't get nearly as short.
> 1 votes

# Answer
# Jstx, 7 bytes

```
£?☺å♥£F

```

Try it online!

Explanation

```
£? # Push the first stack value in binary.
☺  # Push literal 1
å  # Push the second stack value with all characters arithmetically shifted by the first stack value.
♥  # Push literal 3
£F # Push the second stack value in base first stack value converted to decimal.

```
> 1 votes

# Answer
# x86, 26 bytes

Rewrite of the recursive formula as a tail-recursive stack function, since function calls are expensive. Uses \__fastcall convention (input in `ecx`, output in `eax`).

~~The `cmp %esp,%ebp`/`je sum1` branch is done to prevent an extra multiplication of 3 from occurring. It might save bytes to avoid this branch.~~ Reordering the multiplication makes this unnecessary and saves 4 bytes.

```
.section .text
.globl main
main:
        mov     $10, %ecx

start:
        mov     %esp, %ebp          # Save sp
build:
        mov     %ecx, %eax
        and     $1, %eax
        inc     %eax                # n%2 + 1
        push    %eax                # push n%2 + 1
        sar     %ecx                # n >>= 1
        jnz     build               # do while (n)

        xor     %eax, %eax          # sum = 0
sum0:
        lea     (%eax,%eax,2),%eax  # sum *= 3
        pop     %ebx
        add     %ebx, %eax          # pop stack, add to sum
        cmp     %esp, %ebp
        jnz     sum0                # do while stack non-empty

        ret

```

Hexdump:

```
00000039  89 e5 89 c8 83 e0 01 40  50 d1 f9 75 f5 31 c0 8d  |.......@P..u.1..|
00000049  04 40 5b 01 d8 39 e5 75  f6 c3                    |.@[..9.u..|

```

---

Assembly-friendly python:

```
stack = []
while n:
    stack.append(n%2 + 1)
    n //= 2

while stack:
    s *= 3
    s += stack.pop()

```
> 1 votes

# Answer
# Julia 0.6, 34 bytes

```
x->parse(Int,map(x->x+1,bin(x)),3)

```

Try it online!

Tho it seems like this is the cool way

# Julia 0.6, 25 bytes

```
f(n)=n<1?0:n%2+1+3f(n÷2)

```

Try it online!
> 1 votes

# Answer
# Zsh, 37 bytes

```
a=3#$[[##2]$1];echo $[a+${a//[01]/1}]

```

Try it online!

* `$[...]` is another (deprecated?) form of `$(( ))`
* `[#n]` in arithmetic expansion sets the output base but includes the base in output (so you get `2#1001`), `[##n]` omits the base in output: `1001`.
* `n#` in arithmetic expansion sets the input base
* `${var//pat/rep}` replaces all matches of `pat` with `rep`.
> 1 votes

# Answer
# AWK, 43 bytes

```
func n(x){return x<1?0:x%2+1+3*n(int(x/2))}

```

Try it online!

I discovered that `AWK` has `rshift` and `lshift` functions. They use more bytes than just doing a divide and cast, but might be useful sometime. :)
> 0 votes

# Answer
# Bash \+ GNU utilities, 28

```
dc -e?2op|tr 01 12|dc -e3i?p

```

Input read from STDIN.

Try it online!
> 0 votes

# Answer
# Pari/GP, 25 bytes

```
f(n)=if(n,n%2+1+3*f(n\2))

```

Try it online!
> 0 votes

# Answer
# brainfuck, 50 bytes

```
+<,[[>-]++>[<]<[>+[<]<]>>-]>[>]<-<<[>[-<+++>]<<]>.

```

Try it online!

Input and output as code points, and assumes arbitrary size cells otherwise it can't get past n=31.
> 0 votes

# Answer
# Go, 54 bytes

```
func f(n int)(o int){if n>0{o=n%2+1+3*f(n>>1)};return}

```

Base solution is the same as the one that everyone else uses.

Try it online!
> 0 votes

# Answer
# Thunno 2, 4 bytes

```
ḃ⁺3b

```

Try it online!

#### Explanation

```
ḃ⁺3b  # Implicit input
ḃ     # Convert to binary
 ⁺    # Increment each
  3b  # Convert from base-3
      # Implicit output

```
> 0 votes

---
Tags: code-golf, number, base-conversion
---