Addition chains: Difference between revisions

{{trans|Python}}

 

V chain = [0] * n

V in_chain = [0B] * (n + 1)

L(n) [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]

V (best, cnt) = bauer(n)

 

{{out}}

=={{header|C}}==

{{trans|Kotlin}}

#include <stdlib.h>

#include <string.h>

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

return 0;

 

{{out}}

=={{header|C sharp|C#}}==

{{trans|Java}}

 

namespace AdditionChains {

}

}

{{out}}

<pre>N = 7

While this worked, something made it run extremely slow.

{{trans|D}}

#include <tuple>

#include <vector>

 

return 0;

{{out}}

<pre>

=={{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

Implementation using backtracking.

 

 

-- search strategies

isBrauer [_] = True

isBrauer [_,_] = True

 

Usage examples

Tasks implementation

 

task n =

let ch = chains total n

printf "non-Brauer chains(%i)\t: count = %i\tEx: %s\n\n" n (length ch - length br) (show $ reverse $ head nbr)

else

 

<pre>λ> mapM_ task [7,14,21,29,32,42,64]

For the extra task used compiled code, not GHCi.

 

extraTask n =

let ch = chains brauer n

putStrLn "Non-Brauer analysis suppressed\n"

 

 

<pre>L(47) = 8

Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38,'' [http://www.numdam.org/item?id=JTNB_1994__6_1_21_0].

 

binaryChain n | even n = n : binaryChain (n `div` 2)

| odd n = n : binaryChain (n - 1)

c1 `add` c2 = map (head c2 +) c1 ++ c2

 

<pre>λ> binaryChain 191

=={{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

 

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

{{trans|Go}}

This is a translation of the second Go version.

 

const

if nonBrauerCount > 0:

echo "Non-Brauer example: ", nonBrauerExample.join(", ")

 

{{out}}

=={{header|Perl}}==

{{trans|Raku}}

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

Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.

 

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"l(%d) = %d, Brauer:%d,%s Non-Brauer:%d,%s (%s, %d perms)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">bs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">nbc</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ns</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tries</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

 

{{out}}

=={{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>

 

====Faster method====

chain = [0]*n

in_chain = [False]*(n + 1)

for n in [7, 14, 21, 29, 32, 42, 64, 47, 79, 191, 382, 379]:

best, cnt = bauer(n)

{{out}}

<pre>

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

(formerly Perl 6)

{{trans|Kotlin}}

 

sub check-Sequence($pos, @seq, $n, $minLen --> List) {

 

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

{{out}}

<pre>Searching for Brauer chains up to a minimum length of 12:

=={{header|Ruby}}==

{{trans|D}}

if pos > min_len or seq[0] > n then

return min_len, 0

end

 

{{out}}

<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

 

Non-Brauer analysis limited to N = 191 in order to finish in a reasonable time - about 10.75 minutes on my machine.

var maxNonBrauer = 191

 

} else System.print("Non-Brauer analysis suppressed")

}

 

{{out}}

=={{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>