Minimal steps down to 1: Difference between revisions

Content added Content deleted
(Added XPL0 example.)
Line 1,224: Line 1,224:
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|XPL0}}==
<lang XPL0>int MinSteps, \minimal number of steps to get to 1
Subtractor; \1 or 2
char Ns(20000), Ops(20000), MinNs(20000), MinOps(20000);

proc Reduce(N, Step); \Reduce N to 1, recording minimum steps
int N, Step, I;
[if N = 1 then
[if Step < MinSteps then
[for I:= 0 to Step-1 do
[MinOps(I):= Ops(I);
MinNs(I):= Ns(I);
];
MinSteps:= Step;
];
];
if Step >= MinSteps then return; \don't search further
if rem(N/3) = 0 then
[Ops(Step):= 3; Ns(Step):= N/3; Reduce(N/3, Step+1)];
if rem(N/2) = 0 then
[Ops(Step):= 2; Ns(Step):= N/2; Reduce(N/2, Step+1)];
Ops(Step):= Subtractor; Ns(Step):= N-Subtractor; Reduce(N-Subtractor, Step+1);
]; \Reduce

proc ShowSteps(N); \Show minimal steps and how N steps to 1
int N, I;
[MinSteps:= $7FFF_FFFF;
Reduce(N, 0);
Text(0, "N = "); IntOut(0, N);
Text(0, " takes "); IntOut(0, MinSteps); Text(0, " steps: N ");
for I:= 0 to MinSteps-1 do
[Text(0, if MinOps(I)=Subtractor then "-" else "/");
IntOut(0, MinOps(I));
Text(0, "=>"); IntOut(0, MinNs(I)); Text(0, " ");
];
CrLf(0);
]; \ShowSteps

proc ShowCount(Range); \Show count of maximum minimal steps and their Ns
int Range;
int N, MaxSteps;
[MaxSteps:= 0; \find maximum number of minimum steps
for N:= 1 to Range do
[MinSteps:= $7FFF_FFFF;
Reduce(N, 0);
if MinSteps > MaxSteps then
MaxSteps:= MinSteps;
];
Text(0, "Maximum steps: "); IntOut(0, MaxSteps); Text(0, " for N = ");
for N:= 1 to Range do \show numbers (Ns) for Maximum steps
[MinSteps:= $7FFF_FFFF;
Reduce(N, 0);
if MinSteps = MaxSteps then
[IntOut(0, N); Text(0, " ");
];
];
CrLf(0);
]; \ShowCount

int N;
[Subtractor:= 1; \1.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000); \2.
ShowCount(20_000); \2a.
Subtractor:= 2; \3.
for N:= 1 to 10 do ShowSteps(N);
ShowCount(2000); \4.
ShowCount(20_000); \4a.
]</lang>

{{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}}==
=={{header|zkl}}==
Retrieved from "https://rosettacode.org/wiki/Minimal_steps_down_to_1"