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

47 Answers 47

Reset to default
1
2
72
\$\begingroup\$

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}
Improve this answer
\$\endgroup\$
8
  • 12
    \$\begingroup\$ Talk about right tool for the job.. \$\endgroup\$ Commented May 5, 2017 at 7:02
  • 28
    \$\begingroup\$ "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. \$\endgroup\$ Commented May 5, 2017 at 8:51
  • 1
    \$\begingroup\$ @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.) \$\endgroup\$ Commented May 5, 2017 at 12:23
  • 3
    \$\begingroup\$ Related SO code golf (pre-PPCG): Write a Fractran interpreter. \$\endgroup\$ Commented May 8, 2017 at 5:29
  • 3
    \$\begingroup\$ @AnderBiguri It looks like it came out of his studies of the Collatz conjecture; he proved that a generalization of Collatz is equivalent to Fractran and that Fractran is Turing-complete, therefore generalized Collatz is undecidable. \$\endgroup\$ Commented May 8, 2017 at 18:00
24
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Nice this is my solution exactly! \$\endgroup\$ Commented May 4, 2017 at 21:50
  • \$\begingroup\$ @WheatWizard Me as well, aha! \$\endgroup\$ Commented May 5, 2017 at 4:26
19
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ This beats Jelly by 1 byte simply because prime factorization is only one byte here :( \$\endgroup\$ Commented May 4, 2017 at 23:43
  • 7
    \$\begingroup\$ @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. \$\endgroup\$ Commented May 5, 2017 at 0:05
14
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
6
  • 3
    \$\begingroup\$ The lambda version can be shortened to odd`until`\x->div(x*3)2. \$\endgroup\$ Commented May 4, 2017 at 23:55
  • 2
    \$\begingroup\$ The original version can also be shortened one byte via using $ to replace a pair of parentheses: Try it online! \$\endgroup\$ Commented May 5, 2017 at 3:39
  • \$\begingroup\$ @ØrjanJohansen: ah, nice! Thanks. \$\endgroup\$ Commented May 5, 2017 at 5:04
  • \$\begingroup\$ @ais523: How could I have missed that one, Thanks! \$\endgroup\$ Commented May 5, 2017 at 5:05
  • 2
    \$\begingroup\$ I think you forgot to remove a pair of () from the lambda version \$\endgroup\$ Commented May 5, 2017 at 6:41
8
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
  • 2
    \$\begingroup\$ x*3/2 has the same bytecount \$\endgroup\$ Commented May 5, 2017 at 3:42
  • 1
    \$\begingroup\$ f= is usally not needed for js. \$\endgroup\$ Commented May 5, 2017 at 6:18
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ Commented May 5, 2017 at 11:45
  • \$\begingroup\$ @ETHproductions Uhm ... of course ! I missed that. Is there any meta on what the calling code exactly looks like? \$\endgroup\$ Commented May 5, 2017 at 12:17
  • 2
    \$\begingroup\$ @Christoph Here is the relevant meta post. \$\endgroup\$ Commented May 5, 2017 at 14:48
8
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ > Coming soon ... \$\endgroup\$ Commented Dec 23, 2017 at 22:38
7
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Would x_?EvenQ work instead of x_/;EvenQ@x? \$\endgroup\$ Commented May 5, 2017 at 3:25
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

Lean, 139 82 71 bytes

11 bytes saved by ovs.

import data.nat.prime open list λx,prod$map(λp,p+1-p%2)$nat.factors x

Try it online!

I'm really new to lean so, this answer is probably really inefficient in ways I don't yet know. But it works.

We get a list of factors with nat.factors replace 2s with threes using a map and roll it back up with list.prod.

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ p+1-p%2 seems to work instead of the conditional expression. \$\endgroup\$ Commented Oct 6, 2021 at 11:05
  • 1
    \$\begingroup\$ @ovs Nice. It's tough to tell what library functions there are and what they are named. \$\endgroup\$ Commented Oct 6, 2021 at 11:11
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Nice! I had Yf3H$X>p for 8 bytes \$\endgroup\$ Commented May 4, 2017 at 22:20
5
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ ÒDÈ+P should save a byte \$\endgroup\$ Commented May 4, 2017 at 22:28
5
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your obsession is officially confirmed. \$\endgroup\$ Commented May 5, 2017 at 3:38
5
\$\begingroup\$

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:

Ungolfed

Approximate Memory Layout

enter image description here

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
Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to PPCG! :) \$\endgroup\$ Commented Mar 23, 2018 at 11:12
  • \$\begingroup\$ @MartinEnder Thanks, awesome language btw. :) \$\endgroup\$ Commented Mar 23, 2018 at 11:13
  • 1
    \$\begingroup\$ Thanks for using it! :) Can't you simplify the memory layout (and thereby the amount of movement you need to do) if you compute %2 and :2 both into the "modulo" edge? (So you can just get rid of the top two edges.) And then, could you attach the "multiplier" branch onto the "modulo" edge instead of the "divisor" edge so you need less movement after each branch? (You could possibly even rotate that section, so that "result" or "temp 2" touches "modulo" which would mean you only need to copy the final result once before being able to compute the product.) \$\endgroup\$ Commented Mar 23, 2018 at 11:20
  • \$\begingroup\$ @MartinEnder Uhhhm probably. I'm still getting around the "Agony" part of the language so for now I'll probably stick to making the grid smaller without touching the logic ^^ \$\endgroup\$ Commented Mar 23, 2018 at 11:35
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Hint: 2 is both the only even and the smallest prime number. \$\endgroup\$ Commented May 4, 2017 at 22:15
  • \$\begingroup\$ @Dennis I see. Yes, got it now. Thanks! :) \$\endgroup\$ Commented May 4, 2017 at 23:42
  • \$\begingroup\$ Congratulations on learning Jelly. \$\endgroup\$ Commented May 5, 2017 at 3:49
  • \$\begingroup\$ @LeakyNun Thanks! And thanks for teaching it to me. :) \$\endgroup\$ Commented May 5, 2017 at 3:50
  • \$\begingroup\$ Congrats on this answer! \$\endgroup\$ Commented May 7, 2017 at 11:08
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Related. \$\endgroup\$ Commented May 5, 2017 at 10:27
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Well damn, I didn't think of that \$\endgroup\$ Commented Mar 23, 2018 at 12:04
  • 1
    \$\begingroup\$ @ManfredRadlwimmer Don't worry, coding anything in Hexagony is an achievement in itself \$\endgroup\$ Commented Mar 23, 2018 at 12:28
4
\$\begingroup\$

Retina, 23 bytes

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

Try it online! Link is to test suite that runs automatically runs all inputs from 1 to 29. Explanation:

.+ $*

Convert to unary.

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

While the value is even, multiply it by 3/2.

1

Convert to decimal.

Note that any FRACTRAN program is trivially convertible to a Retina program with unary I/O. The fraction itself is converted into a match for a string that appears an exact number of times given by the denominator, and the substitution is then $1 repeated a number of times given by the numerator, although if this is greater than the denominator then $& can be used to golf down the code length. It then remains to loop each fraction back to the start of the script, so that the earliest possible fraction is always the next to be substituted. In the case of a single fraction no group is required of course.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Interesting approach - too bad it's not as short as the existing Pyth solution. \$\endgroup\$ Commented May 5, 2017 at 2:31
  • \$\begingroup\$ @Challenger5 I'm not seeing any other Pyth solution here. \$\endgroup\$ Commented May 5, 2017 at 4:25
  • 1
    \$\begingroup\$ Oh, OK then. It's a more interesting approach than the typical one for this challenge. \$\endgroup\$ Commented May 5, 2017 at 4:27
3
\$\begingroup\$

Risky, 9 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

BQN (CBQN), 30 bytes

{0=2|𝕩?3×𝕊𝕩÷2;𝕩}

Attempt This Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I thought you find [: disgusting. \$\endgroup\$ Commented May 5, 2017 at 3:39
  • \$\begingroup\$ @LeakyNun I do, but I wasn't as clever as Conor O'Brien. \$\endgroup\$ Commented May 5, 2017 at 5:37
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ Huh, you switched algorithm while I was writing up mine. Now we use the same. \$\endgroup\$ Commented May 4, 2017 at 22:24
  • \$\begingroup\$ @Adám Oh, haha. Nice answer! I couldn't resist the opportunity to use roll here. :) \$\endgroup\$ Commented May 4, 2017 at 22:26
  • \$\begingroup\$ Actually I might be able to save some more bytes...edit saved some :D \$\endgroup\$ Commented May 4, 2017 at 22:27
  • \$\begingroup\$ Funny you call it Roll, I call it Under. Hope to get it into APL soon. \$\endgroup\$ Commented May 4, 2017 at 22:28
  • \$\begingroup\$ @Adám Haha it's actually called under. I got the terms confused \$\endgroup\$ Commented May 4, 2017 at 22:29
2
\$\begingroup\$

PHP, 36 Bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ for($a=$argn;!1&$a;)$a*=3/2;echo$a; renaming $argn saves a single byte. \$\endgroup\$ Commented May 5, 2017 at 6:24
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Unicode), 26 bytes

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

Try it online!

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Hah, JS is tied with Japt. A sure sign there's a much shorter solution ;-) \$\endgroup\$ Commented May 4, 2017 at 21:55
  • \$\begingroup\$ 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). \$\endgroup\$ Commented May 4, 2017 at 21:59
  • \$\begingroup\$ Thanks, though the recursive solution really is the shortest. \$\endgroup\$ Commented May 4, 2017 at 22:05
  • \$\begingroup\$ Nice one! I think you can do k m_w3Ã× to save a byte. Also, m_ can be shortened to ®. \$\endgroup\$ Commented May 5, 2017 at 0:43
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.