51
6
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
13This is a nice first challenge, BTW. Welcome to PPCG! – Arnauld – 2018-05-03T14:55:05.913
@Arnauld Thank you! Also thanks for pointing the error out, I did all the examples by hand and really should implement a solution myself first – JMigst – 2018-05-03T15:05:00.810
Can the output be in reverse? E.g.
[(12,12),(6,11),(3,10),(2,5)]
for input(2,5)
? – Laikoni – 2018-05-03T15:08:44.0231@Laikoni Considering all the steps required are still outputted, I think it's fine – JMigst – 2018-05-03T15:15:06.377
Can it be the case that the two input numbers are the same? If so, maybe add an example with that – Luis Mendo – 2018-05-03T15:40:39.043
@LuisMendo I think since it's trivial, as long as the output is consistent with nontrivial answers, it's fine. I'll add that to the post – JMigst – 2018-05-03T16:08:07.650
Is it fine to output a list of the type of each step, instead of the result of each step? – miles – 2018-05-03T23:18:00.160
@miles The type of step as in if you're doubling the j or k? I think since there are already solutions to this and they all output the result of each step, then it should be consistent. I'll add it to the post as well – JMigst – 2018-05-03T23:25:11.943
double one of them and add one to the other,
I initially read "add one to the other" as meaning "add them together". – Flater – 2018-05-04T08:21:50.087Just to be on the safe side, you should point out that it is always possible to reach the state of both integers being equal. I would even suggest a proof, but that likely involves using some concrete, simple algorithm which always works, and that ruins part of the challenge. – Arthur – 2018-05-04T12:47:32.573
@Arthur, if there's a "concrete, simple algorithm which always works", there's no guarantee that it's minimal. – Peter Kagey – 2018-05-04T20:42:34.073
@PeterKagey I'm no golfer, but the simpler algorithms are usually shorter implemented. Sure, the one I have in mind might not be optimal, especially not for every language, but still. – Arthur – 2018-05-04T21:17:49.017
This post spawned a question on Math Stack Exchange: Given a pair of integers, double one and increment the other until equality.
– Peter Kagey – 2018-05-05T00:29:21.267@PeterKagey Reddit /r/mathriddles! That's where I saw the original question. I'll add that to the post – JMigst – 2018-05-05T02:44:06.013
1
I added this to the OEIS as A304027. The pair (34,23) seems to be especially difficult.
– Peter Kagey – 2018-05-05T23:40:11.553