# Collatz Paths: Forwards and Backwards along the Collatz Conjecture

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!

• Our computers wouldn't endure an array of at least 2^31 elements.
– user54200
Aug 4, 2016 at 8:59
• @MatthewRoh Challenge has since been edited. Aug 4, 2016 at 9:02
• This is pretty much a graph-theory path-finding challenge. And I'm pretty sure we had a almost identical one before. Aug 4, 2016 at 9:18
• Possible duplicate of Shortest paths in a divisor graph Aug 4, 2016 at 9:18
• @flawr I don't agree with the duplicate. Yes, both challenges want to find a path in a graph, but the graphs are different, and encoding the graph structure in your answer is the unique part, IMO. See for example my answer, and compare it to the answers in your 'duplicate' question.
– orlp
Aug 4, 2016 at 9:28

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

• You missed one space: iterate s [a] -> iterate s[a] Aug 4, 2016 at 11:18
• Sweet~ Inlining s saves three more bytes! iterate(nub.concat.map f)[a] Also, do you really need the nub?
– Lynn
Aug 4, 2016 at 12:27
• Tell me when you're finished golfing:D Thank you very much. Unfortunately I'm still have trouble understanding monads. Aug 4, 2016 at 12:36
• @nimi Again, thank you very much, I never expected that it is so much more golfable! I didn't know about break and span, really useful! Aug 4, 2016 at 16:31
• Replacing [div n 2,n*3+1]!!mod n 2 with cycle[div n 2,n*3+1]!!n saves one more byte :)
– Lynn
Aug 4, 2016 at 18:34

# 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


# 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


# Python 2, 156179191209181172177 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!

• Your approach does not work, e.g. a(3,1) returns 7 while it should return 6, as the shortest path is 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1 Aug 4, 2016 at 10:46
• @flawr Edited. Hopefully it works now Aug 4, 2016 at 11:51
• Why do you assume that the algorithm you described works? Couldn't a shortest path consist of multiple times going "back and forth"? Aug 4, 2016 at 11:54
• Let f denote a step forward, b a step backward in the collatz sequence. The pattern b->f cannot be in a shortest path, as it is the identity (f is undoing b in any case.) So the shortest path can only consist of patterns f->f, f->b and b->b. That means again that the shortest path is always of the form f->f->...->f or b->b->...->b or f->...->f->b->...->b Aug 4, 2016 at 13:02
• PS: I have the impression your byte count is going in the wrong direction. :D Aug 4, 2016 at 13:08

## JavaScript (ES6), 135 bytes

f=(x,y,a=[(s=[],s=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.

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