Minimal steps down to 1: Difference between revisions
Add Kotlin implementation
(Promote to full task status.) |
(Add Kotlin implementation) |
||
| (23 intermediate revisions by 15 users not shown) | |||
Line 1:
{{task}}
Given:
Line 48 ⟶ 46:
* [https://www.youtube.com/watch?v=f2xi3c1S95M Learn Dynamic Programming (Memoization & Tabulation)] Video of similar task.
=={{header|11l}}==
{{trans|Python: Tabulated}}
<syntaxhighlight 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(‘, ’))</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|C sharp}}==
{{works with|C sharp|7}}
<syntaxhighlight 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);
}</syntaxhighlight>
{{out}}
<pre>
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</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
const int32_t limit = 50'000;
std::vector<int32_t> divisors;
std::vector<int32_t> subtractors;
std::vector<std::vector<std::string>> minimums;
template <typename T>
void print_vector(const std::vector<T>& list) {
for ( uint64_t i = 0; i < list.size(); ++i ) {
std::cout << list[i];
if ( i < list.size() - 1 ) {
std::cout << ", ";
}
}
}
// Assumes that numbers are presented in ascending order up to 'limit'.
void minimum_steps(int32_t n) {
if ( n == 1 ) {
return;
}
int32_t minimum = limit;
int32_t p = 0;
int32_t q = 0;
std::string operator_symbol = "";
for ( int32_t divisor : divisors ) {
if ( n % divisor == 0 ) {
int32_t d = n / divisor;
int32_t steps = minimums[d].size() + 1;
if ( steps < minimum ) {
minimum = steps;
p = d;
q = divisor;
operator_symbol = "/";
}
}
}
for ( int32_t subtractor : subtractors ) {
int32_t d = n - subtractor;
if ( d >= 1 ) {
int32_t steps = minimums[d].size() + 1;
if ( steps < minimum ) {
minimum = steps;
p = d;
q = subtractor;
operator_symbol = "-";
}
}
}
minimums[n].emplace_back(operator_symbol + std::to_string(q) + " -> " + std::to_string(p));
minimums[n].insert(minimums[n].end(), minimums[p].begin(), minimums[p].end());
}
int main() {
for ( int32_t item : { 0, 1 } ) {
divisors = { 2, 3 };
subtractors = { item + 1 };
minimums = std::vector(limit + 1, std::vector<std::string>(0));
std::cout << "With: Divisors: { "; print_vector<int32_t>(divisors);
std::cout << " }, Subtractors: { "; print_vector<int32_t>(subtractors); std::cout << " } =>" << std::endl;
std::cout << " Minimum number of steps to diminish the following numbers down to 1 is:" << std::endl;
for ( int32_t i = 1; i < limit; ++i ) {
minimum_steps(i);
if ( i <= 10 ) {
int32_t steps = minimums[i].size();
const std::string plural = ( steps == 1 ) ? " : " : "s: ";
std::cout << " " << std::setw(2) << i << ": " << steps << " step" + plural;
print_vector<std::string>(minimums[i]); std::cout << std::endl;
}
}
for ( int32_t lim : { 2'000, 20'000, 50'000 } ) {
uint64_t max = 0;
for ( int32_t j = 1; j <= lim; ++j ) {
uint64_t m = minimums[j].size();
if ( m > max ) {
max = m;
}
}
std::vector<int32_t> maxs;
for ( int32_t j = 1; j <= lim; ++j ) {
if ( minimums[j].size() == max ) {
maxs.emplace_back(j);
}
}
int32_t size = maxs.size();
std::string verb1 = ( size == 1 ) ? "is" : "are";
std::string verb2 = ( size == 1 ) ? "has" : "have";
std::string plural = ( size == 1 ) ? "" : "s";
std::cout << " There " << verb1 << " " << size << " number" << plural << " in the range 1 - " << lim
<< " that " << verb2 << " maximum 'minimal steps' of " << max << ":" << std::endl;
std::cout << " [ "; print_vector<int32_t>(maxs); std::cout << " ]" << std::endl;
}
std::cout << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
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 ]
</pre>
=={{header|FreeBASIC}}==
{{trans|XPL0}}
<syntaxhighlight lang="freebasic">Dim Shared As Integer minPasos 'minimal number of steps to get to 1
Dim Shared As Integer Subtractor '1 or 2
Dim Shared As Integer Ns(20000), Ops(20000), MinNs(20000), MinOps(20000)
Sub Reduce(N As Integer, Paso As Integer) 'Reduce N to 1, recording minimum steps
If N = 1 Then
If Paso < minPasos Then
For i As Integer = 0 To Paso-1
MinOps(i) = Ops(i)
MinNs(i) = Ns(i)
Next i
minPasos = Paso
End If
End If
If Paso >= minPasos Then Exit Sub 'don't search further
If N Mod 3 = 0 Then Ops(Paso) = 3 : Ns(Paso) = N/3 : Reduce(N/3, Paso+1)
If N Mod 2 = 0 Then Ops(Paso) = 2 : Ns(Paso) = N/2 : Reduce(N/2, Paso+1)
Ops(Paso) = -Subtractor
Ns(Paso) = N-Subtractor
Reduce(N-Subtractor, Paso+1)
End Sub
Sub ShowSteps(N As Integer) 'Show minimal steps and how N steps to 1
minPasos = 50000
Reduce(N, 0)
Print "N = " & N & " takes " & minPasos & " steps: N";
For i As Integer = 0 To minPasos-1
Print Iif(Sgn(MinOps(i)) < 0, " -", " /");
Print Abs(MinOps(i)) & "=>" & MinNs(i); '" "
Next i
Print
End Sub
Sub ShowCount(Range As Integer) 'Show count of maximum minimal steps and their Ns
Dim As Integer N, MaxSteps
MaxSteps = 0 'find maximum number of minimum steps
For N = 1 To Range
minPasos = 50000
Reduce(N, 0)
If minPasos > MaxSteps Then MaxSteps = minPasos
Next N
Print "Maximum steps:"; MaxSteps; " for N =";
For N = 1 To Range 'show numbers (Ns) for Maximum steps
minPasos = 50000
Reduce(N, 0)
If minPasos = MaxSteps Then Print N; '" ";
Next N
Print
End Sub
Dim As Integer N
Subtractor = 1 '1.
For N = 1 To 10
ShowSteps(N)
Next N
ShowCount(2000) '2.
ShowCount(20000) '2a.
Print
Subtractor = 2 '3.
For N = 1 To 10
ShowSteps(N)
Next N
ShowCount(2000) '4.
ShowCount(20000) '4a.
Sleep</syntaxhighlight>
{{out}}
<pre>Same as XPL0 entry.</pre>
=={{header|Go}}==
<
import (
Line 143 ⟶ 567:
fmt.Println()
}
}</
{{out}}
Line 184 ⟶ 608:
There is 1 number in the range 1-50000 that has maximum 'minimal steps' of 26:
[45925]
</pre>
=={{header|Haskell}}==
<syntaxhighlight 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)</syntaxhighlight>
<pre>λ> 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])</pre>
The task
<syntaxhighlight 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)</syntaxhighlight>
<pre>λ> 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</pre>
=={{header|J}}==
Implementation:
<syntaxhighlight lang="j">step=: {{
~.((#~ 1<:]),y-/m),(#~ (=<.)),y%/n
}}
steps=: {{
m step n^:(1 - 1 e. ])^:a:
}}
show=: {{
paths=.,:,:0 0 1 NB. operator, operand, net value
m=.,m [ n=.,n NB. m: subtractors, n: divisors
for_ok.}.|.m steps n y do. NB. ok: valid net values
last=.{."2 paths
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
prev=. subs,"2 divs NB. we are working backwards from 1
paths=. (,({:"1 prev)e.ok)#,/prev,"1 2/"2 paths
end.
;@((<":y),,)"2((' -/'{~{.);":@{:)"1}:"2}:"1 paths
}}
</syntaxhighlight>
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:
<syntaxhighlight lang="j">taskA=: {{
for_j. 1+i.10 do.
echo rplc&(' 1 steps';' 1 step')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 step.
2-1
2/2
3: 1 step.
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 step.
2/2
3: 1 step.
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
</syntaxhighlight>
=={{header|Java}}==
Algorithm works with any function that supports the <code>Function</code> interface in the code below.
<syntaxhighlight 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";
}
}
}
</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
Line 190 ⟶ 1,159:
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.
<
struct Action{T}
Line 281 ⟶ 1,250:
empty!(memoized)
teststeps(1, failed, actions2, [2000, 20000, 50000])
</
<pre>
With goal 1, divisors [2, 3], subtractors [1]:
Line 352 ⟶ 1,321:
</pre>
=={{header|
{{trans|Java}}
<syntaxhighlight lang="Kotlin">
fun main() {
runTasks(getFunctions1())
runTasks(getFunctions2())
runTasks(getFunctions3())
}
fun runTasks(functions: List<Function>) {
val minPath = getInitialMap(functions, 5)
// Task 1
populateMap(minPath, functions, max)
println("\nWith functions: $functions")
println(" Minimum steps to 1:")
for (n in 2..max) {
val steps = minPath[n]?.size ?: 0
println(" %2d: %d step%s: %s".format(n, steps, if (steps == 1) "" else "s", minPath[n]))
}
// Task 2
displayMaxMin(minPath, functions, 2000)
displayMaxMin(minPath, functions, 20000)
// Task 2a +
displayMaxMin(minPath, functions, 100000)
}
fun displayMaxMin(minPath: MutableMap<Int, List<String>>, functions: List<Function>, max: Int) {
populateMap(minPath, functions, max)
val maxIntegers = getMaxMin(minPath, max)
val maxSteps = maxIntegers.removeAt(0)
val numCount = maxIntegers.size
println(" There ${if (numCount == 1) "is" else "are"} $numCount number${if (numCount == 1) "" else "s"} in the range 1-$max that have maximum 'minimal steps' of $maxSteps:\n $maxIntegers")
}
fun getMaxMin(minPath: Map<Int, List<String>>, max: Int): MutableList<Int> {
var maxSteps = Int.MIN_VALUE
val maxIntegers = mutableListOf<Int>()
for (n in 2..max) {
val len = minPath[n]?.size ?: 0
if (len > maxSteps) {
maxSteps = len
maxIntegers.clear()
maxIntegers.add(n)
} else if (len == maxSteps) {
maxIntegers.add(n)
}
}
maxIntegers.add(0, maxSteps)
return maxIntegers
}
fun populateMap(minPath: MutableMap<Int, List<String>>, functions: List<Function>, max: Int) {
if (n in minPath)
var minFunction:
var minSteps =
for (f in functions) {
if
val result = f.action(n)
val steps = 1 + (minPath[result]?.size ?: 0)
if (steps < minSteps) {
minFunction = f
minSteps = steps
}
}
}
minFunction?.let {
val result = it.action(n)
val path = mutableListOf(it.toString(n))
path.addAll(minPath[result] ?: emptyList())
minPath[n] = path
}
}
}
fun getInitialMap(functions: List<Function>, max: Int): MutableMap<Int, List<String>> {
val minPath = mutableMapOf<Int, List<String>>()
for (i in 2..max) {
for (f in functions) {
if (f.actionOk(i)) {
val result = f.action(i)
if (result == 1) {
minPath[i] = listOf(f.toString(i))
}
}
}
}
return minPath
}
fun getFunctions1(): List<Function> = listOf(
Divide3Function(),
Divide2Function(),
Subtract1Function()
)
fun getFunctions2(): List<Function> = listOf(
Divide3Function(),
Divide2Function(),
Subtract2Function()
)
fun getFunctions3(): List<Function> = listOf(
Divide2Function(),
Divide3Function(),
Subtract2Function(),
Subtract1Function()
)
abstract class Function {
abstract fun action(n: Int): Int
abstract fun actionOk(n: Int): Boolean
abstract fun toString(n: Int): String
}
class Divide2Function : Function() {
override fun action(n: Int) = n / 2
override fun actionOk(n: Int) = n % 2 == 0
override fun toString(n: Int) = "/2 -> ${n / 2}"
override fun toString() = "Divisor 2"
}
class Divide3Function : Function() {
override fun action(n: Int) = n / 3
override fun actionOk(n: Int) = n % 3 == 0
override fun toString(n: Int) = "/3 -> ${n / 3}"
override fun toString() = "Divisor 3"
}
class Subtract1Function : Function() {
override fun action(n: Int) = n - 1
override fun actionOk(n: Int) = true
override fun toString(n: Int) = "-1 -> ${n - 1}"
override fun toString() = "Subtractor 1"
}
class Subtract2Function : Function() {
override fun action(n: Int) = n - 2
override fun actionOk(n: Int) = n > 2
override fun toString(n: Int) = "-2 -> ${n - 2}"
override fun toString() = "Subtractor 2"
}
</syntaxhighlight>
{{out}}
<pre>
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]
6: 2 steps: [/3 -> 2, -1 -> 1]
9: 2 steps: [/3 -> 3, /3 -> 1]
There are 16 numbers in the range 1-2000 that have maximum 'minimal steps' of 14:
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]
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]
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight 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 =
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 >
out =
MinimalStepToOneMaxStepsHelper[out, maxsteps - 1]
];
];
]
allsols = Table[
max = MinimalStepToOne2[i];
{i, MinimalStepToOneMaxSteps[i, max]}
,
{i, 1, 2000}
];
a = Last[SortBy[GatherBy[allsols, Last], First /* Last]];
{a[[1, 2]], a[[All, 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]];
{a[[1, 2]], a[[All, 1]]}</syntaxhighlight>
{{out}}
<pre>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}}</pre>
=={{header|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.
<syntaxhighlight 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])</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Perl}}==
<syntaxhighlight 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;
}</syntaxhighlight>
{{out}}
<pre>
---------------------------------------- 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
</pre>
=={{header|Phix}}==
Using simple iterative (vs recursive) memoisation. To make things a bit more interesting it maintains separate caches for any&all {d,s} sets.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">ckeys</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ms21</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">cdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ckeys</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">cdx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ckeys</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ckeys</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">,{{}})</span>
<span style="color: #000000;">cdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (d then s)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">dsk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dsk</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">dsk</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">dsk</span><span style="color: #0000FF;">:</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">dsk</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">m</span><span style="color: #0000FF;">])+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ms</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%s%d -> %d"</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"/-"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span><span style="color: #000000;">dsk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">step</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">],</span><span style="color: #000000;">steps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cdx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show10</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nWith divisors %v and subtractors %v:\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ms21</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ns</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">steps</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ps</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">eg</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">", eg "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">steps</span><span style="color: #0000FF;">,</span><span style="color: #008000;">","</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d takes %d step%s%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">eg</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ds</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ls</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">steps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">args</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ms21</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">ls</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">steps</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ls</span><span style="color: #0000FF;">></span><span style="color: #000000;">ms</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ls</span>
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">ls</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ms</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lm</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">are</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?{</span><span style="color: #008000;">"is"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">}:{</span><span style="color: #008000;">"are"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">args</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span> <span style="color: #000000;">are</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lm</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ps</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">lim</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ms</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"There %s %d number%s below %d that require%s %d steps: %v\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">args</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">show10</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}})</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">2000</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">20000</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">50000</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">show10</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}})</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">2000</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">20000</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">maxsteps</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">50000</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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,
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}
Line 559 ⟶ 2,116:
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.
<
from functools import lru_cache
Line 614 ⟶ 2,171:
', '.join(str(n) for n in sorted(ans)))
#print(minrec._minrec.cache_info())
print()</
{{out}}
Line 658 ⟶ 2,215:
The table to solve for N contains all the results from 1 up to N. This is used in the solution.
<
"Tabulation, memoised minimised steps to 1"
Line 715 ⟶ 2,272:
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))</
{{out}}
Line 757 ⟶ 2,314:
Those numbers up to 50000 that take the maximum, "minimal steps down to 1":
Taking 26 steps is/are the 1 numbers: 45925</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|Rakudo|2019.11}}
<syntaxhighlight lang="raku" line>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]}<s>} );
%min{$n} = {:op($op[1]), :v($op[0]), :s(1 + %min{$op[0]}<s>)};
});
my $max = %min.max( {.value<s>} ).value<s>;
my @max = %min.grep( {.value.<s> == $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}<s> {
@op.push: "{%min{$n}<op>}=>{%min{$n}<v>}";
$n = %min{$n}<v>;
}
say "($m) {%min{$m}<s>} steps: ", @op.join(', ');
}
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Swift}}==
{{trans|Python}}
<syntaxhighlight 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: ", ")
)
}
}</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">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()
}</syntaxhighlight>
{{out}}
<pre>
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]
</pre>
=={{header|XPL0}}==
<syntaxhighlight 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.
]</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|zkl}}==
<
fcn buildCache(N,D,S){
minCache=Dictionary(1,T(1,"",0));
Line 776 ⟶ 2,758:
do(steps){ v,o,s := minCache[N]; ops.write(" ",o,"-->",N=v); }
return(steps,ops.close())
}</
<
buildCache(MAX,D,S);
Line 791 ⟶ 2,773:
S=T(2); buildCache(MAX,D,S);
}</
{{out}}
<pre style="height:45ex">
| |||