Rosetta Code

Addition chains: Difference between revisions

Page Discussion

Addition chains (view source)

Revision as of 08:45, 7 May 2024

57,692 bytes added ,  1 month ago
m
→‎{{header|11l}}: Void
(add Julia example)
 
(20 intermediate revisions by 11 users not shown)
Line 21:
* brauer-chains(19) : count = 31 Ex: ( 1 2 3 4 8 11 19)
* non-brauer-chains(19) : count = 2 Ex: ( 1 2 3 6 7 12 19)
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F bauer(n)
V chain = [0] * n
V in_chain = [0B] * (n + 1)
[Int] best
V best_len = n
V cnt = 0
 
F extend_chain(Int x, Int =pos) -> Void
I @best_len - pos < 32 & x < @n >> (@best_len - pos)
R
 
@chain[pos] = x
@in_chain[x] = 1B
pos++
 
I @in_chain[@n - x]
I pos == @best_len
@cnt++
E
@best = @chain[0 .< pos]
@best_len = pos
@cnt = 1
E I pos < @best_len
L(i) (pos - 1 .< -1).step(-1)
V c = x + @chain[i]
I c < @n
@extend_chain(c, pos)
 
@in_chain[x] = 0B
 
extend_chain(1, 0)
R (best [+] [n], cnt)
 
L(n) [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
V (best, cnt) = bauer(n)
print("L(#.) = #., count of minimum chain: #.\ne.g.: #.\n".format(n, best.len - 1, cnt, best))</syntaxhighlight>
 
{{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]
 
L(21) = 6, count of minimum chain: 26
e.g.: [1, 2, 4, 8, 16, 20, 21]
 
L(29) = 7, count of minimum chain: 114
e.g.: [1, 2, 4, 8, 16, 24, 28, 29]
 
L(32) = 5, count of minimum chain: 1
e.g.: [1, 2, 4, 8, 16, 32]
 
L(42) = 7, count of minimum chain: 78
e.g.: [1, 2, 4, 8, 16, 32, 40, 42]
 
L(64) = 6, count of minimum chain: 1
e.g.: [1, 2, 4, 8, 16, 32, 64]
 
L(47) = 8, count of minimum chain: 183
e.g.: [1, 2, 4, 8, 12, 13, 26, 39, 47]
 
L(79) = 9, count of minimum chain: 492
e.g.: [1, 2, 4, 8, 16, 24, 26, 52, 78, 79]
 
L(191) = 11, count of minimum chain: 7172
e.g.: [1, 2, 4, 8, 16, 32, 48, 52, 53, 106, 159, 191]
 
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|C}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 219 ⟶ 300:
for (i = 0; i < 12; ++i) findBrauer(nums[i], 12, 79);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 303 ⟶ 384:
</pre>
 
=={{header|C++ sharp|C#}}==
{{trans|Java}}
While this worked, something made it run extremely slow.
<syntaxhighlight lang="csharp">using System;
{{trans|D}}
<lang cpp>#include <iostream>
#include <tuple>
#include <vector>
 
namespace AdditionChains {
std::pair<int, int> tryPerm(int, int, const std::vector<int>&, int, int);
class Program {
static int[] Prepend(int n, int[] seq) {
int[] result = new int[seq.Length + 1];
Array.Copy(seq, 0, result, 1, seq.Length);
result[0] = n;
return result;
}
 
std::pair static Tuple<int, int> checkSeqCheckSeq(int pos, const std::vector<int>&[] seq, int n, int minLenmin_len) {
if (pos > minLenmin_len || seq[0] > n) return {new minLenTuple<int, 0int>(min_len, }0);
else if (seq[0] == n) return {new Tuple<int, int>(pos, 1 });
else if (pos < minLen) if (pos < min_len) return tryPermTryPerm(0, pos, seq, n, minLenmin_len);
else return {new minLenTuple<int, int>(min_len, 0 });
}
}
 
std::pair static Tuple<int, int> tryPermTryPerm(int i, int pos, const std::vector<int>&[] seq, int n, int minLenmin_len) {
if (i > pos) return {new minLenTuple<int, 0int>(min_len, }0);
 
std::vector Tuple<int, int> seq2{res1 = CheckSeq(pos + 1, Prepend(seq[0] + seq[i], seq), n, }min_len);
Tuple<int, int> res2 = TryPerm(i + 1, pos, seq, n, res1.Item1);
seq2.insert(seq2.end(), seq.cbegin(), seq.cend());
auto res1 = checkSeq(pos + 1, seq2, n, minLen);
auto res2 = tryPerm(i + 1, pos, seq, n, res1.first);
 
if (res2.firstItem1 < res1.firstItem1) return res2;
else if (res2.firstItem1 == res1.firstItem1) return {new Tuple<int, int>(res2.firstItem1, res1.secondItem2 + res2.second }Item2);
else throw std::runtime_error("tryPerm exception");
}
 
throw new Exception("TryPerm exception");
std::pair<int, int> initTryPerm(int x) {
return tryPerm(0, 0, { 1 }, x, 12);
}
 
static Tuple<int, int> InitTryPerm(int x) {
void findBrauer(int num) {
return TryPerm(0, 0, new int[] { 1 }, x, 12);
auto res = initTryPerm(num);
std::cout << '\n'; }
std::cout << "N = " << num << '\n';
std::cout << "Minimum length of chains: L(n)= " << res.first << '\n';
std::cout << "Number of minimum length Brauer chains: " << res.second << '\n';
}
 
static void FindBrauer(int num) {
int main() {
Tuple<int, int> res = InitTryPerm(num);
std::vector<int> nums{ 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
Console.WriteLine();
for (int i : nums) {
findBrauer Console.WriteLine(i"N = {0}", num);
Console.WriteLine("Minimum length of chains: L(n)= {0}", res.Item1);
}
Console.WriteLine("Number of minimum length Brauer chains: {0}", res.Item2);
}
 
static void Main(string[] args) {
return 0;
int[] nums = new int[] { 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
}</lang>
Array.ForEach(nums, n => FindBrauer(n));
}
}
}</syntaxhighlight>
{{out}}
<pre>N = 7
N = 7
Minimum length of chains: L(n)= 4
Number of minimum length Brauer chains: 5
Line 402 ⟶ 483:
Number of minimum length Brauer chains: 6583</pre>
 
=={{header|C#|C sharp++}}==
While this worked, something made it run extremely slow.
{{trans|Java}}
{{trans|D}}
<lang csharp>using System;
<syntaxhighlight lang="cpp">#include <iostream>
#include <tuple>
#include <vector>
 
std::pair<int, int> tryPerm(int, int, const std::vector<int>&, int, int);
namespace AdditionChains {
class Program {
static int[] Prepend(int n, int[] seq) {
int[] result = new int[seq.Length + 1];
Array.Copy(seq, 0, result, 1, seq.Length);
result[0] = n;
return result;
}
 
static Tuplestd::pair<int, int> CheckSeqcheckSeq(int pos, const std::vector<int[]>& seq, int n, int min_lenminLen) {
if (pos > min_lenminLen || seq[0] > n) return new{ Tuple<intminLen, int>(min_len,0 0)};
else if (seq[0] == n) return new Tuple<int, int>( return { pos, 1) };
else if (pos < minLen) if (pos < min_len) return TryPermtryPerm(0, pos, seq, n, min_lenminLen);
else return new{ Tuple<int, int>(min_lenminLen, 0) };
}
}
 
static Tuplestd::pair<int, int> TryPermtryPerm(int i, int pos, const std::vector<int[]>& seq, int n, int min_lenminLen) {
if (i > pos) return new{ Tuple<intminLen, int>(min_len,0 0)};
 
Tuplestd::vector<int, int> res1seq2{ = CheckSeq(pos + 1, Prepend(seq[0] + seq[i], seq), n, min_len)};
seq2.insert(seq2.end(), seq.cbegin(), seq.cend());
Tuple<int, int> res2 = TryPerm(i + 1, pos, seq, n, res1.Item1);
auto res1 = checkSeq(pos + 1, seq2, n, minLen);
auto res2 = tryPerm(i + 1, pos, seq, n, res1.first);
 
if (res2.Item1first < res1.Item1first) return res2;
else if (res2.Item1first == res1.Item1first) return new{ Tuple<int, int>(res2.Item1first, res1.Item2second + res2.Item2)second };
else throw std::runtime_error("tryPerm exception");
}
 
std::pair<int, int> initTryPerm(int x) {
throw new Exception("TryPerm exception");
return tryPerm(0, 0, { 1 }, x, 12);
}
 
void findBrauer(int num) {
static Tuple<int, int> InitTryPerm(int x) {
auto res = initTryPerm(num);
return TryPerm(0, 0, new int[] { 1 }, x, 12);
std::cout << }'\n';
std::cout << "N = " << num << '\n';
std::cout << "Minimum length of chains: L(n)= " << res.first << '\n';
std::cout << "Number of minimum length Brauer chains: " << res.second << '\n';
}
 
int main() {
static void FindBrauer(int num) {
std::vector<int> nums{ 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
Tuple<int, int> res = InitTryPerm(num);
for (int i : nums) {
Console.WriteLine();
Console.WriteLinefindBrauer("N = {0}", numi);
Console.WriteLine("Minimum length of chains: L(n)= {0}", res.Item1);
Console.WriteLine("Number of minimum length Brauer chains: {0}", res.Item2);
}
 
static void Main(string[] args) {
int[] nums = new int[] { 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
Array.ForEach(nums, n => FindBrauer(n));
}
}
 
}</lang>
return 0;
}</syntaxhighlight>
{{out}}
<pre>N = 7
N = 7
Minimum length of chains: L(n)= 4
Number of minimum length Brauer chains: 5
Line 503 ⟶ 584:
=={{header|D}}==
{{trans|Scala}}
<langsyntaxhighlight Dlang="d">import std.stdio;
import std.typecons;
 
Line 541 ⟶ 622:
find_brauer(i);
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 592 ⟶ 673:
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
;; 2^n
(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))
Line 639 ⟶ 720:
(printf "L(%d) = %d - brauer-chains: %d non-brauer: %d chains: %a %a "
n *minlg* [*counts* 0] [*counts* 1] [*chains* 0] [*chains* 1]))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 660 ⟶ 741:
 
=={{header|Go}}==
===Version 1===
{{trans|Kotlin}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 814 ⟶ 896:
findBrauer(num, 12, 79)
}
}</langsyntaxhighlight>
 
{{out}}
Line 897 ⟶ 979:
Non-Brauer analysis suppressed
</pre>
<br>
===Version 2===
{{trans|Phix}}
Much faster than Version 1 and can now complete the non-Brauer analysis for N > 79 in a reasonable time.
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"time"
)
 
const (
maxLen = 13
maxNonBrauer = 382
)
 
func max(a, b int) int {
if a > b {
return a
}
return b
}
 
func contains(s []int, n int) bool {
for _, i := range s {
if i == n {
return true
}
}
return false
}
 
func isBrauer(a []int) bool {
for i := 2; i < len(a); i++ {
ok := false
for j := i - 1; j >= 0; j-- {
if a[i-1]+a[j] == a[i] {
ok = true
break
}
}
if !ok {
return false
}
}
return true
}
 
var (
brauerCount, nonBrauerCount int
brauerExample, nonBrauerExample string
)
 
func additionChains(target, length int, chosen []int) int {
le := len(chosen)
last := chosen[le-1]
if last == target {
if le < length {
brauerCount = 0
nonBrauerCount = 0
}
if isBrauer(chosen) {
brauerCount++
brauerExample = fmt.Sprint(chosen)
} else {
nonBrauerCount++
nonBrauerExample = fmt.Sprint(chosen)
}
return le
}
if le == length {
return length
}
if target > maxNonBrauer {
for i := le - 1; i >= 0; i-- {
next := last + chosen[i]
if next <= target && next > chosen[len(chosen)-1] && i < length {
length = additionChains(target, length, append(chosen, next))
}
}
} else {
var ndone []int
for {
for i := le - 1; i >= 0; i-- {
next := last + chosen[i]
if next <= target && next > chosen[len(chosen)-1] && i < length &&
!contains(ndone, next) {
ndone = append(ndone, next)
length = additionChains(target, length, append(chosen, next))
}
}
le--
if le == 0 {
break
}
last = chosen[le-1]
}
}
return length
}
 
func main() {
start := time.Now()
nums := []int{7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
fmt.Println("Searching for Brauer chains up to a minimum length of", maxLen-1)
for _, num := range nums {
brauerCount = 0
nonBrauerCount = 0
le := additionChains(num, maxLen, []int{1})
fmt.Println("\nN =", num)
fmt.Printf("Minimum length of chains : L(%d) = %d\n", num, le-1)
fmt.Println("Number of minimum length Brauer chains :", brauerCount)
if brauerCount > 0 {
fmt.Println("Brauer example :", brauerExample)
}
fmt.Println("Number of minimum length non-Brauer chains :", nonBrauerCount)
if nonBrauerCount > 0 {
fmt.Println("Non-Brauer example :", nonBrauerExample)
}
}
fmt.Printf("\nTook %s\n", time.Since(start))
}</syntaxhighlight>
 
{{out}}
Timing is for an Intel Core i7 8565U machine:
<pre>
Searching for Brauer chains up to a minimum length of 12
 
N = 7
Minimum length of chains : L(7) = 4
Number of minimum length Brauer chains : 5
Brauer example : [1 2 3 4 7]
Number of minimum length non-Brauer chains : 0
 
N = 14
Minimum length of chains : L(14) = 5
Number of minimum length Brauer chains : 14
Brauer example : [1 2 3 4 7 14]
Number of minimum length non-Brauer chains : 0
 
N = 21
Minimum length of chains : L(21) = 6
Number of minimum length Brauer chains : 26
Brauer example : [1 2 3 4 7 14 21]
Number of minimum length non-Brauer chains : 3
Non-Brauer example : [1 2 4 5 8 13 21]
 
N = 29
Minimum length of chains : L(29) = 7
Number of minimum length Brauer chains : 114
Brauer example : [1 2 3 4 7 11 18 29]
Number of minimum length non-Brauer chains : 18
Non-Brauer example : [1 2 3 6 9 11 18 29]
 
N = 32
Minimum length of chains : L(32) = 5
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32]
Number of minimum length non-Brauer chains : 0
 
N = 42
Minimum length of chains : L(42) = 7
Number of minimum length Brauer chains : 78
Brauer example : [1 2 3 4 7 14 21 42]
Number of minimum length non-Brauer chains : 6
Non-Brauer example : [1 2 4 5 8 13 21 42]
 
N = 64
Minimum length of chains : L(64) = 6
Number of minimum length Brauer chains : 1
Brauer example : [1 2 4 8 16 32 64]
Number of minimum length non-Brauer chains : 0
 
N = 47
Minimum length of chains : L(47) = 8
Number of minimum length Brauer chains : 183
Brauer example : [1 2 3 4 7 10 20 27 47]
Number of minimum length non-Brauer chains : 37
Non-Brauer example : [1 2 3 5 7 14 19 28 47]
 
N = 79
Minimum length of chains : L(79) = 9
Number of minimum length Brauer chains : 492
Brauer example : [1 2 3 4 7 9 18 36 43 79]
Number of minimum length non-Brauer chains : 129
Non-Brauer example : [1 2 3 5 7 12 24 31 48 79]
 
N = 191
Minimum length of chains : L(191) = 11
Number of minimum length Brauer chains : 7172
Brauer example : [1 2 3 4 7 8 15 22 44 88 103 191]
Number of minimum length non-Brauer chains : 2615
Non-Brauer example : [1 2 3 4 7 9 14 23 46 92 99 191]
 
N = 382
Minimum length of chains : L(382) = 11
Number of minimum length Brauer chains : 4
Brauer example : [1 2 4 5 9 14 23 46 92 184 198 382]
Number of minimum length non-Brauer chains : 0
 
N = 379
Minimum length of chains : L(379) = 12
Number of minimum length Brauer chains : 6583
Brauer example : [1 2 3 4 7 10 17 27 44 88 176 203 379]
Number of minimum length non-Brauer chains : 2493
Non-Brauer example : [1 2 3 4 7 14 17 31 62 124 131 248 379]
 
Took 1m52.920399026s
</pre>
 
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">class AdditionChains {
private static class Pair {
int f, s
 
Pair(int f, int s) {
this.f = f
this.s = s
}
}
 
private static int[] prepend(int n, int[] seq) {
int[] result = new int[seq.length + 1]
result[0] = n
System.arraycopy(seq, 0, result, 1, seq.length)
return result
}
 
private static Pair check_seq(int pos, int[] seq, int n, int min_len) {
if (pos > min_len || seq[0] > n) return new Pair(min_len, 0)
else if (seq[0] == n) return new Pair(pos, 1)
else if (pos < min_len) return try_perm(0, pos, seq, n, min_len)
else return new Pair(min_len, 0)
}
 
private static Pair try_perm(int i, int pos, int[] seq, int n, int min_len) {
if (i > pos) return new Pair(min_len, 0)
 
Pair res1 = check_seq(pos + 1, prepend(seq[0] + seq[i], seq), n, min_len)
Pair res2 = try_perm(i + 1, pos, seq, n, res1.f)
 
if (res2.f < res1.f) return res2
else if (res2.f == res1.f) return new Pair(res2.f, res1.s + res2.s)
else throw new RuntimeException("Try_perm exception")
}
 
private static Pair init_try_perm(int x) {
return try_perm(0, 0, [1] as int[], x, 12)
}
 
private static void find_brauer(int num) {
Pair res = init_try_perm(num)
System.out.println()
System.out.println("N = " + num)
System.out.println("Minimum length of chains: L(n)= " + res.f)
System.out.println("Number of minimum length Brauer chains: " + res.s)
}
 
static void main(String[] args) {
int[] nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
for (int i : nums) {
find_brauer(i)
}
}
}</syntaxhighlight>
{{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|Haskell}}==
 
Implementation using backtracking.
 
<syntaxhighlight lang="haskell">import Data.List (union)
 
-- search strategies
total [] = []
total (x:xs) = brauer (x:xs) `union` total xs
 
brauer [] = []
brauer (x:xs) = map (+ x) (x:xs)
 
-- generation of chains with given strategy
chains _ 1 = [[1]]
chains sums n = go [[1]]
where
go ch = let next = ch >>= step
complete = filter ((== n) . head) next
in if null complete then go next else complete
 
step ch = (: ch) <$> filter (\s -> s > head ch && s <= n) (sums ch)
 
-- the predicate for Brauer chains
isBrauer [_] = True
isBrauer [_,_] = True
isBrauer (x:y:xs) = (x - y) `elem` (y:xs) && isBrauer (y:xs)</syntaxhighlight>
 
Usage examples
 
<pre>λ> chains total 9
[[9,8,4,2,1],[9,5,4,2,1],[9,6,3,2,1]]
 
λ> chains total 13
[[13,12,8,4,2,1],[13,9,8,4,2,1],[13,12,6,4,2,1],[13,7,6,4,2,1],[13,9,5,4,2,1],[13,8,5,4,2,1],
[13,12,6,3,2,1],[13,7,6,3,2,1],[13,10,5,3,2,1],[13,8,5,3,2,1]]
 
λ> chains brauer 13
[[13,12,8,4,2,1],[13,9,8,4,2,1],[13,12,6,4,2,1],[13,7,6,4,2,1],[13,9,5,4,2,1],[13,12,6,3,2,1],
[13,7,6,3,2,1],[13,10,5,3,2,1],[13,8,5,3,2,1]]
 
λ> filter (not . isBrauer) $ chains total 13
[[13,8,5,4,2,1]]</pre>
 
Tasks implementation
 
<syntaxhighlight lang="haskell">task :: Int -> IO()
task n =
let ch = chains total n
br = filter isBrauer ch
nbr = filter (not . isBrauer) ch
in do
printf "L(%d) = %d\n" n (length (head ch) - 1)
printf "Brauer chains(%i)\t: count = %i\tEx: %s\n" n (length br) (show $ reverse $ head br)
if not $ null nbr
then
printf "non-Brauer chains(%i)\t: count = %i\tEx: %s\n\n" n (length ch - length br) (show $ reverse $ head nbr)
else
putStrLn "No non Brauer chains\n"</syntaxhighlight>
 
<pre>λ> mapM_ task [7,14,21,29,32,42,64]
L(7) = 4
Brauer chains(7) : count = 5 Ex: [1,2,4,6,7]
No non Brauer chains
 
L(14) = 5
Brauer chains(14) : count = 14 Ex: [1,2,4,8,12,14]
No non Brauer chains
 
L(21) = 6
Brauer chains(21) : count = 26 Ex: [1,2,4,8,16,20,21]
non-Brauer chains(21) : count = 3 Ex: [1,2,4,8,9,12,21]
 
L(29) = 7
Brauer chains(29) : count = 114 Ex: [1,2,4,8,16,24,28,29]
non-Brauer chains(29) : count = 18 Ex: [1,2,4,8,12,13,16,29]
 
L(32) = 5
Brauer chains(32) : count = 1 Ex: [1,2,4,8,16,32]
No non Brauer chains
 
L(42) = 7
Brauer chains(42) : count = 78 Ex: [1,2,4,8,16,32,40,42]
non-Brauer chains(42) : count = 6 Ex: [1,2,4,8,16,18,24,42]
 
L(64) = 6
Brauer chains(64) : count = 1 Ex: [1,2,4,8,16,32,64]
No non Brauer chains</pre>
 
For the extra task used compiled code, not GHCi.
 
<syntaxhighlight lang="haskell">extraTask :: Int -> IO()
extraTask n =
let ch = chains brauer n
in do
printf "L(%d) = %d\n" n (length (head ch) - 1)
printf "Brauer chains(%i)\t: count = %i\tEx: %s\n" n (length ch) (show $ reverse $ head ch)
putStrLn "Non-Brauer analysis suppressed\n"
 
main = mapM_ extraTask [47, 79, 191, 382, 379]</syntaxhighlight>
 
<pre>L(47) = 8
Brauer chains(47) : count = 183 Ex: [1,2,4,8,12,13,26,39,47]
Non-Brauer analysis suppressed
 
L(79) = 9
Brauer chains(79) : count = 492 Ex: [1,2,4,8,16,24,26,52,78,79]
Non-Brauer analysis suppressed
 
L(191) = 11
Brauer chains(191) : count = 7172 Ex: [1,2,4,8,16,32,48,52,53,106,159,191]
Non-Brauer analysis suppressed
 
L(382) = 11
Brauer chains(382) : count = 4 Ex: [1,2,4,8,16,17,33,50,83,166,332,382]
Non-Brauer analysis suppressed
 
L(379) = 12
Brauer chains(379) : count = 6583 Ex: [1,2,4,8,16,32,64,96,104,105,210,315,379]
Non-Brauer analysis suppressed</pre>
 
Calculation took about 16 seconds (compiled with -O2 flag). If one doesn't need to count all chains, but just get an example it will be found much faster due to Haskell laziness.
 
=== Nearly optimal chains ===
 
In practical work use binary chains or the smart algorithm given in ''F. Bergeron, J. Berstel, and S. Brlek, published in
Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38,'' [http://www.numdam.org/item?id=JTNB_1994__6_1_21_0].
 
<syntaxhighlight lang="haskell">binaryChain 1 = [1]
binaryChain n | even n = n : binaryChain (n `div` 2)
| odd n = n : binaryChain (n - 1)
 
dichotomicChain n
| n == 3 = [3, 2, 1]
| n == 2 ^ log2 n = takeWhile (> 0) $ iterate (`div` 2) n
| otherwise = let k = n `div` (2 ^ ((log2 n + 1) `div` 2))
in chain n k
where
chain n1 n2
| n2 <= 1 = minChain n1
| otherwise = case n1 `divMod` n2 of
(q, 0) -> minChain q `mul` minChain n2
(q, r) -> [r] `add` (minChain q `mul` chain n2 r)
 
c1 `mul` c2 = map (head c2 *) c1 ++ tail c2
c1 `add` c2 = map (head c2 +) c1 ++ c2
log2 = floor . logBase 2 . fromIntegral</syntaxhighlight>
 
<pre>λ> binaryChain 191
[191,190,95,94,47,46,23,22,11,10,5,4,2,1]
 
λ> dichotomicChain 191
[191,187,176,88,44,22,11,8,4,3,2,1]
 
λ> binaryChain 1910
[1910,955,954,477,476,238,119,118,59,58,29,28,14,7,6,3,2,1]
 
λ> dichotomicChain 1910
[1910,1888,944,472,236,118,59,44,22,15,14,7,6,3,2,1]</pre>
 
=={{header|Java}}==
{{trans|D}}
<langsyntaxhighlight Javalang="java">public class AdditionChains {
private static class Pair {
int f, s;
Line 953 ⟶ 1,510:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 1,002 ⟶ 1,559:
Minimum length of chains: L(n)= 12
Number of minimum length Brauer chains: 6583</pre>
 
 
=={{header|Julia}}==
{{trans|Python}}
<langsyntaxhighlight lang="julia">checksequence(pos, seq, n, minlen) =
pos > minlen || seq[1] > n ? (minlen, 0) :
seq[1] == n ? (pos, 1) :
Line 1,031 ⟶ 1,587:
println("Number of minimum length Brauer chains: $nchains")
end
</langsyntaxhighlight>{{out}}
<pre>
N = 7
Line 1,070 ⟶ 1,626:
Number of minimum length Brauer chains: 6583
</pre>
 
 
=={{header|Kotlin}}==
Line 1,076 ⟶ 1,631:
 
I've then extended the code to count the number of non-Brauer chains of the same minimum length - basically 'brute' force to generate all addition chains and then subtracted the number of Brauer ones - plus examples for both. For N <= 64 this adds little to the execution time but adds about 1 minute for N = 79 and I gave up waiting for N = 191! To deal with these glacial execution times, I've added code which enables you to suppress the non-Brauer generation for N above a specified figure.
<langsyntaxhighlight lang="scala">// version 1.1.51
 
var example: List<Int>? = null
Line 1,166 ⟶ 1,721:
println("Searching for Brauer chains up to a minimum length of 12:")
for (num in nums) findBrauer(num, 12, 79)
}</langsyntaxhighlight>
 
{{out}}
Line 1,249 ⟶ 1,804:
Non-Brauer analysis suppressed
</pre>
 
=={{header|Lua}}==
{{trans|D}}
<syntaxhighlight lang="lua">function index(a,i)
return a[i + 1]
end
 
function checkSeq(pos, seq, n, minLen)
if pos > minLen or index(seq,0) > n then
return minLen, 0
elseif index(seq,0) == n then
return pos, 1
elseif pos < minLen then
return tryPerm(0, pos, seq, n, minLen)
else
return minLen, 0
end
end
 
function tryPerm(i, pos, seq, n, minLen)
if i > pos then
return minLen, 0
end
 
local seq2 = {}
table.insert(seq2, index(seq,0) + index(seq,i))
for j=1,table.getn(seq) do
table.insert(seq2, seq[j])
end
local res1a, res1b = checkSeq(pos + 1, seq2, n, minLen)
local res2a, res2b = tryPerm(i + 1, pos, seq, n, res1a)
 
if res2a < res1a then
return res2a, res2b
elseif res2a == res1a then
return res2a, res1b + res2b
else
error("tryPerm exception")
end
end
 
function initTryPerm(x)
local seq = {}
table.insert(seq, 1)
return tryPerm(0, 0, seq, x, 12)
end
 
function findBrauer(num)
local resa, resb = initTryPerm(num)
print()
print("N = " .. num)
print("Minimum length of chains: L(n) = " .. resa)
print("Number of minimum length Brauer chains: " .. resb)
end
 
function main()
findBrauer(7)
findBrauer(14)
findBrauer(21)
findBrauer(29)
findBrauer(32)
findBrauer(42)
findBrauer(64)
findBrauer(47)
findBrauer(79)
findBrauer(191)
findBrauer(382)
findBrauer(379)
end
 
main()</syntaxhighlight>
{{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|Nim}}==
{{trans|Go}}
This is a translation of the second Go version.
<syntaxhighlight lang="nim">import times, strutils
 
const
MaxLen = 13
MaxNonBrauer = 382
 
func isBrauer(a: seq[int]): bool =
for i in 2..a.high:
block loop:
for j in countdown(i - 1, 0):
if a[i-1] + a[j] == a[i]:
break loop
return false
result = true
 
var
brauerCount, nonBrauerCount: int
brauerExample, nonBrauerExample: seq[int]
 
 
proc additionChains(target, length: int; chosen: seq[int]): int =
var length = length
var le = chosen.len
var last = chosen[^1]
 
if last == target:
if le < length:
brauerCount = 0
nonBrauerCount = 0
if chosen.isBrauer:
inc brauerCount
brauerExample = chosen
else:
inc nonBrauerCount
nonBrauerExample = chosen
return le
 
if le == length: return length
 
if target > MaxNonBrauer:
var nextChosen = chosen & 0
for i in countdown(le - 1, 0):
let next = last + chosen[i]
if next <= target and next > chosen[^1] and i < length:
nextChosen[^1] = next
length = additionChains(target, length, nextChosen)
else:
var ndone = newSeqOfCap[int](le)
var nextChosen = chosen & 0
while true:
for i in countdown(le - 1, 0):
let next = last + chosen[i]
if next <= target and next > chosen[^1] and i < length and next notin ndone:
ndone.add next
nextChosen[^1] = next
length = additionChains(target, length, nextChosen)
dec le
if le == 0: break
last = chosen[le-1]
result = length
 
 
const Nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
 
let start = now()
echo "Searching for Brauer chains up to a minimum length of ", MaxLen - 1
for num in Nums:
brauerCount = 0
nonBrauerCount = 0
let le = additionChains(num, MaxLen, @[1])
echo "\nN = ", num
echo "Minimum length of chains : L($1) = $2".format(num, le - 1)
echo "Number of minimum length Brauer chains: ", brauerCount
if brauerCount > 0:
echo "Brauer example: ", brauerExample.join(", ")
echo "Number of minimum length non-Brauer chains: ", nonBrauerCount
if nonBrauerCount > 0:
echo "Non-Brauer example: ", nonBrauerExample.join(", ")
echo "\nTook ", now() - start</syntaxhighlight>
 
{{out}}
<pre>Searching for Brauer chains up to a minimum length of 12
 
N = 7
Minimum length of chains : L(7) = 4
Number of minimum length Brauer chains: 5
Brauer example: 1, 2, 3, 4, 7
Number of minimum length non-Brauer chains: 0
 
N = 14
Minimum length of chains : L(14) = 5
Number of minimum length Brauer chains: 14
Brauer example: 1, 2, 3, 4, 7, 14
Number of minimum length non-Brauer chains: 0
 
N = 21
Minimum length of chains : L(21) = 6
Number of minimum length Brauer chains: 26
Brauer example: 1, 2, 3, 4, 7, 14, 21
Number of minimum length non-Brauer chains: 3
Non-Brauer example: 1, 2, 4, 5, 8, 13, 21
 
N = 29
Minimum length of chains : L(29) = 7
Number of minimum length Brauer chains: 114
Brauer example: 1, 2, 3, 4, 7, 11, 18, 29
Number of minimum length non-Brauer chains: 18
Non-Brauer example: 1, 2, 3, 6, 9, 11, 18, 29
 
N = 32
Minimum length of chains : L(32) = 5
Number of minimum length Brauer chains: 1
Brauer example: 1, 2, 4, 8, 16, 32
Number of minimum length non-Brauer chains: 0
 
N = 42
Minimum length of chains : L(42) = 7
Number of minimum length Brauer chains: 78
Brauer example: 1, 2, 3, 4, 7, 14, 21, 42
Number of minimum length non-Brauer chains: 6
Non-Brauer example: 1, 2, 4, 5, 8, 13, 21, 42
 
N = 64
Minimum length of chains : L(64) = 6
Number of minimum length Brauer chains: 1
Brauer example: 1, 2, 4, 8, 16, 32, 64
Number of minimum length non-Brauer chains: 0
 
N = 47
Minimum length of chains : L(47) = 8
Number of minimum length Brauer chains: 183
Brauer example: 1, 2, 3, 4, 7, 10, 20, 27, 47
Number of minimum length non-Brauer chains: 37
Non-Brauer example: 1, 2, 3, 5, 7, 14, 19, 28, 47
 
N = 79
Minimum length of chains : L(79) = 9
Number of minimum length Brauer chains: 492
Brauer example: 1, 2, 3, 4, 7, 9, 18, 36, 43, 79
Number of minimum length non-Brauer chains: 129
Non-Brauer example: 1, 2, 3, 5, 7, 12, 24, 31, 48, 79
 
N = 191
Minimum length of chains : L(191) = 11
Number of minimum length Brauer chains: 7172
Brauer example: 1, 2, 3, 4, 7, 8, 15, 22, 44, 88, 103, 191
Number of minimum length non-Brauer chains: 2615
Non-Brauer example: 1, 2, 3, 4, 7, 9, 14, 23, 46, 92, 99, 191
 
N = 382
Minimum length of chains : L(382) = 11
Number of minimum length Brauer chains: 4
Brauer example: 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382
Number of minimum length non-Brauer chains: 0
 
N = 379
Minimum length of chains : L(379) = 12
Number of minimum length Brauer chains: 6583
Brauer example: 1, 2, 3, 4, 7, 10, 17, 27, 44, 88, 176, 203, 379
Number of minimum length non-Brauer chains: 2493
Non-Brauer example: 1, 2, 3, 4, 7, 14, 17, 31, 62, 124, 131, 248, 379
 
Took 1 minute, 33 seconds, 138 milliseconds, 185 microseconds, and 660 nanoseconds</pre>
 
=={{header|Perl}}==
{{trans|Perl 6Raku}}
<langsyntaxhighlight lang="perl">use strict;
use feature 'say';
 
Line 1,360 ⟶ 2,201:
# 47, 79, 191, 382, 379, 379, 12509);
say "Searching for Brauer chains up to a minimum length of 12:";
for (@nums) { findBrauer $_, 12, 79 }</langsyntaxhighlight>
{{out}}
<pre style="height:35ex">N = 7
Line 1,407 ⟶ 2,248:
Number of minimum length non-Brauer chains : 0</pre>
 
=={{header|Perl 6Phix}}==
Modification of [[Addition-chain_exponentiation#Phix]], which probably will be faster if you already know l(n) and only want one (Brauer).<br>
Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.
 
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">nums</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">21</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">29</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">42</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">64</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">47</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">79</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">191</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">382</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">379</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">maxlen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">13</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">max_non_brauer</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">79</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">isBrauer</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- translated from Go</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">3</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">brauer_count</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">non_brauer_count</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">brauer_example</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">non_brauer_example</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">tries</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #7060A8;">ppOpt</span><span style="color: #0000FF;">({</span><span style="color: #004600;">pp_IntCh</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">target</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">-- nb: target and len must be &gt;=2</span>
<span style="color: #000000;">tries</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">=</span><span style="color: #000000;">target</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;"><</span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">brauer_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">non_brauer_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">isBrauer</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">brauer_count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">brauer_example</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">non_brauer_count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">non_brauer_example</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">l</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"working... %s, %,d permutations"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]),</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">}))</span>
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">target</span><span style="color: #0000FF;">></span><span style="color: #000000;">max_non_brauer</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">+</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">target</span> <span style="color: #008080;">and</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">></span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">len</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #000000;">target</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">&</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ndone</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- if chosen was {1,2,4,5}, don't recurse {1,2,4,5,6} twice,
-- once because 5+1=6, and again because 4+2=6, or similar.</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">last</span><span style="color: #0000FF;">+</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">target</span> <span style="color: #008080;">and</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">></span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">[$]</span> <span style="color: #008080;">and</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">len</span> <span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ndone</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ndone</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ndone</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">len</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #000000;">target</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">last</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">len</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Searching for Brauer chains up to a minimum length of %d:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxlen</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nums</span><span style="color: #0000FF;">)-</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">3</span><span style="color: #0000FF;">:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">brauer_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">brauer_example</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #000000;">non_brauer_count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">addition_chains</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxlen</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">bc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">brauer_count</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">nbc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">non_brauer_count</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">bs</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bc</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" eg "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brauer_example</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">","</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">ns</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nbc</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" eg "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">ppf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">non_brauer_example</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">","</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed_short</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (wipe it clean)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"l(%d) = %d, Brauer:%d,%s Non-Brauer:%d,%s (%s, %d perms)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nbc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
 
{{out}}
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:2615, eg {1,2,3,4,7,9,14,23,46,92,99,191}, (1:41, 174071925 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (2:53, 467243477 perms)
l(379) = 12, Brauer:6583, eg {1,2,3,4,7,10,17,27,44,88,176,203,379}, Non-Brauer:2493, eg {1,2,3,4,7,14,17,31,62,124,131,248,379}, (29:45, 3349176887 perms)
</pre>
For comparison with the Kotlin timings, setting the constant max_non_brauer to 79 yields the following
(making it about 20% slower than the Go submission above, on the same box)
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:0, (11s, 43748038 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (17s, 103474842 perms)
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}}
<syntaxhighlight 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)</syntaxhighlight>
{{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>
 
====Faster method====
<syntaxhighlight 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')</syntaxhighlight>
{{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}}==
 
This implementation uses the [https://docs.racket-lang.org/rosette-guide/index.html Rosette] language in Racket. It is inefficient as it asks an SMT solver to enumerate every possible solutions. However, it is very straightforward to write, and in fact is quite efficient for computing <code>l(n)</code> and finding one example (solve n = 379 in ~3 seconds).
 
<syntaxhighlight lang="racket">#lang rosette
 
(define (basic-constraints xs n)
(assert (= 1 (first xs)))
(assert (= n (last xs)))
(assert (apply < xs))
(for ([x (in-list (rest xs))] [xi (in-naturals 1)])
(assert
(apply || (for*/list ([(y yi) (in-parallel (in-list xs) (in-range xi))]
[(z zi) (in-parallel (in-list xs) (in-range xi))])
(= x (+ y z)))))))
 
(define (next-sol xs the-mod)
(not (apply && (for/list ([x (in-list xs)]) (= x (evaluate x the-mod))))))
 
(define (try-len r n enumerate?)
(define xs (build-list (add1 r)
(thunk* (define-symbolic* x integer?)
x)))
(basic-constraints xs n)
(define sols (let loop ([sols '()])
(define the-mod (solve #t))
(cond
[(unsat? the-mod) sols]
[enumerate? (assert (next-sol xs the-mod))
(loop (cons (evaluate xs the-mod) sols))]
[else (list (evaluate xs the-mod))])))
(clear-state!)
(if (empty? sols) #f (cons sols r)))
 
(define (brauer? xs)
(for/and ([x (in-list (rest xs))] [xi (in-naturals 1)] [x* (in-list xs)])
(for/or ([y (in-list xs)] [yi (in-range xi)]) (= x (+ x* y)))))
 
(define (report-chain chain name)
(printf "#~a chains: ~a\n" name (length chain))
(when (not (empty? chain)) (printf "example: ~a\n" (first chain))))
 
(define (compute n enumerate?)
(define sols (for/or ([r (in-naturals 1)]) (try-len r n enumerate?)))
(printf "minimal chain length l(~a) = ~a\n" n (cdr sols))
(cond
[enumerate?
(define-values (brauer-chain non-brauer-chain) (partition brauer? (car sols)))
(report-chain brauer-chain "brauer")
(report-chain non-brauer-chain "non-brauer")]
[else (printf "example: ~a\n" (first (car sols)))]))
 
(define (compute/time n #:enumerate? enumerate?)
(match-define-values (_ _ real _) (time-apply compute (list n enumerate?)))
(printf "total time (ms): ~a\n\n" real))
 
(for ([x (in-list '(19 7 14 21 29 32 42 64 47 79))])
(compute/time x #:enumerate? #t))
 
(for ([x (in-list '(191 382 379 12509))])
(compute/time x #:enumerate? #f))</syntaxhighlight>
 
{{out}}
<pre>
minimal chain length l(19) = 6
#brauer chains: 31
example: (1 2 3 4 8 16 19)
#non-brauer chains: 2
example: (1 2 3 6 7 12 19)
total time (ms): 245
 
minimal chain length l(7) = 4
#brauer chains: 5
example: (1 2 3 6 7)
#non-brauer chains: 0
total time (ms): 47
 
minimal chain length l(14) = 5
#brauer chains: 14
example: (1 2 3 5 7 14)
#non-brauer chains: 0
total time (ms): 95
 
minimal chain length l(21) = 6
#brauer chains: 26
example: (1 2 3 4 7 14 21)
#non-brauer chains: 3
example: (1 2 4 5 8 13 21)
total time (ms): 204
 
minimal chain length l(29) = 7
#brauer chains: 114
example: (1 2 3 6 7 13 16 29)
#non-brauer chains: 18
example: (1 2 3 6 9 11 18 29)
total time (ms): 1443
 
minimal chain length l(32) = 5
#brauer chains: 1
example: (1 2 4 8 16 32)
#non-brauer chains: 0
total time (ms): 42
 
minimal chain length l(42) = 7
#brauer chains: 78
example: (1 2 3 6 9 15 21 42)
#non-brauer chains: 6
example: (1 2 4 5 8 13 21 42)
total time (ms): 808
 
minimal chain length l(64) = 6
#brauer chains: 1
example: (1 2 4 8 16 32 64)
#non-brauer chains: 0
total time (ms): 52
 
minimal chain length l(47) = 8
#brauer chains: 183
example: (1 2 3 5 8 11 22 44 47)
#non-brauer chains: 37
example: (1 2 3 5 7 14 19 28 47)
total time (ms): 6011
 
minimal chain length l(79) = 9
#brauer chains: 492
example: (1 2 4 8 12 13 25 29 54 79)
#non-brauer chains: 129
example: (1 2 4 8 9 12 21 29 58 79)
total time (ms): 38038
 
minimal chain length l(191) = 11
example: (1 2 4 8 16 24 28 29 53 69 138 191)
total time (ms): 1601
 
minimal chain length l(382) = 11
example: (1 2 4 5 9 14 23 46 92 184 368 382)
total time (ms): 2313
 
minimal chain length l(379) = 12
example: (1 2 4 8 12 24 48 72 73 121 129 258 379)
total time (ms): 3176
 
minimal chain length l(12509) = 17
example: (1 2 3 6 12 13 24 48 96 192 384 768 781 1562 3124 6248 12496 12509)
total time (ms): 237617
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Kotlin}}
<syntaxhighlight lang="raku" perl6line>my @Example = ();
 
sub check-Sequence($pos, @seq, $n, $minLen --> List) {
Line 1,505 ⟶ 2,781:
 
say "Searching for Brauer chains up to a minimum length of 12:";
find-Brauer $_, 12, 79 for 7, 14, 21, 29, 32, 42, 64 #, 47, 79, 191, 382, 379, 379, 12509 # un-comment for extra-credit</langsyntaxhighlight>
{{out}}
<pre>Searching for Brauer chains up to a minimum length of 12:
Line 1,554 ⟶ 2,830:
Number of minimum length non-Brauer chains : 0</pre>
 
=={{header|PhixRuby}}==
{{trans|D}}
Modification of [[Addition-chain_exponentiation#Phix]], which probably will be faster if you already know l(n) and only want one (Brauer).<br>
<syntaxhighlight lang="ruby">def check_seq(pos, seq, n, min_len)
Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.
if pos > min_len or seq[0] > n then
<lang Phix>constant nums = {7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
constant maxlen = 13
constant max_non_brauer = 379
 
function isBrauer(sequence a)
-- translated from Go
for i=3 to length(a) do
bool ok = false
for j=i-1 to 1 by -1 do
if a[i-1]+a[j] == a[i] then
ok = true
exit
end if
end for
if not ok then
return false
end if
end for
return true
end function
 
integer last_lm = 0
procedure progress(string m)
puts(1,m&repeat(' ',max(0,last_lm-length(m)))&"\r")
last_lm = length(m)
end procedure
 
integer brauer_count,
non_brauer_count
sequence brauer_example,
non_brauer_example
 
atom t1 = time()+1
atom tries = 0
 
function addition_chains(integer target, len, sequence chosen={1})
-- nb: target and len must be >=2
tries += 1
integer l = length(chosen),
last = chosen[l]
if last=target then
if l<len then
brauer_count = 0
non_brauer_count = 0
end if
if isBrauer(chosen) then
brauer_count += 1
brauer_example = chosen
else
non_brauer_count += 1
non_brauer_example = chosen
end if
return l
end if
if l=len then
if time()>t1 then
progress(sprintf("working... %s, %,d permutations",{sprint(chosen[1..l]),tries}))
t1 = time()+1
end if
elsif target>max_non_brauer then
for i=l to 1 by -1 do
integer next = last+chosen[i]
if next<=target and next>chosen[$] and i<=len then
len = addition_chains(target,len,chosen&next)
end if
end for
else
sequence ndone = {} -- if chosen was {1,2,4,5}, don't recurse {1,2,4,5,6} twice,
-- once because 5+1=6, and again because 4+2=6, or similar.
while true do
for i=l to 1 by -1 do
integer next = last+chosen[i]
if next<=target and next>chosen[$] and i<=len and not find(next,ndone) then
ndone = append(ndone,next)
len = addition_chains(target,len,chosen&next)
end if
end for
l -= 1
if l=0 then exit end if
last = chosen[l]
end while
end if
return len
end function
 
printf(1,"Searching for Brauer chains up to a minimum length of %d:\n",{maxlen-1})
for i=1 to length(nums) do
atom t = time()
brauer_count = 0
brauer_example = {}
non_brauer_count = 0
integer num = nums[i],
l = addition_chains(num,maxlen)
integer bc = brauer_count,
nbc = non_brauer_count
string bs = iff(bc?" eg "&sprint(brauer_example)&",":""),
ns = iff(nbc?" eg "&sprint(non_brauer_example)&",":""),
e = elapsed_short(time()-t)
progress("") -- (wipe it clean)
printf(1,"l(%d) = %d, Brauer:%d,%s Non-Brauer:%d,%s (%s, %d perms)\n",{num,l-1,bc,bs,nbc,ns,e,tries})
end for</lang>
{{out}}
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:2615, eg {1,2,3,4,7,9,14,23,46,92,99,191}, (1:41, 174071925 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (2:53, 467243477 perms)
l(379) = 12, Brauer:6583, eg {1,2,3,4,7,10,17,27,44,88,176,203,379}, Non-Brauer:2493, eg {1,2,3,4,7,14,17,31,62,124,131,248,379}, (29:45, 3349176887 perms)
</pre>
For comparison with the Kotlin timings, setting the constant max_non_brauer to 79 yields the following
(making it about 20% slower than the Go submission above, on the same box)
<pre>
Searching for Brauer chains up to a minimum length of 12:
l(7) = 4, Brauer:5, eg {1,2,3,4,7}, Non-Brauer:0, (0s, 18 perms)
l(14) = 5, Brauer:14, eg {1,2,3,4,7,14}, Non-Brauer:0, (0s, 153 perms)
l(21) = 6, Brauer:26, eg {1,2,3,4,7,14,21}, Non-Brauer:3, eg {1,2,4,5,8,13,21}, (0s, 1014 perms)
l(29) = 7, Brauer:114, eg {1,2,3,4,7,11,18,29}, Non-Brauer:18, eg {1,2,3,6,9,11,18,29}, (0s, 7610 perms)
l(32) = 5, Brauer:1, eg {1,2,4,8,16,32}, Non-Brauer:0, (0s, 7780 perms)
l(42) = 7, Brauer:78, eg {1,2,3,4,7,14,21,42}, Non-Brauer:6, eg {1,2,4,5,8,13,21,42}, (0s, 15935 perms)
l(64) = 6, Brauer:1, eg {1,2,4,8,16,32,64}, Non-Brauer:0, (0s, 17018 perms)
l(47) = 8, Brauer:183, eg {1,2,3,4,7,10,20,27,47}, Non-Brauer:37, eg {1,2,3,5,7,14,19,28,47}, (0s, 105418 perms)
l(79) = 9, Brauer:492, eg {1,2,3,4,7,9,18,36,43,79}, Non-Brauer:129, eg {1,2,3,5,7,12,24,31,48,79}, (0s, 998358 perms)
l(191) = 11, Brauer:7172, eg {1,2,3,4,7,8,15,22,44,88,103,191}, Non-Brauer:0, (11s, 43748038 perms)
l(382) = 11, Brauer:4, eg {1,2,4,5,9,14,23,46,92,184,198,382}, Non-Brauer:0, (17s, 103474842 perms)
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
ifelsif seq[0] == n: then
return pos, 1
ifelsif pos < min_len: then
return try_perm(0, pos, seq, n, min_len)
else
return min_len, 0
return min_len, 0
end
end
 
def try_perm(i, pos, seq, n, min_len):
if i > pos: then
return min_len, 0
end
 
res1res11, res12 = check_seq(pos + 1, prepend([seq[0] + seq[i],] + seq), n, min_len)
res2res21, res22 = try_perm(i + 1, pos, seq, n, res1[0]res11)
 
if res2[0]res21 < res1[0]:res11 then
return res2res21, res22
ifelsif res2[0]res21 == res1[0]:res11 then
return res2[0]res21, res1[1]res12 + res2[1]res22
else
raise Exception("try_perm exception")
raise "try_perm exception"
end
end
 
def init_try_perm(x):
return try_perm(0, 0, [1], x, 12)
end
 
def find_brauer(num):
resactualMin, brauer = init_try_perm(num)
printputs
print "N = ", num, "\n"
print "Minimum length of chains: L(n) = ", res[0]actualMin, "\n"
print "Number of minimum length Brauer chains: ", res[1]brauer, "\n"
end
 
#def main
nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
for i in nums: do
find_brauer(i)</lang>
end
end
 
main()</syntaxhighlight>
{{out}}
<pre>
D:\Code\github\ncoe\rosetta\Addition_chains\Ruby>N = 7
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}}==
Following Scala implementation finds number of minimum length Brauer chains and corresponding length.
<syntaxhighlight lang="scala">
<lang Scala>
object chains{
 
Line 1,818 ⟶ 2,966:
}
}
</syntaxhighlight>
</lang>
<pre>
N = 7
Line 1,875 ⟶ 3,023:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Module Module1
 
Function Prepend(n As Integer, seq As List(Of Integer)) As List(Of Integer)
Line 1,933 ⟶ 3,081:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>N = 7
Line 1,982 ⟶ 3,130:
Minimum length of chains: L(n) = 12
Number of minimum length Brauer chains: 6583</pre>
 
=={{header|Wren}}==
{{trans|Go}}
Based on Version 2 which is itself a translation of the Phix entry.
 
Non-Brauer analysis limited to N = 191 in order to finish in a reasonable time - about 10.75 minutes on my machine.
<syntaxhighlight lang="wren">var maxLen = 13
var maxNonBrauer = 191
 
var isBrauer = Fn.new { |a|
for (i in 2...a.count) {
var ok = false
for (j in i-1..0) {
if (a[i-1] + a[j] == a[i]) {
ok = true
break
}
}
if (!ok) return false
}
return true
}
 
var brauerCount = 0
var nonBrauerCount = 0
var brauerExample = ""
var nonBrauerExample = ""
 
var additionChains // recursive
additionChains = Fn.new { |target, length, chosen|
var le = chosen.count
var last = chosen[-1]
if (last == target) {
if (le < length) {
brauerCount = 0
nonBrauerCount = 0
}
if (isBrauer.call(chosen)) {
brauerCount = brauerCount + 1
brauerExample = chosen.toString
} else {
nonBrauerCount = nonBrauerCount + 1
nonBrauerExample = chosen.toString
}
return le
}
if (le == length) return length
if (target > maxNonBrauer) {
for (i in le-1..0) {
var next = last + chosen[i]
if (next <= target && next > chosen[-1] && i < length) {
length = additionChains.call(target, length, chosen + [next])
}
}
} else {
var ndone = []
while (true) {
for (i in le-1..0) {
var next = last + chosen[i]
if (next <= target && next > chosen[-1] && i < length &&
!ndone.contains(next)) {
ndone.add(next)
length = additionChains.call(target, length, chosen + [next])
}
}
le = le - 1
if (le == 0) break
last = chosen[le-1]
}
}
return length
}
 
var start = System.clock
var nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
System.print("Searching for Brauer chains up to a minimum length of %(maxLen-1)")
for (num in nums) {
brauerCount = 0
nonBrauerCount = 0
var le = additionChains.call(num, maxLen, [1])
System.print("\nN = %(num)")
System.print("Minimum length of chains : L(%(num)) = %(le-1)")
System.print("Number of minimum length Brauer chains : %(brauerCount)")
if (brauerCount > 0) {
System.print("Brauer example : %(brauerExample)")
}
if (num <= maxNonBrauer) {
System.print("Number of minimum length non-Brauer chains : %(nonBrauerCount)")
if (nonBrauerCount > 0) {
System.print("Non-Brauer example : %(nonBrauerExample)")
}
} else System.print("Non-Brauer analysis suppressed")
}
System.print("\nTook %(System.clock - start) seconds.")</syntaxhighlight>
 
{{out}}
<pre>
Searching for Brauer chains up to a minimum length of 12
 
N = 7
Minimum length of chains : L(7) = 4
Number of minimum length Brauer chains : 5
Brauer example : [1, 2, 3, 4, 7]
Number of minimum length non-Brauer chains : 0
 
N = 14
Minimum length of chains : L(14) = 5
Number of minimum length Brauer chains : 14
Brauer example : [1, 2, 3, 4, 7, 14]
Number of minimum length non-Brauer chains : 0
 
N = 21
Minimum length of chains : L(21) = 6
Number of minimum length Brauer chains : 26
Brauer example : [1, 2, 3, 4, 7, 14, 21]
Number of minimum length non-Brauer chains : 3
Non-Brauer example : [1, 2, 4, 5, 8, 13, 21]
 
N = 29
Minimum length of chains : L(29) = 7
Number of minimum length Brauer chains : 114
Brauer example : [1, 2, 3, 4, 7, 11, 18, 29]
Number of minimum length non-Brauer chains : 18
Non-Brauer example : [1, 2, 3, 6, 9, 11, 18, 29]
 
N = 32
Minimum length of chains : L(32) = 5
Number of minimum length Brauer chains : 1
Brauer example : [1, 2, 4, 8, 16, 32]
Number of minimum length non-Brauer chains : 0
 
N = 42
Minimum length of chains : L(42) = 7
Number of minimum length Brauer chains : 78
Brauer example : [1, 2, 3, 4, 7, 14, 21, 42]
Number of minimum length non-Brauer chains : 6
Non-Brauer example : [1, 2, 4, 5, 8, 13, 21, 42]
 
N = 64
Minimum length of chains : L(64) = 6
Number of minimum length Brauer chains : 1
Brauer example : [1, 2, 4, 8, 16, 32, 64]
Number of minimum length non-Brauer chains : 0
 
N = 47
Minimum length of chains : L(47) = 8
Number of minimum length Brauer chains : 183
Brauer example : [1, 2, 3, 4, 7, 10, 20, 27, 47]
Number of minimum length non-Brauer chains : 37
Non-Brauer example : [1, 2, 3, 5, 7, 14, 19, 28, 47]
 
N = 79
Minimum length of chains : L(79) = 9
Number of minimum length Brauer chains : 492
Brauer example : [1, 2, 3, 4, 7, 9, 18, 36, 43, 79]
Number of minimum length non-Brauer chains : 129
Non-Brauer example : [1, 2, 3, 5, 7, 12, 24, 31, 48, 79]
 
N = 191
Minimum length of chains : L(191) = 11
Number of minimum length Brauer chains : 7172
Brauer example : [1, 2, 3, 4, 7, 8, 15, 22, 44, 88, 103, 191]
Number of minimum length non-Brauer chains : 2615
Non-Brauer example : [1, 2, 3, 4, 7, 9, 14, 23, 46, 92, 99, 191]
 
N = 382
Minimum length of chains : L(382) = 11
Number of minimum length Brauer chains : 4
Brauer example : [1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382]
Non-Brauer analysis suppressed
 
N = 379
Minimum length of chains : L(379) = 12
Number of minimum length Brauer chains : 6583
Brauer example : [1, 2, 3, 4, 7, 10, 17, 27, 44, 88, 176, 203, 379]
Non-Brauer analysis suppressed
 
Took 645.993693 seconds.
</pre>
 
=={{header|zkl}}==
{{trans|EchoLisp}}
<langsyntaxhighlight lang="zkl">var exp2=(32).pump(List,(2).pow), // 2^n, n=0..31
_minlg, _counts, _chains; // counters and results
Line 2,019 ⟶ 3,346:
}
}
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">fcn task(n){
_minlg=(0).MAX;
chains(n,List(1),0);
Line 2,026 ⟶ 3,353:
.fmt(n,_minlg,_counts.xplode(),_chains.filter()));
}
T(7,14,21,29,32,42,64,47,79).apply2(task);</langsyntaxhighlight>
{{out}}
<pre>
Alextretyak
1,481

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/263603...364304"