Rebol3 Code Examplex

Rebol [
    title: "Rosetta code: Addition chains"
    file:  %Addition_chains.r3
    url:   https://rosettacode.org/wiki/Addition_chains
]

find-brauer: function/with [
    "Find minimal Brauer (addition) chains for num." {
     Returns [count best-chain], where:
       - count      = number of distinct minimal-length Brauer chains
       - best-chain = one example minimal chain (1..num) as a vector!.}
    num [integer!]
] [
    chain: make vector! reduce ['uint32! n: num]
    in-chain: make bitset! n
    best-len: n
    cnt: 0
    extend-chain 1 0
    reduce [cnt best]
][
    chain: in-chain: best: best-len: cnt: c: n: _

    extend-chain: func [x pos][
        if x * (2 ** (best-len - pos)) < n [ exit ]
        ++ pos
        chain/:pos: x
        in-chain/:x: true
        
        either in-chain/(n - x) [
            ;; found solution
            either pos = best-len [
                cnt: cnt + 1
            ][
                best: copy/part chain pos
                best-len: pos
                cnt: 1
            ]
        ][
            if pos < best-len [
                for i pos 1 -1 [
                    if n > c: x + chain/:i [
                        extend-chain c pos
                    ]
                ]
            ]
        ]
        in-chain/:x: false
    ]
]

foreach num [7 14 21 29 32 42 64 47 79 191 382 379][
    set [cnt: best:] find-brauer num
    print ["N ="  num]
    print ["Minimum length of chains: L(n) =" as-green length? best]
    print ["Number of minimum length Brauer chains:" as-green cnt]
    print ["E.g.:" as-blue mold/flat/only to block! best LF]
]

N = 7
Minimum length of chains: L(n) = 4
Number of minimum length Brauer chains: 5
E.g.: 1 2 4 6 

N = 14
Minimum length of chains: L(n) = 5
Number of minimum length Brauer chains: 14
E.g.: 1 2 4 8 12 

N = 21
Minimum length of chains: L(n) = 6
Number of minimum length Brauer chains: 26
E.g.: 1 2 4 8 16 20 

N = 29
Minimum length of chains: L(n) = 7
Number of minimum length Brauer chains: 114
E.g.: 1 2 4 8 16 24 28 

N = 32
Minimum length of chains: L(n) = 5
Number of minimum length Brauer chains: 1
E.g.: 1 2 4 8 16 

N = 42
Minimum length of chains: L(n) = 7
Number of minimum length Brauer chains: 78
E.g.: 1 2 4 8 16 32 40 

N = 64
Minimum length of chains: L(n) = 6
Number of minimum length Brauer chains: 1
E.g.: 1 2 4 8 16 32 

N = 47
Minimum length of chains: L(n) = 8
Number of minimum length Brauer chains: 183
E.g.: 1 2 4 8 12 13 26 39 

N = 79
Minimum length of chains: L(n) = 9
Number of minimum length Brauer chains: 492
E.g.: 1 2 4 8 16 24 26 52 78 

N = 191
Minimum length of chains: L(n) = 11
Number of minimum length Brauer chains: 7172
E.g.: 1 2 4 8 16 32 48 52 53 106 159 

N = 382
Minimum length of chains: L(n) = 11
Number of minimum length Brauer chains: 4
E.g.: 1 2 4 8 16 17 33 50 83 166 332 

N = 379
Minimum length of chains: L(n) = 12
Number of minimum length Brauer chains: 6583
E.g.: 1 2 4 8 16 32 64 96 104 105 210 315