# Up go the bits!

Given an integer N perform the following steps: (using 9 as an example).

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

# Python 2, 31 bytes

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

Try it online!

• Could you explain how this works? – user79760 Apr 10 '18 at 18:26
• +n%2+1 adds the rightmost binary bit plus 1 to the return value, n/2 right-shifts n by 1 binary bit, 3*f(n/2) recursively adds 3 times this computation on those right-shifted bits, and n and ends the recursion when n is 0 – Noodle9 Apr 11 '18 at 11:52

# JavaScript (Node.js), 23 bytes

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

Try it online!

• x>>1 is the same as x/2 isn't it? – mbomb007 Apr 9 '18 at 13:16
• @mbomb007 I thought and suggested the same just yet, but apparently it becomes Infinity in JS.. Try it online. (You might want to add a TIO-link to you answer, I4m2) – Kevin Cruijssen Apr 9 '18 at 13:23
• @mbomb007 No. 1>>1=0 while 1/2=0.5 – l4m2 Apr 9 '18 at 13:24
• @mbomb007 ... Python? – user202729 Apr 9 '18 at 14:11
• Yeah. Look at the Python answer. That's the reason n/2 works in that one, and the reason I suggested it here. – mbomb007 Apr 9 '18 at 16:16

# Java (JDK 10), 44 bytes

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

Try it online!

• Maybe -~ will help? – user202729 Apr 9 '18 at 12:57
• No, precedence rules. – user202729 Apr 9 '18 at 12:58
• Same question to you: why long? :) And here I thought my sequence approach was smart.. You blew it out of the park in less than 5 minutes.. >.> :'( – Kevin Cruijssen Apr 9 '18 at 13:00
• @KevinCruijssen To be fair with you ... – user202729 Apr 9 '18 at 13:59

# Jelly, 4 bytes

B‘ḅ3

Try it online!

• Binary, Increment, To-base, 3. That's really all that needs to be said. – Adám Apr 9 '18 at 14:01
• @Adám Technically that's From-base, but yes, this is trivial in most, if not all, golfing languages. – Erik the Outgolfer Apr 9 '18 at 16:39

# J, 7 bytes

3#.1+#:

Try it online!

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

• 7 bytes: 3#.1+#: TIO – Galen Ivanov Apr 9 '18 at 12:56
• Also thanks for the template, I need something to learn about : 0. – user202729 Apr 9 '18 at 14:04
• The template is not mine, I forgot who's its author. – Galen Ivanov Apr 9 '18 at 14:20
• That would be me :) – Conor O'Brien Apr 9 '18 at 14:30

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

• Because the conversion to binary is not the final output, the order of the digits doesn't matter. So instead of floor(log(n)):0 you can do 0:log(n) and save some bytes: 43 bytes – user2390246 Apr 10 '18 at 9:25
• @user2390246 of course, thank you. – Giuseppe Apr 10 '18 at 11:55

# 05AB1E, 5 bytes

b€>3β

Try it online!

b       binary
€>     increment each
3β   base 3

# 05AB1E, 5 bytes

2в>3β

Try it online!

• S works for too. – Magic Octopus Urn Apr 10 '18 at 1:17

# 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, 171167151150 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
//  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.. :'(

• Re n.toString(n,2).getBytes() ... I think manual conversion may be shorter. – user202729 Apr 9 '18 at 12:50
• BTW why long and not int? – user202729 Apr 9 '18 at 12:54
• I think in the sequence version you can change out (int)Math.pow(2,t) for 1<<t...and then inline that expression and drop the variable i (152 bytes) – musicman523 Apr 9 '18 at 19:15
• In real life, I’d use 31-Integer.numberOfLeadingZeros(n) instead of (int)(Math.log(n)/Math.log(2)), but it’s not shorter. Unless you use import static in the header, which might stretch the rules too far. – Holger Apr 11 '18 at 8:36
• I just tried to convert your first variant’s loop to a stream solution, with success: n -> n.toString(n,2).chars().reduce(0,(r,c)->r*3+c-47) – Holger Apr 11 '18 at 8:49

# APL (Dyalog), 10 bytes

3⊥1+2⊥⍣¯1⊢

Try it online!

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

# Brachylog, 7 bytes

ḃ+₁ᵐ~ḃ₃

Try it online!

### Explanation

Not that you really need one, but…

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

# Ruby, 27 bytes

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

Try it online!

# Python 2, 56 55 bytes

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

Try it online!

# 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),[]]} # 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. # 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! • Damnit! Why didn't I think of that? Nicely done. – Shaggy Apr 10 '18 at 8:11 # MATL, 127 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 # 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. • Select gives you the index as optional parameter. So you could get rid of your z variable. Also in the expression body you could get rid of the {, } and return statements. So something like this n=>Convert.ToString(n,2).Reverse().Select((x,i)=>(x-47)*Math.Pow(3,i)).Sum(); – NtFreX Apr 11 '18 at 9:38 # Python 2, 56 54 bytes lambda i:int(''.join(int(x)+1for x in bin(i)[2:]),3) Try it online! # 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 } • You can save 5 bytes by replacing the return with x= and reversing the ternary so the ! is no longer necessary: n(x){x=x?x%2+1+3*n(x/2):0;} – Kevin Cruijssen Apr 9 '18 at 13:52 • @KevinCruijssen Nice. Thanks! – O.O.Balance Apr 9 '18 at 13:59 # Husk, 5 bytes B3m→ḋ Try it online! ### Explanation B3m→ḋ ḋ Convert to base 2 m→ Map increment B3 Convert from base 3 # 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. • While this is extremely clever, you can also do this for 32 bytes: Try it online! – Sanchises Apr 11 '18 at 9:54 • And with MATLAB you may even do @(x)base2dec(de2bi(x)+49,3) for 27 (a rare occasion where MATLAB is more lenient than Octave) – Sanchises Apr 11 '18 at 9:55 ## 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

Try it online!

# Japt, 7 bytes

¤£°XÃn3

Try it here

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

Try it online!

# Perl 5, 36 bytes

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

Try it online!

# Pyth, 8

ihMjQ2 3

How to eliminate the space and make the Q implicit?

• I believe this is actually 8 bytes – hakr14 Apr 9 '18 at 16:15
• @hakr14 Yes, you're right – Digital Trauma Apr 9 '18 at 16:19
• How to eliminate the space and make the Q implicit? I don't think you can. – Erik the Outgolfer Apr 9 '18 at 19:31