Zamień dwójki na trójki

36

Biorąc dodatnią liczbę całkowitą n napisać kod do podjęcia jej na czynniki pierwsze i wymienić wszystkie jej czynniki 2z 3.

Na przykład

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

To jest więc celem jest zminimalizowanie liczby bajtów odpowiedzi.

Przypadki testowe

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
Kreator pszenicy
źródło

Odpowiedzi:

63

Fraktran , 3 bajty

3/2

Fractran dosłownie ma tylko jedno wbudowane narzędzie, ale zdarza się, że robi dokładnie to, o co prosi to zadanie. (Sam w sobie jest również kompletny Turinga.)

Język tak naprawdę nie ma znormalizowanej składni ani interpretera. Ten interpreter (w komentarzu do posta na blogu - jest to bardzo prosty język) zaakceptuje pokazaną tutaj składnię. (Istnieją inne interpretery Fractran z innymi składniami, np. Niektórzy napisaliby ten program jako 3 2, lub nawet używając 3i 2jako argumenty wiersza poleceń, co doprowadziłoby do wyniku 0 + 3 bajtów. Wątpię, czy można zrobić lepiej niż 3 w już istniejący tłumacz).

Wyjaśnienie

3/2
 /   Replace a factor of
  2  2
3    with 3
     {implicit: repeat until no more replacements are possible}

źródło
10
Porozmawiaj o odpowiednim narzędziu do pracy.
Kevin Cruijssen
23
„Nie głosuj za trywialnymi rozwiązaniami, które wykorzystują tylko proste wbudowanie”. Cóż, w tym przypadku: Świadomość, że istnieje język „Fractran” z jednym wbudowanym rozwiązaniem tego konkretnego zadania, sama w sobie jest imponująca.
Stewie Griffin
3
Powiązany kod SO golf (wcześniejszy niż PPCG): Napisz tłumacza Fractran .
hobbs
1
@AnderBiguri: Prawdopodobnie szukasz kompletnego języka Turinga, który jest bardzo prosty / łatwy do wdrożenia. Fractran jest naprawdę elegancki jak plandeki Turinga; większość ma o wiele bardziej ostre krawędzie, specjalne przypadki lub detale, które można zmienić bez znaczącej różnicy.
3
@AnderBiguri Wygląda na to, że wyszedł z badań nad przypuszczeniem Collatza; udowodnił, że uogólnienie Collatz jest równoważne Fractranowi i że Fractran jest kompletny w Turinga, dlatego uogólniony Collatz jest nierozstrzygalny.
hobbs
21

Python 2 , 28 bajtów

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

Wypróbuj online!

Rekurencyjnie dziel liczbę przez 2 i mnoży wynik przez 3, o ile liczba jest parzysta. Dziwne liczby same się zwracają.

32 bajty alt:

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

Wypróbuj online . Ma jakiś błąd pływaka. Stała jest log_2(3)-1.

Używa (n&-n)do znalezienia największego współczynnika potęgi-2 z n, konwertuje 3**kdo 2**k, podnosząc go do potęgi log_2(3)-1.

xnor
źródło
Fajnie, to jest właśnie moje rozwiązanie!
Kreator pszenicy
@WheatWizard Me też, aha!
Graviton
18

05AB1E , 4 bajty

Ò1~P

Wypróbuj online!

Jak to działa

Ò     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.
Dennis
źródło
To pokonuje galaretkę o 1 bajt po prostu dlatego, że
rozkład na
5
@HyperNeutrino: Zauważyłem to również: „dlaczego Dennis używa 05AB1E? Och, identyczny algorytm, krótsze wbudowane nazwy”. Musiałem więc znaleźć język, w którym mógłbym to zrobić w jeszcze mniejszej liczbie bajtów, używając jeszcze bardziej odpowiedniego zestawu wbudowanych funkcji.
14

Haskell, 24 23 bajty

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

Podziel przez dwa i pomnóż przez 3, aż do uzyskania dziwnej lewy w Haskell.

Wypróbuj online!

Alternatywnie z funkcją lambda zamiast z funkcją point-free i z tą samą liczbą bajtów:

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

Edycja: @ ais523 zapisał bajt w oryginalnej wersji, a @ Ørjan Johansen w alternatywnej wersji, więc obie wersje mają wciąż tę samą długość. Dzięki!

nimi
źródło
3
Wersję lambda można skrócić odd`until`\x->div(x*3)2.
Ørjan Johansen
2
Oryginalną wersję można również skrócić o jeden bajt, używając $pary nawiasów: Wypróbuj online!
@ ØrjanJohansen: ah, nice! Dzięki.
nimi
@ ais523: Jak mogłem to przegapić, dzięki!
nimi
2
Myślę, że zapomniałeś usunąć parę ()z wersji lambda
97
8

JavaScript (ES6), 19 bajtów

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

Podczas gdy dane wejściowe są podzielne przez dwa, mnoży je przez 1,5, co jest równoważne dzieleniu przez 2 i mnożeniu przez 3.

ETHprodukcje
źródło
2
x*3/2ma tę samą liczbę bajtów
Leaky Nun
1
f=zwykle nie jest potrzebny dla js.
Christoph
3
@Christoph Dzięki, ale aby się nazywać f(x*1.5), musi mieć nazwę f, dlatego też f=jest uwzględniona.
ETHprodukcje
@ETHproductions Uhm ... oczywiście! Tęsknie za tym. Czy jest jakiś meta na tym, jak dokładnie wygląda kod wywołujący?
Christoph
2
@Christoph Oto odpowiedni meta post.
ETHprodukcje
8

Brain-Flak , 76 bajtów

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

Wypróbuj online!

Wyjaśnienie

Ten program działa poprzez podzielenie liczby przez dwa i potrojenie, aż otrzyma resztę jednego z podziału. Następnie przestaje się zapętlać, podwaja się i dodaje jeden do ostatecznej liczby.

Bardziej szczegółowe wyjaśnienie ostatecznie ...

0 '
źródło
> Wkrótce ...
Kreator pszenicy
7

Mathematica, 22 19 bajtów

Dzięki lanlock4 za oszczędność 3 bajtów!

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

Czysta funkcja, która dokonuje wymiany wielokrotnie, jeden czynnik 2 na raz. Działa na wszystkich dodatnich liczbach całkowitych mniejszych niż 2 65537 .

Greg Martin
źródło
Czy x_?EvenQdziałałby zamiast x_/;EvenQ@x?
Nie drzewo
1
Masz całkowitą rację, dzięki!
Greg Martin
6

MATL , 7 , 6 bajtów

Yf1Z|p

Wypróbuj online!

1 bajt zapisany dzięki genialnej obserwacji Dennisa


Najlepszym sposobem na wyjaśnienie tego jest pokazanie stosu w różnych punktach.

Yf  % Prime factors

[2 2 2 3]

1Z| % Bitwise OR with 1

[3 3 3 3]

p   % Product

81

Alternatywne rozwiązanie:

Yfto~+p
DJMcMayhem
źródło
Miły! Miałem Yf3H$X>p8 bajtów
Luis Mendo
6

05AB1E , 6 5 bajtów

Oszczędność bajtu dzięki Adnanowi .

ÒDÈ+P

Wypróbuj online!

Wyjaśnienie

Ò       # 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
Emigna
źródło
2
ÒDÈ+Ppowinien oszczędzić bajt
Adnan
@Adnan: Dzięki!
Emigna
6

Alice , 9 bajtów

2/S 3
o@i

Wypróbuj online!

Alicja ma wbudowaną funkcję zastępowania dzielnika liczby innym. Nie sądziłem, że będę mógł z niego skorzystać tak szybko ...

Używając punktów kodowych znaków dla We / Wy, staje się to 6 bajtów: I23SO@ .

Wyjaśnienie

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.
Martin Ender
źródło
1
Twoja obsesja została oficjalnie potwierdzona.
Leaky Nun
4

Galaretka , 8 5 bajtów

Æ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

Wypróbuj online!

-3 bajty dzięki podpowiedzi @Dennis!

HyperNeutrino
źródło
2
Wskazówka: 2 jest zarówno jedyną parzystą, jak i najmniejszą liczbą pierwszą.
Dennis
@Dennis Rozumiem. Tak, rozumiem teraz. Dzięki! :)
HyperNeutrino
Gratulujemy nauki żelków.
Leaky Nun
@LeakyNun Thanks! I dzięki za nauczenie mnie tego. :)
HyperNeutrino
Gratulujemy tej odpowiedzi!
Erik the Outgolfer
4

Pyth - 14 10 9 bajtów

*^1.5/PQ2

Liczy liczbę 2 sekund w rozkładzie na czynniki pierwsze (/ PQ2). Mnoży wartość wejściową przez 1,5 ^ (# z 2s)

Spróbuj

Maria
źródło
Ciekawe podejście - szkoda, że ​​nie jest tak krótkie jak istniejące rozwiązanie Pyth.
Esolanging Fruit
@ Challenger5 Nie widzę tutaj żadnego innego rozwiązania dla Pyth.
Maria
1
No dobrze. Jest to bardziej interesujące podejście niż typowe dla tego wyzwania.
Esolanging Fruit
4

Sześciokąt , 112 91 bajtów

Rozmiar siatki 6 (91 bajtów)

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

Wersja kompaktowa

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

Rozmiar siatki 7 (112 bajtów)

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

Wypróbuj online!

Wersja kompaktowa:

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

Wersja bez golfa dla lepszej czytelności:

Ungolfed

Przybliżony układ pamięci

enter image description here

Gray Path (inicjalizacja pamięci)

?     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

Wpis w pętli

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

Zielona ścieżka (wartość jest nadal podzielna przez 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"

Czerwona ścieżka (wartości nie można już podzielić przez 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program
Manfred Radlwimmer
źródło
1
Witamy w PPCG! :)
Martin Ender
@MartinEnder Thanks, awesome language btw. :)
Manfred Radlwimmer
1
Dzięki za korzystanie! :) Czy nie możesz uprościć układu pamięci (a co za tym idzie ilości ruchu, który musisz wykonać), jeśli obliczysz %2i :2jedno i drugie do krawędzi „modulo”? (Więc możesz po prostu pozbyć się dwóch górnych krawędzi.) A następnie, czy możesz przymocować gałąź „mnożnika” do krawędzi „modulo” zamiast krawędzi „dzielnika”, aby po każdym odgałęzieniu był mniej ruch? (Być może możesz nawet obrócić tę sekcję, aby „wynik” lub „temp 2” dotknął „modulo”, co oznaczałoby, że musisz tylko skopiować wynik końcowy, zanim będziesz w stanie obliczyć produkt.)
Martin Ender
@MartinEnder Uhhhm prawdopodobnie. Wciąż poruszam się po części „Agonii” języka, więc na razie będę się
starał
3

Brachylog , 7 bajtów

~×₂×₃↰|

Wypróbuj online!

Jak to działa

~×₂×₃↰|      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
Leaky Nun
źródło
2

J , 11 bajtów

[:*/q:+2=q:

Wypróbuj online!

[: cap (symbol zastępczy monadycznie wywołuje następny czasownik)

*/ produkt z

q: czynniki pierwsze

+ plus (tj. z jednym dodanym gdzie)

2 dwa

= jest równy (każdemu)

q: czynniki pierwsze

Adám
źródło
Myślałem, że czujesz się [:obrzydliwie.
Leaky Nun
@LeakyNun Tak, ale nie byłem tak sprytny jak Conor O'Brien .
Adám
2

J , 15 12 10 bajtów

(+2&=)&.q:

Wypróbuj online! Działa podobnie jak poniżej, po prostu ma inną logikę dotycząca wymiany 2z 3.

15 bajtów

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

Wypróbuj online!

Wyjaśnienie

(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
Conor O'Brien
źródło
Huh, you switched algorithm while I was writing up mine. Now we use the same.
Adám
@Adám Oh, haha. Nice answer! I couldn't resist the opportunity to use roll here. :)
Conor O'Brien
Actually I might be able to save some more bytes...edit saved some :D
Conor O'Brien
Funny you call it Roll, I call it Under. Hope to get it into APL soon.
Adám
@Adám Haha it's actually called under. I got the terms confused
Conor O'Brien
2

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
Leaky Nun
źródło
2

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
Luke
źródło
Hah, JS is tied with Japt. A sure sign there's a much shorter solution ;-)
ETHproductions
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
Thanks, though the recursive solution really is the shortest.
Luke
Nice one! I think you can do k m_w3Ã× to save a byte. Also, m_ can be shortened to ®.
Oliver
2

PHP, 36 Bytes

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

Try it online!

Jörg Hülsermann
źródło
1
for($a=$argn;!1&$a;)$a*=3/2;echo$a; renaming $argn saves a single byte.
Christoph
2

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
Esolanging Fruit
źródło
2

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.

Jo King
źródło
Well damn, I didn't think of that
Manfred Radlwimmer
1
@ManfredRadlwimmer Don't worry, coding anything in Hexagony is an achievement in itself
Jo King
1

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
ETHproductions
źródło
1

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.

JAD
źródło
1

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)
bwillsh
źródło
17 bytes
Jo King
1

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
Phil H
źródło
0

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
Mego
źródło