Minimal steps down to 1

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 perferctly 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 dinminishing 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 dinminishing 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.

Perl 6

Works with: Rakudo version 2019.11

<lang perl6>use Lingua::EN::Numbers;

for [2,3], 1, 2000,

   [2,3], 1, 50000,
   [2,3], 2, 2000,
   [2,3], 2, 50000
 -> @div, $sub, $limit {
   my %min = 1 => {:op(), :v(1), :s(0)};
   (2..$limit).map( -> $n {
      my @ops;
      @ops.push: ($n / $_, "/$_") if $n %% $_ for @div;
      @ops.push: ($n - $sub, "-$sub") if $n > $sub;
      my $op = @ops.min( {%min{.[0]}} );
      %min{$n} = {:op($op[1]), :v($op[0]), :s(1 + %min{$op[0]})};
   });

~~my $max = %min.max( {.value~~} ).value~~; my @max = %min.grep( {.value. ~~== $max} )».key.sort(+*);~~~~~~~~
say "\nDivisors: {@div.perl}, subtract: $sub, threshold: {comma $limit}\n" ~ "Below {comma $limit} found {+@max} number{+@max == 1 ?? !! 's'} " ~ "that require{+@max == 1 ?? 's' !! } at least $max steps.";
for flat 1..10, @max -> $m { my @op; my $n = $m; while %min{$n} ~~{ @op.push: "{%min{$n}<op>}=>{%min{$n}<v>}"; $n = %min{$n}<v>; } say "($m) {%min{$m}~~} steps: ", @op.join(', '); }~~~~
~~}</lang>~~

~~Output:~~
Divisors: [2, 3], subtract: 1, threshold: 2,000 Below 2,000 found 16 numbers that require at least 14 steps. (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /3=>1 (4) 2 steps: /2=>2, /2=>1 (5) 3 steps: -1=>4, /2=>2, /2=>1 (6) 2 steps: /2=>3, /3=>1 (7) 3 steps: -1=>6, /2=>3, /3=>1 (8) 3 steps: /2=>4, /2=>2, /2=>1 (9) 2 steps: /3=>3, /3=>1 (10) 3 steps: -1=>9, /3=>3, /3=>1 (863) 14 steps: -1=>862, -1=>861, /3=>287, -1=>286, -1=>285, /3=>95, -1=>94, -1=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1079) 14 steps: -1=>1078, /2=>539, -1=>538, /2=>269, -1=>268, /2=>134, /2=>67, -1=>66, /2=>33, /3=>11, -1=>10, -1=>9, /3=>3, /3=>1 (1295) 14 steps: -1=>1294, /2=>647, -1=>646, /2=>323, -1=>322, /2=>161, -1=>160, /2=>80, /2=>40, /2=>20, /2=>10, -1=>9, /3=>3, /3=>1 (1439) 14 steps: -1=>1438, -1=>1437, /3=>479, -1=>478, -1=>477, /3=>159, /3=>53, -1=>52, /2=>26, /2=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1511) 14 steps: -1=>1510, /2=>755, -1=>754, /2=>377, -1=>376, /2=>188, /2=>94, -1=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1583) 14 steps: -1=>1582, /2=>791, -1=>790, -1=>789, /3=>263, -1=>262, -1=>261, /3=>87, /3=>29, -1=>28, -1=>27, /3=>9, /3=>3, /3=>1 (1607) 14 steps: -1=>1606, /2=>803, -1=>802, /2=>401, -1=>400, /2=>200, /2=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1619) 14 steps: -1=>1618, /2=>809, -1=>808, /2=>404, /2=>202, /2=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1691) 14 steps: -1=>1690, /2=>845, -1=>844, -1=>843, /3=>281, -1=>280, -1=>279, /3=>93, /3=>31, -1=>30, /3=>10, -1=>9, /3=>3, /3=>1 (1727) 14 steps: -1=>1726, -1=>1725, /3=>575, -1=>574, -1=>573, /3=>191, -1=>190, -1=>189, /3=>63, /3=>21, /3=>7, -1=>6, /2=>3, /3=>1 (1823) 14 steps: -1=>1822, /2=>911, -1=>910, -1=>909, /3=>303, /3=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (1871) 14 steps: -1=>1870, -1=>1869, /3=>623, -1=>622, -1=>621, /3=>207, /3=>69, /3=>23, -1=>22, /2=>11, -1=>10, -1=>9, /3=>3, /3=>1 (1895) 14 steps: -1=>1894, /2=>947, -1=>946, /2=>473, -1=>472, /2=>236, /2=>118, -1=>117, /3=>39, /3=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1907) 14 steps: -1=>1906, /2=>953, -1=>952, /2=>476, /2=>238, /2=>119, -1=>118, -1=>117, /3=>39, /3=>13, -1=>12, /2=>6, /2=>3, /3=>1 (1919) 14 steps: -1=>1918, -1=>1917, /3=>639, /3=>213, /3=>71, -1=>70, /2=>35, -1=>34, /2=>17, -1=>16, /2=>8, /2=>4, /2=>2, /2=>1 (1943) 14 steps: -1=>1942, /2=>971, -1=>970, /2=>485, -1=>484, /2=>242, /2=>121, -1=>120, /2=>60, /2=>30, /3=>10, -1=>9, /3=>3, /3=>1 Divisors: [2, 3], subtract: 1, threshold: 50,000 Below 50,000 found 3 numbers that require at least 22 steps. (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /3=>1 (4) 2 steps: /2=>2, /2=>1 (5) 3 steps: -1=>4, /2=>2, /2=>1 (6) 2 steps: /2=>3, /3=>1 (7) 3 steps: -1=>6, /2=>3, /3=>1 (8) 3 steps: /2=>4, /2=>2, /2=>1 (9) 2 steps: /3=>3, /3=>1 (10) 3 steps: -1=>9, /3=>3, /3=>1 (25919) 22 steps: -1=>25918, /2=>12959, -1=>12958, /2=>6479, -1=>6478, /2=>3239, -1=>3238, /2=>1619, -1=>1618, /2=>809, -1=>808, /2=>404, /2=>202, /2=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 (31103) 22 steps: -1=>31102, /2=>15551, -1=>15550, /2=>7775, -1=>7774, /2=>3887, -1=>3886, /2=>1943, -1=>1942, /2=>971, -1=>970, /2=>485, -1=>484, /2=>242, /2=>121, -1=>120, /2=>60, /2=>30, /3=>10, -1=>9, /3=>3, /3=>1 (38879) 22 steps: -1=>38878, /2=>19439, -1=>19438, /2=>9719, -1=>9718, /2=>4859, -1=>4858, /2=>2429, -1=>2428, /2=>1214, /2=>607, -1=>606, /2=>303, /3=>101, -1=>100, /2=>50, /2=>25, -1=>24, /2=>12, /2=>6, /2=>3, /3=>1 Divisors: [2, 3], subtract: 2, threshold: 2,000 Below 2,000 found 1 number that requires at least 17 steps. (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /3=>1 (4) 2 steps: /2=>2, /2=>1 (5) 2 steps: -2=>3, /3=>1 (6) 2 steps: /2=>3, /3=>1 (7) 3 steps: -2=>5, -2=>3, /3=>1 (8) 3 steps: /2=>4, /2=>2, /2=>1 (9) 2 steps: /3=>3, /3=>1 (10) 3 steps: /2=>5, -2=>3, /3=>1 (1699) 17 steps: -2=>1697, -2=>1695, /3=>565, -2=>563, -2=>561, /3=>187, -2=>185, -2=>183, /3=>61, -2=>59, -2=>57, /3=>19, -2=>17, -2=>15, /3=>5, -2=>3, /3=>1 Divisors: [2, 3], subtract: 2, threshold: 50,000 Below 50,000 found 1 number that requires at least 26 steps. (1) 0 steps: (2) 1 steps: /2=>1 (3) 1 steps: /3=>1 (4) 2 steps: /2=>2, /2=>1 (5) 2 steps: -2=>3, /3=>1 (6) 2 steps: /2=>3, /3=>1 (7) 3 steps: -2=>5, -2=>3, /3=>1 (8) 3 steps: /2=>4, /2=>2, /2=>1 (9) 2 steps: /3=>3, /3=>1 (10) 3 steps: /2=>5, -2=>3, /3=>1 (45925) 26 steps: -2=>45923, -2=>45921, /3=>15307, -2=>15305, -2=>15303, /3=>5101, -2=>5099, -2=>5097, /3=>1699, -2=>1697, -2=>1695, /3=>565, -2=>563, -2=>561, /3=>187, -2=>185, -2=>183, /3=>61, -2=>59, -2=>57, /3=>19, -2=>17, -2=>15, /3=>5, -2=>3, /3=>1
~~Python~~
~~Python: Recursive, with memoization~~
Although the stretch goal could be achieved by changing the recursion limit, it does point out a possible issue with this type of solution. But then again, this solution may be more natural to some.
<lang python> from functools import lru_cache

%%
DIVS = {2, 3} SUBS = {1}
class Minrec():
~~"Recursive, memoised minimised steps to 1"~~
~~def __init__(self, divs=DIVS, subs=SUBS): self.divs, self.subs = divs, subs~~
@lru_cache(maxsize=None) def _minrec(self, n): "Recursive, memoised" if n == 1: return 0, ['=1'] possibles = {} for d in self.divs: if n % d == 0: possibles[f'/{d}=>{n // d:2}'] = self._minrec(n // d) for s in self.subs: if n > s: possibles[f'-{s}=>{n - s:2}'] = self._minrec(n - s) thiskind, (count, otherkinds) = min(possibles.items(), key=lambda x: x[1]) ret = 1 + count, [thiskind] + otherkinds return ret
~~def __call__(self, n): "Recursive, memoised" ans = self._minrec(n)[1][:-1] return len(ans), ans~~

~~if __name__ == '__main__':~~
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]: minrec = Minrec(DIVS, SUBS) print('\nMINIMUM STEPS TO 1: Recursive algorithm') print(' Possible divisors: ', DIVS) print(' Possible decrements:', SUBS) for n in range(1, 11): steps, how = minrec(n) print(f' minrec({n:2}) in {steps:2} by: ', ', '.join(how))
upto = 2000 print(f'\n Those numbers up to {upto} that take the maximum, "minimal steps down to 1":') stepn = sorted((minrec(n)[0], n) for n in range(upto, 0, -1)) mx = stepn[-1][0] ans = [x[1] for x in stepn if x[0] == mx] print(' Taking', mx, f'steps is/are the {len(ans)} numbers:', ', '.join(str(n) for n in sorted(ans))) #print(minrec._minrec.cache_info()) print()</lang>

~~Output:~~
MINIMUM STEPS TO 1: Recursive algorithm Possible divisors: {2, 3} Possible decrements: {1} minrec( 1) in 0 by: minrec( 2) in 1 by: /2=> 1 minrec( 3) in 1 by: /3=> 1 minrec( 4) in 2 by: /2=> 2, /2=> 1 minrec( 5) in 3 by: -1=> 4, /2=> 2, /2=> 1 minrec( 6) in 2 by: /3=> 2, /2=> 1 minrec( 7) in 3 by: -1=> 6, /3=> 2, /2=> 1 minrec( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 minrec( 9) in 2 by: /3=> 3, /3=> 1 minrec(10) in 3 by: -1=> 9, /3=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 14 steps is/are the 16 numbers: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943 MINIMUM STEPS TO 1: Recursive algorithm Possible divisors: {2, 3} Possible decrements: {2} minrec( 1) in 0 by: minrec( 2) in 1 by: /2=> 1 minrec( 3) in 1 by: /3=> 1 minrec( 4) in 2 by: /2=> 2, /2=> 1 minrec( 5) in 2 by: -2=> 3, /3=> 1 minrec( 6) in 2 by: /3=> 2, /2=> 1 minrec( 7) in 3 by: -2=> 5, -2=> 3, /3=> 1 minrec( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 minrec( 9) in 2 by: /3=> 3, /3=> 1 minrec(10) in 3 by: /2=> 5, -2=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 17 steps is/are the 1 numbers: 1699
~~Python: Tabulated~~
The stretch goal is attempted.
The table to solve for N contains all the results from 1 up to N. This is used in the solution.
<lang python>class Mintab():
~~"Tabulation, memoised minimised steps to 1"~~
~~def __init__(self, divs=DIVS, subs=SUBS): self.divs, self.subs = divs, subs self.table = None # Last tabulated table self.hows = None # Last tabulated sample steps~~
~~def _mintab(self, n): "Tabulation, memoised minimised steps to 1" divs, subs = self.divs, self.subs~~
table = [n + 2] * (n + 1) # sentinels table[1] = 0 # zero steps to 1 from 1 how = [[] for _ in range(n + 2)] # What steps are taken how[1] = ['='] for t in range(1, n): thisplus1 = table[t] + 1 for d in divs: dt = d * t if dt <= n and thisplus1 < table[dt]: table[dt] = thisplus1 how[dt] = how[t] + [f'/{d}=>{t:2}'] for s in subs: st = s + t if st <= n and thisplus1 < table[st]: table[st] = thisplus1 how[st] = how[t] + [f'-{s}=>{t:2}'] self.table = table self.hows = [h[::-1][:-1] for h in how] # Order and trim return self.table, self.hows
~~def __call__(self, n): "Tabulation" table, hows = self._mintab(n) return table[n], hows[n]~~

~~if __name__ == '__main__':~~
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]: print('\nMINIMUM STEPS TO 1: Tabulation algorithm') print(' Possible divisors: ', DIVS) print(' Possible decrements:', SUBS) mintab = Mintab(DIVS, SUBS) mintab(10) table, hows = mintab.table, mintab.hows for n in range(1, 11): steps, how = table[n], hows[n] print(f' mintab({n:2}) in {steps:2} by: ', ', '.join(how))
for upto in [2000, 50_000]: mintab(upto) table = mintab.table print(f'\n Those numbers up to {upto} that take the maximum, "minimal steps down to 1":') mx = max(table[1:]) ans = [n for n, steps in enumerate(table) if steps == mx] print(' Taking', mx, f'steps is/are the {len(ans)} numbers:', ', '.join(str(n) for n in ans))</lang>

~~Output:~~
MINIMUM STEPS TO 1: Tabulation algorithm Possible divisors: {2, 3} Possible decrements: {1} mintab( 1) in 0 by: mintab( 2) in 1 by: /2=> 1 mintab( 3) in 1 by: /3=> 1 mintab( 4) in 2 by: /2=> 2, /2=> 1 mintab( 5) in 3 by: -1=> 4, /2=> 2, /2=> 1 mintab( 6) in 2 by: /3=> 2, /2=> 1 mintab( 7) in 3 by: -1=> 6, /3=> 2, /2=> 1 mintab( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 mintab( 9) in 2 by: /3=> 3, /3=> 1 mintab(10) in 3 by: -1=> 9, /3=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 14 steps is/are the 16 numbers: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943 Those numbers up to 50000 that take the maximum, "minimal steps down to 1": Taking 22 steps is/are the 3 numbers: 25919, 31103, 38879 MINIMUM STEPS TO 1: Tabulation algorithm Possible divisors: {2, 3} Possible decrements: {2} mintab( 1) in 0 by: mintab( 2) in 1 by: /2=> 1 mintab( 3) in 1 by: /3=> 1 mintab( 4) in 2 by: /2=> 2, /2=> 1 mintab( 5) in 2 by: -2=> 3, /3=> 1 mintab( 6) in 2 by: /3=> 2, /2=> 1 mintab( 7) in 3 by: -2=> 5, -2=> 3, /3=> 1 mintab( 8) in 3 by: /2=> 4, /2=> 2, /2=> 1 mintab( 9) in 2 by: /3=> 3, /3=> 1 mintab(10) in 3 by: /2=> 5, -2=> 3, /3=> 1 Those numbers up to 2000 that take the maximum, "minimal steps down to 1": Taking 17 steps is/are the 1 numbers: 1699 Those numbers up to 50000 that take the maximum, "minimal steps down to 1": Taking 26 steps is/are the 1 numbers: 45925
~~zkl~~
~~<lang zkl></lang> <lang zkl></lang>~~

~~Output:~~