Bringing a pair of integers to equality

Question

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]]

• 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]].

• Standard IO methods apply and standard loopholes banned

• This is code golf so shortest answer in bytes wins

Answer 1

JavaScript (ES6), 111 90 83 bytes

f=(a,b,p=q=[],u=[...p,[a,b]])=>a-b?f(...(q=[[a*2,b+1,u],[a+1,b*2,u],...q]).pop()):u

Try it online!

Commented

f = (                       // f = recursive function taking:
  a, b,                     //   (a, b) = input integers
  p =                       //   p[] = current path
  q = [],                   //   q[] = queue
  u = [...p, [a, b]]        //   u[] = updated path with [a, b] appended to it
) =>                        //
  a - b ?                   // if a is not yet equal to b:
    f(...                   //   recursive call, using spread syntax:
      (q = [                //     prepend the next 2 possible moves in the queue:
        [a * 2, b + 1, u],  //       a * 2, b + 1
        [a + 1, b * 2, u],  //       a + 1, b * 2
        ...q                //
      ]).pop()              //     use the move on the top of the queue
    )                       //   end of recursive call
  :                         // else:
    u                       //   success: return the (updated) path

Answer 2

Haskell, 70 69 bytes

f(w@((i,j):_):r)|i==j=w|1<2=f$r++[(i+1,j*2):w,(i*2,j+1):w]
g x=f[[x]]

Try it online!

A simple BFS. Keeps track of the steps in a list of list of pairs.

g x=f[[x]]                -- start with a single list where the only
                          -- step is the starting pair
f (w@((i,j):_):r) =       -- let w be the first list of steps
                          --     (i,j) the last pair of the first list of steps
                                       ('last' as in last operated on. As we store
                                        the steps in reverse order it's the
                                        first element in the list)
                          --     r all other lists of steps
   i==j=w                 -- if i==j stop and return the first list
   1<2= f                 -- else make a recursive call
          r++             -- where the new input list is r followed by
                          -- the first list extended one time by
          [(i+1,j*2):w,         (i+1,j*2) and one time by
             (i*2,j+1):w]       (i*2,j+1)

Answer 3

Python 3, 90 74 72 bytes

-2 bytes thanks to Dennis.

def f(a,*x):j,k=a[0];return(j==k)*a or f(*x,[(2*j,k+1)]+a,[(j+1,2*k)]+a)

Try it online!

Takes input as a singleton list.

---

Ungolfed

def f(a,*x):              # function taking at least one argument
                          # a is the first argument, all other are stored in x
  j, k = a[0]             # get the newest values of the current path
  return (j==k)*a         # if j is equal to k return the current path
                  or      # else ...
   f(                     # continue ...
     *x,                  # with the remaining paths ...
     [(2*j,k+1)]+a        # and split the current path ...
     [(j+1,2*k)]+a        # in two new ones
    ) 

Answer 4

Pyth, 41 bytes

J]]QL,hhb*2ebWt{KehJ=J+tJm+hJ]d,yK_y_K)hJ

Try it here

Explanation

This is pretty straightforward breadth-first search. Keep a queue of possible sequences (J), and until we get a matching pair, take the next sequence, stick on each of the possible moves, and put them at the end of the queue.
For the sake of brevity, we define a function y (using the lambda expression L) to perform one of the moves, and apply it both forward and in reverse.

Answer 5

Jelly, 20 bytes

ḃ2d2;@+*¥\
0çṪEɗ1#Ḣç

Try it online!

Answer 6

05AB1E, 25 22 20 bytes

Takes a doubly nested list as input and outputs a jagged list with each step at one nest-depth.

[ć¤Ë#¤xs>R‚ø`R‚s¸sâ«

Try it online!

Explanation

[                      # start a loop
 ć                     # extract the first element of the current list (current path)
  ¤Ë#                  # break if all elements in the head are equal
     ¤xs>              # duplicate one copy of the head and increment another
         R             # reverse the incremented copy
          ‚ø           # zip them together
            `R‚        # reverse the tail of the zipped list
               s¸sâ    # cartesian product with the rest of the current path
                   «   # append to the list of all current paths

Answer 7

Retina, 72 bytes

\d+
*
/\b(_+),\1\b/^+%`(_+),(_+)$
$&;_$&$2¶$=;$1$&_
G`\b(_+),\1\b
_+
$.&

Try it online! Only two test cases due to the limitations of unary arithmetic. Explanation:

\d+
*

Convert to unary.

/\b(_+),\1\b/^+

While the input does not contain a pair of identical numbers...

%`(_+),(_+)%

...match the last pair on each line...

$&;_$&$2¶$=;$1$&_

...and turn the line into two lines, one suffixed with the first number incremented and second doubled, the other suffixed with the first number doubled and second incremented.

G`\b(_+),\1\b

Keep the line with the matching pair.

_+
$.&

Convert back to decimal. 89 88-byte unsigned decimal arithmetic version (works with 0 as well):

/\b(\d+),\1\b/^+%`(\d+),(\d+)$
$&;$.(_$1*),$.(2*$2*)¶$=;$.(2*$1*),$.(_$2*
G`\b(\d+),\1\b

Try it online!

Answer 8

MATL, 24 bytes

`vxG1r/q:"tt1rEk(+]td0=~

Running time is random, but it is finite with probability 1.

The code is very inefficient. Inputs requiring more than 4 or 5 steps have a large probability of timing out in the online interpreter.

Try it online!

Explanation

`         % Do...while
  vx      %   Concatenate stack and delete. This clears the stack from contents
          %   of previous iterations   
  G       %   Push input
  1       %   Push 1
  r       %   Push random number uniformly distributed on (0,1)
  /       %   Divide
  q       %   Subtract 1. The result is a random number, t, that has nonzero
          %   probability of being arbitrarily large. Specifically, t is in
          %   the interval (0,1) with probability 1/2; in (1,2) with probability
          %   1/6; ... in (k,k+1) with probability 1/((k+1)*(k+2).
  :       %   Range [1 2 ... floor(t)]
  "       %   For each (that is: do thw following floor(t) times)
    tt    %     Duplicate twice
    1     %     Push 1
    rEk   %     Random number in (0,1), times 2, round down. This produces a 
          %     number i that equals 0 or 1 with probability 1/2
    (     %     Write 1 at entry i. So if the top of the stack is [a b], this
          %     transforms it into either [1 b] or [a 1]
    +     %     Add, element-wise. This gives either [a+1 2*b] or [2*a b+1] 
  ]       %   End for each
  td      %   Duplicate, consecutive difference between the two entries
  0=~     %   Is it not zero? If so, the do...while loop continues with a new
          %   iteration. Normally the code 0=~ could be omitted, because a
          %   nonzero consecutive difference is truthy. But for large t the
          %   numbers a, b may have gone to infinity, and then the consecutive
          %   difference gives NaN
          % End do...while (implicit). Display (implicit)

Answer 9

Stax, 29 26 bytes

ä⌠|Tô&cm♂NV↓↔╗╣¢♠╜╒█¡Φ≈ñY@

Run and debug it

It's a breadth first search. It seems reasonably fast.

It takes a doubly-array-wrapped pair of integers. The output is a space separated list of values. Every two values represents one pair in the path to the solution.

Answer 10

Haskell, 95 bytes

g s|a:_<-[a|a@((x,y):_)<-s,x==y]=a
g s=g$do a@((x,y):_)<-s;[(x*2,y+1):a,(x+1,y*2):a]
h t=g[[t]]

Try it online! Outputs in reverse order, e.g. h(2,5) yields [(12,12),(6,11),(3,10),(2,5)].

Answer 11

Red, 142 bytes

Takes the input as a doubly nested block of the pair of integers in Red's format (2, 5) -> 2x5

Returns the result as a list ot Red pairs, for example 2x5 3x10 6x11 12x12. Includes the initial pair.

func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]do replace/all{%+ 1x0 * 1x2
%* 2x1 + 0x1}"%""append/only a append copy d l "]f a]

Try it online!

Strict input:

The input is two numbers, for example 2 5

Red, 214 bytes

func[a b][g: func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]append/only a append copy d l + 1x0 * 1x2
append/only a append copy d l * 2x1 + 0x1]g a]c: copy[]insert/only c reduce[do rejoin[a 'x b]]g c]

Try it online!

Explanation:

f: func[a b][                 
g: func[c][                                   ; recursive helper function
  a: copy[]                                   ; an empty block
  foreach d c[                                ; for each block of the input 
    l: last d                                 ; take the last pair
    if l/1 = l/2[return d]                    ; if the numbers are equal, return the block 
    append/only a append copy d l + 1x0 * 1x2 ; in place of each block append two blocks
    append/only a append copy d l * 2x1 + 0x1 ; (j+1, k*2) and (j*2, k+1)
  ]                                           ; using Red's arithmetic on pairs
  g a                                         ; calls the function anew
]
c: copy[]insert/only c reduce[do rejoin[a 'x b]]; prepares a nested block from the input
g c                                           ; calls the recursive function 
]