The following problem was posed to me by a friend:
Given a number print out all sequences that begin with 0 and end at where the difference between any two adjacent terms in a sequence is a non-negative power of 2.
For example, the possible sequences for $N = 4$ are:
- 0, 1, 2, 3, 4
- 0, 1, 2, 4
- 0, 1, 3, 4
- 0, 2, 3, 4
- 0, 2, 4
- 0, 4
This is the time where you should stop and see if you can come up with a solution.
The first approach you might consider is to just brute force it but this will definitely lead to a suboptimal solution.
Instead, a recursive approach can be used. The first thing to note is that every sequence begins with and is non-decreasing, so we can effectively disregard this term. The next key step comes from the following question: suppose you are finding the solutions for some and you have already calculated a valid sequence up to . How many valid sequences are possible given that you have already reached ?
In fact, it is exactly the number of sequences that start at and go up to $N-m$ under the same conditions as before. This means, if we have already computed all of the sequences for each value , we can simply append the appropriate set of sequences to our current one after removing the term and performing an offset calculation. For the offset, we increment each term in the sequence by .
Here is a worked example:
Suppose we want to know all of the solutions for and we have reached the point in the computation where we have generated the sequence . Now we need to get from to with the difference between each pair of consecutive terms being a power of . The possible sequences are:
- 0, 1, 3, 4, 5, 6, 7
- 0, 1, 3, 4, 5, 7
- 0, 1, 3, 4, 6, 7
- 0, 1, 3, 5, 6, 7
- 0, 1, 3, 5, 7
- 0, 1, 3, 7
which correspond exactly to the sequences that we found for the example of . For example, the sequence 0, 1, 3, 5, 7 is constructed by taking the sequence 0, 2, 4, removing the 0, and offsetting it by 3 before appending it to the already constructed sequence 0, 1, 3.
Now we only need to know how to generate the initial sequences and then we can recursively solve this problem. Each sequence must start with 0, so the next number has to be a power of 2. Thus, we can just generate all of the sequences where and then recursively solve the problem.
Here is a snippet of Python code that solves the problem recursively:
Unfortunately, this will run into a common problem with recursive algorithms. If I compute the answer for the subproblem and need it again later, I have to compute it all over again since it is never stored. There are several ways of solving this problem (namely caching), so here we will present a dynamic programming solution.
Instead of recursively calling our procedure every time we need the answer to a subproblem, we can iteratively build up all of the subproblems from 1 to and call them as necessary.
So, given , we construct all solutions for in order, and whenever we need to use a previously computed answer, we simply look it up in some table.
We can verify our results by checking the length of the output for matches in A023359 from the OEIS.