Rare numbers: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎{{header|Visual Basic .NET}}: added quicker version
PureFox (talk | contribs)
9,493 edits
→‎{{header|Go}}: Added a second 'quicker' version.
Line 1,400: Line 1,400:


=={{header|Go}}==
=={{header|Go}}==
===Traditional===
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.
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.


Line 1,788: Line 1,789:
74: 8,200,756,128,308,135,597
74: 8,200,756,128,308,135,597
75: 8,320,411,466,598,809,138
75: 8,320,411,466,598,809,138
</pre>
<br>
===Quicker===
{{trans|C#}}
Twice as quick as the first Go version though, despite being a faithful translation, a little slower than the C# and VB.NET versions.
<lang go>package main

import (
"fmt"
"math"
"sort"
"time"
)

type llst = [][]int

var (
d []int // permutation working slice
drar [19]int // digital root lookup array
dac []int // running digital root slice
p [20]int64 // powers of 10
ac []int64 // accumulator slice
pp []int64 // coefficient slice that combines with digits of working slice
sr []int64 // temporary list of squares used for building
)

var (
odd = false // flag for odd number of digits
sum int64 // calculated sum of terms (square candidate)
rt int64 // root of sum
cn = 0 // solution counter
nd = 2 // number of digits
nd1 = nd - 1 // 'nd' helper
ln int // previous value of 'n' (in recurse())
dl int // length of 'd' slice
)

var (
tlo = []int{0, 1, 4, 5, 6} // primary differences starting point
all = seq(-9, 9, 1) // all possible differences
odl = seq(-9, 9, 2) // odd possible differences
evl = seq(-8, 8, 2) // even possible differences
thi = []int{4, 5, 6, 9, 10, 11, 14, 15, 16} // primary sums starting point
alh = seq(0, 18, 1) // all possible sums
odh = seq(1, 17, 2) // odd possible sums
evh = seq(0, 18, 2) // even possible sums
ten = seq(0, 9, 1) // used for odd number of digits
z = seq(0, 0, 1) // no difference, avoids generating a bunch of negative square candidates
t7 = []int{-3, 7} // shortcut for low 5
nin = []int{9} // shortcut for hi 10
tn = []int{10} // shortcut for hi 0 (unused, unneeded)
t12 = []int{2, 12} // shortcut for hi 5
o11 = []int{1, 11} // shortcut for hi 15
pos = []int{0, 1, 4, 5, 6, 9} // shortcut for 2nd lo 0
)

var (
lul = llst{z, odl, nil, nil, evl, t7, odl} // shortcut lookup lo primary
luh = llst{tn, evh, nil, nil, evh, t12, odh, nil, nil, evh, nin, odh, nil, nil,
odh, o11, evh} // shortcut lookup hi primary
l2l = llst{pos, nil, nil, nil, all, nil, all} // shortcut lookup lo secondary
l2h = llst{nil, nil, nil, nil, alh, nil, alh, nil, nil, nil, alh, nil, nil, nil,
alh, nil, alh} // shortcut lookup hi secondary
lu, l2 llst // ditto
chTen = llst{{0, 2, 5, 8, 9}, {0, 3, 4, 6, 9}, {1, 4, 7, 8}, {2, 3, 5, 8},
{0, 3, 6, 7, 9}, {1, 2, 4, 7}, {2, 5, 6, 8}, {0, 1, 3, 6, 9}, {1, 4, 5, 7}}
chAH = llst{{0, 2, 5, 8, 9, 11, 14, 17, 18}, {0, 3, 4, 6, 9, 12, 13, 15, 18}, {1, 4, 7, 8, 10, 13, 16, 17},
{2, 3, 5, 8, 11, 12, 14, 17}, {0, 3, 6, 7, 9, 12, 15, 16, 18}, {1, 2, 4, 7, 10, 11, 13, 16},
{2, 5, 6, 8, 11, 14, 15, 17}, {0, 1, 3, 6, 9, 10, 12, 15, 18}, {1, 4, 5, 7, 10, 13, 14, 16}}
)

// Returns a sequence of integers.
func seq(f, t, s int) []int {
r := make([]int, (t-f)/s+1)
for i := 0; i < len(r); i, f = i+1, f+s {
r[i] = f
}
return r
}

// Returns Integer Square Root.
func isr(s int64) int64 {
return int64(math.Sqrt(float64(s)))
}

// Recursively determines whether 'r' is the reverse of 'f'.
func isRev(nd int, f, r int64) bool {
nd--
if f/p[nd] != r%10 {
return false
}
if nd < 1 {
return true
}
return isRev(nd, f%p[nd], r/10)
}

// Recursive function to evaluate the permutations, no shortcuts.
func recurseLE5(lst llst, lv int) {
if lv == dl { // check if on last stage of permutation
sum = ac[lv-1]
if sum > 0 {
rt = int64(math.Sqrt(float64(sum)))
if rt*rt == sum { // test accumulated sum, append to result if square
sr = append(sr, sum)
}
}
} else {
for _, n := range lst[lv] { // set up next permutation
d[lv] = n
if lv == 0 {
ac[0] = pp[0] * int64(n)
} else {
ac[lv] = ac[lv-1] + pp[lv]*int64(n) // update accumulated sum
}
recurseLE5(lst, lv+1) // recursively call next level
}
}
}

// Recursive function to evaluate the hi permutations, shortcuts added to avoid generating many non-squares, digital root calc added.
func recursehi(lst llst, lv int) {
lv1 := lv - 1
if lv == dl { // check if on last stage of permutation
sum = ac[lv1]
if (0x202021202030213 & (1 << (int(sum) & 63))) != 0 { // test accumulated sum, append to result if square
rt = int64(math.Sqrt(float64(sum)))
if rt*rt == sum {
sr = append(sr, sum)
}
}
} else {
for _, n := range lst[lv] { // set up next permutation
d[lv] = n
if lv == 0 {
ac[0] = pp[0] * int64(n)
dac[0] = drar[n] // update accumulated sum and running dr
} else {
ac[lv] = ac[lv1] + pp[lv]*int64(n)
dac[lv] = dac[lv1] + drar[n]
if dac[lv] > 8 {
dac[lv] -= 9
}
}
switch lv { // shortcuts to be performed on designated levels
case 0: // primary level: set shortcuts for secondary level
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
case 1: // secondary level: set shortcuts for tertiary level
switch ln { // for sums
case 5, 15:
if n < 10 {
lst[2] = evh
} else {
lst[2] = odh
}
case 9:
if ((n >> 1) & 1) == 0 {
lst[2] = evh
} else {
lst[2] = odh
}
case 11:
if ((n >> 1) & 1) == 1 {
lst[2] = evh
} else {
lst[2] = odh
}
}
}
if lv == dl-2 {
// reduce last round according to dr calc
if odd {
lst[dl-1] = chTen[dac[dl-2]]
} else {
lst[dl-1] = chAH[dac[dl-2]]
}
}
recursehi(lst, lv+1) // recursively call next level
}
}
}

// Recursive function to evaluate the lo permutations, shortcuts added to avoid
// generating many non-squares.
func recurselo(lst llst, lv int) {
lv1 := lv - 1
if lv == dl { // check if on last stage of permutation
sum = ac[lv1]
if sum > 0 {
rt = int64(math.Sqrt(float64(sum)))
if rt*rt == sum { // test accumulated sum, append to result if square
sr = append(sr, sum)
}
}
} else {
for _, n := range lst[lv] { // set up next permutation
d[lv] = n
if lv == 0 {
ac[0] = pp[0] * int64(n)
} else {
ac[lv] = ac[lv1] + pp[lv]*int64(n) // update accumulated sum
}
switch lv { // shortcuts to be performed on designated levels
case 0: // primary level: set shortcuts for secondary level
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
case 1: // secondary level: set shortcuts for tertiary level
switch ln { // for difs
case 1:
if (((n + 9) >> 1) & 1) == 0 {
lst[2] = evl
} else {
lst[2] = odl
}
case 5:
if n < 0 {
lst[2] = evl
} else {
lst[2] = odl
}
}
}
recurselo(lst, lv+1) // Recursively call next level
}
}
}

// Produces a list of candidate square numbers.
func listEm(lst, plu, pl2 llst) []int64 {
dl = len(lst)
d = make([]int, dl)
sr = sr[:0]
lu = plu
l2 = pl2
ac = make([]int64, dl)
dac = make([]int, dl) // init support vars
pp = make([]int64, dl)
for i, j := 0, nd1; i < dl; i, j = i+1, j-1 {
// build coefficients array
if len(lst[0]) > 6 {
pp[i] = p[j] + p[i]
} else {
pp[i] = p[j] - p[i]
}
}
// call appropriate recursive function
if nd <= 5 {
recurseLE5(lst, 0)
} else if len(lst[0]) > 8 {
recursehi(lst, 0)
} else {
recurselo(lst, 0)
}
return sr
}

// Reveals whether combining two lists of squares can produce a Rare number.
func reveal(lo, hi []int64) {
var s []string // create temp list of results
for _, l := range lo {
for _, h := range hi {
r := (h - l) >> 1
f := h - r // generate all possible fwd & rev candidates from lists
if isRev(nd, f, r) { // test and append sucesses to temp list
s = append(s, fmt.Sprintf("%20d %11d %10d ", f, isr(h), isr(l)))
}
}
}
sort.Strings(s)
if len(s) > 0 {
for _, t := range s { // if there are any, output sorted results
cn++
tt := ""
if t != s[len(s)-1] {
tt = "\n"
}
fmt.Printf("%2d %s%s", cn, t, tt)
}
} else {
fmt.Printf("%48s", "")
}
}

/* Unsigned variables and functions for nd == 19 */

var (
usum uint64 // unsigned calculated sum of terms (square candidate)
urt uint64 // unsigned root of sum
acu []uint64 // unsigned accumulator slice
ppu []uint64 // unsigned long coefficient slice that combines with digits of working slice
sru []uint64 // unsigned temporary list of squares used for building
)

// Returns Unsigned Integer Square Root.
func isrU(s uint64) uint64 {
return uint64(math.Sqrt(float64(s)))
}

// Recursively determines whether 'r' is the reverse of 'f'.
func isRevU(nd int, f, r uint64) bool {
nd--
if f/uint64(p[nd]) != r%10 {
return false
}
if nd < 1 {
return true
}
return isRevU(nd, f%uint64(p[nd]), r/10)
}

// Recursive function to evaluate the unsigned hi permutations, shortcuts added to avoid
// generating many non-squares, digital root calc added.
func recurseUhi(lst llst, lv int) {
lv1 := lv - 1
if lv == dl { // check if on last stage of permutation
usum = acu[lv1]
if (0x202021202030213 & (1 << (int(usum) & 63))) != 0 { // test accumulated sum, append to result if square
urt = uint64(math.Sqrt(float64(usum)))
if urt*urt == usum {
sru = append(sru, usum)
}
}
} else {
for _, n := range lst[lv] { // set up next permutation
d[lv] = n
if lv == 0 {
acu[0] = ppu[0] * uint64(n)
dac[0] = drar[n] // update accumulated sum and running dr
} else {
if n >= 0 {
acu[lv] = acu[lv1] + ppu[lv]*uint64(n)
} else {
acu[lv] = acu[lv1] - ppu[lv]*uint64(-n)
}
dac[lv] = dac[lv1] + drar[n]
if dac[lv] > 8 {
dac[lv] -= 9
}
}
switch lv { // shortcuts to be performed on designated levels
case 0: // primary level: set shortcuts for secondary level
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
case 1: // secondary level: set shortcuts for tertiary level
switch ln { // for sums
case 5, 15:
if n < 10 {
lst[2] = evh
} else {
lst[2] = odh
}
case 9:
if ((n >> 1) & 1) == 0 {
lst[2] = evh
} else {
lst[2] = odh
}
case 11:
if ((n >> 1) & 1) == 1 {
lst[2] = evh
} else {
lst[2] = odh
}
}
}
if lv == dl-2 {
// reduce last round according to dr calc
if odd {
lst[dl-1] = chTen[dac[dl-2]]
} else {
lst[dl-1] = chAH[dac[dl-2]]
}
}
recurseUhi(lst, lv+1) // recursively call next level
}
}
}

// Recursive function to evaluate the unsigned lo permutations, shortcuts added to avoid
// generating many non-squares.
func recurseUlo(lst llst, lv int) {
lv1 := lv - 1
if lv == dl { // check if on last stage of permutation
usum = acu[lv1]
if usum > 0 {
urt = uint64(math.Sqrt(float64(usum)))
if urt*urt == usum { // test accumulated sum, append to result if square
sru = append(sru, usum)
}
}
} else {
for _, n := range lst[lv] { // set up next permutation
d[lv] = n
if lv == 0 {
acu[0] = ppu[0] * uint64(n)
} else {
if n >= 0 {
acu[lv] = acu[lv1] + ppu[lv]*uint64(n) // update accumulated sum
} else {
acu[lv] = acu[lv1] - ppu[lv]*uint64(-n)
}
}
switch lv { // shortcuts to be performed on designated levels
case 0: // primary level: set shortcuts for secondary level
ln = n
lst[1] = lu[ln]
lst[2] = l2[n]
case 1: // secondary level: set shortcuts for tertiary level
switch ln { // for difs
case 1:
if (((n + 9) >> 1) & 1) == 0 {
lst[2] = evl
} else {
lst[2] = odl
}
case 5:
if n < 0 {
lst[2] = evl
} else {
lst[2] = odl
}
}
}
recurseUlo(lst, lv+1) // Recursively call next level
}
}
}

// Produces a list of candidate square numbers.
func listEmU(lst, plu, pl2 llst) []uint64 {
dl = len(lst)
d = make([]int, dl)
sru = sru[:0]
lu = plu
l2 = pl2
acu = make([]uint64, dl)
dac = make([]int, dl) // init support vars
ppu = make([]uint64, dl)
for i, j := 0, nd1; i < dl; i, j = i+1, j-1 {
// build coefficients array
if len(lst[0]) > 6 {
ppu[i] = uint64(p[j] + p[i])
} else {
ppu[i] = uint64(p[j] - p[i])
}
}
// call appropriate recursive functin on
if len(lst[0]) > 8 {
recurseUhi(lst, 0)
} else {
recurseUlo(lst, 0)
}
return sru
}

// Reveals whether combining two lists of unsigned squares can produce a Rare number.
func revealU(lo, hi []uint64) {
var s []string // create temp list of results
for _, l := range lo {
for _, h := range hi {
r := (h - l) >> 1
f := h - r // generate all possible fwd & rev candidates from lists
if isRevU(nd, f, r) { // test and append sucesses to temp list
s = append(s, fmt.Sprintf("%20d %11d %10d ", f, isrU(h), isrU(l)))
}
}
}
sort.Strings(s)
if len(s) > 0 {
for _, t := range s { // if there are any, output sorted results
cn++
tt := ""
if t != s[len(s)-1] {
tt = "\n"
}
fmt.Printf("%2d %s%s", cn, t, tt)
}
} else {
fmt.Printf("%48s", "")
}
}

var (
bStart time.Time // block start time
tStart time.Time // total start time
)

// Formats time in form hh:mm:ss.fff (i.e. millisecond precision).
func formatTime(d time.Duration) string {
f := d.Milliseconds()
s := f / 1000
f %= 1000
m := s / 60
s %= 60
h := m / 60
m %= 60
return fmt.Sprintf("%02d:%02d:%02d.%03d", h, m, s, f)
}

func main() {
start := time.Now()
fmt.Printf("%3s%20s %11s %10s %3s %11s %11s\n", "nth", "forward", "rt.sum", "rt.dif", "digs", "block time", "total time")
p[0] = 1
for i, j := 0, 1; j < len(p); j++ {
p[j] = p[i] * 10 // create powers of 10 array
i = j
}
for i := 0; i < len(drar); i++ {
drar[i] = (i << 1) % 9 // create digital root array
}
bStart = time.Now()
tStart = bStart
lls := llst{tlo}
hls := llst{thi}
for nd <= 18 { // loop through all numbers of digits
if nd > 2 {
if odd {
hls = append(hls, ten)
} else {
lls = append(lls, all)
hls[len(hls)-1] = alh
}
} // build permutations list
tmp1 := listEm(lls, lul, l2l)
tmp2 := make([]int64, len(tmp1))
copy(tmp2, tmp1)
reveal(tmp2, listEm(hls, luh, l2h)) // reveal results
if !odd && nd > 5 {
hls[len(hls)-1] = alh // restore last element of hls, so that dr shortcut doesn't mess up next nd
}
bTime := formatTime(time.Since(bStart))
tTime := formatTime(time.Since(tStart))
fmt.Printf("%2d: %s %s\n", nd, bTime, tTime)
bStart = time.Now() // restart block timing
nd1 = nd
nd++
odd = !odd
}
// nd == 19
hls = append(hls, ten)
tmp3 := listEmU(lls, lul, l2l)
tmp4 := make([]uint64, len(tmp3))
copy(tmp4, tmp3)
revealU(tmp4, listEmU(hls, luh, l2h)) // reveal unsigned results
fbTime := formatTime(time.Since(bStart))
ftTime := formatTime(time.Since(tStart))
fmt.Printf("%2d: %s %s\n", nd, fbTime, ftTime)
}</lang>

{{out}}
<pre style="height:126ex;overflow:scroll">
nth forward rt.sum rt.dif digs block time total time
1 65 11 3 2: 00:00:00.000 00:00:00.000
3: 00:00:00.000 00:00:00.000
4: 00:00:00.000 00:00:00.000
5: 00:00:00.000 00:00:00.000
2 621770 836 738 6: 00:00:00.000 00:00:00.000
7: 00:00:00.000 00:00:00.000
8: 00:00:00.001 00:00:00.001
3 281089082 23708 330 9: 00:00:00.006 00:00:00.008
4 2022652202 63602 300
5 2042832002 63602 6360 10: 00:00:00.015 00:00:00.023
11: 00:00:00.036 00:00:00.060
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 00:00:00.057 00:00:00.117
9 6979302951885 3586209 1047717 13: 00:00:00.376 00:00:00.494
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
12 20331657922202 6368252 329670
13 20331875722202 6368252 330330
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 00:00:00.981 00:00:01.475
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
19 221462345754122 21045662 69300
20 244062891224042 22011022 1908060
21 245518996076442 22140228 921030
22 248359494187442 22206778 1891560
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 00:00:07.042 00:00:08.517
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
28 2135568943984212 65272218 3267330
29 2135764587964212 65272218 3326670
30 2135786765764212 65272218 3333330
31 4135786945764210 65272218 63333336
32 6157577986646405 105849161 33333333
33 6889765708183410 83866464 82133718
34 8052956026592517 123312255 29999997
35 8052956206592517 123312255 30000003
36 8191154686620818 127950856 3299670
37 8191156864620818 127950856 3300330
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 00:00:18.521 00:00:27.039
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 00:02:13.481 00:02:40.521
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
46 225342478643243522 671330638 363000
47 284684666566486482 754565658 30000
48 284684868364486482 754565658 636000
49 297128548234950692 770186978 32697330
50 297128722852950692 770186978 32702670
51 297148324656930692 770186978 33296670
52 297148546434930692 770186978 33303330
53 497168548234910690 770186978 633363336
54 619431353040136925 1071943279 299667003
55 619631153042134925 1071943279 300333003
56 631688638047992345 1083968809 297302703
57 633288858025996145 1083968809 302637303
58 633488632647994145 1083968809 303296697
59 653488856225994125 1083968809 363303363
60 811865096390477018 1273828556 33030330
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18: 00:06:17.288 00:08:57.810
64 2042401829204402402 2021001202 18915600
65 2060303819041450202 2020110202 199405140
66 2420424089100600242 2200110022 19080600
67 2551755006254571552 2259094848 693000
68 2702373360882732072 2324811012 693000
69 2825378427312735282 2377130742 2508000
70 6531727101458000045 3454234451 1063822617
71 6988066446726832640 2729551744 2554541088
72 8066308349502036608 4016542096 2508000
73 8197906905009010818 4046976144 133408770
74 8200756128308135597 4019461925 495417087
75 8320411466598809138 4079154376 36366330 19: 00:45:42.006 00:54:39.816
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Rare_numbers"