Multi-base primes: Difference between revisions
Added Go
(→{{header|Wren}}: Simple optimization - 3 times speed up.) |
(Added Go) |
||
Line 235:
1727 => { 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 22, 23, 24, 26, 27, 29, 31, 33, 36 }
5347 => { 8, 9, 10, 11, 12, 13, 16, 18, 19, 22, 24, 25, 26, 30, 31, 32, 33, 34, 36 }
</pre>
=={{header|Go}}==
{{trans|Wren}}
{{libheader|Go-rcu}}
This takes about 1.2 seconds and 31.3 seconds to process up to 5 and 6 character strings, respectively.
<lang go>package main
import (
"fmt"
"math"
"rcu"
)
var maxDepth = 6
var c = rcu.PrimeSieve(int(math.Pow(36, float64(maxDepth))), true)
var digits = "0123456789abcdefghijklmnopqrstuvwxyz"
var maxStrings [][][]int
var mostBases = -1
func maxSlice(a []int) int {
max := 0
for _, e := range a {
if e > max {
max = e
}
}
return max
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func process(indices []int) {
minBase := maxInt(2, maxSlice(indices)+1)
if 37 - minBase < mostBases {
return // can't affect results so return
}
var bases []int
for b := minBase; b <= 36; b++ {
n := 0
for _, i := range indices {
n = n*b + i
}
if !c[n] {
bases = append(bases, b)
}
}
count := len(bases)
if count > mostBases {
mostBases = count
indices2 := make([]int, len(indices))
copy(indices2, indices)
maxStrings = [][][]int{[][]int{indices2, bases}}
} else if count == mostBases {
indices2 := make([]int, len(indices))
copy(indices2, indices)
maxStrings = append(maxStrings, [][]int{indices2, bases})
}
}
func printResults() {
fmt.Printf("%d\n", len(maxStrings[0][1]))
for _, m := range maxStrings {
s := ""
for _, i := range m[0] {
s = s + string(digits[i])
}
fmt.Printf("%s -> %v\n", s, m[1])
}
}
func nestedFor(indices []int, length, level int) {
if level == len(indices) {
process(indices)
} else {
indices[level] = 0
if level == 0 {
indices[level] = 1
}
for indices[level] < length {
nestedFor(indices, length, level+1)
indices[level]++
}
}
}
func main() {
for depth := 1; depth <= maxDepth; depth++ {
fmt.Print(depth, " character strings which are prime in most bases: ")
maxStrings = maxStrings[:0]
mostBases = -1
indices := make([]int, depth)
nestedFor(indices, len(digits), 0)
printResults()
fmt.Println()
}
}</lang>
{{out}}
<pre>
1 character strings which are prime in most bases: 34
2 -> [3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36]
2 character strings which are prime in most bases: 18
21 -> [3 5 6 8 9 11 14 15 18 20 21 23 26 29 30 33 35 36]
3 character strings which are prime in most bases: 18
131 -> [4 5 7 8 9 10 12 14 15 18 19 20 23 25 27 29 30 34]
551 -> [6 7 11 13 14 15 16 17 19 21 22 24 25 26 30 32 35 36]
737 -> [8 9 11 12 13 15 16 17 19 22 23 24 25 26 29 30 31 36]
4 character strings which are prime in most bases: 19
1727 -> [8 9 11 12 13 15 16 17 19 20 22 23 24 26 27 29 31 33 36]
5347 -> [8 9 10 11 12 13 16 18 19 22 24 25 26 30 31 32 33 34 36]
5 character strings which are prime in most bases: 18
30271 -> [8 10 12 13 16 17 18 20 21 23 24 25 31 32 33 34 35 36]
6 character strings which are prime in most bases: 18
441431 -> [5 8 9 11 12 14 16 17 19 21 22 23 26 28 30 31 32 33]
</pre>
| |||