

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.
int     MinSteps,       \minimal number of steps to get to 1
        Subtractor;     \1 or 2
char    Ns(20000), Ops(20000), MinNs(20000), MinOps(20000);
 
proc Reduce(N, Step);   \Reduce N to 1, recording minimum steps
int  N, Step, I;
[if N = 1 then
    [if Step < MinSteps then
        [for I:= 0 to Step-1 do
            [MinOps(I):= Ops(I);
            MinNs(I):= Ns(I);
            ];
        MinSteps:= Step;
        ];
    ];
if Step >= MinSteps then return;        \don't search further
if rem(N/3) = 0 then
        [Ops(Step):= 3;  Ns(Step):= N/3;  Reduce(N/3, Step+1)];
if rem(N/2) = 0 then
        [Ops(Step):= 2;  Ns(Step):= N/2;  Reduce(N/2, Step+1)];
Ops(Step):= -Subtractor;  Ns(Step):= N-Subtractor;  Reduce(N-Subtractor, Step+1);
]; \Reduce
 
proc ShowSteps(N);      \Show minimal steps and how N steps to 1
int N, I;
[MinSteps:= $7FFF_FFFF;
Reduce(N, 0);
Text(0, "N = ");  IntOut(0, N);
Text(0, " takes ");  IntOut(0, MinSteps);  Text(0, " steps: N ");
for I:= 0 to MinSteps-1 do
        [Text(0, if extend(MinOps(I)) < 0 then "-" else "/");
        IntOut(0, abs(extend(MinOps(I))));
        Text(0, "=>");  IntOut(0, MinNs(I));  Text(0, " ");
        ];
CrLf(0);
]; \ShowSteps
 
proc ShowCount(Range);  \Show count of maximum minimal steps and their Ns
int  Range;
int  N, MaxSteps;
[MaxSteps:= 0;          \find maximum number of minimum steps
for N:= 1 to Range do
        [MinSteps:= $7FFF_FFFF;
        Reduce(N, 0);
        if MinSteps > MaxSteps then
                MaxSteps:= MinSteps;
        ];
Text(0, "Maximum steps: ");  IntOut(0, MaxSteps);  Text(0, " for N = ");
for N:= 1 to Range do   \show numbers (Ns) for Maximum steps
        [MinSteps:= $7FFF_FFFF;
        Reduce(N, 0);
        if MinSteps = MaxSteps then
                [IntOut(0, N);  Text(0, " ");
                ];
        ];
CrLf(0);
]; \ShowCount
 
int N;
[Subtractor:= 1;                \1.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000);                \2.
ShowCount(20_000);              \2a.
Subtractor:= 2;                 \3.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000);                \4.
ShowCount(20_000);              \4a.
]