Anonymous user
Addition chains: Difference between revisions
→{{header|Python}}: +much faster code
(→{{header|Go}}: Added a second much faster version.) |
(→{{header|Python}}: +much faster code) |
||
Line 2,216:
Minimum length of chains: L(n) = 12
Number of minimum length Brauer chains: 6583</pre>
====Faster method====
<lang python>def bauer(n):
chain = [0]*n
in_chain = [False]*(n + 1)
best = None
best_len = n
cnt = 0
def extend_chain(x=1, pos=0):
nonlocal best, best_len, cnt
if x<<(best_len - pos) < n:
return
chain[pos] = x
in_chain[x] = True
pos += 1
if in_chain[n - x]: # found solution
if pos == best_len:
cnt += 1
else:
best = tuple(chain[:pos])
best_len, cnt = pos, 1
elif pos < best_len:
for i in range(pos - 1, -1, -1):
c = x + chain[i]
if c < n:
extend_chain(c, pos)
in_chain[x] = False
extend_chain()
return best + (n,), cnt
for n in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]:
best, cnt = bauer(n)
print(f'L({n}) = {len(best) - 1}, count of minimum chain: {cnt}\ne.g.: {best}\n')</lang>
{{out}}
<pre>
L(7) = 4, count of minimum chain: 5
e.g.: (1, 2, 4, 6, 7)
L(14) = 5, count of minimum chain: 14
e.g.: (1, 2, 4, 8, 12, 14)
--- snip ---
L(382) = 11, count of minimum chain: 4
e.g.: (1, 2, 4, 8, 16, 17, 33, 50, 83, 166, 332, 382)
L(379) = 12, count of minimum chain: 6583
e.g.: (1, 2, 4, 8, 16, 32, 64, 96, 104, 105, 210, 315, 379)
</pre>
=={{header|Racket}}==
| |||