This was inspired by a math problem I saw somewhere on the internet but do not remember where (UPDATE: The original problem was found on the math riddles subreddit with a proof provided that it is possible, also see this Math SE post), asking for a proof if the following process is possible for any arbitrary pair of integers (from what I remember, it was possible for any given pair):
Given a pair of integers, j and k, double one of them and add one to the other, resulting in a pair of new integers, i.e., (j, k) -> (j+1, k*2) or (j*2, k+1). Then repeat this process with those integers, with the objective of having the pair of integers be equal.
These given examples are not necessarily optimal but show how this process can be done on any integers, positive, negative or zero:
(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)
(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)
(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)
(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)
(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)
Challenge
Create a program that given two integers, outputs the list of steps required to make those integers equal by repeatedly incrementing one and doubling the other
Specifications
- The solution does not have to be optimal but it must solve in a finite number of steps for any arbitrary pair
Input must be two integers
Output may be any reasonable output that clearly denotes the resulting integers of each step, for example:
- a string with two distinct delimiters (any symbol, whitespace, etc), one for each integer in a pair and one for each pair
- e.g., input j, k: 2, 5 -> output: 3,10;6,11;12,12
- a list of lists of integers
- e.g. input j, k: 2, 5 -> output: [[3, 10], [6, 11], [12, 12]]
- a string with two distinct delimiters (any symbol, whitespace, etc), one for each integer in a pair and one for each pair
If the input is a pair of equal numbers, you may output anything as long as it's consistent with other nontrivial answers
- for example
- if input [2, 5] has output [[3, 10], [6, 11], [12, 12]], which does not include the input pair, then input [4, 4] should output nothing.
- if input [2, 5] has output [[2, 5], [3, 10], [6, 11], [12, 12]], which does include the input pair, then input [4, 4] should output [[4, 4]].
- for example
Standard IO methods apply and standard loopholes banned
This is code golf so shortest answer in bytes wins
[(12,12),(6,11),(3,10),(2,5)]
for input(2,5)
? \$\endgroup\$