

Given:

 A starting, positive integer (greater than one), N.
 A selection of possible integer perfect divisors, D.
 And a selection of possible subtractors, S.
The goal is find the minimum number of steps necessary to reduce N down to one.

At any step, the number may be:

 Divided by any member of D if it is perfectly divided by D, (remainder zero).
 OR have one of S subtracted from it, if N is greater than the member of S.


There may be many ways to reduce the initial N down to 1. Your program needs to:

 Find the minimum number of steps to reach 1.
 Show one way of getting fron N to 1 in those minimum steps.


Examples

No divisors, D. a single subtractor of 1.

Obviousely N will take N-1 subtractions of 1 to reach 1
Single divisor of 2; single subtractor of 1:

N = 7 Takes 4 steps N -1=> 6, /2=> 3, -1=> 2, /2=> 1
N = 23 Takes 7 steps N -1=>22, /2=>11, -1=>10, /2=> 5, -1=> 4, /2=> 2, /2=> 1
Divisors 2 and 3; subtractor 1:

N = 11 Takes 4 steps N -1=>10, -1=> 9, /3=> 3, /3=> 1
Task

Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 1:

1. Show the number of steps and possible way of diminishing the numbers 1 to 10 down to 1.
2. Show a count of, and the numbers that: have the maximum minimal_steps_to_1, in the range 1 to 2,000.
Using the possible divisors D, of 2 and 3; together with a possible subtractor S, of 2:

3. Show the number of steps and possible way of diminishing the numbers 1 to 10 down to 1.
4. Show a count of, and the numbers that: have the maximum minimal_steps_to_1, in the range 1 to 2,000.


Optional stretch goal

2a, and 4a: As in 2 and 4 above, but for N in the range 1 to 20_000


Reference

 Learn Dynamic Programming (Memoization & Tabulation) Video of similar task.
import "/fmt" for Fmt
 
var limit = 50000
var divs = []
var subs = []
var mins = []
 
// Assumes the numbers are presented in order up to 'limit'.
var minsteps = Fn.new { |n|
    if (n == 1) {
        mins[1] = []
        return
    }
    var min = limit
    var p = 0
    var q = 0
    var op = ""
    for (div in divs) {
        if (n%div == 0) {
            var d = (n/div).floor
            var steps = mins[d].count + 1
            if (steps < min) {
                min = steps
                p = d
                q = div
                op = "/"
            }
        }
    }
    for (sub in subs) {
        var d = n - sub
        if (d >= 1) {
            var steps = mins[d].count + 1
            if (steps < min) {
                min = steps
                p = d
                q = sub
                op = "-"
            }
        }
    }
    mins[n].add("%(op)%(q) -> %(p)")
    mins[n].addAll(mins[p])
}
 
for (r in 0..1) {
    divs = [2, 3]
    subs = (r == 0) ? [1] : [2]
    mins = List.filled(limit+1, null)
    for (i in 0..limit) mins[i] = []
    Fmt.print("With: Divisors: $n, Subtractors: $n =>", divs, subs)
    System.print("  Minimum number of steps to diminish the following numbers down to 1 is:")
    for (i in 1..limit) {
        minsteps.call(i)
        if (i <= 10) {
            var steps = mins[i].count
            var plural = (steps == 1) ? " " : "s"
            var mi = Fmt.v("s", 0, mins[i], 0, ", ", "")
            Fmt.print("    $2d: $d step$s: $s", i, steps, plural, mi)
        }
    }
    for (lim in [2000, 20000, 50000]) {
        var max = 0
        for (min in mins[0..lim]) {
            var m = min.count
            if (m > max) max = m
        }
        var maxs = []
        var i = 0
        for (min in mins[0..lim]) {
            if (min.count == max) maxs.add(i)
            i = i + 1
        }
        var nums = maxs.count
        var verb   = (nums == 1) ? "is" : "are"
        var verb2  = (nums == 1) ? "has" : "have"
        var plural = (nums == 1) ? "": "s"
        Fmt.write("  There $s $d number$s in the range 1-$d ", verb, nums, plural, lim)
        Fmt.print("that $s maximum 'minimal steps' of $d:", verb2, max)
        System.print("   %(maxs)")
    }
    System.print()
}