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

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 – Francisco Hahn Apr 9 '18 at 13:56 • Will do!!, sorry <?="Will do!!" – Francisco Hahn Apr 9 '18 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 :) .. – Ian H. Apr 9 '18 at 15: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  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: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  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: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 Apr 10 '18 at 19:04 • I've simplified my python pseudocode further. – qwr Apr 10 '18 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. :) – Kevin Cruijssen Apr 10 '18 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 Apr 10 '18 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. – Kevin Cruijssen Apr 11 '18 at 6:42 # Brain-Flak, 74 bytes ({<>(())<>({<({}[()])><>([{}]())<>})}(<>)){{}((({})()){}{}[{}])([][()])}{}  Try it online! ## "Readable" version ({<>(())<> ({ <({}[()])> <> ([{}]()) <> }) } # At this point we have a inverted binary string on the stack (<>) ) { {} ( (({})()){}{}[{}] ) ([][()]) }{}  # Add++, 14 bytes L,BBu1€+B]3$Bb


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