Collatz Paths: Forwards and Backwards along the Collatz Conjecture

Question

The Collatz conjecture is a very well-known conjecture. Take a positive integer; if it's even, divide by 2, else, multiply by 3 and add 1. Repeat until you reach 1 or something else happens. The conjecture is that this process always reaches 1.

You can also reverse the process. Start at 1, multiply by 2, and to branch to multiply by 3 and add 1 numbers, when you reach an even number that is 1 (mod 3), subtract 1 and divide by 3.

A Collatz path combines the two, trying to get from one number to another with those four operations.

For example, to get to 20 from 1:

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

You can also get to 3 from 10 by subtracting 1 and dividing by 3.

With these tools, you can traverse a Collatz path from one number to another. For example, the path from 20 to 3 is (divide by 2), (subtract 1, divide by 3).

In short, the available operations are:

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

Note: not all Collatz paths are short. a(7,3) could run

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

but a shorter path is

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

The Challenge

Find the length of the shortest Collatz path between any two positive integers, p and q.

• Input is any two positive integers less than 2^20 to avoid integer overflow. The input method is left to the discretion of the golfer. The integers may be the same, in which case, the length of the Collatz path is 0.
• Output should be one integer, denoting the length of the shortest Collatz path between p and q.

Test Cases

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

Many thanks to orlp for their help in clarifying this challenge.

As always, if the problem is unclear, please let me know. Good luck and good golfing!

Answer 1

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]

I did not expect that my original version was so much more golfable, this is also the work of @nimi @Lynn and @Laikoni!

Thanks @Laikoni for a byte, @Lynn for 11 14 20 21 bytes, @nimi for 8 bytes!

This expands the the tree of visited numbers (beginning by a) step by step, and checks in each step whether we arrived at the given number b.

Answer 2

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

Answer 3

Pyth, 30 bytes

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

Try it online

How it works

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is [1, 2] or [2, 1], which we special-case.

  *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

Answer 4

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

Since a Collatz path can be imagined as a(1,p) and a(1,q) conjoined at the first number that is common to both sequences and a(1,n) is the original Collatz conjecture, this function calculates the Collatz sequence of p and q, and calculates the length from there. This isn't a pretty golf, so golfing suggestions are very much welcome. The only exception is when p or q == 1. Then, since we can skip directly from 4 to 1 as opposed to a regular Collatz sequence, we need to subtract a step from the result.

Edit: Lots of bug fixing.

Edit: Lots and lots of bug fixing

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

Try it online!

Answer 5

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]

Performs a breadth-first search. x is the starting number, y the destination, a an array of trial values, s an array of the number of inclusive steps on the chain from x, z the current value. If z and y are not equal, compute z*2, z/2 and either z*3+1 or (z-1)/3, depending on whether z is odd or even, then filter out fractions and previously seen values and add them to the search list.

Answer 6

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

Take the length of the symmetric difference of the two forward Collatz sequences starting at the two input numbers and ending at 2. The only exception is if the input is 1, 2 or 2, 1, which we special-case.