Find the minimum number of operations to convert 1 into n, and print the sequence of numbers
Given the problem description, I'm not entirely sure why x is a parameter of min_operations. Could you not hard-code 1?



        val_times_2 = val * 2
        if val_times_2 &lt;= y and val_times_2 not in visited:
            visited.add(val_times_2)
            new_sequences.append(s + [val_times_2])

        val_times_3 = val * 3
        if val_times_3 &lt;= y and val_times_3 not in visited:
            visited.add(val_times_3)
            new_sequences.append(s + [val_times_3])


        val_plus_1 = val + 1
        if val_plus_1 &lt;= y and val_plus_1 not in visited:
            visited.add(val_plus_1)
            new_sequences.append(s + [val_plus_1])


There's some common code here which could certainly be refactored. Perhaps

        for successor in [val + 1, val * 2, val * 3]
            if successor &lt;= y and successor not in visited:
                visited.add(successor)
                new_sequences.append(s + [successor])




However, the approach of storing the full path for each visited element doesn't scale particularly well. All you really need is to find the predecessor: provided you store all of the predecessors, you can work your way back up the chain. One way to do that would be a dictionary (which could also take the place of visited).

def min_operations(y):
    predecessors = dict()
    new_elements = [1]

    while True:
        next_new_elements = []
        for e in new_elements:
            if e == y:
                return unchain(e, predecessors)

            for successor in [val + 1, val * 2, val * 3]
                if successor &lt;= y and successor not in predecessors:
                    predecessors[successor] = y
                    next_new_elements.append(successor)

        new_elements = next_new_elements

def unchain(e, predecessors):
    chain = [e]
    while e in predecessors:
        e = predecessors[chain[-1]]
        chain.append(e)
    return list(reversed(chain))


An alternative way of doing it would be to use lru_cache to find the predecessors on the fly, handing off the caching to the library. Here it is necessary to track the depth as well as the predecessor.

@lru_cache(maxsize=None)
def predecessor(y):
    if y == 1:
        return (0, 0)

    candidates = []
    (decr, _) = predecessor(y - 1)
    candidates.append((decr + 1, y - 1))

    for divisor in [2, 3]:
        if y % divisor == 0:
            (divided, _) = predecessor(y // divisor)
            candidates.append((divided + 1, y // divisor))

    return min(candidates)


Then min_operations is essentially unchain but calling predecessor instead of doing a lookup in a map. This is arguably slightly more elegant, but does run into problems with stack overflow if y is too large.