Minimal steps down to 1: Difference between revisions

Content added Content deleted
(→‎Python: Tabulated: Allied problem.)
Line 447: Line 447:
Up to 50,000 found 1 number that requires at least 26 steps.
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>
(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|Phix}}==
Using simple iterative (vs recursive) memoisation. To make things a bit more interesting it maintains separate caches for any&all {d,s} sets.
<lang Phix>sequence cache = {},
ckeys = {}

function ms21(integer n, sequence ds)
integer cdx = find(ds,ckeys)
if cdx=0 then
ckeys = append(ckeys,ds)
cache = append(cache,{{}})
cdx = length(cache)
end if
for i=length(cache[cdx])+1 to n do
integer ms = n+2
sequence steps = {}
for j=1 to length(ds) do -- (d then s)
for k=1 to length(ds[j]) do
integer dsk = ds[j][k],
ok = iff(j=1?remainder(i,dsk)=0:i>dsk)
if ok then
integer m = iff(j=1?i/dsk:i-dsk),
l = length(cache[cdx][m])+1
if ms>l then
ms = l
steps = prepend(cache[cdx][m],sprintf("%s%d -> %d",{"/-"[j],dsk,m}))
end if
end if
end for
end for
if steps = {} then ?9/0 end if
cache[cdx] = append(cache[cdx],steps)
end for
return cache[cdx][n]
end function

procedure show10(sequence ds)
printf(1,"\nWith divisors %v and subtractors %v:\n",ds)
for n=1 to 10 do
sequence steps = ms21(n,ds)
integer ns = length(steps)
string ps = iff(ns=1?"":"s"),
eg = iff(ns=0?"":", eg "&join(steps,","))
printf(1,"%d takes %d step%s%s\n",{n,ns,ps,eg})
end for
end procedure

procedure maxsteps(sequence ds, integer lim)
integer ms = -1, ls
sequence mc = {}, steps, args
for n=1 to lim do
steps = ms21(n,ds)
ls = length(steps)
if ls>ms then
ms = ls
mc = {n}
elsif ls=ms then
mc &= n
end if
end for
integer lm = length(mc)
string {are,ps,ns} = iff(lm=1?{"is","","s"}:{"are","s",""})
args = { are,lm, ps, lim, ns,ms, mc}
printf(1,"There %s %d number%s below %d that require%s %d steps: %v\n",args)
end procedure

show10({{2,3},{1}})
maxsteps({{2,3},{1}},2000)
maxsteps({{2,3},{1}},20000)
maxsteps({{2,3},{1}},50000)

show10({{2,3},{2}})
maxsteps({{2,3},{2}},2000)
maxsteps({{2,3},{2}},20000)
maxsteps({{2,3},{2}},50000)</lang>
{{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}
There is 1 number below 20000 that requires 24 steps: {19681}
There is 1 number below 50000 that requires 26 steps: {45925}
</pre>


=={{header|Python}}==
=={{header|Python}}==
Retrieved from "https://rosettacode.org/wiki/Minimal_steps_down_to_1"