Minimum transformations from N to 1

mintrans.py

def T(n):

    memo = {
        1 : (0, "<Base>"),
        2 : (1, " / 2"),
        3 : (1, " / 3")
    }

    def build_memo(n):

        nonlocal memo

        if n in memo: return memo[n]

        value, _ = build_memo(n - 1)
        op = " - 1"

        if n % 2 == 0:

            new_value, new_op = build_memo(n / 2)

            if new_value < value:
                value = new_value
                op = " / 2"

        if n % 3 == 0:
            new_value, new_op = build_memo(n / 3)

            if new_value < value:
                value = new_value
                op = " / 3"


        memo[n] = (1 + value), op

        return memo[n]

    build_memo(n)

    return memo

def U(N):

    memo = {
        1 : (0, "<Base>"),
        2 : (1, " / 2"),
        3 : (1, " / 3")
    }

    for n in range(4, N + 1):

        value = memo[n - 1][0]
        op = " - 1"

        if n % 2 == 0:

            new_value = memo[n/2][0]

            if new_value < value:
                value = new_value
                op = " / 2"

        if n % 3 == 0:
            new_value = memo[n/3][0]

            if new_value < value:
                value = new_value
                op = " / 3"


        memo[n] = (1 + value), op

    return memo

ops = {
    " - 1": lambda x : int(x - 1),
    " / 2": lambda x : int(x / 2),
    " / 3": lambda x : int(x / 3),
}

def solve(n):

    import math
    from time import perf_counter

    if n == 1:
        print("You are at one already... "
              "what's wrong with you?")
        return

    tbeg = perf_counter()
    memo = U(n)
    tend = perf_counter()
    elapsed = (tend - tbeg)
    print(f"{n} --> 1 in {memo[n][0]} steps")

    max_width = math.floor(math.log(n, 10)) + 1


    while n != 1:
        op = memo[n][1]
        m  = ops[op](n)
        print(f"{n:>{max_width}d}{op} = {m:>{max_width}d}")
        n = m

    print(f"[{len(memo)} memo entries in {elapsed:.4f} seconds]")

def main():
    try:
        while True:
            n = input(">>> enter a new number: ")
            solve(int(n))
    except (ValueError, KeyboardInterrupt):
        pass
    finally:
        print("goodbye!")


if __name__ == "__main__":
    main()

Sample console session

>>> enter a new number: 10
10 --> 1 in 3 steps
10 - 1 =  9
 9 / 3 =  3
 3 / 3 =  1
[10 memo entries in 0.0000 seconds]
>>> enter a new number: 99
99 --> 1 in 6 steps
99 / 3 = 33
33 / 3 = 11
11 - 1 = 10
10 - 1 =  9
 9 / 3 =  3
 3 / 3 =  1
[99 memo entries in 0.0001 seconds]
>>> enter a new number: 12134
12134 --> 1 in 13 steps
12134 / 2 =  6067
 6067 - 1 =  6066
 6066 / 2 =  3033
 3033 / 3 =  1011
 1011 / 3 =   337
  337 - 1 =   336
  336 / 2 =   168
  168 / 2 =    84
   84 / 3 =    28
   28 - 1 =    27
   27 / 3 =     9
    9 / 3 =     3
    3 / 3 =     1
[12134 memo entries in 0.0063 seconds]
>>> enter a new number: 12
12 --> 1 in 3 steps
12 / 2 =  6
 6 / 2 =  3
 3 / 3 =  1
[12 memo entries in 0.0000 seconds]