Collatz Conjecture related interview

Question

This was an interview question, which seems related to Project Euler Problem 14

Collatz conjecture says that if you do the following

If n is even, replace n by n/2.
If n is odd, replace n by 3n+1.

You ultimately end up with 1.

For instance, 5 -> 16 -> 8 -> 4 -> 2 -> 1

Assuming the conjecture is true, each number has a chain length: The number of steps required to get to 1. (The chain length of 1 is 0).

Now, the problem is given natural numbers n, m and a natural number k, give an algorithm to find all numbers between 1 and n, such that the chain length of those numbers is <= k. There is also the restriction that the chain of any of those numbers must only include numbers between 1 and m (i.e. you cannot go over m).

An easy way is to brute-force it out, and combine that with memoization.

The interviewer said there was an O(S) time algorithm, where S is the number of numbers we need to output.

Does anyone know what it could be?

Answer 1

I think you can solve this in O(S) by running the process backwards. If you know what k is, then you can build up all of the numbers that halt in at most k steps using the following logic:

• 1 has a chain of length 0.
• If a number z has a chain of length n, then 2z has a chain of length n + 1.
• If a number z has a chain of length n, z - 1 is a multiple of three (other than 0 or 3), and (z - 1)/3 is odd, then (z - 1) / 3 has a chain of length n + 1.

From this, you can start building up the numbers in the sequence starting at 1:

                  1
                  |
                  2
                  |
                  4
                  |
                  8
                  |
                  16
                  | \
                  32 \
                  |   5
                  64  |
                 /|   10
                / 128 | \
               21     20 3

We could do this algorithm using a work queue storing numbers we need to visit and the lengths of their chains. We populate the queue with the pair (1, 0), then continuously dequeue an element (z, n) from the queue and enqueue (2z, n + 1) and (possibly) ((z - 1) / 3, n + 1) into the queue. This is essentially doing a breadth-first search in the Collatz graph starting from one. When we find the first element at depth k, we stop the search.

Assuming that the Collatz conjecture holds true, we'll never get any duplicates this way. Moreover, we'll have found all numbers reachable in at most k steps this way (you can quickly check this with a quick inductive proof). And finally, this takes O(S) time. To see this, note that the work done per number generated is a constant (dequeue and insert up to two new numbers into the queue).

Hope this helps!