Addition chains

From Rosetta Code
Addition chains is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

An addition chain of length r for n is a sequence 1 = a(0) < a(1) < a(2) ... < a(r) = n , such as a(k) = a(i) + a(j) ( i < k and j < k , i may be = j) . Each member is the sum of two earlier members, not necessarily distincts.

A 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.

We are interested in chains of minimal length L(n).

Task

For each n in {7,14,21,29,32,42,64} display the following : L(n), the count of Brauer chains of length L(n), an example of such a Brauer chain, the count of non-brauer chains of length L(n), an example of such a chain. (NB: counts may be 0 ).

Extra-credit: Same task for n in {47, 79, 191, 382 , 379, 12509}

References

  • OEIS sequences A079301, A079302. [1]
  • Richard K. Guy - Unsolved problems in Number Theory - C6 - Addition chains.

Example

  • minimal chain length l(19) = 6
  • 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)

EchoLisp[edit]

 
;; 2^n
(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))
 
;; counters and results
(define-values (*minlg* *counts* *chains* *calls*) '(0 null null 0))
 
(define (register-hit chain lg )
(define idx (if (brauer? chain lg) 0 1))
(when (< lg *minlg*)
(set! *counts* (make-vector 2 0))
(set! *chains* (make-vector 2 ""))
(set! *minlg* lg))
(vector+= *counts* idx 1)
(vector-set! *chains* idx (vector->list chain)))
 
;; is chain a brauer chain ?
(define (brauer? chain lg)
(for [(i (in-range 1 lg))]
#:break (not (vector-search* (- [chain i] [chain (1- i)]) chain)) => #f
#t))
 
;; all min chains to target n (brute force)
(define (chains n chain lg (a) (top) (tops null))
(++ *calls*)
(set! top [chain lg])
(cond
[(> lg *minlg*) #f] ;; too long
[(= n top) (register-hit chain lg)] ;; hit
[(< n top) #f] ;; too big
[(and (< *minlg* 32) (< (* top [exp2 (- *minlg* lg)]) n)) #f] ;; too small
[else
(for* ([i (in-range lg -1 -1)] [j (in-range lg (1- i) -1)])
(set! a (+ [chain i] [chain j]))
#:continue (<= a top) ;; increasing sequence
#:continue (memq a tops) ;; prevent duplicates
(set! tops (cons a tops))
(vector-push chain a)
(chains n chain (1+ lg))
(vector-pop chain))]))
 
 
(define (task n)
(set!-values (*minlg* *calls*) '(Infinity 0 ))
(chains n (make-vector 1 1) 0)
(printf "L(%d) = %d - brauer-chains: %d non-brauer: %d chains: %a %a "
n *minlg* [*counts* 0] [*counts* 1] [*chains* 0] [*chains* 1]))
 
Output:
(for-each task {7 14 21 29 32 42 64})

L(7) = 4 - brauer-chains: 5 non-brauer: 0 chains: (1 2 3 4 7)  
L(14) = 5 - brauer-chains: 14 non-brauer: 0 chains: (1 2 3 4 7 14)  
L(21) = 6 - brauer-chains: 26 non-brauer: 3 chains: (1 2 3 4 7 14 21) (1 2 4 5 8 13 21) 
L(29) = 7 - brauer-chains: 114 non-brauer: 18 chains: (1 2 3 4 7 11 18 29) (1 2 3 6 9 11 18 29) 
L(32) = 5 - brauer-chains: 1 non-brauer: 0 chains: (1 2 4 8 16 32)  
L(42) = 7 - brauer-chains: 78 non-brauer: 6 chains: (1 2 3 4 7 14 21 42) (1 2 4 5 8 13 21 42) 
L(64) = 6 - brauer-chains: 1 non-brauer: 0 chains: (1 2 4 8 16 32 64) 

;; a few extras
(task 47)
L(47) = 8 - brauer-chains: 183 non-brauer: 37 chains: (1 2 3 4 7 10 20 27 47) (1 2 3 5 7 14 19 28 47) 
(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) 

Kotlin[edit]

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.

// 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)
}
Output:
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

Scala[edit]

Following Scala implementation finds number of minimum length Brauer chains and corresponding length.

 
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)
}
}
 
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

zkl[edit]

Translation of: EchoLisp
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();
}
}
}
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);
Output:
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))