48
\$\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

47 Answers 47

1
2
1
\$\begingroup\$

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) 
\$\endgroup\$
1
  • \$\begingroup\$ 17 bytes \$\endgroup\$ Commented Mar 23, 2018 at 12:32
1
\$\begingroup\$

Ruby, 23 bytes

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

Try it online!

A recursive lambda, nothing shocking.

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

Vyxal, 5 bytes

ǐ3v∴Π 

Try it Online!

ǐ # Prime factors v∴ # Take max of each and... 3 # 3 Π # Take product 
\$\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\$ Commented Jan 10, 2022 at 19:07
1
\$\begingroup\$

Factor + math.primes.factors math.unicode, 28 bytes

[ factors """"replace Π ] 

Try it online!

Note the strings have literal control characters '2' and '3' embedded in them (you can see them on TIO).

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

Desmos, 29 bytes

f(n)=1.5^{log_2(gcd(n,2^n))}n 

A surprisingly short solution, and an interesting usage of \$\operatorname{gcd}()\$.

Try It On Desmos!

Try It On Desmos! - Prettified

It only works for numbers up to 1024 though. Here is a version that should support significantly more numbers at the cost of a few bytes:

42 bytes

f(n)=1.5^{log_2(gcd(n,2^{ceil(log_2n)}))}n 
\$\endgroup\$
1
\$\begingroup\$

Vyxal, 4 bytes

ǐ1⋎Π 

Try it Online!

How?

ǐ1⋎Π ǐ # Prime factors 1⋎ # Bitwise OR each with one Π # Product 
\$\endgroup\$
1
\$\begingroup\$

Thunno 2, 5 bytes

f1Æ|p 

Try it online!

Explanation

f1Æ|p # Implicit input f # Prime factorisation 1Æ| # Bitwise OR with 1 p # Product of the list # Implicit output 
\$\endgroup\$
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\$

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.