Add two natural numbers

Question

Given two natural numbers (less than 100) as input print the sequence of intermediate results obtained when computing the sum of the two numbers using only the following operations¹:

• n <-> (m+1) for integers nand m satisfying that equation
• (a+b)+c <-> a+(b+c) for integers a,b and c (associative law)

You are not allowed to use the commutative law (swapping the arguments of +)

Example

5+3           # Input
5+(2+1)       # 3 = 2+1
(5+2)+1       # Associative law
(5+(1+1))+1   # 2 = 1+1
((5+1)+1)+1   # Associative law
(6+1)+1       # 5+1 = 6
7+1           # 6+1 = 7
8             # 7+1 = 8

Rules

• Input: two natural numbers (positive integers)
• Output list of all intermediate steps in the calculation of the sum (using the rules defined above), you may omit the final result
• The expressions can be output in any reasonable format (the left and right operands of each + should be clearly determinable)
• You can choose the order in which the operations are applied as long as you reach the final result
• Each expression in the output has to be obtained from the previous expression by applying exactly one allowed operation to the previous operation
• This is code-golf the shortest code wins

Test cases

infix notation:

2+2 -> 2+(1+1) -> (2+1)+1 -> 3+1 -> 4
3+1 -> 4
1+3 -> 1+(2+1) -> 1+((1+1)+1) -> (1+(1+1))+1 -> ((1+1)+1)+1 -> (2+1)+1 -> 3+1 -> 4
1+3 -> 1+(2+1) -> (1+2)+1     -> (1+(1+1))+1 -> ((1+1)+1)+1 -> (2+1)+1 -> 3+1 -> 4
5+3 -> 5+(2+1) -> (5+2)+1     -> (5+(1+1))+1 -> ((5+1)+1)+1 -> (6+1)+1 -> 7+1 -> 8

postfix notation:

 2 2+ -> 2 1 1++ -> 2 1+ 1+ -> 3 1+ -> 4
 3 1+ -> 4
 1 3+ -> 1 2 1++ -> 1 1 1+ 1++ -> 1 1 1++ 1+ -> 1 1+ 1+ 1+ -> 2 1+ 1+ -> 3 1+ -> 4
 1 3+ -> 1 2 1++ -> 1 2+ 1+    -> 1 1 1++ 1+ -> 1 1+ 1+ 1+ -> 2 1+ 1+ -> 3 1+ -> 4
 5 3+ -> 5 2 1++ -> 5 2+ 1+    -> 5 1 1++ 1+ -> 5 1+ 1+ 1+ -> 6 1+ 1+ -> 7 1+ -> 8

Example implementation

---

¹ The operations are based on the formal definition of additon but modified to work without the concept of a successor function.

Answer 1

Jelly, 22 bytes

FṖ.ịoƲ€2¦ṁ¥,/ƭ$ƬṪ§Ƭ;@Ɗ

A monadic Link that accepts a pair of positive integers and yields a list of nested lists representing (much like the reference implementation) one way to perform their sum.

Try it online!

How?

FṖ.ịoƲ€2¦ṁ¥,/ƭ$ƬṪ§Ƭ;@Ɗ - Link: pair of positive integers, A = [n, m]
               Ƭ       - starting with X=A collect up while distinct under:
              $        -   last two links as a monad - f(X):
F                      -     flatten X
             ƭ         -     alternate between:
          ¥            -     (1) last two links as a dyad - F(Flat_X, X):
      €2¦              -           apply to second element, V, of X:
     Ʋ                 -             last four links as a monad - f(V):
 Ṗ                     -               pop -> [1 .. V-1]        or [] if V == 1
  .                    -               0.5
   ị                   -               index into -> [V-1, 1]   or [] if V == 1
    o                  -               logical OR V -> [V-1, 1] or  V if V == 1
            /          -     (2) reduce Flat_X by:
           ,           -           pair -> ...[[[[a,b],c],d],...]
                     Ɗ - last three links as a monad - f(StepsSoFar):
                Ṫ      -   tail -> removes and yields PreviousStep
                  Ƭ    -   starting with PreviousStep collect up while distinct under:
                 §     -     sums
                   ;@  -   append to the tailed StepsSoFar

---

Seems like the sums (§) could be performed within the first collect-loop (Ƭ), but I've not figured out a good way to do so...

Answer 2

Python, 98 bytes

f=lambda m,n:[f"{m}+{n}"]+([n:=n-1]*n and[f"{m}+({n}+1)",*(f"({x})+1"for x in f(m,n)),f"{m+n}+1"])

Attempt This Online!

-1 thanks to @STerliakov

Original Python, 100 bytes

f=lambda m,n:[f"{m}+{n}"]+(n-1and[f"{m}+({n-1}+1)",*(f"({x})+1"for x in f(m,n-1)),f"{m+n-1}+1"]or[])

Attempt This Online!

Outputs a list of strings in infix notation.

Answer 3

Charcoal, 64 bytes

ＮθＮηＦ⊖ηＥ²⪫⟦×(ιθ+×(κＩ⁻η⁺ικ×+1)κ×)+1ι⟧ω⮌Ｅη⪫⟦×(ι⁻⁺θη⊕ι+1×)+1ι⟧ωＩ⁺θη

Try it online! Link is to verbose version of code. Explanation:

ＮθＮη

Input the two numbers.

Ｆ⊖ηＥ²⪫⟦×(ιθ+×(κＩ⁻η⁺ικ×+1)κ×)+1ι⟧ω

Output the steps that split the second number into units and associate them with the first number.

⮌Ｅη⪫⟦×(ι⁻⁺θη⊕ι+1×)+1ι⟧ω

Output the steps that add the units to the first number.

Ｉ⁺θη

Finish with the final sum.

Answer 4

Retina 0.8.2, 90 bytes

\d+
$*
+`\+1(1+)(.*$)
$&¶$%`+($1+1)$2¶($%`+$1)+1$2
+`\(?(1+)\+1\)?(.*$)
$&¶$%`1$1$2
1+
$.&

Try it online! Link is to test suite that outputs all the test cases. Explanation:

\d+
$*

Convert to unary.

+`\+1(1+)(.*$)
$&¶$%`+($1+1)$2¶($%`+$1)+1$2

Repeatedly convert x+<1y> into x+(y+1) and then (x+y)+1 until y is 1.

+`\(?(1+)\+1\)?(.*$)
$&¶$%`1$1$2

Repeatedly convert (x+1) into <1x>.

1+
$.&

Convert to decimal.

Answer 5

JavaScript (Node.js), 99 bytes

x=>g=(y,a='',b=`
`)=>(--y?a+x+`+${y+1+b+a+x}+(${y}+1)`+b+g(y,'('+a,')+1'+b)+a:a)+x+++`+1${a?b:b+x}`

Try it online!

Answer 6

Python, 140 137 bytes

lambda x,y,a='',b='':(a+f"{x}+{y}{b}\n{a}{x}+({y-1}+1){b}\n{f(x,y-1,'('+a,b+')+1')}\n"if~-y else'')+a+f"{x+y-1}+1{b or chr(10)+str(x+y)}"

Attempt This Online!

A port of l4m2's JavaScript answer

Answer 7

Perl 5 (-lp), 135 bytes

1while print,s/\+(?!1\b)\d+/"+(".($&-1)."+1)"/e||s/(\d+)\+\((\d+)\+(\d+)\)/($1+$2)+$3/||(s/^[^+\d]*\K(\d+)\+1\b/$1+1/e,s/\((\d+)\)/$1/)

Try it online!

Answer 8

Scala 3, 153 bytes

def f(m:Int,n:Int):Seq[String]=n match{case 1=>Seq(s"$m+1");case _=>Seq(s"$m+$n")++Seq(s"$m+(${n-1}+1)")++f(m,n-1).map(x=>s"($x)+1")++Seq(s"${m+n-1}+1")}

Attempt This Online!