Minimal steps down to 1: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 535: Line 535:
}}
}}
</lang>
</lang>

Counting the steps is rather trivial -- we build a step function which subtracts the possible subtractors (discarding numbers which are too small) and divides by the possible divisors (discarding numbers which are not integers), then we iterate on that until we find a 1.

Showing the paths is more complicated. The approach used here is to first find the valid step values and then, starting from 1, add the possible subtractors, and multiply by the possible divisors, discarding the values which were not valid for that step and tracking the previous values. Once we have built a representation of the valid paths (at each stage: operator, operand and net result) we reverse and format those.


Task examples:
Task examples:

Revision as of 17:15, 17 January 2022

Task
Minimal steps down to 1
You are encouraged to solve this task according to the task description, using any language you may know.


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

11l

Translation of: Python: Tabulated

<lang 11l>T Mintab 

  Set[Int] divs, subs
  [Int] table
  String hows

  F (divs, subs)
     .divs = copy(divs)
     .subs = copy(subs)

  F _mintab(n)
     ‘Tabulation, memoised minimised steps to 1’
     V table = [n + 2] * (n + 1)
     table[1] = 0
     V how = (0 .< n + 2).map(_ -> [‘’])
     how[1] = [String(‘=’)]
     L(t) 1 .< n
        V thisplus1 = table[t] + 1
        L(d) .divs
           V dt = d * t
           I dt <= n & thisplus1 < table[dt]
              table[dt] = thisplus1
              how[dt] = how[t] [+] [‘/#.=>#2’.format(d, t)]
        L(s) .subs
           V st = s + t
           I st <= n & thisplus1 < table[st]
              table[st] = thisplus1
              how[st] = how[t] [+] [‘-#.=>#2’.format(s, t)]
     .table = table
     .hows = how.map(h -> reversed(h)[0 .< (len)-1])
     R (.table, .hows)

  F ()(n)
     ‘Tabulation’
     V (table, hows) = ._mintab(n)
     R (table[n], hows[n])

L(DIVS, SUBS) [([2, 3], [1]), ([2, 3], [2])] 

  print("\nMINIMUM STEPS TO 1: Tabulation algorithm")
  print(‘  Possible divisors:   ’DIVS)
  print(‘  Possible decrements: ’SUBS)
  V mintab = Mintab(Set(DIVS), Set(SUBS))
  mintab(10)
  L(n) 1..10
     V (steps, how) = (mintab.table[n], mintab.hows[n])
     print(‘    mintab(#2) in #2 by: ’.format(n, steps)‘ ’how.join(‘, ’))

  L(upto) [2000, 50'000]
     mintab(upto)
     print("\n    Those numbers up to "upto‘ that take the maximum, "minimal steps down to 1":’)
     V mx = max(mintab.table[1..])
     V ans = enumerate(mintab.table).filter((n, steps) -> steps == @mx).map((n, steps) -> n)
     print(‘      Taking ’mx‘ steps is/are the ’ans.len‘ numbers: ’ans.map(n -> String(n)).join(‘, ’))</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

C#

Works with: C sharp version 7

<lang csharp>using System; using System.Collections.Generic; using System.Linq;

public static class MinimalSteps { 

   public static void Main() {
       var (divisors, subtractors) = (new int[] { 2, 3 }, new [] { 1 });
       var lookup = CreateLookup(2_000, divisors, subtractors);
       Console.WriteLine($"Divisors: [{divisors.Delimit()}], Subtractors: [{subtractors.Delimit()}]");
       PrintRange(lookup, 10);
       PrintMaxMins(lookup);
       lookup = CreateLookup(20_000, divisors, subtractors);
       PrintMaxMins(lookup);
       Console.WriteLine();

       subtractors = new [] { 2 };
       lookup = CreateLookup(2_000, divisors, subtractors);
       Console.WriteLine($"Divisors: [{divisors.Delimit()}], Subtractors: [{subtractors.Delimit()}]");
       PrintRange(lookup, 10);
       PrintMaxMins(lookup);
       lookup = CreateLookup(20_000, divisors, subtractors);
       PrintMaxMins(lookup);
   }

   private static void PrintRange((char op, int param, int steps)[] lookup, int limit) {
       for (int goal = 1; goal <= limit; goal++) {
           var x = lookup[goal];
           if (x.param == 0) {
               Console.WriteLine($"{goal} cannot be reached with these numbers.");
               continue;
           }
           Console.Write($"{goal} takes {x.steps} {(x.steps == 1 ? "step" : "steps")}: ");
           for (int n = goal; n > 1; ) {
               Console.Write($"{n},{x.op}{x.param}=> ");
               n = x.op == '/' ? n / x.param : n - x.param;
               x = lookup[n];
           }
           Console.WriteLine("1");
       }
   }

   private static void PrintMaxMins((char op, int param, int steps)[] lookup) {
       var maxSteps = lookup.Max(x => x.steps);
       var items = lookup.Select((x, i) => (i, x)).Where(t => t.x.steps == maxSteps).ToList();
       Console.WriteLine(items.Count == 1
           ? $"There is one number below {lookup.Length-1} that requires {maxSteps} steps: {items[0].i}"
           : $"There are {items.Count} numbers below {lookup.Length-1} that require {maxSteps} steps: {items.Select(t => t.i).Delimit()}"
       );
   }

   private static (char op, int param, int steps)[] CreateLookup(int goal, int[] divisors, int[] subtractors)
   {
       var lookup = new (char op, int param, int steps)[goal+1];
       lookup[1] = ('/', 1, 0);
       for (int n = 1; n < lookup.Length; n++) {
           var ln = lookup[n];
           if (ln.param == 0) continue;
           for (int d = 0; d < divisors.Length; d++) {
               int target = n * divisors[d];
               if (target > goal) break;
               if (lookup[target].steps == 0 || lookup[target].steps > ln.steps) lookup[target] = ('/', divisors[d], ln.steps + 1);
           }
           for (int s = 0; s < subtractors.Length; s++) {
               int target = n + subtractors[s];
               if (target > goal) break;
               if (lookup[target].steps == 0 || lookup[target].steps > ln.steps) lookup[target] = ('-', subtractors[s], ln.steps + 1);
           }
       }
       return lookup;
   }

   private static string Delimit<T>(this IEnumerable<T> source) => string.Join(", ", source);

}</lang>

Output:
Divisors: [2, 3], Subtractors: [1]
1 takes 0 steps: 1
2 takes 1 step: 2,-1=> 1
3 takes 1 step: 3,/3=> 1
4 takes 2 steps: 4,-1=> 3,/3=> 1
5 takes 3 steps: 5,-1=> 4,-1=> 3,/3=> 1
6 takes 2 steps: 6,/2=> 3,/3=> 1
7 takes 3 steps: 7,-1=> 6,/2=> 3,/3=> 1
8 takes 3 steps: 8,/2=> 4,-1=> 3,/3=> 1
9 takes 2 steps: 9,/3=> 3,/3=> 1
10 takes 3 steps: 10,-1=> 9,/3=> 3,/3=> 1
There are 16 numbers below 2000 that require 14 steps: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943
There are 5 numbers below 20000 that require 20 steps: 12959, 15551, 17279, 18143, 19439

Divisors: [2, 3], Subtractors: [2]
1 takes 0 steps: 1
2 takes 1 step: 2,/2=> 1
3 takes 1 step: 3,-2=> 1
4 takes 2 steps: 4,-2=> 2,/2=> 1
5 takes 2 steps: 5,-2=> 3,-2=> 1
6 takes 2 steps: 6,/2=> 3,-2=> 1
7 takes 3 steps: 7,-2=> 5,-2=> 3,-2=> 1
8 takes 3 steps: 8,-2=> 6,/2=> 3,-2=> 1
9 takes 2 steps: 9,/3=> 3,-2=> 1
10 takes 3 steps: 10,/2=> 5,-2=> 3,-2=> 1
There is one number below 2000 that requires 17 steps: 1699
There is one number below 20000 that requires 24 steps: 19681

Go

<lang go>package main

import ( 

   "fmt"
   "strings"

)

const limit = 50000

var ( 

   divs, subs []int
   mins       [][]string

)

// Assumes the numbers are presented in order up to 'limit'. func minsteps(n int) { 

   if n == 1 {
       mins[1] = []string{}
       return
   }
   min := limit
   var p, q int
   var op byte
   for _, div := range divs {
       if n%div == 0 {
           d := n / div
           steps := len(mins[d]) + 1
           if steps < min {
               min = steps
               p, q, op = d, div, '/'
           }
       }
   }
   for _, sub := range subs {
       if d := n - sub; d >= 1 {
           steps := len(mins[d]) + 1
           if steps < min {
               min = steps
               p, q, op = d, sub, '-'
           }
       }
   }
   mins[n] = append(mins[n], fmt.Sprintf("%c%d -> %d", op, q, p))
   mins[n] = append(mins[n], mins[p]...)

}

func main() { 

   for r := 0; r < 2; r++ {
       divs = []int{2, 3}
       if r == 0 {
           subs = []int{1}
       } else {
           subs = []int{2}
       }
       mins = make([][]string, limit+1)
       fmt.Printf("With: Divisors: %v, Subtractors: %v =>\n", divs, subs)
       fmt.Println("  Minimum number of steps to diminish the following numbers down to 1 is:")
       for i := 1; i <= limit; i++ {
           minsteps(i)
           if i <= 10 {
               steps := len(mins[i])
               plural := "s"
               if steps == 1 {
                   plural = " "
               }
               fmt.Printf("    %2d: %d step%s: %s\n", i, steps, plural, strings.Join(mins[i], ", "))
           }
       }
       for _, lim := range []int{2000, 20000, 50000} {
           max := 0
           for _, min := range mins[0 : lim+1] {
               m := len(min)
               if m > max {
                   max = m
               }
           }
           var maxs []int
           for i, min := range mins[0 : lim+1] {
               if len(min) == max {
                   maxs = append(maxs, i)
               }
           }
           nums := len(maxs)
           verb, verb2, plural := "are", "have", "s"
           if nums == 1 {
               verb, verb2, plural = "is", "has", ""
           }
           fmt.Printf("  There %s %d number%s in the range 1-%d ", verb, nums, plural, lim)
           fmt.Printf("that %s maximum 'minimal steps' of %d:\n", verb2, max)
           fmt.Println("   ", maxs)
       }
       fmt.Println()
   }

}</lang>

Output:
With: Divisors: [2 3], Subtractors: [1] =>
  Minimum number of steps to diminish the following numbers down to 1 is:
     1: 0 steps: 
     2: 1 step : /2 -> 1
     3: 1 step : /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
  There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
    [863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943]
  There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20:
    [12959 15551 17279 18143 19439]
  There are 3 numbers in the range 1-50000 that have maximum 'minimal steps' of 22:
    [25919 31103 38879]

With: Divisors: [2 3], Subtractors: [2] =>
  Minimum number of steps to diminish the following numbers down to 1 is:
     1: 0 steps: 
     2: 1 step : /2 -> 1
     3: 1 step : /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
  There is 1 number in the range 1-2000 that has maximum 'minimal steps' of 17:
    [1699]
  There is 1 number in the range 1-20000 that has maximum 'minimal steps' of 24:
    [19681]
  There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26:
    [45925]

Haskell

<lang haskell>{-# LANGUAGE DeriveFunctor #-} import Data.List import Data.Ord import Data.Function (on)

-- memoization utilities

data Memo a = Node a (Memo a) (Memo a) 

 deriving Functor

memo :: Integral a => Memo p -> a -> p memo (Node a l r) n 

 | n == 0 = a
 | odd n = memo l (n `div` 2)
 | otherwise = memo r (n `div` 2 - 1)

nats :: Integral a => Memo a nats = Node 0 ((+1).(*2) <$> nats) ((*2).(+1) <$> nats)

memoize :: Integral a => (a -> b) -> (a -> b) memoize f = memo (f <$> nats)

data Step = Div Int | Sub Int 

 deriving Show

run :: Int -> Step -> [(Step, Int)] run n s = case s of 

 Sub i | n > i -> [(s, n - i)]
 Div d | n `mod` d == 0 -> [(s, n `div` d)]
 _ -> []

minSteps :: [Step] -> Int -> (Int, [Step]) minSteps steps = go 

 where
   go = memoize goM
   
   goM 1 = (0, [])
   goM n = minimumBy (comparing fst) $ do
     (s, k) <- steps >>= run n
     let (m, ss) = go k
     return (m+1, s:ss)</lang>

λ> minSteps [Div 2, Div 3, Sub 1] 123
(7,[Div 3,Sub 1,Div 2,Div 2,Sub 1,Div 3,Div 3])

λ> minSteps [Div 5, Div 2, Sub 1, Sub 2] 123
(7,[Sub 1,Div 2,Sub 1,Div 5,Div 2,Div 2,Sub 2])

The task

<lang haskell>showSteps :: Int -> [Step] -> String showSteps = foldl go . show 

 where
   go r (Div d) = r ++ "/" ++ show d
   go r (Sub s) = "(" ++ r ++ "-" ++ show s ++ ")"


task steps = mapM_ (put . go) [1..10] 

 where
   go n = showSteps n <$> minSteps steps n
   put (n,s) = putStrLn $ show n ++ ":\t" ++ s

task2 steps range = mapM_ put longest 

 where
   put (n,(l,s)) = putStrLn $ show l ++ ": " ++
                   showSteps n s
   longest = 
     head $ groupBy ((==) `on` (fst.snd)) $
     sortOn (negate . fst . snd) $
     zip [1..] (minSteps steps <$> range)</lang>

λ> task1 [Div 2, Div 3, Sub 1]
0:	1
1:	2/2
1:	3/3
2:	4/2/2
3:	(5-1)/2/2
2:	6/2/3
3:	(7-1)/2/3
3:	8/2/2/2
2:	9/3/3
3:	(10-1)/3/3

λ> task2 [Div 2, Div 3, Sub 1] [1..2000]
14: ((((((((863-1)-1)/3-1)-1)/3-1)-1)/3-1)/3-1)/3/3
14: ((((((1079-1)/2-1)/2-1)/2/2-1)/2/3-1)-1)/3/3
14: (((((1295-1)/2-1)/2-1)/2-1)/2/2/2/2-1)/3/3
14: ((((((1439-1)-1)/3-1)-1)/3/3-1)/2/2-1)/2/2/3
14: ((((((1511-1)/2-1)/2-1)/2/2-1)/3-1)/3-1)/3/3
14: (((((((1583-1)/2-1)-1)/3-1)-1)/3/3-1)-1)/3/3/3
14: ((((1607-1)/2-1)/2-1)/2/2/2/2-1)/2/2/2/3
14: ((((1619-1)/2-1)/2/2/2-1)/2/2-1)/2/2/2/3
14: (((((((1691-1)/2-1)-1)/3-1)-1)/3/3-1)/3-1)/3/3
14: (((((((1727-1)-1)/3-1)-1)/3-1)-1)/3/3/3-1)/2/3
14: (((((1823-1)/2-1)-1)/3/3-1)/2/2-1)/2/2/2/3
14: (((((((1871-1)-1)/3-1)-1)/3/3/3-1)/2-1)-1)/3/3
14: (((((1895-1)/2-1)/2-1)/2/2-1)/3/3-1)/2/2/3
14: (((((1907-1)/2-1)/2/2/2-1)-1)/3/3-1)/2/2/3
14: (((((1919-1)-1)/3/3/3-1)/2-1)/2-1)/2/2/2/2
14: (((((1943-1)/2-1)/2-1)/2/2-1)/2/2/3-1)/3/3

λ> task1 [Div 2, Div 3, Sub 2]
0:	1
1:	2/2
1:	3/3
2:	4/2/2
2:	(5-2)/3
2:	6/2/3
3:	((7-2)-2)/3
3:	8/2/2/2
2:	9/3/3
3:	(10/2-2)/3

λ> task2 [Div 2, Div 3, Sub 2] [1..2000]
17: (((((((((((1699-2)-2)/3-2)-2)/3-2)-2)/3-2)-2)/3-2)-2)/3-2)/3

J

Implementation: <lang J>step=: Template:~.((

steps=: {{ 

 m step n^:(1 - 1 e. ])^:a:

}}

show=: {{ 

 k=.,:,:0 0 1
 m=.,m [ n=.,n
 for_ok.}.|.m steps n y do.
   last=.{:"2 k
   subs=. (1,.m,.0)+"2]0 0 1*"1 last+"1 0/m
   divs=. (2,.n,.0)+"2]0 0 1*"1 last*"1 0/n
   next=. subs,"2 divs
   k=. (,({:"1 next)e.ok)#,/k,"2 1/"2 next
 end.
 ;@((<":y),_2 }. ,)"2((' -/'{~{.);":@{:)"1 }:"1 |."2 k

}} </lang>

Counting the steps is rather trivial -- we build a step function which subtracts the possible subtractors (discarding numbers which are too small) and divides by the possible divisors (discarding numbers which are not integers), then we iterate on that until we find a 1.

Showing the paths is more complicated. The approach used here is to first find the valid step values and then, starting from 1, add the possible subtractors, and multiply by the possible divisors, discarding the values which were not valid for that step and tracking the previous values. Once we have built a representation of the valid paths (at each stage: operator, operand and net result) we reverse and format those.

Task examples:

<lang J>taskA=: {{ 

  for_j. 1+i.10 do.
    echo j,&":': ',(_1+#x steps y j),&":' steps.'
    echo x show y j
    echo 
  end.

}}

taskB=: {{ 

  echo 'considering positive integers up to ',":m
  tallies=. _1+#@(x steps y)every 1+i.m
  echo (>./tallies) ,&": ' steps: ',&": 1+I.(=>./)tallies
  echo

}}

task=: 2e4 taskB, 2e3 taskB, taskA 

  1 task 2 3

1: 0 steps. 1

2: 1 steps. 2-1 2/2

3: 1 steps. 3/3

4: 2 steps. 4/2-1 4/2/2 4-1/3

5: 3 steps. 5-1/2-1 5-1/2/2 5-1-1/3

6: 2 steps. 6/3-1 6/3/2 6/2/3

7: 3 steps. 7-1/3-1 7-1/3/2 7-1/2/3

8: 3 steps. 8/2/2-1 8/2/2/2 8/2-1/3

9: 2 steps. 9/3/3

10: 3 steps. 10-1/3/3

considering positive integers up to 2000 14 steps: 863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943

considering positive integers up to 20000 20 steps: 12959 15551 17279 18143 19439 

  2 task 2 3

1: 0 steps. 1

2: 1 steps. 2/2

3: 1 steps. 3-2 3/3

4: 2 steps. 4-2/2 4/2/2

5: 2 steps. 5-2-2 5-2/3

6: 2 steps. 6/2-2 6/3/2 6/2/3

7: 3 steps. 7-2-2-2 7-2-2/3

8: 3 steps. 8-2/2-2 8/2-2/2 8/2/2/2 8-2/3/2 8-2/2/3

9: 2 steps. 9/3-2 9/3/3

10: 3 steps. 10/2-2-2 10/2-2/3

considering positive integers up to 2000 17 steps: 1699

considering positive integers up to 20000 24 steps: 19681</lang>

Java

Algorithm works with any function that supports the Function interface in the code below.

<lang java> import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map;

public class MinimalStepsDownToOne { 

   public static void main(String[] args) {
       runTasks(getFunctions1());
       runTasks(getFunctions2());
       runTasks(getFunctions3());
   }
   
   private static void runTasks(List<Function> functions) {
       Map<Integer,List<String>> minPath = getInitialMap(functions, 5);

       //  Task 1
       int max = 10;
       populateMap(minPath, functions, max);
       System.out.printf("%nWith functions:  %s%n", functions);
       System.out.printf("  Minimum steps to 1:%n");
       for ( int n = 2 ; n <= max ; n++ ) {
           int steps = minPath.get(n).size();
           System.out.printf("    %2d: %d step%1s: %s%n", n, steps, steps == 1 ? "" : "s", minPath.get(n));
       }
       
       //  Task 2
       displayMaxMin(minPath, functions, 2000);

       //  Task 2a
       displayMaxMin(minPath, functions, 20000);

       //  Task 2a +
       displayMaxMin(minPath, functions, 100000);
   }
   
   private static void displayMaxMin(Map<Integer,List<String>> minPath, List<Function> functions, int max) {
       populateMap(minPath, functions, max);
       List<Integer> maxIntegers = getMaxMin(minPath, max);
       int maxSteps = maxIntegers.remove(0);
       int numCount = maxIntegers.size();
       System.out.printf("  There %s %d number%s in the range 1-%d that have maximum 'minimal steps' of %d:%n    %s%n", numCount == 1 ? "is" : "are", numCount, numCount == 1 ? "" : "s", max, maxSteps, maxIntegers);
       
   }
   
   private static List<Integer> getMaxMin(Map<Integer,List<String>> minPath, int max) {
       int maxSteps = Integer.MIN_VALUE;
       List<Integer> maxIntegers = new ArrayList<Integer>();
       for ( int n = 2 ; n <= max ; n++ ) {
           int len = minPath.get(n).size();
           if ( len > maxSteps ) {
               maxSteps = len;
               maxIntegers.clear();
               maxIntegers.add(n);
           }
           else if ( len == maxSteps ) {
               maxIntegers.add(n);
           }
       }
       maxIntegers.add(0, maxSteps);
       return maxIntegers;
   }

   private static void populateMap(Map<Integer,List<String>> minPath, List<Function> functions, int max) {
       for ( int n = 2 ; n <= max ; n++ ) {
           if ( minPath.containsKey(n) ) {
               continue;
           }
           Function minFunction = null;
           int minSteps = Integer.MAX_VALUE;
           for ( Function f : functions ) {
               if ( f.actionOk(n) ) {
                   int result = f.action(n);
                   int steps = 1 + minPath.get(result).size();
                   if ( steps < minSteps ) {
                       minFunction = f;
                       minSteps = steps;
                   }
               }
           }
           int result = minFunction.action(n);
           List<String> path = new ArrayList<String>();
           path.add(minFunction.toString(n));
           path.addAll(minPath.get(result));
           minPath.put(n, path);
       }
       
   }

   private static Map<Integer,List<String>> getInitialMap(List<Function> functions, int max) {
       Map<Integer,List<String>> minPath = new HashMap<>();
       for ( int i = 2 ; i <= max ; i++ ) {
           for ( Function f : functions ) {
               if ( f.actionOk(i) ) {
                   int result = f.action(i);
                   if ( result == 1 ) {
                       List<String> path = new ArrayList<String>();
                       path.add(f.toString(i));
                       minPath.put(i, path);
                   }
               }
           }
       }
       return minPath;
   }

   private static List<Function> getFunctions3() {
       List<Function> functions = new ArrayList<>();
       functions.add(new Divide2Function());
       functions.add(new Divide3Function());
       functions.add(new Subtract2Function());
       functions.add(new Subtract1Function());
       return functions;
   }

   private static List<Function> getFunctions2() {
       List<Function> functions = new ArrayList<>();
       functions.add(new Divide3Function());
       functions.add(new Divide2Function());
       functions.add(new Subtract2Function());
       return functions;
   }

   private static List<Function> getFunctions1() {
       List<Function> functions = new ArrayList<>();
       functions.add(new Divide3Function());
       functions.add(new Divide2Function());
       functions.add(new Subtract1Function());
       return functions;
   }
   
   public abstract static class Function {
       abstract public int action(int n);
       abstract public boolean actionOk(int n);
       abstract public String toString(int n);
   }
   
   public static class Divide2Function extends Function {
       @Override public int action(int n) {
           return n/2;
       }

       @Override public boolean actionOk(int n) {
           return n % 2 == 0;
       }

       @Override public String toString(int n) {
           return "/2 -> " + n/2;
       }
       
       @Override public String toString() {
           return "Divisor 2";
       }
       
   }

   public static class Divide3Function extends Function {
       @Override public int action(int n) {
           return n/3;
       }

       @Override public boolean actionOk(int n) {
           return n % 3 == 0;
       }

       @Override public String toString(int n) {
           return "/3 -> " + n/3;
       }

       @Override public String toString() {
           return "Divisor 3";
       }

   }

   public static class Subtract1Function extends Function {
       @Override public int action(int n) {
           return n-1;
       }

       @Override public boolean actionOk(int n) {
           return true;
       }
   
       @Override public String toString(int n) {
           return "-1 -> " + (n-1);
       }

       @Override public String toString() {
           return "Subtractor 1";
       }

   }

   public static class Subtract2Function extends Function {
       @Override public int action(int n) {
           return n-2;
       }

       @Override public boolean actionOk(int n) {
           return n > 2;
       }
   
       @Override public String toString(int n) {
           return "-2 -> " + (n-2);
       }

       @Override public String toString() {
           return "Subtractor 2";
       }

   }

} </lang>

Output:

With functions:  [Divisor 3, Divisor 2, Subtractor 1]
  Minimum steps to 1:
     2: 1 step : [-1 -> 1]
     3: 1 step : [/3 -> 1]
     4: 2 steps: [/2 -> 2, -1 -> 1]
     5: 3 steps: [-1 -> 4, /2 -> 2, -1 -> 1]
     6: 2 steps: [/3 -> 2, -1 -> 1]
     7: 3 steps: [-1 -> 6, /3 -> 2, -1 -> 1]
     8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1]
     9: 2 steps: [/3 -> 3, /3 -> 1]
    10: 3 steps: [-1 -> 9, /3 -> 3, /3 -> 1]
  There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
    [863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943]
  There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20:
    [12959, 15551, 17279, 18143, 19439]
  There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 24:
    [77759]

With functions:  [Divisor 3, Divisor 2, Subtractor 2]
  Minimum steps to 1:
     2: 1 step : [/2 -> 1]
     3: 1 step : [-2 -> 1]
     4: 2 steps: [/2 -> 2, /2 -> 1]
     5: 2 steps: [-2 -> 3, -2 -> 1]
     6: 2 steps: [/3 -> 2, /2 -> 1]
     7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1]
     8: 3 steps: [/2 -> 4, /2 -> 2, /2 -> 1]
     9: 2 steps: [/3 -> 3, -2 -> 1]
    10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1]
  There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 17:
    [1699]
  There is 1 number in the range 1-20000 that have maximum 'minimal steps' of 24:
    [19681]
  There is 1 number in the range 1-100000 that have maximum 'minimal steps' of 28:
    [98413]

With functions:  [Divisor 2, Divisor 3, Subtractor 2, Subtractor 1]
  Minimum steps to 1:
     2: 1 step : [-1 -> 1]
     3: 1 step : [-2 -> 1]
     4: 2 steps: [/2 -> 2, -1 -> 1]
     5: 2 steps: [-2 -> 3, -2 -> 1]
     6: 2 steps: [/2 -> 3, -2 -> 1]
     7: 3 steps: [-2 -> 5, -2 -> 3, -2 -> 1]
     8: 3 steps: [/2 -> 4, /2 -> 2, -1 -> 1]
     9: 2 steps: [/3 -> 3, -2 -> 1]
    10: 3 steps: [/2 -> 5, -2 -> 3, -2 -> 1]
  There is 1 number in the range 1-2000 that have maximum 'minimal steps' of 13:
    [1943]
  There are 2 numbers in the range 1-20000 that have maximum 'minimal steps' of 17:
    [17495, 19439]
  There are 22 numbers in the range 1-100000 that have maximum 'minimal steps' of 19:
    [58319, 69983, 76463, 77759, 78623, 87479, 89423, 90071, 90287, 90359, 90383, 90395, 91259, 91355, 91367, 93311, 95255, 95471, 95903, 96119, 96191, 98171]

Julia

This is a non-recursive solution that is memoized for the count-only portions of the task, but not memoized when an example is to be listed. Interestingly, for the specified tasks only the starting points of 2 and 3 are processed without use of memoization.

Implemented as a generic solution for any functions acting on an integer and taking any range of second arguments, with the goal solution also specifiable. To do so generically, it is also necessary to specify a failure condition, which in the example is falling below 1. <lang julia>import Base.print

struct Action{T} 

   f::Function
   i::T

end

struct ActionOutcome{T} 

   act::Action{T}
   out::T

end

Base.print(io::IO, ao::ActionOutcome) = print(io, "$(ao.act.f) $(ao.act.i) yields $(ao.out)")

memoized = Dict{Int, Int}()

function findshortest(start, goal, fails, actions, verbose=true, maxsteps=100000) 

   solutions, numsteps = Vector{Vector{ActionOutcome}}(), 0
   seqs = [ActionOutcome[ActionOutcome(Action(div, 0), start)]]
   if start == goal
       verbose && println("For start of $start, no steps needed.\n")
       return 0
   end
   while numsteps < maxsteps && isempty(solutions)
       newsequences = Vector{Vector{ActionOutcome}}()
       numsteps += 1
       for seq in seqs
           for (act, arr) in actions, x in arr
               result = act(seq[end].out, x)
               if !fails(result)
                   newactionseq = vcat(seq, ActionOutcome(Action(act, x), result))
                   numsteps == 1 && popfirst!(newactionseq)
                   if result == goal
                       push!(solutions, newactionseq)
                   else
                       push!(newsequences, newactionseq)
                   end
               end
           end
           if !verbose && isempty(solutions) &&
                          all(x -> haskey(memoized, x[end].out), newsequences)
               minresult = minimum(x -> memoized[x[end].out], newsequences) + numsteps
               memoized[start] = minresult
               return minresult
           end
       end
       seqs = newsequences
   end
   if verbose
       l = length(solutions)
       print("There ", l > 1 ? "are $l solutions" : "is $l solution", 
           " for path of length ", numsteps, " from $start to $goal.\nExample: ")
       for step in solutions[1]
           print(step, step.out == 1 ? "\n\n" : ", ")
       end
   end
   memoized[start] = numsteps
   return numsteps

end

failed(n) = n < 1

const divisors = [2, 3] divide(n, x) = begin q, r = divrem(n, x); r == 0 ? q : -1 end

const subtractors1, subtractors2 = [1], [2] subtract(n, x) = n - x

actions1 = Dict(divide => divisors, subtract => subtractors1) actions2 = Dict(divide => divisors, subtract => subtractors2)

function findmaxshortest(g, fails, acts, maxn) 

   stepcounts = [findshortest(n, g, fails, acts, false) for n in 1:maxn]
   maxs = maximum(stepcounts)
   maxstepnums = findall(x -> x == maxs, stepcounts)
   println("There are $(length(maxstepnums)) with $maxs steps for start between 1 and $maxn: ", maxstepnums)

end

function teststeps(g, fails, acts, maxes) 

   println("\nWith goal $g, divisors $(acts[divide]), subtractors $(acts[subtract]):")
   for n in 1:10
       findshortest(n, g, fails, acts)
   end
   for maxn in maxes
       findmaxshortest(g, fails, acts, maxn)
   end

end

teststeps(1, failed, actions1, [2000, 20000, 50000]) empty!(memoized) teststeps(1, failed, actions2, [2000, 20000, 50000])

</lang>

Output:
With goal 1, divisors [2, 3], subtractors [1]:
For start of 1, no steps needed.

There are 2 solutions for path of length 1 from 2 to 1.
Example: divide 2 yields 1

There is 1 solution for path of length 1 from 3 to 1.
Example: divide 3 yields 1

There are 3 solutions for path of length 2 from 4 to 1.
Example: divide 2 yields 2, divide 2 yields 1

There are 3 solutions for path of length 3 from 5 to 1.
Example: subtract 1 yields 4, divide 2 yields 2, divide 2 yields 1

There are 3 solutions for path of length 2 from 6 to 1.
Example: divide 2 yields 3, divide 3 yields 1

There are 3 solutions for path of length 3 from 7 to 1.
Example: subtract 1 yields 6, divide 2 yields 3, divide 3 yields 1

There are 3 solutions for path of length 3 from 8 to 1.
Example: divide 2 yields 4, divide 2 yields 2, divide 2 yields 1

There is 1 solution for path of length 2 from 9 to 1.
Example: divide 3 yields 3, divide 3 yields 1

There is 1 solution for path of length 3 from 10 to 1.
Example: subtract 1 yields 9, divide 3 yields 3, divide 3 yields 1

There are 16 with 14 steps for start between 1 and 2000: [863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943]
There are 5 with 20 steps for start between 1 and 20000: [12959, 15551, 17279, 18143, 19439]
There are 3 with 22 steps for start between 1 and 50000: [25919, 31103, 38879]

With goal 1, divisors [2, 3], subtractors [2]:
For start of 1, no steps needed.

There is 1 solution for path of length 1 from 2 to 1.
Example: divide 2 yields 1

There are 2 solutions for path of length 1 from 3 to 1.
Example: divide 3 yields 1

There are 2 solutions for path of length 2 from 4 to 1.
Example: divide 2 yields 2, divide 2 yields 1

There are 2 solutions for path of length 2 from 5 to 1.
Example: subtract 2 yields 3, divide 3 yields 1

There are 3 solutions for path of length 2 from 6 to 1.
Example: divide 2 yields 3, divide 3 yields 1

There are 2 solutions for path of length 3 from 7 to 1.
Example: subtract 2 yields 5, subtract 2 yields 3, divide 3 yields 1

There are 5 solutions for path of length 3 from 8 to 1.
Example: divide 2 yields 4, divide 2 yields 2, divide 2 yields 1

There are 2 solutions for path of length 2 from 9 to 1.
Example: divide 3 yields 3, divide 3 yields 1

There are 2 solutions for path of length 3 from 10 to 1.
Example: divide 2 yields 5, subtract 2 yields 3, divide 3 yields 1

There are 1 with 17 steps for start between 1 and 2000: [1699]
There are 1 with 24 steps for start between 1 and 20000: [19681]
There are 1 with 26 steps for start between 1 and 50000: [45925]

Mathematica/Wolfram Language

<lang Mathematica>$RecursionLimit = 3000; ClearAll[MinimalStepToOne, MinimalStepToOneHelper] MinimalStepToOne[n_Integer] := Module[{res}, 

 res = Reap[MinimalStepToOneHelper[{n}]]-1, 1;
 SortBy[res, Length]
 ]

MinimalStepToOneHelper[steps_List] := Module[{n, out}, 

 n = Last[steps];
 If[n == 1,
  Sow[steps];
  ,
  If[Divisible[n, 3],
   out = steps~Join~{" /3=> ", n/3};
   MinimalStepToOneHelper[out]
   ];
  If[Divisible[n, 2],
   out = steps~Join~{" /2=> ", n/2};
   MinimalStepToOneHelper[out]
   ];
  If[n > 1,
   out = steps~Join~{" -1=> ", n - 1};
   MinimalStepToOneHelper[out]
   ];
  ]
 ]

Do[ 

sel = First[MinimalStepToOne[i]];
Print[First[sel], 
 ": (" <> ToString[(Length[sel] - 1)/2] <> " steps) ", sel // Row]
,
{i, 1, 10}
]

$RecursionLimit = 3000; ClearAll[MinimalStepToOne2, MinimalStepToOneHelper2] MinimalStepToOne2[nn_Integer] := 

Module[{res, done, solution, maxsteps},
 done = False;
 solution = {};
 MinimalStepToOneHelper2[steps_List] := Module[{n, out},
   n = Last[steps];
   If[n == 1,
    solution = steps;
    ,
    If[solution === {},
      If[Divisible[n, 3],
       out = steps~Join~{" /3=> ", n/3};
       MinimalStepToOneHelper2[out]
       ];
      If[Divisible[n, 2],
       out = steps~Join~{" /2=> ", n/2};
       MinimalStepToOneHelper2[out]
       ];
      If[n > 1,
       out = steps~Join~{" -1=> ", n - 1};
       MinimalStepToOneHelper2[out]
       ];
      ];
    ];
   ];
 MinimalStepToOneHelper2[{nn}];
 maxsteps = (Length[solution] - 1)/2;
 maxsteps
 ]

$RecursionLimit = 3000; ClearAll[MinimalStepToOneMaxSteps, MinimalStepToOneMaxStepsHelper] MinimalStepToOneMaxSteps[n_Integer, maxsteps_Integer] := 

Module[{res},
 res = Reap[MinimalStepToOneMaxStepsHelper[{n}, maxsteps]]-1, 1;
 (Min[Length /@ res] - 1)/2
 ]

MinimalStepToOneMaxStepsHelper[steps_List, maxsteps_Integer] := 

Module[{n, out},
 n = Last[steps];
 If[n == 1,
  Sow[steps];
  ,
  If[maxsteps > 0,
    If[Divisible[n, 3],
     out = steps~Join~{" /3=> ", n/3};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    If[Divisible[n, 2],
     out = steps~Join~{" /2=> ", n/2};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    If[n > 1,
     out = steps~Join~{" -1=> ", n - 1};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    ];
  ];
 ]

allsols = Table[ 

  max = MinimalStepToOne2[i];
  {i, MinimalStepToOneMaxSteps[i, max]}
  ,
  {i, 1, 2000}
  ];

a = Last[SortBy[GatherBy[allsols, Last], First /* Last]]; {a1, 2, aAll, 1}

$RecursionLimit = 3000; ClearAll[MinimalStepToOne, MinimalStepToOneHelper] MinimalStepToOne[n_Integer] := Module[{res}, 

 res = Reap[MinimalStepToOneHelper[{n}]]-1, 1;
 SortBy[res, Length]
 ]

MinimalStepToOneHelper[steps_List] := Module[{n, out}, 

 n = Last[steps];
 If[n == 1,
  Sow[steps];
  ,
  If[Divisible[n, 3],
   out = steps~Join~{" /3=> ", n/3};
   MinimalStepToOneHelper[out]
   ];
  If[Divisible[n, 2],
   out = steps~Join~{" /2=> ", n/2};
   MinimalStepToOneHelper[out]
   ];
  If[n > 2,
   out = steps~Join~{" -2=> ", n - 2};
   MinimalStepToOneHelper[out]
   ];
  ]
 ]

Do[ 

sel = First[MinimalStepToOne[i]];
Print[First[sel], 
 ": (" <> ToString[(Length[sel] - 1)/2] <> " steps) ", sel // Row]
,
{i, 1, 10}
]

$RecursionLimit = 3000; ClearAll[MinimalStepToOne2, MinimalStepToOneHelper2] MinimalStepToOne2[nn_Integer] := 

Module[{res, done, solution, maxsteps},
 done = False;
 solution = {};
 MinimalStepToOneHelper2[steps_List] := Module[{n, out},
   n = Last[steps];
   If[n == 1,
    solution = steps;
    ,
    If[solution === {},
      If[Divisible[n, 3],
       out = steps~Join~{" /3=> ", n/3};
       MinimalStepToOneHelper2[out]
       ];
      If[Divisible[n, 2],
       out = steps~Join~{" /2=> ", n/2};
       MinimalStepToOneHelper2[out]
       ];
      If[n > 2,
       out = steps~Join~{" -2=> ", n - 2};
       MinimalStepToOneHelper2[out]
       ];
      ];
    ];
   ];
 MinimalStepToOneHelper2[{nn}];
 maxsteps = (Length[solution] - 1)/2;
 maxsteps
 ]

$RecursionLimit = 3000; ClearAll[MinimalStepToOneMaxSteps, MinimalStepToOneMaxStepsHelper] MinimalStepToOneMaxSteps[n_Integer, maxsteps_Integer] := 

Module[{res},
 res = Reap[MinimalStepToOneMaxStepsHelper[{n}, maxsteps]]-1, 1;
 (Min[Length /@ res] - 1)/2
 ]

MinimalStepToOneMaxStepsHelper[steps_List, maxsteps_Integer] := 

Module[{n, out},
 n = Last[steps];
 If[n == 1,
  Sow[steps];
  ,
  If[maxsteps > 0,
    If[Divisible[n, 3],
     out = steps~Join~{" /3=> ", n/3};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    If[Divisible[n, 2],
     out = steps~Join~{" /2=> ", n/2};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    If[n > 2,
     out = steps~Join~{" -2=> ", n - 2};
     MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
     ];
    ];
  ];
 ]

allsols = Table[ 

  max = MinimalStepToOne2[i];
  {i, MinimalStepToOneMaxSteps[i, max]}
  ,
  {i, 1, 2000}
  ];

a = Last[SortBy[GatherBy[allsols, Last], First /* Last]]; {a1, 2, aAll, 1}</lang>

Output:
1: (0 steps) 1
2: (1 steps) 2 -1=> 1
3: (1 steps) 3 /3=> 1
4: (2 steps) 4 -1=> 3 /3=> 1
5: (3 steps) 5 -1=> 4 -1=> 3 /3=> 1
6: (2 steps) 6 /2=> 3 /3=> 1
7: (3 steps) 7 -1=> 6 /2=> 3 /3=> 1
8: (3 steps) 8 /2=> 4 -1=> 3 /3=> 1
9: (2 steps) 9 /3=> 3 /3=> 1
10: (3 steps) 10 -1=> 9 /3=> 3 /3=> 1
{14, {863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943}}

1: (0 steps) 1
2: (1 steps) 2 /2=> 1
3: (1 steps) 3 -2=> 1
4: (2 steps) 4 -2=> 2 /2=> 1
5: (2 steps) 5 -2=> 3 -2=> 1
6: (2 steps) 6 /2=> 3 -2=> 1
7: (3 steps) 7 -2=> 5 -2=> 3 -2=> 1
8: (3 steps) 8 -2=> 6 /2=> 3 -2=> 1
9: (2 steps) 9 /3=> 3 -2=> 1
10: (3 steps) 10 /2=> 5 -2=> 3 -2=> 1
{17, {1699}}

Nim

We use two recursive functions, the first one to find the minimal length sequences, the second one to find the minimal number of steps. For both, we use memoization. The program takes about 10 ms to execute.

<lang Nim>import strformat, strutils, tables

type 

 Sequence = seq[Natural]

 Context = object
   divisors: seq[int]
   subtractors: seq[int]
   seqCache: Table[int, Sequence]  # Mapping number -> sequence to reach 1.
   stepCache: Table[int, int]      # Mapping number -> number of steps to reach 1.


proc initContext(divisors, subtractors: openArray[int]): Context = 

 ## Initialize a context.
 for d in divisors: doAssert d > 1, "divisors must be greater than 1."
 for s in subtractors: doAssert s > 0, "substractors must be greater than 0."
 result.divisors = @divisors
 result.subtractors = @subtractors
 result.seqCache[1] = @[Natural 1]
 result.stepCache[1] = 0


proc minStepsDown(context: var Context; n: Natural): Sequence = 

 # Return a minimal sequence to reach the value 1.

 assert n > 0, "“n” must be positive."
 if n in context.seqCache: return context.seqCache[n]

 var
   minSteps = int.high
   minPath: Sequence

 for val in context.divisors:
   if n mod val == 0:
     var path = context.minStepsDown(n div val)
     if path.len < minSteps:
       minSteps = path.len
       minPath = move(path)

 for val in context.subtractors:
   if n - val > 0:
     var path = context.minStepsDown(n - val)
     if path.len < minSteps:
       minSteps = path.len
       minPath = move(path)

 result = n & minPath
 context.seqCache[n] = result


proc minStepsDownCount(context: var Context; n: Natural): int = 

 ## Compute the mininum number of steps without keeping the sequence.

 assert n > 0, "“n” must be positive."
 if n in context.stepCache: return context.stepCache[n]

 result = int.high

 for val in context.divisors:
   if n mod val == 0:
     let steps = context.minStepsDownCount(n div val)
     if steps < result: result = steps

 for val in context.subtractors:
   if n - val > 0:
     let steps = context.minStepsDownCount(n - val)
     if steps < result: result = steps

 inc result
 context.stepCache[n] = result


template plural(n: int): string = 

 if n > 1: "s" else: ""

proc printMinStepsDown(context: var Context; n: Natural) = 

 ## Search and print the sequence to reach one.

 let sol = context.minStepsDown(n)
 stdout.write &"{n} takes {sol.len - 1} step{plural(sol.len - 1)}: "
 var prev = 0
 for val in sol:
   if prev == 0:
     stdout.write val
   elif prev - val in context.subtractors:
     stdout.write " - ", prev - val, " → ", val
   else:
     stdout.write " / ", prev div val, " → ", val
   prev = val
 stdout.write '\n'


proc maxMinStepsCount(context: var Context; nmax: Positive): tuple[steps: int; list: seq[int]] = 

 ## Return the maximal number of steps needed for numbers between 1 and "nmax"
 ## and the list of numbers needing this number of steps.

 for n in 2..nmax:
   let nsteps = context.minStepsDownCount(n)
   if nsteps == result.steps:
     result.list.add n
   elif nsteps > result.steps:
     result.steps = nsteps
     result.list = @[n]


proc run(divisors, subtractors: openArray[int]) = 

 ## Run the search for given divisors and subtractors.

 var context = initContext(divisors, subtractors)
 echo &"Using divisors: {divisors} and substractors: {subtractors}"
 for n in 1..10: context.printMinStepsDown(n)
 for nmax in [2_000, 20_000]:
   let (steps, list) = context.maxMinStepsCount(nmax)
   stdout.write if list.len == 1: &"There is 1 number " else: &"There are {list.len} numbers "
   echo &"below {nmax} that require {steps} steps: ", list.join(", ")


run(divisors = [2, 3], subtractors = [1]) echo "" run(divisors = [2, 3], subtractors = [2])</lang>

Output:
Using divisors: [2, 3] and substractors: [1]
1 takes 0 step: 1
2 takes 1 step: 2 - 1 → 1
3 takes 1 step: 3 / 3 → 1
4 takes 2 steps: 4 / 2 → 2 - 1 → 1
5 takes 3 steps: 5 - 1 → 4 / 2 → 2 - 1 → 1
6 takes 2 steps: 6 / 2 → 3 / 3 → 1
7 takes 3 steps: 7 - 1 → 6 / 2 → 3 / 3 → 1
8 takes 3 steps: 8 / 2 → 4 / 2 → 2 - 1 → 1
9 takes 2 steps: 9 / 3 → 3 / 3 → 1
10 takes 3 steps: 10 - 1 → 9 / 3 → 3 / 3 → 1
There are 16 numbers below 2000 that require 14 steps: 863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943
There are 5 numbers below 20000 that require 20 steps: 12959, 15551, 17279, 18143, 19439

Using divisors: [2, 3] and substractors: [2]
1 takes 0 step: 1
2 takes 1 step: 2 / 2 → 1
3 takes 1 step: 3 - 2 → 1
4 takes 2 steps: 4 - 2 → 2 / 2 → 1
5 takes 2 steps: 5 - 2 → 3 - 2 → 1
6 takes 2 steps: 6 / 2 → 3 - 2 → 1
7 takes 3 steps: 7 - 2 → 5 - 2 → 3 - 2 → 1
8 takes 3 steps: 8 / 2 → 4 - 2 → 2 / 2 → 1
9 takes 2 steps: 9 / 3 → 3 - 2 → 1
10 takes 3 steps: 10 / 2 → 5 - 2 → 3 - 2 → 1
There is 1 number below 2000 that require 17 steps: 1699
There is 1 number below 20000 that require 24 steps: 19681

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Minimal_steps_down_to_1 use warnings; no warnings 'recursion'; use List::Util qw( first ); use Data::Dump 'dd';

for ( [ 2000, [2, 3], [1] ], [ 2000, [2, 3], [2] ] ) 

 {
 my ( $n, $div, $sub ) = @$_;
 print "\n", '-' x 40, " divisors @$div subtractors @$sub\n";
 my ($solve, $max) = minimal( @$_ );
 printf "%4d takes %s step(s): %s\n",
   $_, $solve->[$_] =~ tr/ // - 1, $solve->[$_] for 1 .. 10;
 print "\n";
 printf "%d number(s) below %d that take $#$max steps: %s\n",
   $max->[-1] =~ tr/ //, $n, $max->[-1];
 ($solve, $max) = minimal( 20000, $div, $sub );
 printf "%d number(s) below %d that take $#$max steps: %s\n",
   $max->[-1] =~ tr/ //, 20000, $max->[-1];
 }

sub minimal 

 {
 my ($top, $div, $sub) = @_;
 my @solve = (0, ' ');
 my @maximal;
 for my $n ( 2 .. $top )
   {
   my @pick;
   for my $d ( @$div )
     {
     $n % $d and next;
     my $ans = "/$d $solve[$n / $d]";
     $pick[$ans =~ tr/ //] //= $ans;
     }
   for my $s ( @$sub )
     {
     $n > $s or next;
     my $ans = "-$s $solve[$n - $s]";
     $pick[$ans =~ tr/ //] //= $ans;
     }
   $solve[$n] = first { defined  } @pick;
   $maximal[$solve[$n] =~ tr/ // - 1] .= " $n";
   }
 return \@solve, \@maximal;
 }</lang>
Output:
---------------------------------------- divisors 2 3 subtractors 1
   1 takes 0 step(s):  
   2 takes 1 step(s): /2  
   3 takes 1 step(s): /3  
   4 takes 2 step(s): /2 /2  
   5 takes 3 step(s): -1 /2 /2  
   6 takes 2 step(s): /2 /3  
   7 takes 3 step(s): -1 /2 /3  
   8 takes 3 step(s): /2 /2 /2  
   9 takes 2 step(s): /3 /3  
  10 takes 3 step(s): -1 /3 /3  

16 number(s) below 2000 that take 14 steps:  863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943
5 number(s) below 20000 that take 20 steps:  12959 15551 17279 18143 19439

---------------------------------------- divisors 2 3 subtractors 2
   1 takes 0 step(s):  
   2 takes 1 step(s): /2  
   3 takes 1 step(s): /3  
   4 takes 2 step(s): /2 /2  
   5 takes 2 step(s): -2 /3  
   6 takes 2 step(s): /2 /3  
   7 takes 3 step(s): -2 -2 /3  
   8 takes 3 step(s): /2 /2 /2  
   9 takes 2 step(s): /3 /3  
  10 takes 3 step(s): /2 -2 /3  

1 number(s) below 2000 that take 17 steps:  1699
1 number(s) below 20000 that take 24 steps:  19681

Phix

Using simple iterative (vs recursive) memoisation. To make things a bit more interesting it maintains separate caches for any&all {d,s} sets. <lang Phix>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
                       steps = prepend(cache[cdx][m],sprintf("%s%d -> %d",{"/-"[j],dsk,m}))
                   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,"%d 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,       mc}
   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)</lang>

Output:
With divisors {2,3} and subtractors {1}:
1 takes 0 steps
2 takes 1 step, eg /2 -> 1
3 takes 1 step, eg /3 -> 1
4 takes 2 steps, eg /2 -> 2,/2 -> 1
5 takes 3 steps, eg -1 -> 4,/2 -> 2,/2 -> 1
6 takes 2 steps, eg /2 -> 3,/3 -> 1
7 takes 3 steps, eg -1 -> 6,/2 -> 3,/3 -> 1
8 takes 3 steps, eg /2 -> 4,/2 -> 2,/2 -> 1
9 takes 2 steps, eg /3 -> 3,/3 -> 1
10 takes 3 steps, eg -1 -> 9,/3 -> 3,/3 -> 1
There are 16 numbers below 2000 that require 14 steps: {863,1079,1295,1439,1511,1583,1607,1619,1691,1727,1823,1871,1895,1907,1919,1943}
There are 5 numbers below 20000 that require 20 steps: {12959,15551,17279,18143,19439}
There are 3 numbers below 50000 that require 22 steps: {25919,31103,38879}

With divisors {2,3} and subtractors {2}:
1 takes 0 steps
2 takes 1 step, eg /2 -> 1
3 takes 1 step, eg /3 -> 1
4 takes 2 steps, eg /2 -> 2,/2 -> 1
5 takes 2 steps, eg -2 -> 3,/3 -> 1
6 takes 2 steps, eg /2 -> 3,/3 -> 1
7 takes 3 steps, eg -2 -> 5,-2 -> 3,/3 -> 1
8 takes 3 steps, eg /2 -> 4,/2 -> 2,/2 -> 1
9 takes 2 steps, eg /3 -> 3,/3 -> 1
10 takes 3 steps, eg /2 -> 5,-2 -> 3,/3 -> 1
There is 1 number below 2000 that requires 17 steps: {1699}
There is 1 number below 20000 that requires 24 steps: {19681}
There is 1 number below 50000 that requires 26 steps: {45925}

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 tabulated algorithm solves the allied problem of "Find the minimum steps in going from 1 to N, where at each step a member of D can be a multiplier or a member of S can be added".

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

Raku

(formerly 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(+*);

   if $limit == 2000 {
       say "\nDivisors: {@div.perl}, subtract: $sub";
       steps(1..10);
   }
   say "\nUp to {comma $limit} found {+@max} number{+@max == 1 ??  !! 's'} " ~
       "that require{+@max == 1 ?? 's' !! } at least $max steps.";
   steps(@max);

   sub steps (*@list) {
       for @list -> $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
(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

Up to 2,000 found 16 numbers that require at least 14 steps.
(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

Up to 50,000 found 3 numbers that require at least 22 steps.
(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
(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

Up to 2,000 found 1 number that requires at least 17 steps.
(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

Up to 50,000 found 1 number that requires at least 26 steps.
(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

Swift

Translation of: Python

<lang swift>func minToOne(divs: [Int], subs: [Int], upTo n: Int) -> ([Int], String) { 

 var table = Array(repeating: n + 2, count: n + 1)
 var how = Array(repeating: [""], count: n + 2)

 table[1] = 0
 how[1] = ["="]

 for t in 1..<n {
   let thisPlus1 = table[t] + 1

   for div in divs {
     let dt = div * t

     if dt <= n && thisPlus1 < table[dt] {
       table[dt] = thisPlus1
       how[dt] = how[t] + ["/\(div)=>  \(t)"]
     }
   }

   for sub in subs {
     let st = sub + t

     if st <= n && thisPlus1 < table[st] {
       table[st] = thisPlus1
       how[st] = how[t] + ["-\(sub)=> \(t)"]
     }
   }
 }

 return (table, how.map({ $0.reversed().dropLast() }))

}

for (divs, subs) in [([2, 3], [1]), ([2, 3], [2])] { 

 print("\nMINIMUM STEPS TO 1:")
 print("  Possible divisors:  \(divs)")
 print("  Possible decrements: \(subs)")

 let (table, hows) = minToOne(divs: divs, subs: subs, upTo: 10)

 for n in 1...10 {
   print("    mintab(  \(n)) in {  \(table[n])} by: ", hows[n].joined(separator: ", "))
 }

 for upTo in [2_000, 50_000] {
   print("\n    Those numbers up to \(upTo) that take the maximum, \"minimal steps down to 1\":")
   let (table, _) = minToOne(divs: divs, subs: subs, upTo: upTo)
   let max = table.dropFirst().max()!
   let maxNs = table.enumerated().filter({ $0.element == max })

   print(
     "      Taking", max, "steps are the \(maxNs.count) numbers:",
     maxNs.map({ String($0.offset) }).joined(separator: ", ")
   )
 }

}</lang>

Output:
MINIMUM STEPS TO 1:
  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 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 are the 3 numbers: 25919, 31103, 38879

MINIMUM STEPS TO 1:
  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 are the 1 numbers: 1699

    Those numbers up to 50000 that take the maximum, "minimal steps down to 1":
      Taking 26 steps are the 1 numbers: 45925

Wren

Translation of: Go
Library: Wren-fmt

<lang ecmascript>import "/fmt" for Fmt

var limit = 50000 var divs = [] var subs = [] var mins = []

// Assumes the numbers are presented in order up to 'limit'. var minsteps = Fn.new { |n| 

   if (n == 1) {
       mins[1] = []
       return
   }
   var min = limit
   var p = 0
   var q = 0
   var op = ""
   for (div in divs) {
       if (n%div == 0) {
           var d = (n/div).floor
           var steps = mins[d].count + 1
           if (steps < min) {
               min = steps
               p = d
               q = div
               op = "/"
           }
       }
   }
   for (sub in subs) {
       var d = n - sub
       if (d >= 1) {
           var steps = mins[d].count + 1
           if (steps < min) {
               min = steps
               p = d
               q = sub
               op = "-"
           }
       }
   }
   mins[n].add("%(op)%(q) -> %(p)")
   mins[n].addAll(mins[p])

}

for (r in 0..1) { 

   divs = [2, 3]
   subs = (r == 0) ? [1] : [2]
   mins = List.filled(limit+1, null)
   for (i in 0..limit) mins[i] = []
   Fmt.print("With: Divisors: $n, Subtractors: $n =>", divs, subs)
   System.print("  Minimum number of steps to diminish the following numbers down to 1 is:")
   for (i in 1..limit) {
       minsteps.call(i)
       if (i <= 10) {
           var steps = mins[i].count
           var plural = (steps == 1) ? " " : "s"
           var mi = Fmt.v("s", 0, mins[i], 0, ", ", "")
           Fmt.print("    $2d: $d step$s: $s", i, steps, plural, mi)
       }
   }
   for (lim in [2000, 20000, 50000]) {
       var max = 0
       for (min in mins[0..lim]) {
           var m = min.count
           if (m > max) max = m
       }
       var maxs = []
       var i = 0
       for (min in mins[0..lim]) {
           if (min.count == max) maxs.add(i)
           i = i + 1
       }
       var nums = maxs.count
       var verb   = (nums == 1) ? "is" : "are"
       var verb2  = (nums == 1) ? "has" : "have"
       var plural = (nums == 1) ? "": "s"
       Fmt.write("  There $s $d number$s in the range 1-$d ", verb, nums, plural, lim)
       Fmt.print("that $s maximum 'minimal steps' of $d:", verb2, max)
       System.print("   %(maxs)")
   }
   System.print()

}</lang>

Output:
With: Divisors: [2, 3], Subtractors: [1] =>
  Minimum number of steps to diminish the following numbers down to 1 is:
     1: 0 steps:  
     2: 1 step : /2 -> 1
     3: 1 step : /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
  There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
   [863, 1079, 1295, 1439, 1511, 1583, 1607, 1619, 1691, 1727, 1823, 1871, 1895, 1907, 1919, 1943]
  There are 5 numbers in the range 1-20000 that have maximum 'minimal steps' of 20:
   [12959, 15551, 17279, 18143, 19439]
  There are 3 numbers in the range 1-50000 that have maximum 'minimal steps' of 22:
   [25919, 31103, 38879]

With: Divisors: [2, 3], Subtractors: [2] =>
  Minimum number of steps to diminish the following numbers down to 1 is:
     1: 0 steps:  
     2: 1 step : /2 -> 1
     3: 1 step : /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
  There is 1 number  in the range 1-2000 that has maximum 'minimal steps' of 17:
   [1699]
  There is 1 number  in the range 1-20000 that has maximum 'minimal steps' of 24:
   [19681]
  There is 1 number  in the range 1-50000 that has maximum 'minimal steps' of 26:
   [45925]

XPL0

<lang XPL0>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. ]</lang>

Output:
N = 1 takes 0 steps: N 
N = 2 takes 1 steps: N /2=>1 
N = 3 takes 1 steps: N /3=>1 
N = 4 takes 2 steps: N /2=>2 /2=>1 
N = 5 takes 3 steps: N -1=>4 /2=>2 /2=>1 
N = 6 takes 2 steps: N /3=>2 /2=>1 
N = 7 takes 3 steps: N -1=>6 /3=>2 /2=>1 
N = 8 takes 3 steps: N /2=>4 /2=>2 /2=>1 
N = 9 takes 2 steps: N /3=>3 /3=>1 
N = 10 takes 3 steps: N -1=>9 /3=>3 /3=>1 
Maximum steps: 14 for N = 863 1079 1295 1439 1511 1583 1607 1619 1691 1727 1823 1871 1895 1907 1919 1943 
Maximum steps: 20 for N = 12959 15551 17279 18143 19439 
N = 1 takes 0 steps: N 
N = 2 takes 1 steps: N /2=>1 
N = 3 takes 1 steps: N /3=>1 
N = 4 takes 2 steps: N /2=>2 /2=>1 
N = 5 takes 2 steps: N -2=>3 /3=>1 
N = 6 takes 2 steps: N /3=>2 /2=>1 
N = 7 takes 3 steps: N -2=>5 -2=>3 /3=>1 
N = 8 takes 3 steps: N /2=>4 /2=>2 /2=>1 
N = 9 takes 2 steps: N /3=>3 /3=>1 
N = 10 takes 3 steps: N /2=>5 -2=>3 /3=>1 
Maximum steps: 17 for N = 1699 
Maximum steps: 24 for N = 19681

zkl

<lang zkl>var minCache; // (val:(newVal,op,steps)) fcn buildCache(N,D,S){ 

  minCache=Dictionary(1,T(1,"",0));
  foreach n in ([2..N]){
     ops:=List();
     foreach d in (D){ if(n%d==0) ops.append(T(n/d,  String("/",d))) }
     foreach s in (S){ if(n>s)    ops.append(T(n - s,String("-",s))) }
     mcv:=fcn(op){ minCache[op[0]][2] };	// !ACK!, dig out steps
     v,op := ops.reduce(			// find min steps to get to op

'wrap(vo1,vo2){ if(mcv(vo1)<mcv(vo2)) vo1 else vo2 }); 

     minCache[n]=T(v, op, 1 + minCache[v][2])  // this many steps to get to n
  }

} fcn stepsToOne(N){ // D & S are determined by minCache 

  ops,steps := Sink(String).write(N), minCache[N][2];
  do(steps){ v,o,s := minCache[N]; ops.write(" ",o,"-->",N=v); }
  return(steps,ops.close())

}</lang> <lang zkl>MAX, D,S := 50_000, T(2,3), T(1); buildCache(MAX,D,S);

do(2){ 

  println("\nDivisors: %s, subtracters: %s".fmt(D.concat(","), S.concat(",")));
  foreach n in ([1..10]){ println("%2d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }

  maxSteps:=minCache.reduce(fcn(mkv,kv){ if(mkv[1][2]>kv[1][2]) mkv else kv })[1][2];
  biggies :=minCache.filter('wrap(kv){ kv[1][2]==maxSteps }).pump(List,fcn(kv){ kv[0].toInt() }).sort();
  println("\nBelow %,d, found %d numbers that require %d steps (the mostest)."
     .fmt(MAX,biggies.len(),maxSteps));
  foreach n in (biggies){ println("%,6d: %d steps: %s".fmt(n,stepsToOne(n).xplode())) }

  S=T(2); buildCache(MAX,D,S);

}</lang>

Output:
Divisors: 2,3, subtracters: 1
 1: 0 steps: 1
 2: 1 steps: 2 -1-->1
 3: 1 steps: 3 /3-->1
 4: 2 steps: 4 -1-->3 /3-->1
 5: 3 steps: 5 -1-->4 -1-->3 /3-->1
 6: 2 steps: 6 /3-->2 -1-->1
 7: 3 steps: 7 -1-->6 /3-->2 -1-->1
 8: 3 steps: 8 /2-->4 -1-->3 /3-->1
 9: 2 steps: 9 /3-->3 /3-->1
10: 3 steps: 10 -1-->9 /3-->3 /3-->1

Below 50,000, found 3 numbers that require 22 steps (the mostest).
25,919: 22 steps: 25919 -1-->25918 -1-->25917 /3-->8639 -1-->8638 -1-->8637 /3-->2879 -1-->2878 -1-->2877 /3-->959 -1-->958 -1-->957 /3-->319 -1-->318 /3-->106 /2-->53 -1-->52 /2-->26 /2-->13 -1-->12 /3-->4 -1-->3 /3-->1
31,103: 22 steps: 31103 -1-->31102 -1-->31101 /3-->10367 -1-->10366 -1-->10365 /3-->3455 -1-->3454 -1-->3453 /3-->1151 -1-->1150 -1-->1149 /3-->383 -1-->382 -1-->381 /3-->127 -1-->126 /3-->42 /3-->14 /2-->7 -1-->6 /3-->2 -1-->1
38,879: 22 steps: 38879 -1-->38878 /2-->19439 -1-->19438 /2-->9719 -1-->9718 /2-->4859 -1-->4858 /2-->2429 -1-->2428 /2-->1214 /2-->607 -1-->606 /3-->202 -1-->201 /3-->67 -1-->66 /3-->22 -1-->21 /3-->7 -1-->6 /3-->2 -1-->1

Divisors: 2,3, subtracters: 2
 1: 0 steps: 1
 2: 1 steps: 2 /2-->1
 3: 1 steps: 3 -2-->1
 4: 2 steps: 4 -2-->2 /2-->1
 5: 2 steps: 5 -2-->3 -2-->1
 6: 2 steps: 6 /3-->2 /2-->1
 7: 3 steps: 7 -2-->5 -2-->3 -2-->1
 8: 3 steps: 8 -2-->6 /3-->2 /2-->1
 9: 2 steps: 9 /3-->3 -2-->1
10: 3 steps: 10 /2-->5 -2-->3 -2-->1

Below 50,000, found 1 numbers that require 26 steps (the mostest).
45,925: 26 steps: 45925 -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 -2-->1
Retrieved from "https://rosettacode.org/wiki/Minimal_steps_down_to_1?oldid=296784"