Addition chains: Difference between revisions
m
→{{header|11l}}: Void
m (fixed typo) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (40 intermediate revisions by 16 users not shown) | |||
Line 1:
{{draft task}}
An
A [[wp:Addition_chain#Brauer_chain|Brauer chain]] for n is an addition chain where a(k) = a(k-1) + a(j) with j < k. Each member uses the previous member as a summand.
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}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
typedef int bool;
typedef struct {
int x, y;
} pair;
int* example = NULL;
int exampleLen = 0;
void reverse(int s[], int len) {
int i, j, t;
for (i = 0, j = len - 1; i < j; ++i, --j) {
t = s[i];
s[i] = s[j];
s[j] = t;
}
}
pair tryPerm(int i, int pos, int seq[], int n, int len, int minLen);
pair checkSeq(int pos, int seq[], int n, int len, int minLen) {
pair p;
if (pos > minLen || seq[0] > n) {
p.x = minLen; p.y = 0;
return p;
}
else if (seq[0] == n) {
example = malloc(len * sizeof(int));
memcpy(example, seq, len * sizeof(int));
exampleLen = len;
p.x = pos; p.y = 1;
return p;
}
else if (pos < minLen) {
return tryPerm(0, pos, seq, n, len, minLen);
}
else {
p.x = minLen; p.y = 0;
return p;
}
}
pair tryPerm(int i, int pos, int seq[], int n, int len, int minLen) {
int *seq2;
pair p, res1, res2;
size_t size = sizeof(int);
if (i > pos) {
p.x = minLen; p.y = 0;
return p;
}
seq2 = malloc((len + 1) * size);
memcpy(seq2 + 1, seq, len * size);
seq2[0] = seq[0] + seq[i];
res1 = checkSeq(pos + 1, seq2, n, len + 1, minLen);
res2 = tryPerm(i + 1, pos, seq, n, len, res1.x);
free(seq2);
if (res2.x < res1.x)
return res2;
else if (res2.x == res1.x) {
p.x = res2.x; p.y = res1.y + res2.y;
return p;
}
else {
printf("Error in tryPerm\n");
p.x = 0; p.y = 0;
return p;
}
}
pair initTryPerm(int x, int minLen) {
int seq[1] = {1};
return tryPerm(0, 0, seq, x, 1, minLen);
}
void printArray(int a[], int len) {
int i;
printf("[");
for (i = 0; i < len; ++i) printf("%d ", a[i]);
printf("\b]\n");
}
bool isBrauer(int a[], int len) {
int i, j;
bool ok;
for (i = 2; i < len; ++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;
}
bool isAdditionChain(int a[], int len) {
int i, j, k;
bool ok, exit;
for (i = 2; i < len; ++i) {
if (a[i] > a[i - 1] * 2) return FALSE;
ok = FALSE; exit = FALSE;
for (j = i - 1; j >= 0; --j) {
for (k = j; k >= 0; --k) {
if (a[j] + a[k] == a[i]) { ok = TRUE; exit = TRUE; break; }
}
if (exit) break;
}
if (!ok) return FALSE;
}
if (example == NULL && !isBrauer(a, len)) {
example = malloc(len * sizeof(int));
memcpy(example, a, len * sizeof(int));
exampleLen = len;
}
return TRUE;
}
void nextChains(int index, int len, int seq[], int *pcount) {
for (;;) {
int i;
if (index < len - 1) {
nextChains(index + 1, len, seq, pcount);
}
if (seq[index] + len - 1 - index >= seq[len - 1]) return;
seq[index]++;
for (i = index + 1; i < len - 1; ++i) {
seq[i] = seq[i-1] + 1;
}
if (isAdditionChain(seq, len)) (*pcount)++;
}
}
int findNonBrauer(int num, int len, int brauer) {
int i, count = 0;
int *seq = malloc(len * sizeof(int));
seq[0] = 1;
seq[len - 1] = num;
for (i = 1; i < len - 1; ++i) {
seq[i] = seq[i - 1] + 1;
}
if (isAdditionChain(seq, len)) count = 1;
nextChains(2, len, seq, &count);
free(seq);
return count - brauer;
}
void findBrauer(int num, int minLen, int nbLimit) {
pair p = initTryPerm(num, minLen);
int actualMin = p.x, brauer = p.y, nonBrauer;
printf("\nN = %d\n", num);
printf("Minimum length of chains : L(%d) = %d\n", num, actualMin);
printf("Number of minimum length Brauer chains : %d\n", brauer);
if (brauer > 0) {
printf("Brauer example : ");
reverse(example, exampleLen);
printArray(example, exampleLen);
}
if (example != NULL) {
free(example);
example = NULL;
exampleLen = 0;
}
if (num <= nbLimit) {
nonBrauer = findNonBrauer(num, actualMin + 1, brauer);
printf("Number of minimum length non-Brauer chains : %d\n", nonBrauer);
if (nonBrauer > 0) {
printf("Non-Brauer example : ");
printArray(example, exampleLen);
}
if (example != NULL) {
free(example);
example = NULL;
exampleLen = 0;
}
}
else {
printf("Non-Brauer analysis suppressed\n");
}
}
int main() {
int i;
int nums[12] = {7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379};
printf("Searching for Brauer chains up to a minimum length of 12:\n");
for (i = 0; i < 12; ++i) findBrauer(nums[i], 12, 79);
return 0;
}</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]
Non-Brauer analysis suppressed
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
</pre>
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
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 Tuple<int, int> CheckSeq(int pos, int[] seq, int n, int min_len) {
if (pos > min_len || seq[0] > n) return new Tuple<int, int>(min_len, 0);
if (seq[0] == n) return new Tuple<int, int>(pos, 1);
if (pos < min_len) return TryPerm(0, pos, seq, n, min_len);
return new Tuple<int, int>(min_len, 0);
}
static Tuple<int, int> TryPerm(int i, int pos, int[] seq, int n, int min_len) {
if (i > pos) return new Tuple<int, int>(min_len, 0);
Tuple<int, int> 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);
if (res2.Item1 < res1.Item1) return res2;
if (res2.Item1 == res1.Item1) return new Tuple<int, int>(res2.Item1, res1.Item2 + res2.Item2);
throw new Exception("TryPerm exception");
}
static Tuple<int, int> InitTryPerm(int x) {
return TryPerm(0, 0, new int[] { 1 }, x, 12);
}
static void FindBrauer(int num) {
Tuple<int, int> res = InitTryPerm(num);
Console.WriteLine();
Console.WriteLine("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) {
int[] nums = new int[] { 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
Array.ForEach(nums, n => FindBrauer(n));
}
}
}</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|C++}}==
While this worked, something made it run extremely slow.
{{trans|D}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <tuple>
#include <vector>
std::pair<int, int> tryPerm(int, int, const std::vector<int>&, int, int);
std::pair<int, int> checkSeq(int pos, const std::vector<int>& seq, int n, int minLen) {
if (pos > minLen || seq[0] > n) return { minLen, 0 };
else if (seq[0] == n) return { pos, 1 };
else if (pos < minLen) return tryPerm(0, pos, seq, n, minLen);
else return { minLen, 0 };
}
std::pair<int, int> tryPerm(int i, int pos, const std::vector<int>& seq, int n, int minLen) {
if (i > pos) return { minLen, 0 };
std::vector<int> seq2{ seq[0] + seq[i] };
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.first < res1.first) return res2;
else if (res2.first == res1.first) return { res2.first, res1.second + res2.second };
else throw std::runtime_error("tryPerm exception");
}
std::pair<int, int> initTryPerm(int x) {
return tryPerm(0, 0, { 1 }, x, 12);
}
void findBrauer(int num) {
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';
}
int main() {
std::vector<int> nums{ 7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379 };
for (int i : nums) {
findBrauer(i);
}
return 0;
}</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|D}}==
{{trans|Scala}}
<syntaxhighlight lang="d">import std.stdio;
import std.typecons;
alias Pair = Tuple!(int, int);
auto check_seq(int pos, int[] seq, int n, int min_len) {
if (pos>min_len || seq[0]>n) return Pair(min_len, 0);
else if (seq[0] == n) return Pair( pos, 1);
else if (pos<min_len) return try_perm(0, pos, seq, n, min_len);
else return Pair(min_len, 0);
}
auto try_perm(int i, int pos, int[] seq, int n, int min_len) {
if (i>pos) return Pair(min_len, 0);
auto res1 = check_seq(pos+1, [seq[0]+seq[i]]~seq, n, min_len);
auto res2 = try_perm(i+1, pos, seq, n, res1[0]);
if (res2[0] < res1[0]) return res2;
else if (res2[0] == res1[0]) return Pair(res2[0], res1[1]+res2[1]);
else throw new Exception("Try_perm exception");
}
auto init_try_perm = function(int x) => try_perm(0, 0, [1], x, 12);
void find_brauer(int num) {
auto res = init_try_perm(num);
writeln;
writeln("N = ", num);
writeln("Minimum length of chains: L(n)= ", res[0]);
writeln("Number of minimum length Brauer chains: ", res[1]);
}
void main() {
auto nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379];
foreach (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|EchoLisp}}==
<
;; 2^n
(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))
Line 70 ⟶ 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>
{{out}}
<pre>
Line 88 ⟶ 738:
(task 79)
L(79) = 9 - brauer-chains: 492 non-brauer: 129 chains: (1 2 3 4 7 9 18 36 43 79) (1 2 3 5 7 12 24 31 48 79)
</pre>
=={{header|Go}}==
===Version 1===
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
import "fmt"
var example []int
func reverse(s []int) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
func checkSeq(pos, n, minLen int, seq []int) (int, int) {
switch {
case pos > minLen || seq[0] > n:
return minLen, 0
case seq[0] == n:
example = seq
return pos, 1
case pos < minLen:
return tryPerm(0, pos, n, minLen, seq)
default:
return minLen, 0
}
}
func tryPerm(i, pos, n, minLen int, seq []int) (int, int) {
if i > pos {
return minLen, 0
}
seq2 := make([]int, len(seq)+1)
copy(seq2[1:], seq)
seq2[0] = seq[0] + seq[i]
res11, res12 := checkSeq(pos+1, n, minLen, seq2)
res21, res22 := tryPerm(i+1, pos, n, res11, seq)
switch {
case res21 < res11:
return res21, res22
case res21 == res11:
return res21, res12 + res22
default:
fmt.Println("Error in tryPerm")
return 0, 0
}
}
func initTryPerm(x, minLen int) (int, int) {
return tryPerm(0, 0, x, minLen, []int{1})
}
func findBrauer(num, minLen, nbLimit int) {
actualMin, brauer := initTryPerm(num, minLen)
fmt.Println("\nN =", num)
fmt.Printf("Minimum length of chains : L(%d) = %d\n", num, actualMin)
fmt.Println("Number of minimum length Brauer chains :", brauer)
if brauer > 0 {
reverse(example)
fmt.Println("Brauer example :", example)
}
example = nil
if num <= nbLimit {
nonBrauer := findNonBrauer(num, actualMin+1, brauer)
fmt.Println("Number of minimum length non-Brauer chains :", nonBrauer)
if nonBrauer > 0 {
fmt.Println("Non-Brauer example :", example)
}
example = nil
} else {
println("Non-Brauer analysis suppressed")
}
}
func isAdditionChain(a []int) bool {
for i := 2; i < len(a); i++ {
if a[i] > a[i-1]*2 {
return false
}
ok := false
jloop:
for j := i - 1; j >= 0; j-- {
for k := j; k >= 0; k-- {
if a[j]+a[k] == a[i] {
ok = true
break jloop
}
}
}
if !ok {
return false
}
}
if example == nil && !isBrauer(a) {
example = make([]int, len(a))
copy(example, a)
}
return true
}
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
}
func nextChains(index, le int, seq []int, pcount *int) {
for {
if index < le-1 {
nextChains(index+1, le, seq, pcount)
}
if seq[index]+le-1-index >= seq[le-1] {
return
}
seq[index]++
for i := index + 1; i < le-1; i++ {
seq[i] = seq[i-1] + 1
}
if isAdditionChain(seq) {
(*pcount)++
}
}
}
func findNonBrauer(num, le, brauer int) int {
seq := make([]int, le)
seq[0] = 1
seq[le-1] = num
for i := 1; i < le-1; i++ {
seq[i] = seq[i-1] + 1
}
count := 0
if isAdditionChain(seq) {
count = 1
}
nextChains(2, le, seq, &count)
return count - brauer
}
func main() {
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 12:")
for _, num := range nums {
findBrauer(num, 12, 79)
}
}</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]
Non-Brauer analysis suppressed
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
</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}}
<syntaxhighlight lang="java">public 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, new int[]{1}, 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);
}
public static void main(String[] args) {
int[] nums = new int[]{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|Julia}}==
{{trans|Python}}
<syntaxhighlight lang="julia">checksequence(pos, seq, n, minlen) =
pos > minlen || seq[1] > n ? (minlen, 0) :
seq[1] == n ? (pos, 1) :
pos < minlen ? trypermutation(0, pos, seq, n, minlen) : (minlen, 0)
function trypermutation(i, pos, seq, n, minlen)
if i > pos
return minlen, 0
end
res1 = checksequence(pos + 1, pushfirst!(deepcopy(seq), seq[1] + seq[i + 1]), n, minlen)
res2 = trypermutation(i + 1, pos, seq, n, res1[1])
if res2[1] < res1[1]
return res2
elseif res2[1] == res1[1]
return res2[1], res1[2] + res2[2]
else
throw("trypermutation exception: res2 head > res1 head")
end
end
for num in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]
(minlen, nchains) = trypermutation(0, 0, [1], num, 12)
println("N = $num\nMinimum length of chains: L(n) = $minlen")
println("Number of minimum length Brauer chains: $nchains")
end
</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|Kotlin}}==
As far as the minimal Brauer chains are concerned, I've translated the code in the Scala entry which even on my modest machine is reasonably fast for generating these in isolation - negligible for N <= 79, 10 seconds for N = 191, 25 seconds for N = 382 and about 2.5 minutes for N = 379. However, N = 12509 (which according to tables requires a minimum length of 17) is still well out of reach using this code.
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.
<syntaxhighlight lang="scala">// version 1.1.51
var example: List<Int>? = null
fun checkSeq(pos: Int, seq: List<Int>, n: Int, minLen: Int): Pair<Int, Int> =
if (pos > minLen || seq[0] > n) minLen to 0
else if (seq[0] == n) { example = seq; pos to 1 }
else if (pos < minLen) tryPerm(0, pos, seq, n, minLen)
else minLen to 0
fun tryPerm(i: Int, pos: Int, seq: List<Int>, n: Int, minLen: Int): Pair<Int, Int> {
if (i > pos) return minLen to 0
val res1 = checkSeq(pos + 1, listOf(seq[0] + seq[i]) + seq, n, minLen)
val res2 = tryPerm(i + 1, pos, seq, n, res1.first)
return if (res2.first < res1.first) res2
else if (res2.first == res1.first) res2.first to (res1.second + res2.second)
else { println("Exception in tryPerm"); 0 to 0 }
}
fun initTryPerm(x: Int, minLen: Int) = tryPerm(0, 0, listOf(1), x, minLen)
fun findBrauer(num: Int, minLen: Int, nbLimit: Int) {
val (actualMin, brauer) = initTryPerm(num, minLen)
println("\nN = $num")
println("Minimum length of chains : L($num) = $actualMin")
println("Number of minimum length Brauer chains : $brauer")
if (brauer > 0) println("Brauer example : ${example!!.reversed()}")
example = null
if (num <= nbLimit) {
val nonBrauer = findNonBrauer(num, actualMin + 1, brauer)
println("Number of minimum length non-Brauer chains : $nonBrauer")
if (nonBrauer > 0) println("Non-Brauer example : ${example!!}")
example = null
}
else {
println("Non-Brauer analysis suppressed")
}
}
fun isAdditionChain(a: IntArray): Boolean {
for (i in 2 until a.size) {
if (a[i] > a[i - 1] * 2) return false
var ok = false
jloop@ for (j in i - 1 downTo 0) {
for (k in j downTo 0) {
if (a[j] + a[k] == a[i]) { ok = true; break@jloop }
}
}
if (!ok) return false
}
if (example == null && !isBrauer(a)) example = a.toList()
return true
}
fun isBrauer(a: IntArray): Boolean {
for (i in 2 until a.size) {
var ok = false
for (j in i - 1 downTo 0) {
if (a[i - 1] + a[j] == a[i]) { ok = true; break }
}
if (!ok) return false
}
return true
}
fun findNonBrauer(num: Int, len: Int, brauer: Int): Int {
val seq = IntArray(len)
seq[0] = 1
seq[len - 1] = num
for (i in 1 until len - 1) seq[i] = seq[i - 1] + 1
var count = if (isAdditionChain(seq)) 1 else 0
fun nextChains(index: Int) {
while (true) {
if (index < len - 1) nextChains(index + 1)
if (seq[index] + len - 1 - index >= seq[len - 1]) return
seq[index]++
for (i in index + 1 until len - 1) seq[i] = seq[i - 1] + 1
if (isAdditionChain(seq)) count++
}
}
nextChains(2)
return count - brauer
}
fun main(args: Array<String>) {
val nums = listOf(7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379)
println("Searching for Brauer chains up to a minimum length of 12:")
for (num in nums) findBrauer(num, 12, 79)
}</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]
Non-Brauer analysis suppressed
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
</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|Raku}}
<syntaxhighlight lang="perl">use strict;
use feature 'say';
my @Example = ();
sub checkSeq {
my($pos, $n, $minLen, @seq) = @_;
if ($pos > $minLen || $seq[0] > $n) {
return $minLen, 0;
} elsif ($seq[0] == $n) {
@Example = @seq;
return $pos, 1;
} elsif ($pos < $minLen) {
return tryPerm(0, $pos, $n, $minLen, @seq);
} else {
return $minLen, 0;
}
}
sub tryPerm {
my($i, $pos, $n, $minLen, @seq) = @_;
return $minLen, 0 if $i > $pos;
my @res1 = checkSeq($pos+1, $n, $minLen, ($seq[0]+$seq[$i],@seq));
my @res2 = tryPerm($i+1, $pos, $n, $res1[0], @seq);
if ($res2[0] < $res1[0]) {
return $res2[0], $res2[1];
} elsif ($res2[0] == $res1[0]) {
return $res2[0], $res1[1]+$res2[1];
} else {
say "Error in tryPerm";
return 0, 0;
}
}
sub initTryPerm {
my($x, $minLen) = @_;
return tryPerm(0, 0, $x, $minLen, (1));
}
sub findBrauer {
my($num, $minLen, $nbLimit) = @_;
my ($actualMin, $brauer) = initTryPerm($num, $minLen);
say "\nN = ". $num;
say "Minimum length of chains : L($num) = $actualMin";
say "Number of minimum length Brauer chains : ". $brauer;
say "Brauer example : ". join ' ', reverse @Example if $brauer > 0;
@Example = ();
if ($num <= $nbLimit) {
my $nonBrauer = findNonBrauer($num, $actualMin+1, $brauer);
say "Number of minimum length non-Brauer chains : ". $nonBrauer;
say "Non-Brauer example : ". join ' ', @Example if $nonBrauer > 0;
@Example = ();
} else {
say "Non-Brauer analysis suppressed";
}
}
sub isAdditionChain {
my(@a) = @_;
for my $i (2 .. $#a) {
return 0 if $a[$i] > $a[$i-1]*2;
my $ok = 0;
for my $j (reverse 0 .. $i-1) {
for my $k (reverse 0 .. $j) {
$ok = 1, last if $a[$j]+$a[$k] == $a[$i];
}
}
return 0 unless $ok;
}
@Example = @a if !isBrauer(@a) and !@Example;
return 1;
}
sub isBrauer {
my(@a) = @_;
for my $i (2 .. $#a) {
my $ok = 0;
for my $j (reverse 0 .. $i-1) {
$ok = 1, last if $a[$i-1]+$a[$j] == $a[$i];
}
return 0 unless $ok;
}
return 1;
}
sub findNonBrauer {
our($num, $len, $brauer) = @_;
our @seq = 1 .. $len-1; push @seq, $num;
our $count = isAdditionChain(@seq) ? 1 : 0;
sub nextChains {
my($index) = @_;
while () {
nextChains($index+1) if $index < $len-1;
return if ($seq[$index]+$len-1-$index >= $seq[$len-1]);
$seq[$index]++;
for ($index+1 .. $len-2) { $seq[$_] = $seq[$_-1] + 1;}
$count++ if isAdditionChain(@seq);
}
}
nextChains(2);
return $count - $brauer;
}
my @nums = (7, 14, 21, 29, 32, 42, 64); # unlock below for extra credits,
# 47, 79, 191, 382, 379, 379, 12509);
say "Searching for Brauer chains up to a minimum length of 12:";
for (@nums) { findBrauer $_, 12, 79 }</syntaxhighlight>
{{out}}
<pre style="height:35ex">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</pre>
=={{header|Phix}}==
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 >=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" line>my @Example = ();
sub check-Sequence($pos, @seq, $n, $minLen --> List) {
if ($pos > $minLen or @seq[0] > $n) {
return $minLen, 0;
} elsif (@seq[0] == $n) {
@Example = @seq;
return $pos, 1;
} elsif ($pos < $minLen) {
return try-Permutation 0, $pos, @seq, $n, $minLen;
} else {
return $minLen, 0;
}
}
multi sub try-Permutation($i, $pos, @seq, $n, $minLen --> List) {
return $minLen, 0 if $i > $pos;
my @res1 = check-Sequence $pos+1, (@seq[0]+@seq[$i],@seq).flat, $n, $minLen;
my @res2 = try-Permutation $i+1, $pos, @seq, $n, @res1[0];
if (@res2[0] < @res1[0]) {
return @res2[0], @res2[1];
} elsif (@res2[0] == @res1[0]) {
return @res2[0], @res1[1]+@res2[1];
} else {
note "Error in try-Permutation";
return 0, 0;
}
}
multi sub try-Permutation($x, $minLen --> List) {
return try-Permutation 0, 0, [1], $x, $minLen;
}
sub find-Brauer($num, $minLen, $nbLimit) {
my ($actualMin, $brauer) = try-Permutation $num, $minLen;
say "\nN = ", $num;
say "Minimum length of chains : L($num) = $actualMin";
say "Number of minimum length Brauer chains : ", $brauer;
say "Brauer example : ", @Example.reverse if $brauer > 0;
@Example = ();
if ($num ≤ $nbLimit) {
my $nonBrauer = find-Non-Brauer $num, $actualMin+1, $brauer;
say "Number of minimum length non-Brauer chains : ", $nonBrauer;
say "Non-Brauer example : ", @Example if $nonBrauer > 0;
@Example = ();
} else {
say "Non-Brauer analysis suppressed";
}
}
sub is-Addition-Chain(@a --> Bool) {
for 2 .. @a.end -> $i {
return False if @a[$i] > @a[$i-1]*2 ;
my $ok = False;
for $i-1 … 0 -> $j {
for $j … 0 -> $k {
{ $ok = True; last } if @a[$j]+@a[$k] == @a[$i];
}
}
return False unless $ok;
}
@Example = @a unless @Example or is-Brauer @a;
return True;
}
sub is-Brauer(@a --> Bool) {
for 2 .. @a.end -> $i {
my $ok = False;
for $i-1 … 0 -> $j {
{ $ok = True; last } if @a[$i-1]+@a[$j] == @a[$i];
}
return False unless $ok;
}
return True;
}
sub find-Non-Brauer($num, $len, $brauer --> Int) {
my @seq = flat 1 .. $len-1, $num;
my $count = is-Addition-Chain(@seq) ?? 1 !! 0;
sub next-Chains($index) {
loop {
next-Chains $index+1 if $index < $len-1;
return if @seq[$index]+$len-1-$index ≥ @seq[$len-1];
@seq[$index]++;
for $index^..^$len-1 { @seq[$_] = @seq[$_-1] + 1 }
$count++ if is-Addition-Chain @seq;
}
}
next-Chains 2;
return $count - $brauer;
}
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</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</pre>
=={{header|Ruby}}==
{{trans|D}}
<syntaxhighlight lang="ruby">def check_seq(pos, seq, n, min_len)
if pos > min_len or seq[0] > n then
return min_len, 0
elsif seq[0] == n then
return pos, 1
elsif pos < min_len then
return try_perm(0, pos, seq, n, min_len)
else
return min_len, 0
end
end
def try_perm(i, pos, seq, n, min_len)
if i > pos then
return min_len, 0
end
res11, res12 = check_seq(pos + 1, [seq[0] + seq[i]] + seq, n, min_len)
res21, res22 = try_perm(i + 1, pos, seq, n, res11)
if res21 < res11 then
return res21, res22
elsif res21 == res11 then
return res21, res12 + res22
else
raise "try_perm exception"
end
end
def init_try_perm(x)
return try_perm(0, 0, [1], x, 12)
end
def find_brauer(num)
actualMin, brauer = init_try_perm(num)
puts
print "N = ", num, "\n"
print "Minimum length of chains: L(n)= ", actualMin, "\n"
print "Number of minimum length Brauer chains: ", 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)
end
end
main()</syntaxhighlight>
{{out}}
<pre>
D:\Code\github\ncoe\rosetta\Addition_chains\Ruby>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">
object chains{
def check_seq(pos:Int,seq:List[Int],n:Int,min_len:Int):(Int,Int) = {
if(pos>min_len || seq(0)>n) (min_len,0)
else if(seq(0) == n) (pos,1)
else if(pos<min_len) try_perm(0,pos,seq,n,min_len)
else (min_len,0)
}
def try_perm(i:Int,pos:Int,seq:List[Int],n:Int,min_len:Int):(Int,Int) = {
if(i>pos) return (min_len,0)
val res1 = check_seq(pos+1,seq(0)+seq(i) :: seq,n,min_len)
val res2 = try_perm(i+1,pos,seq,n,res1._1)
if(res2._1 < res1._1) res2
else if(res2._1 == res1._1) (res2._1,res1._2 + res2._2)
else {
println("Try_perm exception")
(0,0)
}
}
val init_try_perm = (x:Int) => try_perm(0,0,List[Int](1),x,10)
def find_brauer(num:Int): Unit = {
val res = init_try_perm(num)
println()
println("N = %d".format(num))
println("Minimum length of chains: L(n)= " + res._1 + f"\nNumber of minimum length Brauer chains: " + res._2)
}
def main(args:Array[String]) :Unit = {
val nums = List(7,14,21,29,32,42,64)
for (i <- nums) find_brauer(i)
}
}
</syntaxhighlight>
<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 = 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|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function Prepend(n As Integer, seq As List(Of Integer)) As List(Of Integer)
Dim result As New List(Of Integer) From {
n
}
result.AddRange(seq)
Return result
End Function
Function CheckSeq(pos As Integer, seq As List(Of Integer), n As Integer, min_len As Integer) As Tuple(Of Integer, Integer)
If pos > min_len OrElse seq(0) > n Then
Return Tuple.Create(min_len, 0)
End If
If seq(0) = n Then
Return Tuple.Create(pos, 1)
End If
If pos < min_len Then
Return TryPerm(0, pos, seq, n, min_len)
End If
Return Tuple.Create(min_len, 0)
End Function
Function TryPerm(i As Integer, pos As Integer, seq As List(Of Integer), n As Integer, min_len As Integer) As Tuple(Of Integer, Integer)
If i > pos Then
Return Tuple.Create(min_len, 0)
End If
Dim res1 = CheckSeq(pos + 1, Prepend(seq(0) + seq(i), seq), n, min_len)
Dim res2 = TryPerm(i + 1, pos, seq, n, res1.Item1)
If res2.Item1 < res1.Item1 Then
Return res2
End If
If res2.Item1 = res1.Item1 Then
Return Tuple.Create(res2.Item1, res1.Item2 + res2.Item2)
End If
Throw New Exception("TryPerm exception")
End Function
Function InitTryPerm(x As Integer) As Tuple(Of Integer, Integer)
Return TryPerm(0, 0, New List(Of Integer) From {1}, x, 12)
End Function
Sub FindBrauer(num As Integer)
Dim res = InitTryPerm(num)
Console.WriteLine("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)
Console.WriteLine()
End Sub
Sub Main()
Dim nums() = {7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379}
Array.ForEach(nums, Sub(n) FindBrauer(n))
End Sub
End Module</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|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}}
<syntaxhighlight lang="zkl">var exp2=(32).pump(List,(2).pow), // 2^n, n=0..31
_minlg, _counts, _chains; // counters and results
fcn register_hit(chain,lg){ // save [upto 2] chains
idx:=(if(isBrauer(chain,lg)) 0 else 1);
if(lg<_minlg) _counts,_chains,_minlg=List(0,0), List("",""), lg;
_counts[idx]+=1;
_chains[idx]=chain.copy();
}
// is chain a brauer chain ?
fcn isBrauer(chain,lg){
foreach i in (lg){
if(not chain.holds(chain[i+1] - chain[i])) return(False);
}
True
}
// all min chains to target n (brute force)
fcn chains(n,chain,lg){
top,tops:=chain[lg], List();
if(lg>_minlg) {} // too long
else if(n==top) register_hit(chain,lg); // hit
else if(n<top) {} // too big
else if((_minlg<32) and (top*exp2[_minlg - lg]<n)){} // too small
else{
foreach i,j in ([lg..0,-1],[lg..i,-1]){
a:=chain[i] + chain[j];
if(a<=top) continue; // increasing sequence
if(tops.holds(a)) continue; // prevent duplicates
tops.append(a);
chain.append(a);
self.fcn(n,chain,lg+1); // recurse
chain.pop();
}
}
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn task(n){
_minlg=(0).MAX;
chains(n,List(1),0);
println("L(%2d) = %d; Brauer-chains: %3d; non-brauer: %3d; chains: %s"
.fmt(n,_minlg,_counts.xplode(),_chains.filter()));
}
T(7,14,21,29,32,42,64,47,79).apply2(task);</syntaxhighlight>
{{out}}
<pre>
L( 7) = 4; Brauer-chains: 5; non-brauer: 0; chains: L(L(1,2,3,4,7))
L(14) = 5; Brauer-chains: 14; non-brauer: 0; chains: L(L(1,2,3,4,7,14))
L(21) = 6; Brauer-chains: 26; non-brauer: 3; chains: L(L(1,2,3,4,7,14,21),L(1,2,4,5,8,13,21))
L(29) = 7; Brauer-chains: 114; non-brauer: 18; chains: L(L(1,2,3,4,7,11,18,29),L(1,2,3,6,9,11,18,29))
L(32) = 5; Brauer-chains: 1; non-brauer: 0; chains: L(L(1,2,4,8,16,32))
L(42) = 7; Brauer-chains: 78; non-brauer: 6; chains: L(L(1,2,3,4,7,14,21,42),L(1,2,4,5,8,13,21,42))
L(64) = 6; Brauer-chains: 1; non-brauer: 0; chains: L(L(1,2,4,8,16,32,64))
L(47) = 8; Brauer-chains: 183; non-brauer: 37; chains: L(L(1,2,3,4,7,10,20,27,47),L(1,2,3,5,7,14,19,28,47))
L(79) = 9; Brauer-chains: 492; non-brauer: 129; chains: L(L(1,2,3,4,7,9,18,36,43,79),L(1,2,3,5,7,12,24,31,48,79))
</pre>
| |||