Given a positive integer n write some code to take its prime factorization and replace all of its factors of 2 with 3.

For example

12 = 2 * 2 * 3 -> 3 * 3 * 3 = 27

This is so the goal is to minimize the byte count of your answer.

Test cases

1 -> 1
2 -> 3
3 -> 3
4 -> 9
5 -> 5
6 -> 9
7 -> 7
8 -> 27
9 -> 9
10 -> 15
11 -> 11
12 -> 27
13 -> 13
14 -> 21
15 -> 15
16 -> 81
17 -> 17
18 -> 27
19 -> 19
20 -> 45
21 -> 21
22 -> 33
23 -> 23
24 -> 81
25 -> 25
26 -> 39
27 -> 27
28 -> 63
29 -> 29
share|improve this question

24 Answers 24

Fractran, 3 bytes

3/2

Fractran literally only has one builtin, but it happens to do exactly what this task is asking for. (It's also Turing-complete, by itself.)

The language doesn't really have a standardised syntax or interpreter. This interpreter (in a comment to a blog post – it's a very simple language) will accept the syntax shown here. (There are other Fractran interpreters with other syntaxes, e.g. some would write this program as 3 2, or even using 3 and 2 as command line arguments, which would lead to a score of 0+3 bytes. I doubt it's possible to do better than 3 in a pre-existing interpreter, though.)

Explanation

3/2
 /   Replace a factor of
  2  2
3    with 3
     {implicit: repeat until no more replacements are possible}
share|improve this answer
5  
Talk about right tool for the job.. – Kevin Cruijssen 17 hours ago
7  
"Don't upvote trivial solutions that only uses a simple builtin." Well, in this case: Knowing that there's a language "Fractran" that has a single builtin that solves this specific task is by itself impressive. – Stewie Griffin 15 hours ago
    
Does this do primer factorization? – Pandya 12 hours ago
    
@Pandya: Some Fractran implementations use prime factorization internally (as an optimization), but they don't have to; the language operates on factors, not prime factors. (It just happens that 2 and 3 are prime.) – ais523 11 hours ago

Python 2, 28 bytes

f=lambda n:n%2*n or 3*f(n/2)

Try it online!

Recursively divide the number by 2 and multiplies the result by 3, as long as the number is even. Odd numbers return themselves.

32 byte alt:

lambda n:n*(n&-n)**0.58496250072

Try it online. Has some float error. The constant is log_2(3)-1.

Uses (n&-n) to find the greatest power-of-2 factor of n, the converts 3**k to 2**k by raising it to the power of log_2(3)-1.

share|improve this answer
    
Nice this is my solution exactly! – Wheat Wizard yesterday
    
@WheatWizard Me as well, aha! – Yam B 19 hours ago

05AB1E, 4 bytes

Ò1~P

Try it online!

How it works

Ò     Compute the prime factorization of the input.
 1~   Perform bitwise OR with 1, making the only even prime (2) odd (3).
   P  Take the product of the result.
share|improve this answer
    
This beats Jelly by 1 byte simply because prime factorization is only one byte here :( – Hyper Neutrino yesterday
3  
@HyperNeutrino: I noticed that too: "why is Dennis using 05AB1E? Oh, identical algorithm, shorter builtin names". So I had to go and find a language where I could do it in even fewer bytes, via the use of an even more appropriate set of builtins. – ais523 yesterday

Haskell, 24 23 bytes

until odd$(*3).(`div`2)

The divide by two and multiply by 3 until odd trick in Haskell.

Try it online!

Alternative with a lambda instead of a pointfree function and with the same byte count:

odd`until`\x->div(x*3)2

Edit: @ais523 saved a byte in the original version and @Ørjan Johansen one in the alternative version, so both version have still the same length. Thanks!

share|improve this answer
3  
The lambda version can be shortened to odd`until`\x->div(x*3)2. – Ørjan Johansen yesterday
2  
The original version can also be shortened one byte via using $ to replace a pair of parentheses: Try it online! – ais523 20 hours ago
    
@ØrjanJohansen: ah, nice! Thanks. – nimi 19 hours ago
    
@ais523: How could I have missed that one, Thanks! – nimi 19 hours ago
2  
I think you forgot to remove a pair of () from the lambda version – CAD97 17 hours ago

Brain-Flak, 76 bytes

{{({}[()]<([({})]()<({}{})>)>)}{}([{}]()){{}((({})){}{})<>}<>}<>({}({}){}())

Try it online!

Explanation

This program works by dividing the number by two and tripling until it gets a remainder of one from the division. Then it stops looping and doubles and adds one to the final number.

More detailed explanation coming soon...

share|improve this answer

JavaScript (ES6), 19 bytes

f=x=>x%2?x:f(x*1.5)

While the input is divisible by two, multiplies it by 1.5, which is equivalent to dividing by 2 and multiplying by 3.

share|improve this answer
1  
x*3/2 has the same bytecount – Leaky Nun 20 hours ago
1  
f= is usally not needed for js. – Christoph 18 hours ago
    
@Christoph Thanks, but in order to call itself f(x*1.5) it needs to have the name f, hence why the f= is included. – ETHproductions 12 hours ago
    
@ETHproductions Uhm ... of course ! I missed that. Is there any meta on what the calling code exactly looks like? – Christoph 12 hours ago
1  
@Christoph Here is the relevant meta post. – ETHproductions 9 hours ago

MATL, 7, 6 bytes

Yf1Z|p

Try it online!

1 byte saved thanks to Dennis's genius observation


The best way to explain this is to show the stack at various points.

Yf  % Prime factors

[2 2 2 3]

1Z| % Bitwise OR with 1

[3 3 3 3]

p   % Product

81

Alternate solution:

Yfto~+p
share|improve this answer
    
Nice! I had Yf3H$X>p for 8 bytes – Luis Mendo yesterday

05AB1E, 6 5 bytes

Saved a byte thanks to Adnan.

ÒDÈ+P

Try it online!

Explanation

Ò       # push list of prime factors of input
 D      # duplicate
  È     # check each factor for evenness (1 if true, else 0)
   +    # add list of factors and list of comparison results
    P   # product
share|improve this answer
1  
ÒDÈ+P should save a byte – Adnan yesterday
    
@Adnan: Thanks! – Emigna 18 hours ago

Alice, 9 bytes

2/S 3
o@i

Try it online!

Alice has a built-in to replace a divisor of a number with another. I didn't think I'd actually get to make use of it so soon...

Using the code points of characters for I/O, this becomes 6 bytes: I23SO@.

Explanation

2   Push 2 (irrelevant).
/   Reflect to SE. Switch to Ordinal.
i   Read all input as a string.
    The IP bounces up and down, hits the bottom right corner and turns around,
    bounces down again.
i   Try to read more input, but we're at EOF so this pushes an empty string.
/   Reflect to W. Switch to Cardinal.
2   Push 2.
    The IP wraps around to the last column.
3   Push 3.
S   Implicitly discard the empty string and convert the input string to the integer
    value it contains. Then replace the divisor 2 with the divisor 3 in the input.
    This works by multiplying the value by 3/2 as long as it's divisible by 2.
/   Reflect to NW. Switch to Ordinal.
    Immediately bounce off the top boundary. Move SW.   
o   Implicitly convert the result to a string and print it.
    Bounce off the bottom left corner. Move NE.
/   Reflect to S. Switch to Cardinal.
@   Terminate the program.
share|improve this answer
1  
Your obsession is officially confirmed. – Leaky Nun 20 hours ago

Mathematica, 22 19 bytes

Thanks to lanlock4 for saving 3 bytes!

#//.x_?EvenQ:>3x/2&

Pure function that does the replacement repeatedly, one factor of 2 at a time. Works on all positive integers less than 265537.

share|improve this answer
    
Would x_?EvenQ work instead of x_/;EvenQ@x? – lanlock4 20 hours ago
1  
You're totally right, thanks! – Greg Martin 19 hours ago

Java, 38 bytes

int f(int n){return n%2>0?n:f(n/2*3);}

Try it online!


Previous 43-byte solution:

int f(int n){for(;n%2<1;)n=n/2*3;return n;}

Try it online!

share|improve this answer

Retina, 23 bytes

.+
$*
+`^(1+)\1$
$&$1
1

Try it online!

share|improve this answer

Jelly, 8 5 bytes

Æf3»P

Æf3»P  Main Link, argument is z
Æf     Prime factors
  3»   Takes maximum of 3 and the value for each value in the array
    P  Takes the product of the whole thing

Try it online!

-3 bytes thanks to a hint from @Dennis!

share|improve this answer
1  
Hint: 2 is both the only even and the smallest prime number. – Dennis yesterday
    
@Dennis I see. Yes, got it now. Thanks! :) – Hyper Neutrino yesterday
    
Congratulations on learning Jelly. – Leaky Nun 20 hours ago
    
@LeakyNun Thanks! And thanks for teaching it to me. :) – Hyper Neutrino 20 hours ago

Pyth - 14 10 9 bytes

*^1.5/PQ2

Counts the number of 2s in the prime factorization (/PQ2). Multiplies the input by 1.5^(# of 2s)

Try it

share|improve this answer
    
Interesting approach - too bad it's not as short as the existing Pyth solution. – Challenger5 21 hours ago
    
@Challenger5 I'm not seeing any other Pyth solution here. – Svetlana 19 hours ago
1  
Oh, OK then. It's a more interesting approach than the typical one for this challenge. – Challenger5 19 hours ago

Brachylog, 7 bytes

~×₂×₃↰|

Try it online!

How it works

~×₂×₃↰|      original program
?~×₂×₃↰.|?.  with implicit input (?) and output (.) added

?~×₂         input "un-multiplied" by 2
    ×₃       multiplied by 3
      ↰      recursion
       .     is the output
        |    or (in case the above fails, meaning that the input
                 cannot be "un-multiplied" by 2)
         ?.  the input is the output
share|improve this answer
    
Related. – ais523 13 hours ago

J, 11 bytes

[:*/q:+2=q:

Try it online!

[: cap (placeholder to call the next verb monadically)

*/ the product of

q: the prime factors

+ plus (i.e. with one added where)

2 two

= is equal to (each of)

q: the prime factors

share|improve this answer
    
I thought you find [: disgusting. – Leaky Nun 20 hours ago
    
@LeakyNun I do, but I wasn't as clever as Conor O'Brien. – Adám 18 hours ago

J, 15 12 10 bytes

(+2&=)&.q:

Try it online! Works similar to below, just has different logic concerning replacement of 2 with 3.

15 bytes

(2&={,&3)"+&.q:

Try it online!

Explanation

(2&={,&3)"+&.q:
           &.    "under"; applies the verb on the right, then the left,
                 then the inverse of the right
             q:  prime factors
(       )"+      apply inside on each factor
     ,&3         pair with three: [factor, 3]
 2&=             equality with two: factor == 2
    {            list selection: [factor, 3][factor == 2]
                 gives us 3 for 2 and factor for anything else
           &.q:  under prime factor
share|improve this answer
    
Huh, you switched algorithm while I was writing up mine. Now we use the same. – Adám yesterday
    
@Adám Oh, haha. Nice answer! I couldn't resist the opportunity to use roll here. :) – Conor O'Brien yesterday
    
Actually I might be able to save some more bytes...edit saved some :D – Conor O'Brien yesterday
    
Funny you call it Roll, I call it Under. Hope to get it into APL soon. – Adám yesterday
    
@Adám Haha it's actually called under. I got the terms confused – Conor O'Brien yesterday

Pyth, 9 bytes

Integer output \o/

*F+1.|R1P

Test suite.

How it works

*F+1.|R1P
        P   prime factorization
    .|R1    bitwise OR each element with 1
*F+1        product
share|improve this answer

Japt, 19 16 10 9 7 bytes

k ®w3Ã×

Try it online!

Explanation

 k ®   w3Ã ×
Uk mZ{Zw3} r*1
U              # (input)
 k m           # for every prime factor
    Z{Zw3}     # replace it by the maximum of itself and 3
           r*1 # output the product
share|improve this answer
    
Hah, JS is tied with Japt. A sure sign there's a much shorter solution ;-) – ETHproductions yesterday
    
Hints: × is a shortcut for r@X*Y}1 (or just r*1), which might come in handy. There's also XwY which is Math.max(X,Y). – ETHproductions yesterday
    
Thanks, though the recursive solution really is the shortest. – Luke yesterday
    
Thanks for the hints. I think I got it now. – Luke yesterday
    
Nice one! I think you can do k m_w3Ã× to save a byte. Also, m_ can be shortened to ®. – obarakon 23 hours ago

Japt, 7 bytes

k mw3 ×

Try it online!

Explanation

k mw3 ×

k        // Factorize the input.
  mw3    // Map each item X by taking max(X, 3).
      ×  // Take the product of the resulting array.
         // Implicit: output result of last expression
share|improve this answer

CJam, 10 bytes

rimf2Zer:*

Really simple.

Explanation:

ri  e# Read integer:  | 28
mf  e# Prime factors: | [2 2 7]
2   e# Push 2:        | [2 2 7] 2
Z   e# Push 3:        | [2 2 7] 2 3
er  e# Replace:       | [3 3 7]
:*  e# Product:       | 63
share|improve this answer

APL (Dyalog Unicode), 26 bytes

{⍵(⊣×(3*⊢)×(÷2*⊢))2⍟⍵∨2*⍵}

Try it online!

This is too verbose, I must be doing something wrong...

share|improve this answer

R, 42 bytes

The only right amount of bytes in an answer.

x=gmp::factorize(scan());x[x==2]=3;prod(x)

Pretty straightforward, uses the gmp package to factorize x, replaces 2s by 3s, and returns the product.

share|improve this answer

PHP, 36 Bytes

for($a=$argn;$a%2<1;)$a*=3/2;echo$a;

Try it online!

share|improve this answer
1  
for($a=$argn;!1&$a;)$a*=3/2;echo$a; renaming $argn saves a single byte. – Christoph 17 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.