Rosetta Code

Rare numbers: Difference between revisions

Page Discussion

Rare numbers (view source)

Revision as of 19:26, 2 October 2019

2,751 bytes removed ,  4 years ago
→‎{{header|Go}}: Replaced Cartesian product with a recursive loop, unified the two previous versions and extended Rare number generation to 18 digits.
(→‎Version 2: Replaced with version which has relatively low memory requirement.)
(→‎{{header|Go}}: Replaced Cartesian product with a recursive loop, unified the two previous versions and extended Rare number generation to 18 digits.)
Line 119:
 
=={{header|Go}}==
This uses many of the hints within Shyam Sunder Gupta's webpage combined with Nigel Galloway's general approach (see Talk page) of working from (n-r) and deducing the Rare numbers with various numbers of digits from there.
===Version 1===
This uses most of the hints within Shyam Sunder Gupta's webpage combined with Nigel Galloway's general approach (see Talk page) of working from (n-r) and deducing the Rare numbers with various numbers of digits from there.
 
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.
 
As the algorithm used does not generate the Rare numbers in order, a sorted list is also printed.
<lang go>package main
 
Line 152 ⟶ 148:
sum = sum*10 + int64(digits[i])
}
}
return sum
}
 
func sumDigits(n int64) int64 {
var sum int64
for n > 0 {
d := n % 10
sum += d
n /= 10
}
return sum
Line 167 ⟶ 153:
 
func isSquare(n int64) bool {
if 0x202021202030213&(1<<(n&63)) != 0 {
root := int64(math.Sqrt(float64(n)))
return root*root == n
}
return false
}
 
// 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
}
 
Line 226 ⟶ 180:
start := time.Now()
pow := int64(1)
fmt.Println("Aggregate timings to process all numbers up to:")
// terms of (n-r) expression for number of digits from 2 to maxDigits
allTerms := make([][]term, maxDigits-1)
Line 254 ⟶ 209:
}
fl := []int8{0, 1, 4, 6}
dl := seq(-9, 9, 1) // all differences
zl := []int8{0} // zero differences only
el := seq(-8, 8, 2) // even differences only
ol := seq(-9, 9, 2) // odd differences only
il := seq(0, 9, 1)
var rares []int64
Line 264 ⟶ 219:
lists[i] = [][]int8{{f}}
}
var digits []int8
fmt.Printf("The rare numbers with up to %d digits are:\n", maxDigits)
count := 0
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)
}
}
var indices [][2]int8
for _, t := range allTerms[nd-2] {
indices = append(indices, [2]int8{t.ix1, t.ix2})
}
 
// Recursive closure to generate (n+r) candidates from (n-r) candidates
for _, list := range lists {
// and hence find Rare numbers with a candsgiven :=number cp(list..of digits.)
var fnpr func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr int64, nd, level int)
for _, cand := range cands {
fnpr = func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr int64, nd, level int) {
nmr := int64(0)
if level for i, t :== range allTerms[nd-2]len(dis) {
digits[indices[0][0]] nmr += t.coeff * int64(fml[cand[i0]][di[0]][0])
digits[indices[0][1]] = }fml[cand[0]][di[0]][1]
le if nmr <:= 0 || !isSquarelen(nmrdi) {
if nd%2 == 1 continue{
}le--
var dis digits[nd/2] = di[le]int8
}
dis = append(dis, seq(0, int8(len(fml[cand[0]]))-1, 1))
for i, d := range di[1; i < len(cand); i++:le] {
disdigits[indices[i+1][0]] = append(dis, seq(0, int8(len(dmd[cand[i+1]]))-1, 1))[d][0]
}digits[indices[i+1][1]] = dmd[cand[i+1]][d][1]
if nd%2 == 1 {}
r dis := appendtoInt64(disdigits, iltrue)
npr := nmr + }2*r
if dis = cp!isSquare(dis...npr) {
for _, di := range dis {return
}
digits[indices[0][0]] = fml[cand[0]][di[0]][0]
count++
digits[indices[0][1]] = fml[cand[0]][di[0]][1]
fmt.Printf(" R/N le %2d:=", len(dicount)
fmt.Printf(" %9s ms", commatize(time.Since(start).Milliseconds()))
if nd%2 == 1 {
n := toInt64(digits, le--false)
fmt.Printf(" (%s)\n", digits[nd/2] = di[le]commatize(n))
rares = append(rares, }n)
} for i, d := range di[1:le]else {
for _, num := range digitsdis[indices[i+1][0]level] = dmd[cand[i+1]][d][0]{
digitsdi[indices[i+1][1]level] = dmd[cand[i+1]][d][1]num
fnpr(cand, di, dis, indices, }nmr, nd, level+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>
 
// Recursive closure to generate (n-r) candidates with a given number of digits.
{{output}}
var fnmr func(cand []int8, list [][]int8, indices [][2]int8, nd, level int)
<pre>
fnmr = func(cand []int8, list [][]int8, indices [][2]int8, nd, level int) {
The rare numbers with up to 15 digits are:
1: if level == len(list) 65{
2: nmr := 621,770int64(0)
3: for 281i,089,082 t := range allTerms[nd-2] {
4: 2,022,652,202 nmr += t.coeff * int64(cand[i])
5: 2,042,832,002 }
if nmr <= 0 || !isSquare(nmr) {
6: 868,591,084,757
7: 872,546,974,178 return
8: 872,568,754,178 }
9: 6,979,302,951,885 var dis [][]int8
dis = append(dis, seq(0, int8(len(fml[cand[0]]))-1, 1))
10: 20,313,693,904,202
for i := 1; i < len(cand); i++ {
11: 20,313,839,704,202
dis = append(dis, seq(0, int8(len(dmd[cand[i]]))-1, 1))
12: 20,331,657,922,202
}
13: 20,331,875,722,202
if nd%2 == 1 {
14: 20,333,875,702,202
dis = append(dis, il)
15: 40,313,893,704,200
}
16: 40,351,893,720,200
di := make([]int8, len(dis))
17: 200,142,385,731,002
fnpr(cand, di, dis, indices, nmr, nd, 0)
18: 204,238,494,066,002
} else {
19: 221,462,345,754,122
for _, num := range list[level] {
20: 244,062,891,224,042
cand[level] = num
21: 245,518,996,076,442
fnmr(cand, list, indices, nd, level+1)
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>
 
===Version 2===
To deal with the high memory overhead of the first version, this version delivers the Cartesian products 100 at a time rather than ''en masse''. Not surprisingly, this version is slower than the first and its now taking about 43 seconds to get to 15 digits. However, the pay-off is that 16 and 17 digit numbers can now be processed in a reasonable time without running out of memory.
<lang go>package main
 
import (
"fmt"
"math"
"sort"
"time"
)
 
type term struct {
coeff int64
ix1, ix2 int8
}
 
const (
maxDigits = 17
chanBufSize = 100
)
 
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 {
if 0x202021202030213&(1<<(n&63)) != 0 {
root := int64(math.Sqrt(float64(n)))
return root*root == n
}
return false
}
 
// From the Cartesian product of two or more lists task - Extra credit 1.
// Changed to yield results 'chanBufSize' at a time rather than en masse.
func cp(ch chan<- []int8, a ...[]int8) {
c := 1
for _, a := range a {
c *= len(a)
}
if c == 0 {
close(ch)
return
}
b := make([]int8, c*len(a))
n := make([]int8, len(a))
s := 0
for i := 0; i < c; i++ {
e := s + len(a)
pi := b[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
}
ch <- pi
s = e
}
close(ch)
}
 
func seq(from, to, step int8) []int8 {
var res []int8
for i := from; i <= to; i += step {
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)
fmt.Println("Aggregate timings to process all numbers up to:")
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}},
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) // all differences
zl := []int8{0} // zero differences only
el := seq(-8, 8, 2) // even differences only
ol := seq(-9, 9, 2) // odd differences only
il := seq(0, 9, 1)
var rares []int64
lists := make([][][]int8, 4)
for i, f := range fl {
lists[i] = [][]int8{{f}}
}
for nd := 2; nd <= maxDigits; nd++ {
digits := make([]int8, nd)
if nd == 4 {
lists[0] = append(lists[0], zl)
Line 513 ⟶ 302:
indices = append(indices, [2]int8{t.ix1, t.ix2})
}
 
for _, list := range lists {
chcand := make(chan []int8, chanBufSizelen(list))
go cpfnmr(chcand, list..., indices, nd, 0)
for cand := range ch {
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, 1))
for i := 1; i < len(cand); i++ {
dis = append(dis, seq(0, int8(len(dmd[cand[i]]))-1, 1))
}
if nd%2 == 1 {
dis = append(dis, il)
}
ch2 := make(chan []int8, chanBufSize)
go cp(ch2, dis...)
for di := range ch2 {
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))
}
}
}
fmt.Printf(" %2d digits: %9s ms\n", nd, commatize(time.Since(start).Milliseconds()))
}
 
sort.Slice(rares, func(i, j int) bool { return rares[i] < rares[j] })
fmt.Printf("\nThe rare numbers with up to %d digits are:\n", maxDigits)
for i, rare := range rares {
fmt.Printf(" %2d: %22s23s\n", i+1, commatize(rare))
}
}</lang>
 
{{output}}
Timings are for an Intel Core i7-8565U machine with 32GB RAM running Go 1.13.1 on Ubuntu 18.04.
<pre>
Aggregate timings to process all numbers up to:
R/N 1: 0 ms (65)
2 digits: 0 ms
3 digits: 0 ms
4 digits: 0 ms
5 digits: 0 ms
6 digits R/N 2: 01 ms (621,770)
76 digits: 1 ms
87 digits: 62 ms
98 digits: 915 ms
10 digits R/N 3: 118 15 ms (281,089,082)
11 9 digits: 180 20 ms
12 digits R/N 4: 1,363 20 ms (2,022,652,202)
13 digits R/N 5: 2,323 59 ms (2,042,832,002)
1410 digits: 26,586 99 ms
1511 digits: 43,034 137 ms
16 digits R/N 6: 405,029 361 ms (872,546,974,178)
17 digits R/N 7: 678,839 389 ms (872,568,754,178)
R/N 8: 738 ms (868,591,084,757)
12 digits: 888 ms
R/N 9: 1,130 ms (6,979,302,951,885)
13 digits: 1,446 ms
R/N 10: 4,990 ms (20,313,693,904,202)
R/N 11: 5,058 ms (20,313,839,704,202)
R/N 12: 6,475 ms (20,331,657,922,202)
R/N 13: 6,690 ms (20,331,875,722,202)
R/N 14: 7,293 ms (20,333,875,702,202)
R/N 15: 16,685 ms (40,313,893,704,200)
R/N 16: 16,818 ms (40,351,893,720,200)
14 digits: 17,855 ms
R/N 17: 17,871 ms (200,142,385,731,002)
R/N 18: 18,079 ms (221,462,345,754,122)
R/N 19: 20,774 ms (816,984,566,129,618)
R/N 20: 22,155 ms (245,518,996,076,442)
R/N 21: 22,350 ms (204,238,494,066,002)
R/N 22: 22,413 ms (248,359,494,187,442)
R/N 23: 22,687 ms (244,062,891,224,042)
R/N 24: 26,698 ms (403,058,392,434,500)
R/N 25: 26,905 ms (441,054,594,034,340)
15 digits: 27,932 ms
R/N 26: 77,599 ms (2,133,786,945,766,212)
R/N 27: 96,932 ms (2,135,568,943,984,212)
R/N 28: 99,869 ms (8,191,154,686,620,818)
R/N 29: 102,401 ms (8,191,156,864,620,818)
R/N 30: 103,535 ms (2,135,764,587,964,212)
R/N 31: 105,255 ms (2,135,786,765,764,212)
R/N 32: 109,232 ms (8,191,376,864,400,818)
R/N 33: 122,372 ms (2,078,311,262,161,202)
R/N 34: 148,814 ms (8,052,956,026,592,517)
R/N 35: 153,226 ms (8,052,956,206,592,517)
R/N 36: 185,251 ms (8,650,327,689,541,457)
R/N 37: 187,467 ms (8,650,349,867,341,457)
R/N 38: 189,163 ms (6,157,577,986,646,405)
R/N 39: 217,112 ms (4,135,786,945,764,210)
R/N 40: 230,719 ms (6,889,765,708,183,410)
16 digits: 231,583 ms
R/N 41: 236,505 ms (86,965,750,494,756,968)
R/N 42: 237,391 ms (22,542,040,692,914,522)
R/N 43: 351,728 ms (67,725,910,561,765,640)
17 digits: 360,678 ms
R/N 44: 392,403 ms (284,684,666,566,486,482)
R/N 45: 513,738 ms (225,342,456,863,243,522)
R/N 46: 558,603 ms (225,342,458,663,243,522)
R/N 47: 653,047 ms (225,342,478,643,243,522)
R/N 48: 718,569 ms (284,684,868,364,486,482)
R/N 49: 1,087,602 ms (871,975,098,681,469,178)
R/N 50: 1,763,809 ms (865,721,270,017,296,468)
R/N 51: 1,779,059 ms (297,128,548,234,950,692)
R/N 52: 1,787,466 ms (297,128,722,852,950,692)
R/N 53: 1,888,803 ms (811,865,096,390,477,018)
R/N 54: 1,940,347 ms (297,148,324,656,930,692)
R/N 55: 1,965,331 ms (297,148,546,434,930,692)
R/N 56: 2,273,287 ms (898,907,259,301,737,498)
R/N 57: 2,657,073 ms (631,688,638,047,992,345)
R/N 58: 2,682,636 ms (619,431,353,040,136,925)
R/N 59: 2,948,725 ms (619,631,153,042,134,925)
R/N 60: 3,011,962 ms (633,288,858,025,996,145)
R/N 61: 3,077,937 ms (633,488,632,647,994,145)
R/N 62: 3,928,545 ms (653,488,856,225,994,125)
R/N 63: 4,195,016 ms (497,168,548,234,910,690)
18 digits: 4,445,897 ms
 
The rare numbers with up to 1718 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
26: 2,078,311,262,161,202
27: 2,133,786,945,766,212
28: 2,135,568,943,984,212
29: 2,135,764,587,964,212
30: 2,135,786,765,764,212
31: 4,135,786,945,764,210
32: 6,157,577,986,646,405
33: 6,889,765,708,183,410
34: 8,052,956,026,592,517
35: 8,052,956,206,592,517
36: 8,191,154,686,620,818
37: 8,191,156,864,620,818
38: 8,191,376,864,400,818
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457
41: 22,542,040,692,914,522
42: 67,725,910,561,765,640
43: 86,965,750,494,756,968
44: 225,342,456,863,243,522
45: 225,342,458,663,243,522
46: 225,342,478,643,243,522
47: 284,684,666,566,486,482
48: 284,684,868,364,486,482
49: 297,128,548,234,950,692
50: 297,128,722,852,950,692
51: 297,148,324,656,930,692
52: 297,148,546,434,930,692
53: 497,168,548,234,910,690
54: 619,431,353,040,136,925
55: 619,631,153,042,134,925
56: 631,688,638,047,992,345
57: 633,288,858,025,996,145
58: 633,488,632,647,994,145
59: 653,488,856,225,994,125
60: 811,865,096,390,477,018
61: 865,721,270,017,296,468
62: 871,975,098,681,469,178
63: 898,907,259,301,737,498
</pre>
 
PureFox
9,492

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/293907"