Minimal steps down to 1: Difference between revisions

Content added Content deleted
m (format.)
Line 186: Line 186:
table, hows = self._mintab(n)
table, hows = self._mintab(n)
return table[n], hows[n]
return table[n], hows[n]
</lang>



⚫
{{out}}
<pre>
if __name__ == '__main__':
if __name__ == '__main__':
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]:
for DIVS, SUBS in [({2, 3}, {1}), ({2, 3}, {2})]:
Line 209: Line 207:
ans = [n for n, steps in enumerate(table) if steps == mx]
ans = [n for n, steps in enumerate(table) if steps == mx]
print(' Taking', mx, f'steps is/are the {len(ans)} numbers:',
print(' Taking', mx, f'steps is/are the {len(ans)} numbers:',
', '.join(str(n) for n in ans))</pre>
', '.join(str(n) for n in ans))</lang>

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