Substitua dois por três

36

Dado um número inteiro positivo, escreva algum código para obter sua fatoração primária e substituir todos os fatores de 2por 3.

Por exemplo

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

Isso é portanto, o objetivo é minimizar a contagem de bytes de sua resposta.

Casos de teste

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
Assistente de Trigo
fonte

Respostas:

63

Fractran , 3 bytes

3/2

O Fractran literalmente tem apenas um embutido, mas acontece exatamente o que esta tarefa está solicitando. (Também é Turing-completo, por si só.)

O idioma realmente não tem uma sintaxe ou intérprete padronizado. Esse intérprete (em um comentário em uma postagem de blog - é uma linguagem muito simples) aceitará a sintaxe mostrada aqui. (Existem outros intérpretes Fractran com outras sintaxes, por exemplo, alguns escreveriam este programa como 3 2, ou mesmo usando 3e 2como argumentos de linha de comando, o que levaria a uma pontuação de 0 + 3 bytes. Duvido que seja possível fazer melhor que 3 em um intérprete pré-existente).

Explicação

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

fonte
10
Fale sobre ferramenta certa para o trabalho ..
Kevin Cruijssen
23
"Não vote em soluções triviais que usam apenas um simples embutido." Bem, neste caso: saber que existe uma linguagem "Fractran" que possui um único componente que resolve essa tarefa específica é, por si só, impressionante.
Stewie Griffin
3
Golf relacionado ao código SO (pré-PPCG): Escreva um intérprete Fractran .
Hobbs
1
@AnderBiguri: Provavelmente procurando uma linguagem completa de Turing que seja muito simples / fácil de implementar. Fractran é realmente elegante como os tarpits de Turing; a maioria tem muito mais arestas, casos especiais ou detalhes que podem ser alterados sem fazer uma grande diferença.
3
@AnderBiguri Parece que saiu de seus estudos sobre a conjectura de Collatz; ele provou que uma generalização de Collatz é equivalente a Fractran e que Fractran é completo em Turing, portanto Collatz generalizada é indecidível.
hobbs
21

Python 2 , 28 bytes

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

Experimente online!

Divida recursivamente o número por 2 e multiplique o resultado por 3, desde que o número seja par. Números ímpares retornam a si mesmos.

Alt de 32 bytes:

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

Experimente online . Tem algum erro de flutuação. A constante é log_2(3)-1.

Usa (n&-n)para encontrar o maior fator de potência-2 de n, convertido 3**kem 2**k, elevando-o à potência de log_2(3)-1.

xnor
fonte
Bom, esta é exatamente a minha solução!
Wheat Wizard
@WheatWizard Me também, aha!
Graviton 5/05
18

05AB1E , 4 bytes

Ò1~P

Experimente online!

Como funciona

Ò     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
fonte
Este bate Jelly por 1 byte simplesmente porque o primeiro-fatoração é apenas um byte aqui :(
HyperNeutrino
5
@HyperNeutrino: Também notei: "por que Dennis está usando o 05AB1E? Ah, algoritmo idêntico, nomes internos mais curtos". Então, tive que procurar uma linguagem em que pudesse fazê-lo em menos bytes, usando um conjunto ainda mais apropriado de componentes internos.
14

Haskell, 24 23 bytes

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

Divida por dois e multiplique por 3 até um truque ímpar em Haskell.

Experimente online!

Alternativa com uma lambda em vez de uma função sem ponto e com a mesma contagem de bytes:

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

Edit: @ ais523 salvou um byte na versão original e @ Ørjan Johansen na versão alternativa, portanto, ambas as versões ainda têm o mesmo comprimento. Obrigado!

nimi
fonte
3
A versão lambda pode ser reduzida para odd`until`\x->div(x*3)2.
Ørjan Johansen
2
A versão original também pode ser reduzida em um byte usando-o $para substituir um par de parênteses: Experimente online!
@ ØrjanJohansen: ah, que bom! Obrigado.
nimi 5/05
@ ais523: Como eu poderia ter perdido essa, obrigado!
Nimi
2
Eu acho que você esqueceu de remover um par da ()versão lambda #
1297
8

JavaScript (ES6), 19 bytes

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

Enquanto a entrada é divisível por dois, multiplica-a por 1,5, o que equivale a dividir por 2 e multiplicar por 3.

ETHproductions
fonte
2
x*3/2tem o mesmo bytecount
Leaky Nun
1
f=geralmente não é necessário para js.
Christoph
3
@Christoph Obrigado, mas para se autodenominar f(x*1.5)precisa ter o nome e f, por isso, o motivo f=está incluído.
ETHproductions
@ETHproductions Uhm ... é claro! Eu senti falta disso. Existe alguma meta sobre como o código de chamada se parece exatamente?
Christoph
2
@Christoph Aqui está a meta post relevante.
ETHproductions
8

Flacidez cerebral , 76 bytes

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

Experimente online!

Explicação

Esse programa funciona dividindo o número por dois e triplicando até obter o restante de um da divisão. Então ele pára de repetir e dobra e adiciona um ao número final.

Explicação mais detalhada eventualmente ...

0 '
fonte
> Em breve ...
Wheat Wizard
7

Mathematica, 22 19 bytes

Obrigado ao lanlock4 por economizar 3 bytes!

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

Função pura que faz a substituição repetidamente, um fator de 2 por vez. Funciona em todos os números inteiros positivos menores que 2 65537 .

Greg Martin
fonte
Iria x_?EvenQtrabalhar em vez de x_/;EvenQ@x?
Não é uma árvore
1
Você está totalmente certo, obrigado!
Greg Martin
6

05AB1E , 6 5 bytes

Guardou um byte graças a Adnan .

ÒDÈ+P

Experimente online!

Explicação

Ò       # 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
fonte
2
ÒDÈ+Pdeve salvar um byte
Adnan
@ Adnan: Obrigado!
Emigna
6

Alice , 9 bytes

2/S 3
o@i

Experimente online!

Alice tem um built-in para substituir um divisor de um número por outro. Eu não achava que iria usá-lo tão cedo ...

Usando os pontos de código dos caracteres para E / S, isso se torna 6 bytes: I23SO@ .

Explicação

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
fonte
1
Sua obsessão é oficialmente confirmada.
Freira vazada
4

Geléia , 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

Experimente online!

-3 bytes graças a uma dica de @Dennis!

HyperNeutrino
fonte
2
Dica: 2 é o único número par e o menor número primo.
Dennis19
@ Dennis eu vejo. Sim, entendi agora. Obrigado! :)
HyperNeutrino
Parabéns por aprender Jelly.
Freira vazada
@LeakyNun Thanks! E obrigado por me ensinar isso. :)
HyperNeutrino
Parabéns por esta resposta!
Erik the Outgolfer
4

Pitão - 14 10 9 bytes

*^1.5/PQ2

Conta o número de 2s na fatoração principal (/ PQ2). Multiplica a entrada por 1,5 ^ (# de 2s)

Tente

Maria
fonte
Abordagem interessante - que pena que não é tão curta quanto a solução Pyth existente.
Esolanging Fruit
@ Challenger5 Não estou vendo nenhuma outra solução Pyth aqui.
Maria
1
Oh, ok então. É uma abordagem mais interessante do que a típica para este desafio.
Esolanging Fruit
4

Hexagonia , 112 91 bytes

Tamanho da grade 6 (91 bytes)

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

Versão compacta

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

Tamanho da grade 7 (112 bytes)

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

Experimente online!

Versão compacta:

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

Versão Ungolfed para melhor legibilidade:

Ungolfed

Layout aproximado da memória

insira a descrição da imagem aqui

Caminho cinza (inicialização da memória)

?     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

Entrada de loop

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

Caminho verde (o valor ainda é divisível por 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"

Caminho vermelho (o valor não é mais divisível por 2)

} = & " ~ & ' Drag what's left of "Input" along to "Multiplier"
*             Multiply "Multiplier" with "Temp 2"
! @           Output result, exit program
Manfred Radlwimmer
fonte
1
Bem-vindo ao PPCG! :)
Martin Ender
@MartinEnder Obrigado, incrível linguagem btw. :)
Manfred Radlwimmer
1
Obrigado por usá-lo! :) Você não pode simplificar o layout da memória (e, portanto, a quantidade de movimento que precisa fazer) se calcular %2e :2ambos na borda do "módulo"? (Para que você possa se livrar das duas arestas superiores.) E então, você pode anexar o ramo "multiplicador" à aresta "módulo" em vez da aresta "divisor" para precisar de menos movimento após cada ramo? (Você pode até girar essa seção, para que "result" ou "temp 2" toque em "modulo", o que significa que você só precisa copiar o resultado final uma vez antes de poder calcular o produto.)
Martin Ender,
@MartinEnder Uhhhm provavelmente. Eu ainda estou recebendo em torno da parte "Agony" da língua então por enquanto eu provavelmente vou ficar a fazer a grade menor, sem tocar a lógica ^^
Manfred Radlwimmer
3

Braquilog , 7 bytes

~×₂×₃↰|

Experimente online!

Como funciona

~×₂×₃↰|      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
Freira Furada
fonte
2

J , 11 bytes

[:*/q:+2=q:

Experimente online!

[: cap (espaço reservado para chamar o próximo verbo monadicamente)

*/ o produto de

q: os principais fatores

+ mais (ou seja, com um adicionado onde)

2 dois

= é igual a (cada um)

q: os principais fatores

Adão
fonte
Eu pensei que você acha [:nojento.
Freira vazada
@LeakyNun sim, mas não era tão inteligente quanto Conor O'Brien .
Adám 5/05
2

J , 15 12 10 bytes

(+2&=)&.q:

Experimente online! Funciona de maneira semelhante à abaixo, apenas possui uma lógica diferente em relação à substituição de 2por3 .

15 bytes

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

Experimente online!

Explicação

(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
fonte
Você trocou o algoritmo enquanto eu escrevia o meu. Agora usamos o mesmo.
Adám 4/17/17
@ Adám Ah, haha. Boa resposta! Não pude resistir à oportunidade de usar rollaqui. :)
Conor O'Brien
Na verdade, eu poderia ser capaz de salvar mais alguns bytes ... editar salvo algumas: D
Conor O'Brien
Engraçado você chamar isso de Roll, eu chamo de Under. Espero colocá-lo em APL em breve.
Adám 4/17/17
@ Adám Haha, na verdade, é chamado sob. Eu tenho os termos confusos
Conor O'Brien
2

Pitão , 9 bytes

Saída inteira \ o /

*F+1.|R1P

Conjunto de teste .

Como funciona

*F+1.|R1P
        P   prime factorization
    .|R1    bitwise OR each element with 1
*F+1        product
Freira Furada
fonte
2

Japt , 19 16 10 9 7 bytes

k ®w3Ã×

Experimente online!

Explicação

 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
fonte
Hah, JS está empatado com Japt. Um sinal claro de que há uma solução muito mais curtos ;-)
ETHproductions
Dicas: ×é um atalho para r@X*Y}1(ou apenas r*1), que pode ser útil. Há também o XwYque é Math.max(X,Y).
ETHproductions
Obrigado, embora a solução recursiva seja realmente a mais curta.
Luke
Agradável! Eu acho que você pode fazer k m_w3Ã×para salvar um byte. Além disso, m_pode ser reduzido para ®.
Oliver
2

PHP, 36 bytes

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

Experimente online!

Jörg Hülsermann
fonte
1
for($a=$argn;!1&$a;)$a*=3/2;echo$a;renomear $argnsalva um único byte.
Christoph
2

CJam, 10 9 bytes

rimf1f|:*

Realmente simples.

Explicação:

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
fonte
2

Hexagonia , 28 27 26 bytes

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

Experimente online!

Dispostas:

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

Isso basicamente é executado:

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

Neste ponto, é um exercício sobre como posso torturar o caminho do loop para minimizar bytes.

Brincadeira
fonte
Bem, caramba, eu não tinha pensado nisso
Manfred Radlwimmer
1
@ManfredRadlwimmer Não se preocupe, codificação nada em Hexagony é uma realização em si
Jo rei
1

Japonês , 7 bytes

k mw3 ×

Experimente online!

Explicação

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
fonte
1

R, 42 bytes

A única quantidade certa de bytes em uma resposta.

x=gmp::factorize(scan());x[x==2]=3;prod(x)

Bem simples, usa o gmppacote para fatorar x, substitui 2s por 3s e retorna o produto.

JAD
fonte
1

Befunge-93 , 20 bytes

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

Experimente 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
fonte
17 bytes
Jo King
1

Perl 6 , 14 bytes

{1.5**.lsb*$_}

lsb retorna a posição do bit menos significativo, contado a partir da direita. Ou seja, quantos zeros à direita na representação binária, que é o mesmo que o número de fatores de 2. Portanto, eleve 3/2 a essa potência e pronto.

say {$_*1.5**.lsb}(24);
> 81
Phil H
fonte
0

Na verdade , 9 bytes

w⌠i1|ⁿ⌡Mπ

Experimente online!

Explicação:

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
fonte