

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.
func minToOne(divs: [Int], subs: [Int], upTo n: Int) -> ([Int], [[String]]) {
  var table = Array(repeating: n + 2, count: n + 1)
  var how = Array(repeating: [""], count: n + 2)
 
  table[1] = 0
  how[1] = ["="]
 
  for t in 1..<n {
    let thisPlus1 = table[t] + 1
 
    for div in divs {
      let dt = div * t
 
      if dt <= n && thisPlus1 < table[dt] {
        table[dt] = thisPlus1
        how[dt] = how[t] + ["/\(div)=>  \(t)"]
      }
    }
 
    for sub in subs {
      let st = sub + t
 
      if st <= n && thisPlus1 < table[st] {
        table[st] = thisPlus1
        how[st] = how[t] + ["-\(sub)=> \(t)"]
      }
    }
  }
 
  return (table, how.map({ $0.reversed().dropLast() }))
}
 
for (divs, subs) in [([2, 3], [1]), ([2, 3], [2])] {
  print("\nMINIMUM STEPS TO 1:")
  print("  Possible divisors:  \(divs)")
  print("  Possible decrements: \(subs)")
 
  let (table, hows) = minToOne(divs: divs, subs: subs, upTo: 10)
 
  for n in 1...10 {
    print("    mintab(  \(n)) in {  \(table[n])} by: ", hows[n].joined(separator: ", "))
  }
 
  for upTo in [2_000, 50_000] {
    print("\n    Those numbers up to \(upTo) that take the maximum, \"minimal steps down to 1\":")
    let (table, _) = minToOne(divs: divs, subs: subs, upTo: upTo)
    let max = table.dropFirst().max()!
    let maxNs = table.enumerated().filter({ $0.element == max })
 
    print(
      "      Taking", max, "steps are the \(maxNs.count) numbers:",
      maxNs.map({ String($0.offset) }).joined(separator: ", ")
    )
  }
}