

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.
with javascript_semantics
sequence cache = {},
         ckeys = {}
 
function ms21(integer n, sequence ds)
    integer cdx = find(ds,ckeys)
    if cdx=0 then
        ckeys = append(ckeys,ds)
        cache = append(cache,{{}})
        cdx = length(cache)
    end if
    for i=length(cache[cdx])+1 to n do
        integer ms = n+2
        sequence steps = {}
        for j=1 to length(ds) do    -- (d then s)
            for k=1 to length(ds[j]) do
                integer dsk = ds[j][k],
                        ok = iff(j=1?remainder(i,dsk)=0:i>dsk)
                if ok then
                    integer m = iff(j=1?i/dsk:i-dsk),
                            l = length(cache[cdx][m])+1
                    if ms>l then
                        ms = l
                        string step = sprintf("%s%d -> %d",{"/-"[j],dsk,m})
                        steps = prepend(deep_copy(cache[cdx][m]),step)
                    end if
                end if
            end for
        end for
        if steps = {} then ?9/0 end if
        cache[cdx] = append(cache[cdx],steps)
    end for
    return cache[cdx][n]
end function
 
procedure show10(sequence ds)
    printf(1,"\nWith divisors %v and subtractors %v:\n",ds)
    for n=1 to 10 do
        sequence steps = ms21(n,ds)
        integer ns = length(steps)
        string ps = iff(ns=1?"":"s"),
               eg = iff(ns=0?"":", eg "&join(steps,","))
        printf(1,"%2d takes %d step%s%s\n",{n,ns,ps,eg})
    end for
end procedure
 
procedure maxsteps(sequence ds, integer lim)
    integer ms = -1, ls
    sequence mc = {}, steps, args
    for n=1 to lim do
        steps = ms21(n,ds)
        ls = length(steps)
        if ls>ms then
            ms = ls
            mc = {n}
        elsif ls=ms then
            mc &= n
        end if
    end for
    integer lm = length(mc)
    string {are,ps,ns} = iff(lm=1?{"is","","s"}:{"are","s",""})
    args = {       are,lm,      ps,     lim,            ns,ms, shorten(mc,"",3)}
    printf(1,"There %s %d number%s below %d that require%s %d steps: %v\n",args)
end procedure
 
show10({{2,3},{1}})
maxsteps({{2,3},{1}},2000)
maxsteps({{2,3},{1}},20000)
maxsteps({{2,3},{1}},50000)
 
show10({{2,3},{2}})
maxsteps({{2,3},{2}},2000)
maxsteps({{2,3},{2}},20000)
maxsteps({{2,3},{2}},50000)
