Rare numbers: Difference between revisions
Content deleted Content added
→{{header|F_Sharp|F#}}: 43 down |
→Version 1: Replaced with much faster version. |
||
Line 120:
=={{header|Go}}==
===Version 1===
This
Although fast (numbers up to 15 digits are processed in around 28 seconds), it runs out of memory when trying to process numbers longer than this.
Timings are for an Intel Core i7-8565U machine with 32GB RAM running Go 1.13.1 on Ubuntu 18.04.
<lang go>package main
Line 130 ⟶ 131:
"fmt"
"math"
"sort"
"time"
)
type term struct {
}
const maxDigits = 15
func
sum :=
if !reverse {
for i :=
sum = sum*10 +
}
} else {
for i :=
sum = sum*10 +
}
}
Line 153 ⟶ 156:
}
func sumDigits(n
var sum
for n > 0 {
d := n % 10
Line 163 ⟶ 166:
}
func
if 0x202021202030213&(1<<(n&63)) != 0 {
root := int64(math.Sqrt(float64(n)))
}
return
}
// From the Cartesian product of two or more lists task - Extra credit 1.
func cp(a ...[]int8) [][]int8 {
c
for _, a := range a {
c *= len(a)
}
return nil
}
p := make([][]int8, c)
b := make([]int8, c*len(a))
for i := range
pi :=
s =
for j, n :=
pi[j] =
}
for j := len(n) - 1; j >= 0; j-- {
n[j]++
if n[j] < int8(len(a[j])) {
break
}
}
}
return
}
func
var res []int8
for i := from;
res = append(res, i)
}
return
}
func commatize(n
s := fmt.Sprintf("%d", n)
le := len(s)
Line 216 ⟶ 225:
func main() {
start := time.Now()
allTerms := make([][]term, maxDigits-1)
var terms []term
pow *= 10
pow1, pow2 := pow, int64(1)
for i1, i2 := int8(0), int8(r-1); i1 < i2; i1, i2 = i1+1, i2-1 {
terms = append(terms, term{pow1 - pow2, i1, i2})
}
}
// map of first minus last digits for
fml := map[int8][][]int8{
0: {{2, 2}, {8, 8}},
1: {{6, 5}, {8, 7}},
4: {{4, 0}},
6: {{6, 0}, {8, 2}},
}
// map of other digit differences for 'n' to pairs giving this value
dmd := make(map[int8][][]int8)
for i := int8(0); i < 100; i++ {
a := []int8{i / 10, i % 10}
d := a[0] - a[1]
dmd[d] = append(dmd[d], a)
}
fl := []int8{0, 1, 4, 6}
dl := seq(-9, 9, 1)
zl := []int8{0}
el := seq(-8, 8, 2)
ol := seq(-9, 9, 2)
il := seq(0, 9, 1)
var rares []int64
lists := make([][][]int8, 4)
for i, f := range fl {
lists[i] = [][]int8{{f}}
}
fmt.Printf("The rare numbers with up to %d digits are:\n", maxDigits)
for nd := 2; nd <= maxDigits; nd++ {
digits := make([]int8, nd)
if nd == 4 {
lists[0] = append(lists[0], zl)
lists[1] = append(lists[1], ol)
lists[2] = append(lists[2], el)
lists[3] = append(lists[3], ol)
} else if len(allTerms[nd-2]) > len(lists[0]) {
for i := 0; i < 4; i++ {
lists[i] = append(lists[i], dl)
}
}
for
for _, list := range lists {
cands := cp(list...)
for _, cand := range cands {
nmr := int64(0)
for i, t := range allTerms[nd-2] {
nmr += t.coeff * int64(cand[i])
}
if nmr <= 0 || !isSquare(nmr) {
continue
}
for i := 1;
dis = append(dis, seq(0,
}
}
le :=
if nd%2 ==
digits[nd/2] =
}
}
if !isSquare(npr) {
continue
}
rares = append(rares, toInt64(digits, false))
}
}
}
}
sort.Slice(rares, func(i, j int) bool { return rares[i] < rares[j] })
for i, rare := range rares {
fmt.Printf(" %2d: %19s\n", i+1, commatize(rare))
}
fmt.Printf("\nUp to %d digits processed in %s\n", maxDigits, time.Since(start))
}</lang>
{{output}}
<pre>
The
1: 65
2: 621,770
3: 281,089,082
4: 2,022,652,202
5: 2,042,832,002
6: 868,591,084,757
7: 872,546,974,178
8: 872,568,754,178
9: 6,979,302,951,885
10: 20,313,693,904,202
11: 20,313,839,704,202
12: 20,331,657,922,202
13: 20,331,875,722,202
14: 20,333,875,702,202
15: 40,313,893,704,200
16: 40,351,893,720,200
17: 200,142,385,731,002
18: 204,238,494,066,002
19: 221,462,345,754,122
20: 244,062,891,224,042
21: 245,518,996,076,442
22: 248,359,494,187,442
23: 403,058,392,434,500
24: 441,054,594,034,340
25: 816,984,566,129,618
Up to 15 digits processed in 28.174979081s
</pre>
| |||