Replace twos with threes

Question

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 code-golf 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

Answer 1

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}

Answer 2

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.

Answer 3

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.

Answer 4

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!

Answer 5

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.

Answer 6

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 eventually...

Answer 7

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 2⁶⁵⁵³⁷.

Answer 8

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

Answer 9

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

Answer 10

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.

Answer 11

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

Answer 12

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!

Answer 13

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!

Answer 14

Hexagony, 112 91 bytes

Grid size 6 (91 bytes)

      ? { 2 . . <
     / = { * = \ "
    . & . . . { _ '
   . . { . . } ' * 2
  _ } { / . } & . ! "
 . > % . . < | . . @ |
  \ . . \ . | ~ . . 3
   . . " . } . " . "
    . & . \ = & / 1
     \ = { : = } .
      [ = { { { <

Compact version

?{2..</={*=\".&...{_'..{..}'*2_}{/.}&.!".>%..<|..@|\..\.|~..3..".}.".".&.\=&/1\={:=}.[={{{<

Grid size 7 (112 bytes)

       ? { 2 " ' 2 <
      / { * \ / : \ "
     . = . = . = | . 3
    / & / { . . } { . "
   . > $ } { { } / = . 1
  _ . . } . . _ . . & . {
 . > % < . . ~ & . . " . |
  | . . } - " . ' . @ | {
   . . . = & . . * ! . {
    . . . _ . . . _ . =
     > 1 . . . . . < [
      . . . . . . . .
       . . . . . . .

Try it online!

Compact Version:

?{2"'2</{*\/:\".=.=.=|.3/&/{..}{.".>$}{{}/=.1_..}.._..&.{.>%<..~&..".||..}-".'.@|{...=&..*!.{..._..._.=>1.....<[

Ungolfed Version for better readability:

Approximate Memory Layout

Grey Path (Memory initialization)

?     Read input as integer (Input)
{     Move to memory edge "Divisor left"
2     Set current memory edge to 2 
" '   Move to memory edge "Divisor right" 
2     Set current memory edge to 2
"     Move to memory edge "Multiplier" 
3     Set current memory edge to 3
"     Move to memory edge "Temp 2" 
1     Set current memory edge to 1 
{ { { Move to memory edge "Modulo"
=     Turn memory pointer around 
[     Continue with next instruction pointer

Loop entry

%     Set "Modulo" to Input mod Divisor
<     Branch depending on result

Green Path (value is still divisible by 2)

} } {     Move to memory edge "Result"
=         Turn memory pointer around 
*         Set "Result" to "Temp 2" times "Multiplier" (3) 
{ = &     Copy "Result" into "Temp2" 
{ { } } = Move to "Temp"
:         Set "Temp" to Input / Divisor (2)
{ = &     Copy "Temp" back to "Input"
"         Move back to "Modulo"

Red Path (value is no longer divisible by 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program

Answer 15

Retina, 23 bytes

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

Try it online!

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

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

Answer 20

PHP, 36 Bytes

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

Try it online!

Answer 21

CJam, 10 9 bytes

rimf1f|:*

Really simple.

Explanation:

ri  e# Read integer:         | 28
mf  e# Prime factors:        | [2 2 7]
1   e# Push 1:               | [2 2 7] 1
f|  e# Bitwise OR with each: | [3 3 7]
:*  e# Product:              | 63

Answer 22

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

Answer 23

Hexagony, 28 27 26 bytes

?'2{{(\}}>='!:@=$\%<..>)"*

Try it online!

Laid out:

    ? ' 2 {
   { ( \ } }
  > = ' ! : @
 = $ \ % < . .
  > ) " * . .
   . . . . .
    . . . .

This basically runs:

num = input()
while num%2 == 0:
    num = (num/2)*3
print num

At this point it's an exercise on how torturous I can get the loop path to minimise bytes.

Answer 24

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

Answer 25

APL (Dyalog Unicode), 26 bytes

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

Try it online!

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

Answer 26

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.

Answer 27

Befunge-93, 20 bytes

&>:2%!#v_.@
 ^*3/2 <

Try it online!

& - take in input and add it to the stack
> - move right
: - duplicate the top of the stack
2 - add two to the stack
% - pop 2 and the input off the stack and put input%2 on the stack
! - logical not the top of the stack
# - jump over the next command
_ - horizontal if, if the top of the stack is 0 (i.e. input%2 was non zero) go 
    right, else go left

If Zero:
. - output the top of the stack
@ - end code

If Not Zero:
v - move down
< - move left
2 - add 2 the top of the stack
/ - pop top two, add var/2 to the stack
3 - add 3 to stack
* - pop top two, add var*3 to the stack
^ - move up
> - move right (and start to loop)

Answer 28

Perl 6, 14 bytes

{1.5**.lsb*$_}

lsb returns the position of the least-significant bit, counted from the right. That is, how many trailing zeroes in the binary representation, which is the same as the number of factors of 2. So raise 3/2 to that power and we're done.

say {$_*1.5**.lsb}(24);
> 81

Answer 29

Pyke, 5 bytes

P1.|B

Try it online!

Answer 30

Actually, 9 bytes

w⌠i1|ⁿ⌡Mπ

Try it online!

Explanation:

w⌠i1|ⁿ⌡Mπ
w          factor into [prime, exponent] pairs
 ⌠i1|ⁿ⌡M   for each pair:
  i          flatten
   1|        prime | 1 (bitwise OR)
     ⁿ       raise to exponent
        π  product

Answer 31

Pari/GP, 23 bytes

f(n)=if(n%2,n,f(3*n/2))

Try it online!

---

Pari/GP, 23 bytes

n->n*1.5^valuation(n,2)

Try it online!

Answer 32

C (gcc), 23 bytes

f(n){n=n&1?n:f(n/2*3);}

Try it online!

Answer 33

Chip -z, 123 bytes

tv~S
a^v.bv.cv.dv.ev.fv.gv.
 zLxzLxzLxzLxzLxzLxzLxz-vh
A##L##L##L##L##L##L##L##'
B))L))L))L))L))L))L))'
   C  D  E  F  G  H

Try it online! (Includes a bashy wrapper for numeric conversion).

Explanation

This solution uses Chip's 'native' data type, an unsigned 8-bit integer. Any input or output that would be outside the bounds of that type will produce undefined results.

I and O are done via raw bytes values, hence the wrapper in the TIO.

The algorithm, in C-ish looks something like this:

uchar byte = in();
while(!(byte & 0x1)) {
  byte += byte>>1; // logical shift
}
out(byte);

The bulk of this program are the eight full adders (##) and their wiring (L, ), x, ...).

To see all steps of the computation, delete the S. You may want to adjust the hexdump format to "%d\n" for nicer output.

Answer 34

Ruby, 23 bytes

f=->n{n%2<1?f[n/2*3]:n}

Try it online!

A recursive lambda, nothing shocking.