| Bytes | Lang | Time | Link |
|---|---|---|---|
| 004 | Thunno 2 | 230721T065717Z | The Thon |
| 004 | Vyxal | 210915T101035Z | emanresu |
| 026 | x86 | 180410T185800Z | qwr |
| 074 | BrainFlak | 180409T202210Z | MegaTom |
| 054 | Go | 180411T114413Z | Kristoff |
| 052 | Java 10 | 180409T124514Z | Kevin Cr |
| 117 | Whitespace | 180410T133756Z | Kevin Cr |
| 037 | Zsh | 180411T060159Z | muru |
| 034 | Julia 0.6 | 180410T191938Z | gggg |
| 007 | Jstx | 180410T160436Z | Quantum6 |
| 005 | 05AB1E | 180409T124820Z | Uriel |
| 043 | R | 180409T131043Z | Giuseppe |
| 028 | Ruby | 180410T083339Z | anna328p |
| 050 | brainfuck | 180410T002511Z | Jo King |
| 054 | Excel | 180409T232857Z | Sophia L |
| 025 | Pari/GP | 180409T182750Z | alephalp |
| 066 | dc | 180409T174700Z | brhfl |
| 007 | Stax | 180409T135551Z | recursiv |
| 008 | Pyth | 180409T151404Z | Digital |
| 036 | Perl 5 | 180409T160453Z | Xcali |
| 128 | C# Visual C# Compiler | 180409T155754Z | Hyarus |
| 006 | MATL | 180409T150007Z | Stewie G |
| 008 | CJam | 180409T152657Z | Luis Men |
| 010 | APL Dyalog | 180409T124646Z | Uriel |
| 028 | Bash + GNU utilities | 180409T151659Z | Digital |
| 064 | PHP | 180409T132919Z | Francisc |
| 043 | AWK | 180409T145328Z | Robert B |
| 032 | Octave with the communication toolbox | 180409T134100Z | Stewie G |
| 005 | Husk | 180409T143622Z | Fyr |
| 006 | Japt | 180409T142950Z | Etheryte |
| 032 | Haskell | 180409T142420Z | Angs |
| 036 | Retina 0.8.2 | 180409T141116Z | Neil |
| 007 | J | 180409T124856Z | DELETE_M |
| 027 | C | 180409T133834Z | O.O.Bala |
| 007 | Japt | 180409T134439Z | Shaggy |
| 019 | Attache | 180409T133351Z | Conor O& |
| 023 | JavaScript Node.js | 180409T124532Z | l4m2 |
| 027 | Ruby | 180409T132426Z | Kirill L |
| 054 | Python 2 | 180409T130207Z | ElPedro |
| 031 | Python 2 | 180409T130603Z | Dennis |
| 055 | Python 2 | 180409T130328Z | TFeld |
| 044 | Java JDK 10 | 180409T125622Z | DELETE_M |
| 014 | Add++ | 180409T125329Z | caird co |
| 007 | Brachylog | 180409T125114Z | Fatalize |
| 004 | Jelly | 180409T124447Z | Erik the |
Thunno 2, 4 bytes
ḃ⁺3b
Explanation
ḃ⁺3b # Implicit input
ḃ # Convert to binary
⁺ # Increment each
3b # Convert from base-3
# Implicit output
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 Reordering the multiplication makes this unnecessary and saves 4 bytes.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.
.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()
Brain-Flak, 74 bytes
({<>(())<>({<({}[()])><>([{}]())<>})}(<>)){{}((({})()){}{}[{}])([][()])}{}
"Readable" version
({<>(())<>
({
<({}[()])>
<>
([{}]())
<>
})
}
# At this point we have a inverted binary string on the stack
(<>)
)
{
{}
(
(({})()){}{}[{}]
)
([][()])
}{}
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.
Java 10, 81 52 bytes (Base conversion)
n->n.toString(n,2).chars().reduce(0,(r,c)->r*3+c-47)
-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).
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.. :'(
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.
Zsh, 37 bytes
a=3#$[[##2]$1];echo $[a+${a//[01]/1}]
$[...]is another (deprecated?) form of$(( ))[#n]in arithmetic expansion sets the output base but includes the base in output (so you get2#1001),[##n]omits the base in output:1001.n#in arithmetic expansion sets the input base${var//pat/rep}replaces all matches ofpatwithrep.
Julia 0.6, 34 bytes
x->parse(Int,map(x->x+1,bin(x)),3)
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)
Jstx, 7 bytes
£?☺å♥£F
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.
R, 55 43 bytes
function(n)(n%/%2^(x=0:log2(n))%%2+1)%*%3^x
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!
brainfuck, 50 bytes
+<,[[>-]++>[<]<[>+[<]<]>>-]>[>]<-<<[>[-<+++>]<<]>.
Input and output as code points, and assumes arbitrary size cells otherwise it can't get past n=31.
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.
dc, 66 bytes
[2~rd0<B]dsBxz1-si[1+z:tz0<T]dsTx0dsj[ljd1+dsj;tr3r^*+ljli>M]dsMxp
[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.
Stax, 7 bytes
É¥ê4¼⌐○
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
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();}
I am counting System because i use Convert and Math.
MATL, 12 7 6 bytes
BQ3_ZA
Saved 5 bytes thanks to Giuseppe and another one thanks to Luis Mendo.
Old 7 byte answer:
YBQc3ZA
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*
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
CJam, 8 bytes
ri2b:)3b
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
PHP, 84 64 Bytes
ORIGINAL Code
function f($n){$b=decbin($n);echo base_convert($b+str_repeat('1',strlen($b)),3,10);}
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
}
AWK, 43 bytes
func n(x){return x<1?0:x%2+1+3*n(int(x/2))}
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. :)
Octave with the communication toolbox, 33 32 bytes
@(x)(de2bi(x)+1)*3.^(0:log2(x))'
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.
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.
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.
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
}
Attache, 19 bytes
FromBase&3@1&`+@Bin
This is a composition of three functions:
FromBase&31&`+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),[]]}
Brachylog, 7 bytes
ḃ+₁ᵐ~ḃ₃
Explanation
Not that you really need one, but…
ḃ To binary
+₁ᵐ Map increment
~ḃ₃ From ternary