Conjectura de Collatz (OEIS A006577)

66

Esta é a conjectura de Collatz (OEIS A006577 ):

  • Comece com um número inteiro n > 1.
  • Repita as seguintes etapas:
    • Se n for par, divida-o por 2.
    • Se n for ímpar, multiplique por 3 e adicione 1.

Está provado que, para todos os números inteiros positivos de até 5 * 2 60 , ou cerca de 57640000000000000000000 , n se tornará 1 .

Sua tarefa é descobrir quantas iterações são necessárias (de reduzir pela metade ou triplicar mais um) para atingir 1 .

Relevante xkcd :)

Regras:

  • O menor código vence.
  • Se um número <2 for inserido, ou um não inteiro, ou um número não, a saída não importará.

Casos de teste

2  -> 1
16 -> 4
5  -> 5
7  -> 16
Maçaneta da porta
fonte

Respostas:

19

GolfScript, 24 23 21 20 18 caracteres

~{(}{3*).2%6\?/}/,

Assume a entrada em stdin. Teste online

Volatilidade
fonte
3
1+é de caixa especial como ).
Pedro
@PeterTaylor claro, esqueci disso;)
Volatilidade
11
Bom trabalho! <! - padding ->
Peter Taylor
11
@ Peter: O <! - -> não funciona nos comentários. Use isso em seu lugar.
Ilmari Karonen
2
Ou isto.
Timwi
15

C - 50 47 caracteres

Infelizmente, o pequeno C pobre requer uma quantidade enorme de código para E / S básica, portanto, encurtar tudo isso fez com que a interface do usuário fosse pouco intuitiva.

b;main(a){return~-a?b++,main(a&1?3*a+1:a/2):b;}

Compile com, por exemplo gcc -o 1 collatz.c. A entrada é unária com dígitos separados por espaço e você encontrará a resposta no código de saída. Um exemplo com o número 17:

$> ./1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
$> echo $?
12
$>
Para s
fonte
11
return~-a?salva 1. A mudança b++para o ?caso também deve ser salva b--.
precisa saber é o seguinte
Hehe você está dobrando as regras de modo muito: P 1 para a criatividade e usando uma linguagem não geralmente usado para golfe
Doorknob
Obrigado ugoren! Eu devo estar bêbado quando escrevi. :)
Fors
12

Caracteres Perl 34 (+1)

$\++,$_*=$_&1?3+1/$_:.5while$_>1}{

Abusar $\na saída final, como de costume. Execute com a -popção de linha de comando, a entrada é retirada stdin.

Salvo um byte devido a Elias Van Ootegem . Especificamente, a observação de que os dois seguintes são equivalentes:

$_=$_*3+1
$_*=3+1/$_

Embora tenha um byte a mais, ele salva dois bytes encurtando $_/2para apenas .5.

Uso da amostra:

$ echo 176 | perl -p collatz.pl
18

PHP 54 bytes

<?for(;1<$n=&$argv[1];$c++)$n=$n&1?$n*3+1:$n/2;echo$c;

A arquemesis de Javascript para o Wooden Spoon Award parece ter ficado um pouco aquém neste desafio. Porém, não há muito espaço para criatividade com esse problema. A entrada é tomada como um argumento de linha de comando.

Uso da amostra:

$ php collatz.php 176
18
primo
fonte
11
Levei um tempo para descobrir o que os suportes inigualáveis estão fazendo :)
marinus
11
Repetindo $_na ternário parece um desperdício, você pode raspar um outro personagem, usando *=como este: $\++,$_*=$_&1?3+1/$_:.5while$_>1}{. Multiplicando por 1/$_tem o mesmo efeito que +1, por isso $_*=3+1/$_funciona muito bem
Elias Van Ootegem
@EliasVanOotegem $_*=3+1/$_é brilhante, obrigado!
Primo
11

Mathematica (35)

If[#>1,#0@If[OddQ@#,3#+1,#/2]+1,0]&

Uso:

If[#>1,#0[If[OddQ@#,3#+1,#/2]]+1,0]&@16
>> 4
milhas
fonte
Não é uma função válida, 10,3 reclamar de um @ desonestos no final
CalculatorFeline
@ Está chamando o argumento, eu não sei por que ele estava lá, apenas uma edição rápida
milhas
Tem que ter cuidado :)
CalculatorFeline
10

Como normalmente faço, começarei as respostas com as minhas.

JavaScript, 46 44 caracteres (executado no console)

for(n=prompt(),c=1;n>1;n=n%2?n*3+1:n/2,++c)c
Maçaneta da porta
fonte
Qual é o objetivo de ~~ prompt () se você disse que a saída não importa se é um número não inteiro? Você pode salvar dois caracteres se livrando de ~~.
Resorath
@Resorath Ah, esqueci de fundição automático de JS: P graças
Doorknob
9

Java, 165, 156, 154.134.131.129.128 , 126 (as línguas detalhadas também precisam de um pouco de amor)

class a{public static void main(String[]a){for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y));}}

Tudo é feito dentro do para

for(int x=Short.valueOf(a[0]),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y))

Isso é um homem bonito. Graças a Pater Taylor !!!, e a idéia de usar um loop for foi roubada da ugoren

Substituí Inteiro por Curto.

jsedano
fonte
11
Você pode facilmente salvar o comprimento de i(,++y). Você pode salvar mais dois usando em <vez de ==.
Peter Taylor
@PeterTaylor você está certo, meus comparações será mais curta com <, mas eu não entendo a parte do pré-incremento
jsedano
2
Os dois lados do seu segundo ternário são estruturalmente idênticos; portanto, você pode inserir o ternário no primeiro argumento da chamada recursiva.
Peter Taylor #
11
OH MEU DEUS isso é brilhante
jsedano
2
Eu sei que tem sido cerca de 3,5 anos, mas você ainda pode golf-lo por 5 bytes : class a{public static void main(String[]a){for(int x=new Short(a[0]),y=0;x>1;System.out.println(++y))x=x%2<1?x/2:x*3+1;}}Alterações feitas: 1) Substituído Short.valueOf(...)com new Short(...)a -4 bytes e 2) eu coloquei o x=x%2<1?x/2:x*3+1;no corpo do for-loop para se livrar da vírgula para -1 byte .
Kevin Cruijssen
9

Rebmu : 28

u[++jE1 AeEV?a[d2A][a1M3a]]j

Em um problema tão breve e matemático, o GolfScript provavelmente vencerá um pouco por cento contra o Rebmu (se não for necessário dizer, leia arquivos da Internet ou gere arquivos JPG). No entanto, acho que a maioria concordaria que a lógica do Golfscript não é tão fácil de seguir e a pilha executável total em execução é maior.

Embora o criador de Rebol, Carl Sassenrath, tenha me dito que achou Rebmu "ilegível", ele está ocupado e não tem tempo para realmente praticar a transformação de porco-latino por meio de silêncio . Isso realmente é apenas transformado em:

u [
    ++ j
    e1 a: e ev? a [
        d2 a
    ] [
        a1 m3 a
    ]
]
j

Observe que o espaço era necessário para obter um a: em vez de um a . Este é um "conjunto de palavras!" e o avaliador percebe esse tipo de símbolo para acionar a atribuição.

Se fosse escrito em Rebol sem abreviação (ainda que de forma desajeitada), você obteria:

until [
    ++ j
    1 == a: either even? a [
        divide a 2
    ] [
        add 1 multiply 3 a
    ]
 ]
 j

Rebol, como Ruby, avalia blocos até seu último valor. O loop UNTIL é uma forma curiosa de loop que não possui condição de loop, apenas para de loop quando seu bloco é avaliado como algo que não é FALSO ou NENHUM. Portanto, no momento em que 1 ==o resultado da atribuição de A (o argumento para rebmu) ao resultado da condicional Collatz (ou é um IF-ELSE que avalia o ramo que ele escolhe) ... o loop é interrompido.

J e K são inicializados com o valor inteiro zero em Rebmu. E, como mencionado acima, a coisa toda é avaliada até o último valor. Portanto, uma referência J no final do programa significa que você obtém o número de iterações.

Uso:

>> rebmu/args [u[++jE1 AeEV?a[d2A][a1M3a]]j] 16
== 4
Dr. Rebmu
fonte
8

Repl de Python, 48

Não estou convencido de que não exista uma expressão mais curta do que n=3*n+1;n/=1+n%2*5;. Provavelmente encontrei uma dúzia de expressões diferentes do mesmo tamanho ...

i=0
n=input()
while~-n:n=3*n+1;n/=1+n%2*5;i+=1
i

editar: Encontrei outra solução que nunca será contestada, mas é divertida demais para não ser compartilhada.

s='s'
i=s
n=i*input()
while 1:
 while n==n[::2]+n[::2]:i+=s;n=n[::2]
 if n==s:i.rindex(s);break
 n=3*n+s
 i+=s
boothby
fonte
11
Meu cérebro está doendo agora.
Daniero
11
@daniero a segunda solução é apenas para você.
Boothby
Oh uau. Estou honrado!
Daniero
4
(n//2,n*3+1)[n%2]é mais curto.
Evpok
11
@ Evpok não n/2funcionaria tão bem quanto sabemos que é mesmo?
18716 george #
7

APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕
marinus
fonte
resposta antiga, ainda, 27:{1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2}
Uriel
11
{1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵}
ngn 16/01/19
7

J, 30 caracteres

<:#-:`(1+3&*)`]@.(2&|+1&=)^:a:

Acabou um pouco mais do que o desejado

uso:

   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:2
1
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:16
4
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:5
5
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:7
16
   <:#-:`(1+3&*)`]@.(2&|+1&=)^:a:27
111
  • -:`(1+3&*)`]é um gerúndio composto por três verbos, usado em três ocasiões. -:significa "reduzir pela metade" (1+3&*)ou (1+3*])codifica a etapa de multiplicação e ](identidade) ajuda ao término.

  • 2&|+1&=forma um índice para o gerúndio. literalmente, "o restante após a divisão por dois mais se é igual a um".

  • #verb^:a:itera a função até que o resultado seja estável (aqui, forçado explicitamente), enquanto coleta as etapas e as conta. Roubado de @JB . <:diminui a contagem de etapas em um para alinhar com os requisitos da pergunta.

John Dvorak
fonte
6
Sempre que vejo uma apresentação em J, conto os smilies. Este faz muito bem: <:, #-:, :`(, &*), =), )^:.
primo
3
@primo nice; quer a explicação deles? :-) <:significa "decremento" ou "menor ou igual", #significa "contagem de" ou "n vezes", -:significa "metade" ou "epsilon-igualdade", :`(significa por sua vez o final da referida "metade", o vínculo entre dois verbos em um gerúndio e um parêntese esquerdo (usado para agrupar). &*)significa "ligado à multiplicação" (3 ligado à multiplicação cria o operador "vezes três") e o fim do agrupamento. =realiza verificação de igualdade ou, no sentido unário, auto-classificação. ^:é a conjunção de poder (iteração verbal). Uma vez que um monte de verbos J terminar com dois pontos, ... :-)
John Dvorak
Anos depois ... Bloco de loop aprimorado: '- & 2 # (> & 1 * -: + 2 & | * +: +>: @ -:) ^: a:' -> -1 char. : P
randomra 26/01
Mais anos depois ... <:#a:2&(<*|+|6&*%~)19 bytes (-11)
milhas
6

Esquema Gambit, 106 98 caracteres, 40 parênteses

(let((f(lambda(x)(cond((= x 1) 0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))))(f(read)))

91 89 caracteres com define diretamente

(define(f x)(cond((= x 1)0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))(f(read))

Valentin CLEMENT
fonte
Eu não trabalho há muito tempo, mas tenho notado que geralmente as pessoas postam 1 resposta por linguagem de programação.
jsedano
Desculpe, eu não estava ciente de que :)
Valentin CLEMENT
Editado para remover o Python.
Valentin CLEMENT
11
Não é verdade! As pessoas tendem a postar uma resposta por linguagem de programação, mas é porque estão tentando não competir diretamente com outra pessoa com uma resposta mais curta. Mas ninguém vai reclamar se você postar uma resposta diferente no mesmo idioma.
breadbox
@breadbox não é verdade. Eu posto uma resposta por idioma se cada solução é interessante por si só em comparação com a outra. Se ambas as soluções são tão interessantes quanto as duas juntas (o mesmo algoritmo, sem truques de linguagem interessantes), eu as coloco como uma. Normalmente, não posto várias soluções porque escolho um idioma primeiro e depois resolvo o problema nesse idioma - então geralmente tenho preguiça de escrever o mesmo em um idioma diferente - ou embarco em uma jornada para aprender outra programação língua.
quer
6

PowerShell: 77 74 71 70 61

Código de golfe:

for($i=(read-host);$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x

Notas:

Inicialmente, tentei pegar a entrada do usuário sem forçá-la a um número inteiro, mas isso foi interrompido de uma maneira interessante. Quaisquer entradas ímpares seriam processadas incorretamente, mas mesmo as entradas funcionariam bem. Levei um minuto para perceber o que estava acontecendo.

Ao executar a multiplicação ou adição, o PowerShell trata a entrada não digitada como uma string primeiro. Portanto, '5'*3+1torna-se '5551' em vez de 16. As entradas pares se comportaram bem porque o PowerShell não tem uma ação padrão para divisão contra seqüências de caracteres. Mesmo as entradas pares que progrediriam com números ímpares funcionavam bem porque, quando o PowerShell chegou a um número ímpar no loop, a variável já era forçada a um número inteiro pelas operações matemáticas.

Obrigado a Danko Durbic por apontar que eu poderia simplesmente inverter a operação de multiplicação e não precisar converter read-hostpara int, pois o PowerShell baseia suas operações no primeiro objeto.

Dica do PowerShell Golfer: Para alguns cenários, como este, switchbate if/else. Aqui, a diferença era de 2 caracteres.

Protip cortesia de Danko Durbic : Para esse cenário em particular, uma matriz pode ser usada em vez de switch, para salvar mais 8 caracteres!

Não há verificação de erro para valores não inteiros ou números inteiros menores que dois.

Se você deseja auditar o script, coloque um ;$ipouco antes da última chave de fechamento no script.

Não sei exatamente o quão bem o PowerShell lida com números que evoluem para valores muito grandes, mas espero que a precisão seja perdida em algum momento. Infelizmente, também espero que não haja muito que possa ser feito sobre isso sem inchar seriamente o script.


Código não jogado, com comentários:

# Start for loop to run Collatz algorithm.
# Store user input in $i.
# Run until $i reaches 1.
# Increment a counter, $x, with each run.
for($i=(read-host);$i-ne1;$x++)
{
    # New $i is defined based on an array element derived from old $i.
    $i=(
        # Array element 0 is the even numbers operation.
        ($i/2),
        # Array element 1 is the odd numbers operation.
        (3*$i+1)
    # Array element that defines the new $i is selected by $i%2.
    )[$i%2]
}

# Output $x when the loop is done.
$x

# Variable cleanup. Don't include in golfed code.
rv x,i

Casos de teste:

Abaixo estão alguns exemplos com a auditoria ativada. Também editei a saída para maior clareza, adicionando rótulos à entrada e contagem final e colocando espaçamento para separar os valores de Collatz.

---
Input: 2

1

Steps: 1

---
Input: 16

8
4
2
1

Steps: 4

---
Input: 5

16
8
4
2
1

Steps: 5

---
Input: 7

22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 16

---
Input: 42

21
64
32
16
8
4
2
1

Steps: 8

---
Input: 14

7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 17

---
Input: 197

592
296
148
74
37
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 26

---
Input: 31

94
47
142
71
214
107
322
161
484
242
121
364
182
91
274
137
412
206
103
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 106

---
Input: 6174

3087
9262
4631
13894
6947
20842
10421
31264
15632
7816
3908
1954
977
2932
1466
733
2200
1100
550
275
826
413
1240
620
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Steps: 111

---
Input: 8008135

24024406
12012203
36036610
18018305
54054916
27027458
13513729
40541188
20270594
10135297
30405892
15202946
7601473
22804420
11402210
5701105
17103316
8551658
4275829
12827488
6413744
3206872
1603436
801718
400859
1202578
601289
1803868
901934
450967
1352902
676451
2029354
1014677
3044032
1522016
761008
380504
190252
95126
47563
142690
71345
214036
107018
53509
160528
80264
40132
20066
10033
30100
15050
7525
22576
11288
5644
2822
1411
4234
2117
6352
3176
1588
794
397
1192
596
298
149
448
224
112
56
28
14
7
22
11
34
17
52
26
13
40
20
10
5
16
8
4
2
1

Steps: 93
---

Bits interessantes sobre os números de entrada que não são dos casos de teste da pergunta:

Iszi
fonte
2
Agradável! Você ainda pode reduzi-lo um pouco, substituindo switchpor$i=(($i/2),($i*3+1))[$i%2]
Danko Durbić 30/11
2
Além disso, você não precisa converter read-hostpara número - basta alterar $i*3para 3*$i.
Danko Durbić 30/11
Uma matriz em vez de mudar? Brilhante! E trocando $i*3- por que eu não pensei nisso já?
Iszi
11
param($i)for(;$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x- troque o host de leitura por um parâmetro, para obter 56 bytes . Link Try It Online
TessellatingHeckler
6

80386 montagem, 16 bytes

Este exemplo usa a sintaxe da AT&T e a convenção de chamada de chamada rápida, o argumento entra em ecx:

collatz:
        or $-1,%eax              # 3 bytes, eax = -1;
.Loop:  inc %eax                 # 1 byte,  eax += 1;
        lea 1(%ecx,%ecx,2),%edx  # 4 bytes, edx = 3*ecx + 1;
        shr %ecx                 # 2 bytes, CF = ecx & 1;
                                 #          ecx /= 2;
                                 #          ZF = ecx == 0;
        cmovc %edx,%ecx          # 3 bytes, if (CF) ecx = edx;
        jnz .Loop                # 2 bytes, if (!ZF) goto .Loop;
        ret                      # 1 byte,  return (eax);

Aqui estão os 16 bytes resultantes do código da máquina:

83 c8 ff 40 8d 54 49 01 d1 e9 0f 42 ca 75 f4 c3
FUZxxl
fonte
6

Braquilog , 16 bytes

1b|{/₂ℕ|×₃+₁}↰+₁

Experimente online!

Explicação

         Either:
  1        The input is 1.
  b        In which case we unify the output with 0 by beheading the 1
           (which removes the leading digit of the 1, and an "empty integer"
           is the same as zero).
|        Or:
  {        This inline predicate evaluates a single Collatz step on the input.
           Either:
    /₂       Divide the input by 2.
    ℕ        And ensure that the result is a natural number (which is
             equivalent to asserting that the input was even).
  |        Or:
    ×₃+₁     Multiply the input by 3 and add 1.
  }
  ↰        Recursively call the predicate on this result.
  +₁       And add one to the output of the recursive call.

Uma solução alternativa na mesma contagem de bytes:

;.{/₂ℕ|×₃+₁}ⁱ⁾1∧

Experimente online!

;.          The output of this is a pair [X,I] where X is the input and
            I will be unified with the output.
{/₂ℕ|×₃+₁}  This is the Collatz step predicate we've also used above.
ⁱ⁾          We iterate this predicate I times on X. Since we haven't actually
            specified I, it is still a free variable that Brachylog can backtrack
            over and it will keep adding on iterations until the next
            constraint can be satisfied.
1           Require the result of the iteration to be 1. Once this is
            satisfied, the output variable will have been unified with
            the minimum number of iterations to get here.
∧           This AND is just used to prevent the 1 from being implicitly
            unified with the output variable as well.
Martin Ender
fonte
5

GolfScript (23 caracteres)

~{.1&{.3*)}*.2/.(}do;],

Teste online

Peter Taylor
fonte
5

F # - 65 caracteres

let rec c n=function 1->n|i->c(n+1)(if i%2=0 then i/2 else i*3+1)
Daniel
fonte
5

Python 68 58 54 52 caracteres

f=lambda n:1+(n-2and f((n/2,3*n+1)[n%2]));f(input())

Obrigado a Bakuriu e boothby pelas dicas :)

Valentin CLEMENT
fonte
Você pode usar n%2and 3*n+1or n/2para salvar 5 caracteres. Também em python2, você pode remover a chamada para int, reduzindo o tamanho para 58 bytes.
Bakuriu 3/08/13
Oh, você pode até obter mais curto do que isso: [n/2,3*n+1][n%2].
usar o seguinte comando
Isso é bacana!
Valentin CLEMENT
Este python é 2.7? Eu recebo um erro no Python 3.5.1? unsupported operand type(s) for -: 'str' and 'int'
george
5

Retina , 43 bytes

11
2
(2+)1
$1$1$0$0$0$0
2.*
$0x
)`2
1
1?x
1

Recebe e imprime a saída em unário.

Cada linha deve ir para seu próprio arquivo. 1 byte por arquivo extra adicionado à contagem de bytes.

Você pode executar o código como um arquivo com o -ssinalizador Por exemplo:

> echo -n 1111111|retina -s collatz
1111111111111111

O algoritmo é um loop de executar uma etapa Collatz com o número unário e adicionar um novo marcador de etapa xno final da string, se o número não for 1.

Quando o loop termina 1, convertemos os marcadores em um número unário (removendo o primeiro 1) que é a saída desejada.

randomra
fonte
5

Gelatina , não concorrente

12 bytes Esta resposta não é competitiva, pois o desafio antecede a criação do Jelly.

×3‘$HḂ?ß0’?‘

Experimente online!

Como funciona

×3‘$HḂ?ß0’?‘  Main link. Argument: n (integer)

     Ḃ?       Yield the last bit of n is 1:
   $            Evaluate the three links to the left as a monadic chain:
×3                Multiply n by 3.
  ‘               Increment the product by 1.
    H           Else, halve n.
         ’?   If n-1 is non-zero:
       ß        Recursively call the main link.
        0     Else, yield 0.
           ‘  Increment the result by 1.
Dennis
fonte
4

dc, 27 caracteres

Aplicando a magia negra de boothby :

?[d3*1+d2%5*1+/d1<x]dsxxkzp

Não tenho muita certeza se entendo como - ou isso - funciona.

Uso:
$ dc collatz.dc <<< 7
16

dc, 36 caracteres

Minha própria criação; uma abordagem um pouco mais tradicional, mesmo que eu tenha que lidar bastante com o idioma para superar a falta de uma elseparte das ifdeclarações:

?[2/2Q]se[dd2%[0=e3*1+]xd1<x]dsxxkzp

Internamente, ele produz todos os números da sequência e os armazena na pilha, depois abre a final 1e exibe a altura da pilha.

daniero
fonte
11
Paridade não é magia negra.
Boothby
11
Não, mas é um truque muito legal lá! Na verdade, eu mesmo fiz coisas semelhantes, mas não pensei nisso neste caso. O que me surpreendeu por um segundo foi a divisão, mas entendi: você divide por seis, revertendo a primeira operação (* = 3, + = 1) pela segunda se a paridade estiver errada e, por causa da divisão inteira, a adição será também, e basicamente fizemos / = 2. Muito inteligente :)
daniero
11
+1. Eu pensei que iria esmagar esse desafio com dc, mas só chegava a 40. Eu vi sua resposta 27. Ah bem.
Digital Trauma
Eu não tinha visto esse desafio, mas escrevi um tempo atrás sobre como imprimir a sequência Collatz em DC. Minha abordagem é semelhante à sua, mas perde por um byte, então não vejo realmente um motivo para publicá-la. No entanto, quando eu olhava a minha para ver como é fácil passar de uma etapa para outra, imprimi o número de etapas, vi algo que pode obter um byte da sua ... Como a sequência Collatz sempre passa de 2 para 1, você pode alterar sua condição 2<xe se livrar da k. Apenas no caso de você querer um byte de volta depois de quatro anos. : D
brhfl 25/08
4

brainfuck , 59 56 bytes

,-[<->[[>]+<[-<]>>]>[-<<[++>+<]>->]<<[+>+++<]<<+>>>]<<<.

Experimente online! (Ligeiramente modificado para facilitar o uso)

Entrada e saída como códigos de caracteres. Isso é mais útil com células de tamanho arbitrário, mas ainda pode funcionar com valores pequenos em tamanhos limitados de célula.

Como funciona

Tape Format:
Counter 0 Copy Number Binary...
^End           ^Start

,-[ Get input, decrement by 1 and start loop
  <->                  Initialises the copy of the value at -1
  [[>]+<[-<]>>]        Converts the input to binary while preserving a negative copy
  <+>>[-<<[++>+<]>->] If the last digit of the binary is 1 (n-1 is odd), divide by 2 and decrement
  <<[+>+++<]            If the last digit of the binary is 0 (n-1 is even), multiply by 3
  <<+>>>               Increment counter and end on n-1
]<<<.                 End loop and print counter
Brincadeira
fonte
4

Hexagonia , 48 44 bytes

?(]$_)"){{?{*')}/&!/={:<$["/>&_(.<@2'%<>./>=

Experimente online!

Expandido:

     ? ( ] $ _
    ) " ) { { ?
   { * ' ) } / &
  ! / = . { < $ [
 " / > & _ ( . < @
  2 ' % < > : / >
   = . . . . . .
    . . . . . .
     . . . . .

Note que isso falha 1por uhh ... razões . Honestamente, não tenho mais certeza de como isso funciona. Tudo o que sei é que o código para números ímpares é executado ao contrário para números pares? De alguma forma?

A nova versão é muito mais limpa que a anterior, mas possui mais algumas direções em comparação e também termina em um erro de divisão por zero. O único caso em que não ocorre erro é quando ele realmente lida 1corretamente.

Brincadeira
fonte
If a number < 2 is input ... output does not matter.: o)
Sok
@ Sok Sim, é por isso que eu postei em vez de ficar louco tentando consertar isso #
Jo King
3

C, 70 69 caracteres

Muito simples, sem truques.
Lê a entrada de stdin.

a;
main(b){
    for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
    printf("%d",a);
}
Ugoren
fonte
3

Q, 46

{i::0;{x>1}{i+:1;$[x mod 2;1+3*x;(_)x%2]}\x;i}
tmartin
fonte
32 bytes com(#)1_(1<){(1+3*x;x%2)0=x mod 2}\
streetster
3

Ruby 1.9, 49 caracteres

Rubyfied resposta Python de Valentin CLEMENT , usando a sintaxe lambda stabby. Sqeezed-lo em uma declaração para ilegibilidade adicional.

(f=->n{n>1&&1+f[[n/2,3*n+1][n%2]]||0})[gets.to_i]

Algumas sobrecargas porque Ruby, ao contrário do Python, não está feliz em misturar números com booleanos.

daniero
fonte
3

C ++ ( 51 48)

Esta é uma função recursiva que faz isso; a leitura de entrada vem separadamente.

int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}

Tenho certeza de que posso fazer algum tipo de truque "e / ou" com as == 0coisas, mas não tenho idéia de como.

Joe Z.
fonte
Você pode remover ==0e trocar os lados do condicional.
Maçaneta da porta
Além disso, não há necessidade de lidar n==1porque eu especificado na pergunta que o número é sempre maior do que 1
Doorknob
O problema é que n==1é o caso de recursão base. Colocar n==2lá não melhoraria a pontuação.
Joe Z.
Ah, então você pode simplesmente substituí-lo com esta: return~-n?e trocar os lados condicionais
Doorknob
. n==1== n<2.
CalculatorFeline
3

~ - ~! (Sem comentários) - 71 53

Obviamente, essa linguagem não é a melhor para o golfe, pois falta uma grande quantidade de funcionalidades nativas, mas essa é a beleza dela.

'=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:

Primeiro, defina '''como sua entrada. A função ''pode ser chamada com %a entrada e retornará a resposta, da seguinte maneira:

'''=~~~~~:''&%:

Isso retornará ~~~~~. Na verdade, ele funciona para n==1(faz um loop para sempre n==0).

Como sempre com esse idioma, não testado.

cjfaure
fonte
3

JavaScript (ES6) - 29 caracteres

f=x=>x>1?f(x%2?x*3+1:x/2)+1:0

Cria uma função fque aceita um único argumento e retorna o número de iterações.

JavaScript - 31 caracteres

for(c=0;n>1;n=n%2?n*3+1:n/2)++c

Assume que a entrada está na variável ne cria uma variável cque contém o número de iterações (e também será exibida cno console como o último comando).

MT0
fonte
11
28 bytes
Shaggy
3

Perl 6, 40 bytes

Método da função recursiva, conforme Valentin CLEMENT e daniero : 40 caracteres

sub f(\n){n>1&&1+f n%2??3*n+1!!n/2}(get)

Método da lista preguiçosa: 32 caracteres

+(get,{$_%2??$_*3+1!!$_/2}...^1)
Mouq
fonte
3

> <>, 27 26 23 bytes

\ln;
\::2%:@5*1+2,*+:2=?

Como as outras respostas, <<>, isso cria a sequência na pilha. Quando a sequência atinge 2, o tamanho da pilha é o número de etapas executadas.

Graças a @Hohmannfan, economizamos 3 bytes por um método muito inteligente de calcular diretamente o próximo valor. A fórmula usada para calcular o próximo valor na sequência é:

f(n)=n5(nmod2)+12+(nmod2)

A fração mapeia números pares para 0,5 e números ímpares para 3. Multiplicando ne adicionando n%2conclui o cálculo - não é necessário escolher o próximo valor!

Edit 2: Aqui está a versão pré- @ Hohmannfan:

\ln;
\:::3*1+@2,@2%?$~:2=?

O truque aqui é que ambos 3n+1e n/2são computados em cada etapa da sequência, e aquele a ser descartado da sequência é escolhido posteriormente. Isso significa que o código não precisa ramificar até que 1 seja alcançado e o cálculo da sequência pode residir em uma linha de código.

Edit: Golpeou outro caractere depois de perceber que o único número inteiro positivo que pode levar a 1 é 2. Como a saída do programa não importa para a entrada <2, a geração da sequência pode terminar quando 2 for atingido, deixando o tamanho da pilha sendo o número exato de etapas necessárias.

Versão anterior:

\~ln;
\:::3*1+@2,@2%?$~:1=?
Sok
fonte
11
Você pode jogar até 23 se abrir a segunda linha ainda mais:\::2%:@5*1+2,*+:2=?
Hohmannfan 14/12