Minimal steps down to 1

Minimal steps down to 1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Given:

• A starting, positive integer (greater than one), N.
• A selection of possible integer perfect devisors, 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

Ref

[Learn Dynamic Programming (Memoization & Tabulation)] Video of similar task.

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

1. %%

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]

</lang>

Output:

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))