547 lines
18 KiB
Go
547 lines
18 KiB
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)
|
|
}
|