Addition chains: Difference between revisions

* non-brauer-chains(19) : count = 2 Ex: ( 1 2 3 6 7 12 19)

<br><br>

 

=={{header|C}}==

{{trans|Kotlin}}

#include <stdlib.h>

#include <string.h>

for (i = 0; i < 12; ++i) findBrauer(nums[i], 12, 79);

return 0;

 

{{out}}

</pre>

 

 

 

 

 

 

 

 

 

}

{{out}}

Minimum length of chains: L(n)= 4

Number of minimum length Brauer chains: 5

Number of minimum length Brauer chains: 6583</pre>

 

 

 

 

 

 

 

 

 

 

{{out}}

Minimum length of chains: L(n)= 4

Number of minimum length Brauer chains: 5

=={{header|D}}==

{{trans|Scala}}

import std.typecons;

 

find_brauer(i);

}

{{out}}

<pre>N = 7

 

=={{header|EchoLisp}}==

;; 2^n

(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))

(printf "L(%d) = %d - brauer-chains: %d non-brauer: %d chains: %a %a "

n *minlg* [*counts* 0] [*counts* 1] [*chains* 0] [*chains* 1]))

{{out}}

<pre>

===Version 1===

{{trans|Kotlin}}

 

import "fmt"

findBrauer(num, 12, 79)

}

 

{{out}}

{{trans|Phix}}

Much faster than Version 1 and can now complete the non-Brauer analysis for N > 79 in a reasonable time.

 

import (

}

fmt.Printf("\nTook %s\n", time.Since(start))

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

private static class Pair {

int f, s

}

}

{{out}}

<pre>N = 7

Minimum length of chains: L(n)= 12

Number of minimum length Brauer chains: 6583</pre>

 

=={{header|Java}}==

{{trans|D}}

private static class Pair {

int f, s;

}

}

{{out}}

<pre>N = 7

=={{header|Julia}}==

{{trans|Python}}

pos > minlen || seq[1] > n ? (minlen, 0) :

seq[1] == n ? (pos, 1) :

println("Number of minimum length Brauer chains: $nchains")

end

<pre>

N = 7

Number of minimum length Brauer chains: 6583

</pre>

 

=={{header|Kotlin}}==

 

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.

 

var example: List<Int>? = null

println("Searching for Brauer chains up to a minimum length of 12:")

for (num in nums) findBrauer(num, 12, 79)

 

{{out}}

=={{header|Lua}}==

{{trans|D}}

return a[i + 1]

end

end

 

{{out}}

<pre>N = 7

Minimum length of chains: L(n) = 12

Number of minimum length Brauer chains: 6583</pre>

 

=={{header|Perl}}==

use feature 'say';

 

# 47, 79, 191, 382, 379, 379, 12509);

say "Searching for Brauer chains up to a minimum length of 12:";

{{out}}

<pre style="height:35ex">N = 7

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>

 

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.

 

 

{{out}}

<pre>

=={{header|Python}}==

{{trans|Java}}

return [n] + seq

 

nums = [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]

for i in nums:

{{out}}

<pre>

Minimum length of chains: L(n) = 12

Number of minimum length Brauer chains: 6583</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).

 

 

(define (basic-constraints xs n)

 

(for ([x (in-list '(191 382 379 12509))])

 

{{out}}

total time (ms): 237617

</pre>

 

=={{header|Scala}}==

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

object chains{

 

}

}

<pre>

N = 7

=={{header|Visual Basic .NET}}==

{{trans|C#}}

 

Function Prepend(n As Integer, seq As List(Of Integer)) As List(Of Integer)

End Sub

 

{{out}}

<pre>N = 7

Minimum length of chains: L(n) = 12

Number of minimum length Brauer chains: 6583</pre>

 

=={{header|zkl}}==

{{trans|EchoLisp}}

_minlg, _counts, _chains; // counters and results

}

}

_minlg=(0).MAX;

chains(n,List(1),0);

.fmt(n,_minlg,_counts.xplode(),_chains.filter()));

}

{{out}}

<pre>