

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.
Dim Shared As Integer minPasos       'minimal number of steps to get to 1
Dim Shared As Integer Subtractor     '1 or 2
Dim Shared As Integer Ns(20000), Ops(20000), MinNs(20000), MinOps(20000)
 
Sub Reduce(N As Integer, Paso As Integer) 'Reduce N to 1, recording minimum steps
    If N = 1 Then
        If Paso < minPasos Then
            For i As Integer = 0 To Paso-1
                MinOps(i) = Ops(i)
                MinNs(i) = Ns(i)
            Next i
            minPasos = Paso
        End If
    End If
    If Paso >= minPasos Then Exit Sub     'don't search further
    If N Mod 3 = 0 Then Ops(Paso) = 3 : Ns(Paso) = N/3 : Reduce(N/3, Paso+1)
    If N Mod 2 = 0 Then Ops(Paso) = 2 : Ns(Paso) = N/2 : Reduce(N/2, Paso+1)
    Ops(Paso) = -Subtractor 
    Ns(Paso) = N-Subtractor 
    Reduce(N-Subtractor, Paso+1)
End Sub
 
Sub ShowSteps(N As Integer)     'Show minimal steps and how N steps to 1
    minPasos = 50000
    Reduce(N, 0)
    Print "N = " & N & " takes " & minPasos & " steps: N";
    For i As Integer = 0 To minPasos-1
        Print Iif(Sgn(MinOps(i)) < 0, " -", " /");
        Print Abs(MinOps(i)) & "=>" & MinNs(i); '" "
    Next i
    Print
End Sub
 
Sub ShowCount(Range As Integer) 'Show count of maximum minimal steps and their Ns
    Dim As Integer N, MaxSteps
    MaxSteps = 0          'find maximum number of minimum steps
    For N = 1 To Range
        minPasos = 50000
        Reduce(N, 0)
        If minPasos > MaxSteps Then MaxSteps = minPasos
    Next N
    Print "Maximum steps:"; MaxSteps; " for N =";
    For N = 1 To Range    'show numbers (Ns) for Maximum steps
        minPasos = 50000
        Reduce(N, 0)
        If minPasos = MaxSteps Then Print N; '" ";
    Next N
    Print
End Sub
 
Dim As Integer N
Subtractor = 1        '1.
For N = 1 To 10 
    ShowSteps(N)
Next N
ShowCount(2000)       '2.
ShowCount(20000)      '2a.
 
Print
Subtractor = 2        '3.
For N = 1 To 10 
    ShowSteps(N)
Next N
ShowCount(2000)       '4.
ShowCount(20000)      '4a.
Sleep