### April 24, 2018

Today’s exercise is a game that mathematicians play; it comes from /u/HarryPotter5777 on Reddit:

You are given a pair of integers. You make a sequence of steps in which one member of the pair is doubled and the other is incremented by one. Your goal is to find a sequence in which the two members of the pair are equal. For instance, the sequence (1 8), (2 9), (4 10), (5 20), (10 21), (11 42), (22 43), (44 44) ends with the two numbers equal, so (1 8) is a valid starting pair.

The question is whether or not it is always possible to find a sequence, regardless of the starting pair, which makes the two numbers equal. /u/shouldertarget gives a hand-waving explanation that the answer is “Yes” later in the Reddit thread mentioned above.

Your task is to write a program that, given a starting pair, derives a sequence that makes the two numbers equal. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Since this is a coding side, I wrote code rather than find a theoretic mathematical solution. So in Python a brute-force solution using generators. So far found solutions for all tuples up until (10,10). I recon with dynamic programming, this solution can be made very efficiently.

Example output:

—- 2 5 —-

(12, 12, [‘r’, ‘l’, ‘l’])

So (12,12) is found by applying:

– r: times 2 right (plus 1 left) = (3,10)

– l: times 2 left (plus 1 right) = (6,11)

– l: times 2 left (plus 1 right) = (12,12)

from collections import deque

def find_seq(x, y):

table = {}

dq = deque([(x, y, None, None)])

while dq:

x, y, px, py = dq.popleft()

table[(x, y)] = (px, py)

if x == y:

path = []

while x and y:

path.append((x, y))

x, y = table[(x, y)]

return path[::-1]

else:

table[(x, y)] = (px, py)

dq.append((2

x, y + 1, x, y))y, x, y))dq.append((x+1, 2

return None

print(find_seq(1, 8))

Perl6 solution that caches similar to PowerShell’s solution:

Here’s a solution in C++11.

Example Usage:

Here’s a solution in C.

Example:

Line 54 in my C code above should be replaced with the following code. Otherwise the first step is sometimes omitted from the output.

Here’s a solution in racket: