186 lines
15 KiB
C#
186 lines
15 KiB
C#
using static System.Math; // for Sqrt()
|
|
using System.Collections.Generic; // for List<>, .Count
|
|
using System.Linq; // for .Last(), .ToList()
|
|
using System.Diagnostics; // for Stopwatch()
|
|
using static System.Console; // for Write(), WriteLine()
|
|
using llst = System.Collections.Generic.List<int[]>;
|
|
class Program
|
|
{
|
|
#region vars
|
|
static int[] d, // permutation working array
|
|
drar = new int[19], // digital root lookup array
|
|
dac; // running digital root array
|
|
static long[] p = new long[20], // powers of 10
|
|
ac, // accumulator array
|
|
pp; // long coefficient array that combines with digits of working array
|
|
static bool odd = false; // flag for odd number of digits
|
|
static long sum, // calculated sum of terms (square candidate)
|
|
rt; // root of sum
|
|
static int cn = 0, // solution counter
|
|
nd = 2, // number of digits
|
|
nd1 = nd - 1, // nd helper
|
|
ln, // previous value of "n" (in Recurse())
|
|
dl; // length of "d" array;
|
|
static Stopwatch sw = new Stopwatch(), swt = new Stopwatch(); // for timings
|
|
static List<long> sr = new List<long>(); // temporary list of squares used for building
|
|
static readonly int[] tlo = new int[] { 0, 1, 4, 5, 6 }, // primary differences starting point
|
|
all = Seq(-9, 9), // all possible differences
|
|
odl = Seq(-9, 9, 2), // odd possible differences
|
|
evl = Seq(-8, 8, 2), // even possible differences
|
|
thi = new int[] { 4, 5, 6, 9, 10, 11, 14, 15, 16 }, // primary sums staring point. note: (0, 1) omitted, as any square generated will not have enough digits
|
|
alh = Seq(0, 18), // all possible sums
|
|
odh = Seq(1, 17, 2), // odd possible sums
|
|
evh = Seq(0, 18, 2), // even possible sums
|
|
ten = Seq(0, 9), // used for odd number of digits
|
|
z = Seq(0, 0), // no difference, used to avoid generating a bunch of negative square candidates
|
|
t7 = new int[] { -3, 7 }, // shortcut for low 5
|
|
nin = new int[] { 9 }, // shortcut for hi 10
|
|
tn = new int[] { 10 }, // shortcut for hi 0 (unused, uneeded)
|
|
t12 = new int[] { 2, 12 }, // shortcut for hi 5
|
|
o11 = new int[] { 1, 11 }, // shortcut for hi 15
|
|
pos = new int[] { 0, 1, 4, 5, 6, 9 }; // shortcut for 2nd lo 0
|
|
static llst lul = new llst { z, odl, null, null, evl, t7, odl }, // shortcut lookup lo primary
|
|
luh = new llst { tn, evh, null, null, evh, t12, odh, null, null, evh, nin, odh, null, null, odh, o11, evh }, // shortcut lookup hi primary
|
|
l2l = new llst { pos, null, null, null, all, null, all }, // shortcut lookup lo secondary
|
|
l2h = new llst { null, null, null, null, alh, null, alh, null, null, null, alh, null, null, null, alh, null, alh }, lu, l2; // shortcut lookup hi secondary
|
|
static int[][] chTen = new int[][] { new int[] { 0,2,5,8,9 }, new int[] { 0,3,4,6,9 }, new int[] { 1,4,7,8 }, new int[] { 2,3,5,8 },
|
|
new int[] { 0,3,6,7,9 }, new int[] { 1,2,4,7 }, new int[] { 2,5,6,8 }, new int[] { 0,1,3,6,9 }, new int[] { 1,4,5,7 } };
|
|
static int[][] chAH = new int[][] { new int[] { 0,2,5,8,9,11,14,17,18 }, new int[] { 0,3,4,6,9,12,13,15,18 }, new int[] { 1,4,7,8,10,13,16,17 },
|
|
new int[] { 2,3,5,8,11,12,14,17 }, new int[] { 0,3,6,7,9,12,15,16,18 }, new int[] { 1,2,4,7,10,11,13,16 },
|
|
new int[] { 2,5,6,8,11,14,15,17 }, new int[] { 0,1,3,6,9,10,12,15,18 }, new int[] { 1,4,5,7,10,13,14,16 } };
|
|
#endregion vars
|
|
|
|
// Returns a sequence of integers
|
|
static int[] Seq(int f, int t, int s = 1) { int[] r = new int[(t - f) / s + 1]; for (int i = 0; i < r.Length; i++, f += s) r[i] = f; return r; }
|
|
|
|
// Returns Integer Square Root
|
|
static long ISR(long s) { return (long)Sqrt(s); }
|
|
|
|
// Recursively determines whether "r" is the reverse of "f"
|
|
static bool IsRev(int nd, long f, long r) { nd--; return f / p[nd] != r % 10 ? false : (nd < 1 ? true : IsRev(nd, f % p[nd], r / 10)); }
|
|
|
|
// Recursive procedure to evaluate the permutations, no shortcuts
|
|
static void RecurseLE5(llst lst, int lv) { if (lv == dl) { // check if on last stage of permutation
|
|
if ((sum = ac[lv - 1]) > 0) if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); } // test accumulated sum, append to result if square
|
|
else foreach (int n in lst[lv]) { // set up next permutation
|
|
d[lv] = n; if (lv == 0) ac[0] = pp[0] * n; else ac[lv] = ac[lv - 1] + pp[lv] * n; // update accumulated sum
|
|
RecurseLE5(lst, lv + 1); } } // Recursively call next level
|
|
|
|
// Recursive procedure to evaluate the hi permutations, shortcuts added to avoid generating many non-squares, digital root calc added
|
|
static void Recursehi(llst lst, int lv) {
|
|
int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
|
|
if ((0x202021202030213 & (1 << (int)((sum = ac[lv1]) & 63))) != 0) // test accumulated sum, append to result if square
|
|
if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); }
|
|
else foreach (int n in lst[lv]) { // set up next permutation
|
|
d[lv] = n; if (lv == 0) { ac[0] = pp[0] * n; dac[0] = drar[n]; } // update accumulated sum and running dr
|
|
else { ac[lv] = ac[lv1] + pp[lv] * 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: lst[1] = lu[ln = n]; lst[2] = l2[n]; break; // primary level: set shortcuts for secondary level
|
|
case 1: // secondary level: set shortcuts for tertiary level
|
|
switch (ln) { // for sums
|
|
case 5: case 15: lst[2] = n < 10 ? evh : odh; break;
|
|
case 9: lst[2] = ((n >> 1) & 1) == 0 ? evh : odh; break;
|
|
case 11: lst[2] = ((n >> 1) & 1) == 1 ? evh : odh; break; } break; }
|
|
if (lv == dl - 2) lst[dl - 1] = odd ? chTen[dac[dl - 2]] : chAH[dac[dl - 2]]; // reduce last round according to dr calc
|
|
Recursehi(lst, lv + 1); } } // Recursively call next level
|
|
|
|
// Recursive procedure to evaluate the lo permutations, shortcuts added to avoid generating many non-squares
|
|
static void Recurselo(llst lst, int lv) { int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
|
|
if ((sum = ac[lv1]) > 0) if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); } // test accumulated sum, append to result if square
|
|
else foreach (int n in lst[lv]) { // set up next permutation
|
|
d[lv] = n; if (lv == 0) ac[0] = pp[0] * n; else ac[lv] = ac[lv1] + pp[lv] * n; // update accumulated sum
|
|
switch (lv) { // shortcuts to be performed on designated levels
|
|
case 0: lst[1] = lu[ln = n]; lst[2] = l2[n]; break; // primary level: set shortcuts for secondary level
|
|
case 1: // secondary level: set shortcuts for tertiary level
|
|
switch (ln) { // for difs
|
|
case 1: lst[2] = (((n + 9) >> 1) & 1) == 0 ? evl : odl; break;
|
|
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
|
|
Recurselo(lst, lv + 1); } } // Recursively call next level
|
|
|
|
// Produces a list of candidate square numbers
|
|
static List<long> listEm(llst lst, llst plu, llst pl2) {
|
|
d = new int[dl = lst.Count]; sr.Clear(); lu = plu; l2 = pl2; ac = new long[dl]; dac = new int[dl]; // init support vars
|
|
pp = new long[dl]; for (int i = 0, j = nd1; i < dl; i++, j--) pp[i] = lst[0].Length > 6 ? p[j] + p[i] : p[j] - p[i]; // build coefficients array
|
|
if (nd <= 5) RecurseLE5(lst, 0); else { if (lst[0].Length > 8) Recursehi(lst, 0); else Recurselo(lst, 0); } return sr; } // call appropriate recursive procedure
|
|
|
|
// Reveals whether combining two lists of squares can produce a Rare number
|
|
static void Reveal(List<long> lo, List<long> hi) { List<string> s = new List<string>(); // create temp list of results
|
|
foreach (long l in lo) foreach (long h in hi) { long r = (h - l) >> 1, f = h - r; // generate all possible fwd & rev candidates from lists
|
|
if (IsRev(nd, f, r)) s.Add(string.Format("{0,20} {1,11} {2,10} ", f, ISR(h), ISR(l))); } // test and append sucesses to temp list
|
|
s.Sort(); if (s.Count > 0) foreach (string t in s) // if there are any, output sorted results
|
|
Write("{0,2} {1}{2}", ++cn, t, t == s.Last() ? "" : "\n"); else Write("{0,48}", ""); }
|
|
|
|
static void Main(string[] args) {
|
|
WriteLine("{0,3}{1,20} {2,11} {3,10} {4,4}{5,16} {6, 17}", "nth", "forward", "rt.sum", "rt.dif", "digs", "block time", "total time");
|
|
p[0] = 1; for (int i = 0, j = 1; j < p.Length; i = j++) p[j] = p[i] * 10; // create powers of 10 array
|
|
for (int i = 0; i < drar.Length; i++) drar[i] = (i << 1) % 9; // create digital root array
|
|
llst lls = new llst { tlo }, hls = new llst { thi }; sw.Start(); swt.Start(); // initialize permutations list, timers
|
|
for (; nd <= 18; nd1 = nd++, odd = !odd) { // loop through all numbers of digits
|
|
if (nd > 2) if (odd) hls.Add(ten); else { lls.Add(all); hls[hls.Count - 1] = alh; } // build permutations list
|
|
Reveal(listEm(lls, lul, l2l).ToList(), listEm(hls, luh, l2h)); // reveal results
|
|
if (!odd && nd > 5) hls[hls.Count - 1] = alh; // restore last element of hls, so that dr shortcut doesn't mess up next nd
|
|
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed); sw.Restart(); }
|
|
// 19
|
|
hls.Add(ten);
|
|
Reveal(listEmU(lls, lul, l2l).ToList(), listEmU(hls, luh, l2h)); // reveal unsigned results
|
|
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed);
|
|
}
|
|
#region 19
|
|
static ulong usum, // unsigned calculated sum of terms (square candidate)
|
|
urt; // unsigned root of sum
|
|
static ulong[] acu, // unsigned accumulator array
|
|
ppu; // unsigned long coefficient array that combines with digits of working array
|
|
static List<ulong> sru = new List<ulong>(); // unsigned temporary list of squares used for building
|
|
|
|
// Reveals whether combining two lists of unsigned squares can produce a Rare number
|
|
static void Reveal(List<ulong> lo, List<ulong> hi) {
|
|
List<string> s = new List<string>(); // create temp list of results
|
|
foreach (ulong l in lo) foreach (ulong h in hi) { ulong r = (h - l) >> 1, f = h - r; // generate all possible fwd & rev candidates from lists
|
|
if (IsRev(nd, f, r)) s.Add(string.Format("{0,20} {1,11} {2,10} ", f, ISR(h), ISR(l))); } // test and append sucesses to temp list
|
|
s.Sort(); if (s.Count > 0) foreach (string t in s) // if there are any, output sorted results
|
|
Write("{0,2} {1}{2}", ++cn, t, t == s.Last() ? "" : "\n"); else Write("{0,48}", ""); }
|
|
|
|
// Produces a list of unsigned candidate square numbers
|
|
static List<ulong> listEmU(llst lst, llst plu, llst pl2) {
|
|
d = new int[dl = lst.Count]; sru.Clear(); lu = plu; l2 = pl2; acu = new ulong[dl]; dac = new int[dl]; // init support vars
|
|
ppu = new ulong[dl]; for (int i = 0, j = nd1; i < dl; i++, j--) ppu[i] = (ulong)(lst[0].Length > 6 ? p[j] + p[i] : p[j] - p[i]); // build coefficients array
|
|
if (lst[0].Length > 8) RecurseUhi(lst, 0); else RecurseUlo(lst, 0); return sru; } // call recursive procedure
|
|
|
|
// Recursive procedure to evaluate the unsigned hi permutations, shortcuts added to avoid generating many non-squares, digital root calc added
|
|
static void RecurseUhi(llst lst, int lv) { int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
|
|
if ((0x202021202030213 & (1 << (int)((usum = acu[lv1]) & 63))) != 0) // test accumulated sum, append to result if square
|
|
if ((urt = (ulong)Sqrt(usum)) * urt == usum) sru.Add(usum); }
|
|
else foreach (int n in lst[lv]) { // set up next permutation
|
|
d[lv] = n; if (lv == 0) { acu[0] = ppu[0] * (uint)n; dac[0] = drar[n]; } // update accumulated sum and running dr
|
|
else { acu[lv] = n >= 0 ? acu[lv1] + ppu[lv] * (uint)n : acu[lv1] - ppu[lv] * (uint)-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: lst[1] = lu[ln = n]; lst[2] = l2[n]; break; // primary level: set shortcuts for secondary level
|
|
case 1: // secondary level: set shortcuts for tertiary level
|
|
switch (ln) { // for sums
|
|
case 5: case 15: lst[2] = n < 10 ? evh : odh; break;
|
|
case 9: lst[2] = ((n >> 1) & 1) == 0 ? evh : odh; break;
|
|
case 11: lst[2] = ((n >> 1) & 1) == 1 ? evh : odh; break; } break; }
|
|
if (lv == dl - 2) lst[dl - 1] = odd ? chTen[dac[dl - 2]] : chAH[dac[dl - 2]]; // reduce last round according to dr calc
|
|
RecurseUhi(lst, lv + 1); } } // Recursively call next level
|
|
|
|
// Recursive procedure to evaluate the unsigned lo permutations, shortcuts added to avoid generating many non-squares
|
|
static void RecurseUlo(llst lst, int lv) { int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
|
|
if ((usum = acu[lv1]) > 0) if ((urt = (ulong)Sqrt(usum)) * urt == usum) sru.Add(usum); } // test accumulated sum, append to result if square
|
|
else foreach (int n in lst[lv]) { // set up next permutation
|
|
d[lv] = n; if (lv == 0) acu[0] = ppu[0] * (uint)n;
|
|
else acu[lv] = n >= 0 ? acu[lv1] + ppu[lv] * (uint)n : acu[lv1] - ppu[lv] * (uint)-n; // update accumulated sum
|
|
switch (lv) { // shortcuts to be performed on designated levels
|
|
case 0: lst[1] = lu[ln = n]; lst[2] = l2[n]; break; // primary level: set shortcuts for secondary level
|
|
case 1: // secondary level: set shortcuts for tertiary level
|
|
switch (ln) { // for difs
|
|
case 1: lst[2] = (((n + 9) >> 1) & 1) == 0 ? evl : odl; break;
|
|
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
|
|
RecurseUlo(lst, lv + 1); } } // Recursively call next level
|
|
|
|
// Returns unsigned Integer Square Root
|
|
static ulong ISR(ulong s) { return (ulong)Sqrt(s); }
|
|
|
|
// Recursively determines whether "r" is the reverse of "f"
|
|
static bool IsRev(int nd, ulong f, ulong r) { nd--; return f / (ulong)p[nd] != r % 10 ? false : (nd < 1 ? true : IsRev(nd, f % (ulong)p[nd], r / 10)); }
|
|
#endregion 19
|
|
}
|