Anonymous user
Addition chains: Difference between revisions
Added EchoLisp
m (added the interesting couple (191,382)) |
(Added EchoLisp) |
||
Line 4:
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.
We are interested in chains of minimal length
'''Task'''
For each n in {7,14,21,29,32,42,64} display the following :
Extra-credit: Same task for n in {47, 79, 191, 382 , 379, 12509}
Line 19:
* minimal chain length l(19) = 6
* brauer-chains(19) : count = 31 Ex:
* non-brauer-chains(19) : count = 2 Ex:
=={{header|EchoLisp}}==
<lang scheme>
;; 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 null))
(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]))
</lang>
{{out}}
<pre>
(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) null
L(14) = 5 - brauer-chains: 14 non-brauer: 0 chains: (1 2 3 4 7 14) null
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) null
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) null
;; 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)
</pre>
| |||