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 operations1:

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

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

• Does this challenge fit in expression-building? Nov 13 at 15:18
• Thanks for clarifying... Should I delete my attempt? See here Nov 14 at 12:42
• @Tobias321 Yes, you can undelete it once you have found time to fix your solution Nov 14 at 14:39

# 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... # 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. • 99 by extracting n-1 into variable Nov 15 at 2:09 # 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. # 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. # 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!

# 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

# 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!

# 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!