Python iterate through unique commutative equations

Question

Inspired by the math of this video, I was curious how long it takes get a number, n, where I can use the number, 1, and a few operations like addition and subtraction, in the binary base. Currently, I have things coded up like this:

import itertools as it

def brute(m):
    out = set()
    for combo in it.product(['+','*','|'], repeat=m):
        x = parse(combo)
        if type(x) == int and 0 < x-1:
            out.add(x)
    return out

def parse(ops):
    eq = ""
    last = 1
    for op in ops:
        if op == "|":
            last *= 2
            last += 1
        else:
            eq += str(last)
            eq += op
            last = 1
    eq += str(last)
    return eval(eq)

Here, "|" refers to concatenation, thus combo = ("+","|","*","|","|") would parse as 1+11*111 = 1+3*7 = 22. I'm using this to build a table of how many numbers are m operations away and study how this grows. Currently I am using the itertools product function to search all possible operation combos, despite this being a bit repetitive, as "+" and "*" are both commutative operations. Is there a clean way to only generate the commutatively unique expressions?

Currently, my best idea is to have a second brute force program, brute2(k) which only uses the operations "*" and "|", and then have:

def brute(m):
    out = set()
    for k in range(m):
       for a,b in it.product(brute(k),brute2(m-k)):
           out.add(a+b)

if I memoize things, this would be pretty decent, but I'm not sure if there's a more pythonic or efficient way than this. Furthermore, this fails to cleanly generalize if I decide to add more operations in like subtraction.

What I'm hoping to achieve is insight on if there is some module or simple method which will efficiently iterate through the operation combos. Currently, itertools.product has complexity O(3^m). However, with memoizing and using the brute2 method, it seems I could get things down to complexity O(|brute(m-1)|), which seems to be asymptotically ~O(1.5^m). While I am moderately happy with this second method, it would be nice if there was a more generalizable method which would extend for arbitrary amounts of operations, some of which are commutative.

Update:

I've now gotten my second idea coded up. With this, I was able to quickly get all numbers reachable in 42 operations, when my old code got stuck for hours after 20 operations. Here is the new code:

memo1 = {0:{1}}
def brute1(m):
    if m not in memo1:
        out = set(brute2(m+1))
        for i in range(m):
            for a,b in it.product(brute1(i),brute2(m-i)):
                out.add(a+b)
        memo1[m] = set(out)
    return memo1[m]
    
memo2 = {0:{1}}
def brute2(m):
    if m not in memo2:
        out = set()
        for i in range(m):
            for x in brute2(i):
                out.add(x*(2**(m-i)-1))
        memo2[m] = set(out)
    return memo2[m]

I were to generalize this, you order all your commutative operations, [op_1,op_2,... op_x], have brute(n,0) return all numbers reachable with n non-commutative operations, and then have:

memo = {}
def brute(n,i):
    if (n,i) not in memo:
        out = brute(n,i-1) #in case I don't use op_i
        for x in range(1,n): #x is the number of operations before my last use of op_i, if combo = (op_i,"|","+","+","*","+",op_i,"*","|"), this case would be covered when x = 6
            for a,b in it.product(brute(x,i),brute(n-x-1,i-1)):
                out.add(a op_i b)
        memo[(n,i)] = out
    return memo[(n,i)]

However, you have to be careful about order of operations. If I did addition and then multiplication, things would be totally different, and this would say different things. If there's a hierarchy like PEMDAS, and you don't want to consider parentheses, I believe you just list the operations in decreasing order of priority, i.e. op_1 is the first operation you do etc. If you allow general parenthesization, then you should have something like this I believe:

memo = {0:1}
def brute(m, ops):
    if m not in memo:
        out = set()
        for i in range(m):
            for a,b in it.product(brute(i),brute(m-i-1)):
                for op in ops:
                    out.add( op(a,b) )
        memo[m] = out
    return memo[m]

I'm more interested in the case where we have some sort of PEMDAS system in place, and the parentheses are implied by the sequence of operations, but feedback on the validity/efficiency to either case is still welcome.