Addition chains: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,622: / Line 1,622: @@
 l(379) = 12, Brauer:6583, eg {1,2,3,4,7,10,17,27,44,88,176,203,379}, Non-Brauer:0, (2:19, 622842429 perms)
 </pre>
+=={{header|Python}}==
+{{trans|Java}}
+<lang python>def prepend(n, seq):
+    return [n] + seq
+def check_seq(pos, seq, n, min_len):
+    if pos > min_len or seq[0] > n:
+        return min_len, 0
+    if seq[0] == n:
+        return pos, 1
+    if pos < min_len:
+        return try_perm(0, pos, seq, n, min_len)
+    return min_len, 0
+def try_perm(i, pos, seq, n, min_len):
+    if i > pos:
+        return min_len, 0
+    res1 = check_seq(pos + 1, prepend(seq[0] + seq[i], seq), n, min_len)
+    res2 = try_perm(i + 1, pos, seq, n, res1[0])
+    if res2[0] < res1[0]:
+        return res2
+    if res2[0] == res1[0]:
+        return res2[0], res1[1] + res2[1]
+    raise Exception("try_perm exception")
+def init_try_perm(x):
+    return try_perm(0, 0, [1], x, 12)
+def find_brauer(num):
+    res = init_try_perm(num)
+    print
+    print "N = ", num
+    print "Minimum length of chains: L(n) = ", res[0]
+    print "Number of minimum length Brauer chains: ", res[1]
+# main
+nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
+for i in nums:
+    find_brauer(i)</lang>
+{{out}}
+<pre>
+N =  7
+Minimum length of chains: L(n) =  4
+Number of minimum length Brauer chains:  5
+N =  14
+Minimum length of chains: L(n) =  5
+Number of minimum length Brauer chains:  14
+N =  21
+Minimum length of chains: L(n) =  6
+Number of minimum length Brauer chains:  26
+N =  29
+Minimum length of chains: L(n) =  7
+Number of minimum length Brauer chains:  114
+N =  32
+Minimum length of chains: L(n) =  5
+Number of minimum length Brauer chains:  1
+N =  42
+Minimum length of chains: L(n) =  7
+Number of minimum length Brauer chains:  78
+N =  64
+Minimum length of chains: L(n) =  6
+Number of minimum length Brauer chains:  1
+N =  47
+Minimum length of chains: L(n) =  8
+Number of minimum length Brauer chains:  183
+N =  79
+Minimum length of chains: L(n) =  9
+Number of minimum length Brauer chains:  492
+N =  191
+Minimum length of chains: L(n) =  11
+Number of minimum length Brauer chains:  7172
+N =  382
+Minimum length of chains: L(n) =  11
+Number of minimum length Brauer chains:  4
+N =  379
+Minimum length of chains: L(n) =  12
+Number of minimum length Brauer chains:  6583</pre>
 =={{header|Scala}}==