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 ⁶⁰ , 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

GolfScript, 24 23 21 20 18 caracteres

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

Assume a entrada em stdin. Teste online

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

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

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

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

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.

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

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

APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕

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.

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

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:

• 14e 197são números Keith
• 31é um Mersenne Prime
• 6174é a constante de Kaprekar
• E, finalmente, eu apenas gosto 8008135. E Numberphile , obviamente.

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

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.

GolfScript (23 caracteres)

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

Teste online

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)

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 :)

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.

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.

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.

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

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

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.

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);
}

Q, 46

{i::0;{x>1}{i+:1;$[x mod 2;1+3*x;(_)x%2]}\x;i}

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.

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.

~ - ~! (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.

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

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)

> <>, 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 é:

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=?