43
\$\begingroup\$

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
\$\endgroup\$
0

42 Answers 42

1
2
1
\$\begingroup\$

Risky, 9 bytes

*\?+0+0+0__?\?+?:2

Try it online!

\$\endgroup\$
1
\$\begingroup\$

tinylisp, 47 bytes

(load library
(d F(q((N)(i(odd? N)N(F(*(/ N 2)3

Defines a function F that takes an integer and returns an integer. Try it online!

Ungolfed/explanation

The best part is, this uses tail recursion, so it works for arbitrarily large numbers (though it does get horrifically slow).

(load library)   ; The library defines the odd?, *, and / functions

(def F           ; Define F to be
 (q              ; a list representing a function
  ((N)           ; that takes one argument, N:
   (if (odd? N)  ; If N is odd
    N            ; just return it
    (F           ; else call F recursively on
     (*          ; the product of
      (/ N 2)    ; N divided by 2
      3))))))    ; with 3
\$\endgroup\$
1
\$\begingroup\$

Taxi, 1243 bytes

Go to Post Office:W 1 L 1 R 1 L.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:S 1 L 1 R.Pickup a passenger going to Cyclone.Go to Cyclone:N 5 L 2 L.[A]Pickup a passenger going to Narrow Path Park.Pickup a passenger going to Divide and Conquer.2 is waiting at Starchild Numerology.Go to Starchild Numerology:N 1 R 3 L.Pickup a passenger going to Divide and Conquer.Go to Zoom Zoom:W 1 R 3 R.Go to Narrow Path Park:W 1 L 1 L 1 R.Go to Divide and Conquer:E 1 R 2 R.Pickup a passenger going to Cyclone.Go to Cyclone:E 1 L 1 L 2 L.Pickup a passenger going to Equal's Corner.Pickup a passenger going to Trunkers.Go to Trunkers:S 1 L.Pickup a passenger going to Equal's Corner.Go to Equal's Corner:W 1 L.Switch to plan B if no one is waiting.Pickup a passenger going to Multiplication Station.3 is waiting at Starchild Numerology.Go to Starchild Numerology:N 1 R.Pickup a passenger going to Multiplication Station.Go to Multiplication Station:W 1 R 2 R 1 R 4 L.Pickup a passenger going to Cyclone.Go to Cyclone:S 1 R 2 L 2 R.Switch to plan A.[B]Go to Narrow Path Park:N 4 R 1 R 1 L 1 R.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:E 1 R.Pickup a passenger going to Post Office.Go to Post Office:N 1 L 1 R.

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ For those wondering what this does: Divide by 2. If that's an integer, multiply the result by 3 and start over. Otherwise, exit the loop and print the result before it was divided by 2. \$\endgroup\$ Jan 10 at 19:07
0
\$\begingroup\$

Pyke, 5 bytes

P1.|B

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 23 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

Ruby, 23 bytes

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

Try it online!

A recursive lambda, nothing shocking.

\$\endgroup\$
0
\$\begingroup\$

R, 34 bytes

function(x){while(!x%%2)x=x/2*3;x}

Try it online!

Or: recursive version (same bytes)

f=function(x)`if`(x%%2,x,f(x/2*3))

Try it online!

2 is the only even prime number, so we divide the input by 2 and multiply by 3 until it's no longer even.


Edit: now reading the other answers, this approach has already been used many times in other languages...

\$\endgroup\$
0
\$\begingroup\$

Assembly (NASM, 32-bit, Linux), 57 bytes

mov ebx,3
l:mul ebx
rcr eax,1
jnc l
rcl eax,1
div ebx
ret

Try it online!

Both, the input and the output are in the eax register.

\$\endgroup\$
0
\$\begingroup\$

MMIX, 20 bytes (5 instrs)

00000000: 4e000004 3f000001 1b000003 4f00fffe  N¡¡¥?¡¡¢ñ¡¡¤O¡”“
00000010: f8010000                             ẏ¢¡¡
r23 BEV  $0,1F      // if(!(i & 1)) goto end
0H  SRU  $0,$0,1    // loop: i >>= 1
    MULU $0,$0,3    // i *= 3
    BEV  $0,0B      // if(!(i & 1)) goto loop
1H  POP  1,0        // return i

If it could be guaranteed the number was even, it could be cut down to four instructions (the first instruction is just to avoid halving if already odd).

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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