# 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


# 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


# 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 print.

# 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.

• Try +REPT(1,LEN(BASE(A1,2))) instead of nesting SUBSTITUTE? – Chronocidal Apr 10 '18 at 13:15
• Or, even +REPT(1,1+LOG(A2,2)), since REPT ignores the non-integer portion of the number – Chronocidal Apr 10 '18 at 13:30
• It's a good suggestion but I couldn't make it work for the range covered by the test cases. The complete solution there is =DECIMAL(REPT(1,1+LOG(A1,2))+BASE(A1,2),3) which is only 43 bytes! But unfortunately it gets the wrong answer even for the 93825 test case, due to rounding error as it passes through a representation as a double, and I can't figure out how to work around that. – Sophia Lechner Apr 11 '18 at 0:06

# 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!

• the left shift gets binary digits right to left, and x%2+1 increases the binary value according to the spec. – qwr Apr 10 '18 at 19:34

# 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.


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


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

# Bash + GNU utilities, 28

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


Try it online!

# Pari/GP, 25 bytes

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


Try it online!

# 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.

# 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!

# 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.

# 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!