Anonymous user
Addition chains: Difference between revisions
→{{header|EchoLisp}}: added zkl
m (fixed typo) |
(→{{header|EchoLisp}}: added zkl) |
||
Line 88:
(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|zkl}}==
{{trans|EchoLisp}}
<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();
}
}
}</lang>
<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);</lang>
{{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>
| |||