Rare numbers: Difference between revisions
→{{header|Go}}: Added a second version based on Nigel Galloway;s approach.
m (→{{header|REXX}}: added wording to the REXX section header.) |
(→{{header|Go}}: Added a second version based on Nigel Galloway;s approach.) |
||
Line 74:
=={{header|Go}}==
===Version 1===
This takes into account all the hints within Shyam Sunder Gupta's webpage. It also makes use of his observation that no rare number below 10^20 ends in 3 and uses a bit arithmetic trick to further filter out numbers that cannot be perfect squares and thereby avoid the expensive math.Sqrt operation.
Line 344 ⟶ 345:
Took 12m43.807949011s
</pre>
===Version 2===
This is based on Nigel Galloway's approach (see Talk page) of working from (n-r) and deducing the Rare numbers with various numbers of digits from there.
It is more than 500 times faster than Version 1, taking 1.3, 2.3, 28.5 and 42.1 seconds to process all 12, 13, 14 and 15 digit numbers respectively. However, it uses a lot of memory for the Cartesian products.
<lang go>package main
import (
"fmt"
"math"
"sort"
"time"
)
type term struct {
coeff int64
ix1, ix2 int8
}
var (
maxDigits = 15
maxSquares = int64(math.Ceil(math.Sqrt(2 * math.Pow10(maxDigits))))
)
func toInt64(digits []int8, reverse bool) int64 {
sum := int64(0)
if !reverse {
for i := 0; i < len(digits); i++ {
sum = sum*10 + int64(digits[i])
}
} else {
for i := len(digits) - 1; i >= 0; i-- {
sum = sum*10 + int64(digits[i])
}
}
return sum
}
func isSquare(n int64) bool {
root := int64(math.Sqrt(float64(n)))
return root*root == n
}
// From the Cartesian product of two or more lists task - Extra credit 1.
func cp(a ...[]int8) [][]int8 {
c := 1
for _, a := range a {
c *= len(a)
}
if c == 0 {
return nil
}
p := make([][]int8, c)
b := make([]int8, c*len(a))
n := make([]int8, len(a))
s := 0
for i := range p {
e := s + len(a)
pi := b[s:e]
p[i] = pi
s = e
for j, n := range n {
pi[j] = a[j][n]
}
for j := len(n) - 1; j >= 0; j-- {
n[j]++
if n[j] < int8(len(a[j])) {
break
}
n[j] = 0
}
}
return p
}
func seq(from, to int8) []int8 {
var res []int8
for i := from; i <= to; i++ {
res = append(res, i)
}
return res
}
func commatize(n int64) string {
s := fmt.Sprintf("%d", n)
le := len(s)
for i := le - 3; i >= 1; i -= 3 {
s = s[0:i] + "," + s[i:]
}
return s
}
func main() {
start := time.Now()
pow := int64(1)
// terms of (n-r) expression for number of digits from 2 to maxDigits
allTerms := make([][]term, maxDigits-1)
for r := 2; r <= maxDigits; r++ {
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})
pow1 /= 10
pow2 *= 10
}
allTerms[r-2] = terms
}
// map of first minus last digits for 'n' to pairs giving this value
fml := map[int8][][]int8{
0: {{2, 2}, {8, 8}},
1: {{6, 5}, {8, 7}},
4: {{4, 0}},
5: {{8, 3}},
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, 5, 6}
dl := seq(-9, 9)
il := seq(0, 9)
var rares []int64
lists := [][]int8{fl}
fmt.Printf("The rare numbers with up to %d digits are:\n", maxDigits)
for nd := 2; nd <= maxDigits; nd++ {
digits := make([]int8, nd)
if len(allTerms[nd-2]) > len(lists) {
lists = append(lists, dl)
}
var indices [][2]int8
for _, t := range allTerms[nd-2] {
indices = append(indices, [2]int8{t.ix1, t.ix2})
}
cands := cp(lists...)
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
}
var dis [][]int8
dis = append(dis, seq(0, int8(len(fml[cand[0]]))-1))
for i := 1; i < len(cand); i++ {
dis = append(dis, seq(0, int8(len(dmd[cand[i]]))-1))
}
if nd%2 == 1 {
dis = append(dis, il)
}
dis = cp(dis...)
for _, di := range dis {
digits[indices[0][0]] = fml[cand[0]][di[0]][0]
digits[indices[0][1]] = fml[cand[0]][di[0]][1]
le := len(di)
if nd%2 == 1 {
le--
digits[nd/2] = di[le]
}
for i, d := range di[1:le] {
digits[indices[i+1][0]] = dmd[cand[i+1]][d][0]
digits[indices[i+1][1]] = dmd[cand[i+1]][d][1]
}
r := toInt64(digits, true)
npr := nmr + 2*r
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 rare numbers with up to 15 digits are:
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 42.075636626s
</pre>
| |||