# 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


# 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
Commented Apr 10, 2018 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 Commented Apr 11, 2018 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? Commented Apr 9, 2018 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) Commented Apr 9, 2018 at 13:23
• @mbomb007 No. 1>>1=0 while 1/2=0.5
– l4m2
Commented Apr 9, 2018 at 13:24
• @mbomb007 ... Python? Commented Apr 9, 2018 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. Commented Apr 9, 2018 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? Commented Apr 9, 2018 at 12:57
• No, precedence rules. Commented Apr 9, 2018 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.. >.> :'( Commented Apr 9, 2018 at 13:00
• @KevinCruijssen To be fair with you ... Commented Apr 9, 2018 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.
Commented Apr 9, 2018 at 14:01
• @Adám Technically that's From-base, but yes, this is trivial in most, if not all, golfing languages. Commented Apr 9, 2018 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 Commented Apr 9, 2018 at 12:56
• Also thanks for the template, I need something to learn about : 0. Commented Apr 9, 2018 at 14:04
• The template is not mine, I forgot who's its author. Commented Apr 9, 2018 at 14:20
• That would be me :) Commented Apr 9, 2018 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 Commented Apr 10, 2018 at 9:25
• @user2390246 of course, thank you. Commented Apr 10, 2018 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. Commented Apr 10, 2018 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. Commented Apr 9, 2018 at 12:50
• BTW why long and not int? Commented Apr 9, 2018 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) Commented Apr 9, 2018 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. Commented Apr 11, 2018 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) Commented Apr 11, 2018 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. Commented Apr 10, 2018 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(); Commented Apr 11, 2018 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;} Commented Apr 9, 2018 at 13:52 • @KevinCruijssen Nice. Thanks! Commented Apr 9, 2018 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! Commented Apr 11, 2018 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) Commented Apr 11, 2018 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

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 }  • Here is when i see i have a loooogn way to go at programming....had no idea of the existence of strtr Commented Apr 9, 2018 at 13:56 • Will do!!, sorry <?="Will do!!" Commented Apr 9, 2018 at 14:20 # 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  • I kinda like the :) .. Commented Apr 9, 2018 at 15:34 # 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 Commented Apr 10, 2018 at 19:34 # 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. • At this point, why not write assembly? Also I have a slightly simpler iterative method in my answer codegolf.stackexchange.com/a/161833/17360 – qwr Commented Apr 10, 2018 at 19:04 • I've simplified my python pseudocode further. – qwr Commented Apr 10, 2018 at 19:46 • @qwr Your Python code is almost the same as the displayed Java code. Java is just more verbose and error-prone. The only difference is that my Java code is a nested while-loop, and yours is separated. I could do that as well in Java, but since it's nested in Whitespace I chose to write it as such in the Java pseudo-code as well. Also, Whitespace doesn't have any way to know the number of items left on the stack, which is why I push the 0 at the start, and in the INNER_LOOP part of the code do: swap, check if 0, swap back. Nice Assembly answer, though. So I've +1-ed it. :) Commented Apr 10, 2018 at 20:30 • I still think you can get rid of the n < 1 check by pushing values until n is 0 and then popping them until you hit your boundary value (0). The stack depth doesn't need to be stored explicitly and there shouldn't even need to be swapping (if you mean swapping the top two values like in lisp) – qwr Commented Apr 10, 2018 at 20:40 • @qwr "I still think you can get rid of the n < 1 check by pushing values until n is 0" Umm.. checking if n < 1 (or n == 0) IS pushing values until n is 0.. Or am I misinterpreting something here.. :S "The stack depth doesn't need to be stored explicitly" In Java it does, otherwise I can't create the array. I could have used a java.util.Stack instead, but I just used an array to make it less verbose. In Whitespace the stack is of undefined size. Commented Apr 11, 2018 at 6:42 # Brain-Flak, 74 bytes ({<>(())<>({<({}[()])><>([{}]())<>})}(<>)){{}((({})()){}{}[{}])([][()])}{}  Try it online! ## "Readable" version ({<>(())<> ({ <({}[()])> <> ([{}]()) <> }) } # At this point we have a inverted binary string on the stack (<>) ) { {} ( (({})()){}{}[{}] ) ([][()]) }{}  • -2 bytes – Jo King Commented Apr 10, 2018 at 0:00 # Vyxal, 4 bytes b›3β  Try it Online! b # Binary › # Increment 3β # From base 3  # Add++, 14 bytes L,BBu1€+B]3$Bb


Try it online!

# Japt, 7 bytes

¤£°XÃn3


Try it here

f 0=0