A conjectura de Collatz é uma conjectura muito conhecida. Pegue um número inteiro positivo; se for par, divida por 2; caso contrário, multiplique por 3 e adicione 1. Repita até chegar 1ou algo acontecer. A conjectura é que esse processo sempre alcança 1.

Você também pode reverter o processo. Comece em 1, multiplique por 2 e ramifique para multiply by 3 and add 1números, quando atingir um número par 1 (mod 3), subtraia 1 e divida por 3.

Um caminho Collatz combina os dois, tentando passar de um número para outro com essas quatro operações.

Por exemplo, para ir 20de 1:

1     *2
2     *2
4     *2
8     *2
16    *2
5     (-1)/3
10    *2
20    *2

Você também pode obter a 3partir 10subtraindo 1 e dividindo por 3.

Com essas ferramentas, você pode percorrer um caminho Collatz de um número para outro. Por exemplo, o caminho de 20para 3é (dividir por 2), (subtrair 1, dividir por 3).

Em resumo, as operações disponíveis são:

n * 2       always
n // 2      if n % 2 == 0
n * 3 + 1   if n % 2 == 1
(n-1) // 3  if n % 6 == 4

Nota: nem todos os caminhos da Collatz são curtos. a(7,3)poderia correr

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

mas um caminho mais curto é

7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 3

O desafio

Encontre o comprimento do caminho Collatz mais curto entre dois inteiros positivos pe q.

• Entrada é dois inteiros positivos menores que 2^20para evitar o excesso de números inteiros. O método de entrada é deixado a critério do jogador de golfe. Os números inteiros podem ser os mesmos; nesse caso, o comprimento do caminho da Collatz é 0.
• A saída deve ser um número inteiro, indicando o comprimento do caminho Collatz mais curto entre pe q.

Casos de teste

a(2,1)
1

a(4,1)
1         # 4 -> 1

a(3,1)
6         # 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1

a(11,12)
11        # 11 -> 34 -> 17 -> 52 -> 26 -> 13
          # -> 40 -> 20 -> 10 -> 3 -> 6 -> 12

a(15,9)
20        # 46 -> 23 -> 70 -> 35 -> 106 -> 53 -> 160 -> 80 -> 40 -> 13
          # -> 26 -> 52 -> 17 -> 34 -> 11 -> 22 ->  7 -> 14 -> 28 -> 9

Muito obrigado ao orlp por sua ajuda no esclarecimento deste desafio.

Como sempre, se o problema não estiver claro, entre em contato. Boa sorte e bom golfe!

Haskell, 170 158 157 146 143 137 135 112 109 108 106 100 99 bytes

a!b=length$fst$break(elem b)$iterate(>>= \n->2*n:cycle[div n 2,n*3+1]!!n:[div(n-1)3|mod n 6==4])[a]

Eu não esperava que minha versão original fosse muito mais jogável, esse também é o trabalho de @nimi @Lynn e @Laikoni!

Obrigado @Laikoni por um byte, @Lynn por 11 14 20 21 bytes, @nimi por 8 bytes!

Isso expande a árvore dos números visitados (começando por a) passo a passo e verifica em cada passo se chegamos ao número especificado b.

Python 2, 110 bytes

a=lambda p,q,s={0}:1+a(p,q,s.union(*({p,n*2,[n/2,n*3+1][n%2]}|set([~-n/3]*(n%6==4))for n in s)))if{q}-s else-1

Pitão, 30 bytes

|q*FQ2ls-M.pm.u&n2N?%N2h*3N/N2

Experimente online

Como funciona

Tome o comprimento da diferença simétrica das duas sequências Collatz para frente, começando nos dois números de entrada e terminando em 2. A única exceção é se a entrada for [1, 2]or [2, 1], ou qual caso especial.

  *FQ                        product of the input
|q   2                       if that equals 2, return 1 (True), else:
            m                  map for d in input:
             .u                  cumulative fixed-point: starting at N=d, iterate N ↦
               &n2N?%N2h*3N/N2     N != 2 and (N*3 + 1 if N % 2 else N/2)
                                 until a duplicate is found, and return the sequence
          .p                   permutations
        -M                     map difference
       s                       concatenate
      l                        length

Python 2, 156 179 191 209 181 172 177 171 bytes

Como um caminho Collatz pode ser imaginado como a(1,p)e a(1,q)conjugado no primeiro número comum a ambas as seqüências e a(1,n)é a conjectura original de Collatz, essa função calcula a sequência Collatz de pe qe calcula o comprimento a partir daí. Como o golfe não é bonito, sugestões de golfe são muito bem-vindas. A única exceção é quando p or q == 1. Então, como podemos pular diretamente de 4para 1, ao contrário de uma sequência Collatz regular, precisamos subtrair um passo do resultado.

Edit: Muita correção de bugs.

Editar: Muitas e muitas correções de bugs

f=lambda p:[p]if p<3else f([p//2,p*3+1][p%2])+[p]
def a(p,q):
 i=1;c=f(p);d=f(q)
 if sorted((p,q))==(1,2):return 1
 while c[:i]==d[:i]!=d[:i-1]:i+=1
 return len(c+d)-2*i+2

Experimente online!

JavaScript (ES6), 135 bytes

f=(x,y,a=[(s=[],s[0]=s[x]=1,x)],z=a.shift())=>z-y?[z*2,z/2,z%2?z*3+1:~-z/3].map(e=>e%1||s[e]?0:s[a.push(e),e]=-~s[z])&&f(x,y,a):~-s[y]

Executa uma pesquisa pela primeira vez. xé o número inicial, yo destino, auma matriz de valores de teste, suma matriz do número de passos incluído na cadeia de x, zo valor actual. Se ze ynão são iguais, computação z*2, z/2e quer z*3+1ou (z-1)/3, dependendo se zé par ou ímpar, então filtrar frações e valores vistos anteriormente e adicioná-los à lista de pesquisa.

Python 2, 80 bytes

p=lambda n:n-2and{n}|p([n/2,n*3+1][n%2])or{n}
lambda m,n:m*n==2or len(p(m)^p(n))

Tome o comprimento da diferença simétrica das duas seqüências Collatz para frente, começando nos dois números de entrada e terminando em 2. A única exceção é se a entrada for 1, 2 ou 2, 1, o que nós especializamos.