Rosetta Code

Minimal steps down to 1: Difference between revisions

Page Discussion

Minimal steps down to 1 (view source)

Revision as of 14:49, 30 January 2022

20,098 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, made p2js compatible
m (J: grammar)
m (→‎{{header|Phix}}: added syntax colouring, made p2js compatible)
Line 1,575:
=={{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.
<!--<lang Phix>sequence cache = {},(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
ckeys = {}
<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>
function ms21(integer n, sequence ds)
integer cdx = find(ds,ckeys)
<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>
if cdx=0 then
<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>
ckeys = append(ckeys,ds)
<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>
cache = append(cache,{{}})
<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>
cdx = length(cache)
<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>
end if
<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>
for i=length(cache[cdx])+1 to n do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer ms = n+2
<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>
sequence steps = {}
<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>
for j=1 to length(ds) do -- (d then s)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for k=1 to length(ds[j]) do
<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>
integer dsk = ds[j][k],
<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>
ok = iff(j=1?remainder(i,dsk)=0:i>dsk)
<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>
if ok then
<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>
integer m = iff(j=1?i/dsk:i-dsk),
<span style="color: #008080;">if</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
l = length(cache[cdx][m])+1
<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>
if ms>l then
<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>
ms = l
<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>
steps = prepend(cache[cdx][m],sprintf("%s%d -> %d",{"/-"[j],dsk,m}))
<span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span>
end if
<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 -&gt; %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>
end if
<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>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if steps = {} then ?9/0 end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
cache[cdx] = append(cache[cdx],steps)
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<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>
return cache[cdx][n]
<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>
end function
<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>
procedure show10(sequence ds)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
printf(1,"\nWith divisors %v and subtractors %v:\n",ds)
for n=1 to 10 do
<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>
sequence steps = ms21(n,ds)
<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>
integer ns = length(steps)
<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>
string ps = iff(ns=1?"":"s"),
<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>
eg = iff(ns=0?"":", eg "&join(steps,","))
<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>
printf(1,"%d takes %d step%s%s\n",{n,ns,ps,eg})
<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>
end for
<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>
end procedure
<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>
procedure maxsteps(sequence ds, integer lim)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
integer ms = -1, ls
sequence mc = {}, steps, args
<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>
for n=1 to lim do
<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>
steps = ms21(n,ds)
<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>
ls = length(steps)
<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>
if ls>ms then
<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>
ms = ls
<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>
mc = {n}
<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>
elsif ls=ms then
<span style="color: #000000;">ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ls</span>
mc &= n
<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>
end if
<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>
end for
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">n</span>
integer lm = length(mc)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
string {are,ps,ns} = iff(lm=1?{"is","","s"}:{"are","s",""})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
args = { are,lm, ps, lim, ns,ms, mc}
<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>
printf(1,"There %s %d number%s below %d that require%s %d steps: %v\n",args)
<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>
end procedure
<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>
show10({{2,3},{1}})
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
maxsteps({{2,3},{1}},2000)
maxsteps({{2,3},{1}},20000)
<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>
maxsteps({{2,3},{1}},50000)
<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>
show10({{2,3},{2}})
<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>
maxsteps({{2,3},{2}},2000)
maxsteps({{2,3},{2}},20000)
<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>
maxsteps({{2,3},{2}},50000)</lang>
<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>
<!--</lang>-->
{{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,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}
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/296788"