

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 strformat, strutils, tables
 
type
 
  Sequence = seq[Natural]
 
  Context = object
    divisors: seq[int]
    subtractors: seq[int]
    seqCache: Table[int, Sequence]  # Mapping number -> sequence to reach 1.
    stepCache: Table[int, int]      # Mapping number -> number of steps to reach 1.
 
 
proc initContext(divisors, subtractors: openArray[int]): Context =
  ## Initialize a context.
  for d in divisors: doAssert d > 1, "divisors must be greater than 1."
  for s in subtractors: doAssert s > 0, "substractors must be greater than 0."
  result.divisors = @divisors
  result.subtractors = @subtractors
  result.seqCache[1] = @[Natural 1]
  result.stepCache[1] = 0
 
 
proc minStepsDown(context: var Context; n: Natural): Sequence =
  # Return a minimal sequence to reach the value 1.
 
  assert n > 0, "“n” must be positive."
  if n in context.seqCache: return context.seqCache[n]
 
  var
    minSteps = int.high
    minPath: Sequence
 
  for val in context.divisors:
    if n mod val == 0:
      var path = context.minStepsDown(n div val)
      if path.len < minSteps:
        minSteps = path.len
        minPath = move(path)
 
  for val in context.subtractors:
    if n - val > 0:
      var path = context.minStepsDown(n - val)
      if path.len < minSteps:
        minSteps = path.len
        minPath = move(path)
 
  result = n & minPath
  context.seqCache[n] = result
 
 
proc minStepsDownCount(context: var Context; n: Natural): int =
  ## Compute the mininum number of steps without keeping the sequence.
 
  assert n > 0, "“n” must be positive."
  if n in context.stepCache: return context.stepCache[n]
 
  result = int.high
 
  for val in context.divisors:
    if n mod val == 0:
      let steps = context.minStepsDownCount(n div val)
      if steps < result: result = steps
 
  for val in context.subtractors:
    if n - val > 0:
      let steps = context.minStepsDownCount(n - val)
      if steps < result: result = steps
 
  inc result
  context.stepCache[n] = result
 
 
template plural(n: int): string =
  if n > 1: "s" else: ""
 
proc printMinStepsDown(context: var Context; n: Natural) =
  ## Search and print the sequence to reach one.
 
  let sol = context.minStepsDown(n)
  stdout.write &"{n} takes {sol.len - 1} step{plural(sol.len - 1)}: "
  var prev = 0
  for val in sol:
    if prev == 0:
      stdout.write val
    elif prev - val in context.subtractors:
      stdout.write " - ", prev - val, " → ", val
    else:
      stdout.write " / ", prev div val, " → ", val
    prev = val
  stdout.write '\n'
 
 
proc maxMinStepsCount(context: var Context; nmax: Positive): tuple[steps: int; list: seq[int]] =
  ## Return the maximal number of steps needed for numbers between 1 and "nmax"
  ## and the list of numbers needing this number of steps.
 
  for n in 2..nmax:
    let nsteps = context.minStepsDownCount(n)
    if nsteps == result.steps:
      result.list.add n
    elif nsteps > result.steps:
      result.steps = nsteps
      result.list = @[n]
 
 
proc run(divisors, subtractors: openArray[int]) =
  ## Run the search for given divisors and subtractors.
 
  var context = initContext(divisors, subtractors)
  echo &"Using divisors: {divisors} and substractors: {subtractors}"
  for n in 1..10: context.printMinStepsDown(n)
  for nmax in [2_000, 20_000]:
    let (steps, list) = context.maxMinStepsCount(nmax)
    stdout.write if list.len == 1: &"There is 1 number " else: &"There are {list.len} numbers "
    echo &"below {nmax} that require {steps} steps: ", list.join(", ")
 
 
run(divisors = [2, 3], subtractors = [1])
echo ""
run(divisors = [2, 3], subtractors = [2])