

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.
T Mintab
   Set[Int] divs, subs
   [Int] table
   [[String]] hows
 
   F (divs, subs)
      .divs = copy(divs)
      .subs = copy(subs)
 
   F _mintab(n)
      ‘Tabulation, memoised minimised steps to 1’
      V table = [n + 2] * (n + 1)
      table[1] = 0
      V how = (0 .< n + 2).map(_ -> [‘’])
      how[1] = [String(‘=’)]
      L(t) 1 .< n
         V thisplus1 = table[t] + 1
         L(d) .divs
            V dt = d * t
            I dt <= n & thisplus1 < table[dt]
               table[dt] = thisplus1
               how[dt] = how[t] [+] [‘/#.=>#2’.format(d, t)]
         L(s) .subs
            V st = s + t
            I st <= n & thisplus1 < table[st]
               table[st] = thisplus1
               how[st] = how[t] [+] [‘-#.=>#2’.format(s, t)]
      .table = table
      .hows = how.map(h -> reversed(h)[0 .< (len)-1])
      R (.table, .hows)
 
   F ()(n)
      ‘Tabulation’
      V (table, hows) = ._mintab(n)
      R (table[n], hows[n])
 
L(DIVS, SUBS) [([2, 3], [1]), ([2, 3], [2])]
   print("\nMINIMUM STEPS TO 1: Tabulation algorithm")
   print(‘  Possible divisors:   ’DIVS)
   print(‘  Possible decrements: ’SUBS)
   V mintab = Mintab(Set(DIVS), Set(SUBS))
   mintab(10)
   L(n) 1..10
      V (steps, how) = (mintab.table[n], mintab.hows[n])
      print(‘    mintab(#2) in #2 by: ’.format(n, steps)‘ ’how.join(‘, ’))
 
   L(upto) [2000, 50'000]
      mintab(upto)
      print("\n    Those numbers up to "upto‘ that take the maximum, "minimal steps down to 1":’)
      V mx = max(mintab.table[1..])
      V ans = enumerate(mintab.table).filter((n, steps) -> steps == @mx).map((n, steps) -> n)
      print(‘      Taking ’mx‘ steps is/are the ’ans.len‘ numbers: ’ans.map(n -> String(n)).join(‘, ’))