Rare numbers: Difference between revisions

← Older editNewer edit →
Content deleted Content added
→‎Quicker: slight speedup with added digital root consideration
m →‎Quicker: a few more minor speed tweaks
Line 738: Line 738:
pp; // long coefficient array that combines with digits of working array
pp; // long coefficient array that combines with digits of working array
static bool odd = false; // flag for odd number of digits
static bool odd = false; // flag for odd number of digits
static long lim, // minimum limit for generated list of squares
static long sum, // calculated sum of terms (square candidate)
sum, // calculated sum of terms (square candidate)
rt; // root of sum
rt; // root of sum
static int cn = 0, // solution counter
static int cn = 0, // solution counter
Line 774: Line 773:
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 } };
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
#endregion vars

// Returns a sequence of integers
// 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; }
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
// Returns Integer Square Root
static long ISR(long s) { return (long)Sqrt(s); }
static long ISR(long s) { return (long)Sqrt(s); }
Line 783: Line 782:
// Recursively determines whether "r" is the reverse of "f"
// 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)); }
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
// 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
static void RecurseLE5(llst lst, int lv) { if (lv == dl) { // check if on last stage of permutation
if ((sum = ac[lv - 1]) > lim) if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); } // test accumulated sum, append to result if square
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
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
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
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
// 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) {
static void Recursehi(llst lst, int lv) {
int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
if ((sum = ac[lv1]) > lim) if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); } // test accumulated sum, append to result if square
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
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
d[lv] = n; if (lv == 0) { ac[0] = pp[0] * n; dac[0] = drar[n]; } // update accumulated sum and running dr
Line 807: Line 807:
if (lv == dl - 2) lst[dl - 1] = odd ? chTen[dac[dl - 2]] : chAH[dac[dl - 2]]; // reduce last round according to dr calc
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
Recursehi(lst, lv + 1); } } // Recursively call next level

// Recursive procedure to evaluate the lo permutations, shortcuts added to avoid generating many non-squares
// 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
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]) > lim) if ((rt = (long)Sqrt(sum)) * rt == sum) sr.Add(sum); } // test accumulated sum, append to result if square
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
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
d[lv] = n; if (lv == 0) ac[0] = pp[0] * n; else ac[lv] = ac[lv1] + pp[lv] * n; // update accumulated sum
Line 820: Line 820:
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
Recurselo(lst, lv + 1); } } // Recursively call next level
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
// 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
static void Reveal(List<long> lo, List<long> hi) { List<string> s = new List<string>(); // create temp list of results
Line 827: Line 833:
s.Sort(); if (s.Count > 0) foreach (string t in s) // if there are any, output sorted results
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}", ""); }
Write("{0,2} {1}{2}", ++cn, t, t == s.Last() ? "" : "\n"); else Write("{0,48}", ""); }

⚫
// Produces a list of candidate square numbers
⚫
static List<long> listEm(llst lst, long lmt, llst plu, llst pl2) {
⚫
d = new int[dl = lst.Count]; lim = lmt; 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] = lmt > 0 ? 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

static void Main(string[] args) {
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");
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");
Line 841: Line 841:
for (; nd <= 18; nd1 = nd++, odd = !odd) { // loop through all numbers of digits
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
if (nd > 2) if (odd) hls.Add(ten); else { lls.Add(all); hls[hls.Count - 1] = alh; } // build permutations list
Reveal(listEm(lls, 0, lul, l2l).ToList(), listEm(hls, p[nd1], luh, l2h)); // reveal results
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
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(); }
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed); sw.Restart(); }
// 19
// 19
hls.Add(ten);
hls.Add(ten);
Reveal(listEm(lls, 0UL, lul, l2l).ToList(), listEm(hls, (ulong)p[nd1], luh, l2h)); // reveal unsigned results
Reveal(listEmU(lls, lul, l2l).ToList(), listEmU(hls, luh, l2h)); // reveal unsigned results
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed);
WriteLine("{0,2}: {1} {2}", nd, sw.Elapsed, swt.Elapsed);
}
}
#region 19
#region 19
static ulong ulim, // unsigned minimum limit for generated list of squares
static ulong usum, // unsigned calculated sum of terms (square candidate)
usum, // unsigned calculated sum of terms (square candidate)
urt; // unsigned root of sum
urt; // unsigned root of sum
static ulong[] acu, // unsigned accumulator array
static ulong[] acu, // unsigned accumulator array
ppu; // unsigned long coefficient array that combines with digits of working 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
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
// Reveals whether combining two lists of unsigned squares can produce a Rare number
static void Reveal(List<ulong> lo, List<ulong> hi) {
static void Reveal(List<ulong> lo, List<ulong> hi) {
Line 864: Line 863:
s.Sort(); if (s.Count > 0) foreach (string t in s) // if there are any, output sorted results
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}", ""); }
Write("{0,2} {1}{2}", ++cn, t, t == s.Last() ? "" : "\n"); else Write("{0,48}", ""); }

// Produces a list of unsigned candidate square numbers
// Produces a list of unsigned candidate square numbers
static List<ulong> listEm(llst lst, ulong lmt, llst plu, llst pl2) {
static List<ulong> listEmU(llst lst, llst plu, llst pl2) {
d = new int[dl = lst.Count]; ulim = lmt; sru.Clear(); lu = plu; l2 = pl2; acu = new ulong[dl]; dac = new int[dl]; // init support vars
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)(lmt > 0 ? p[j] + p[i] : p[j] - p[i]); // build coefficients array
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
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
// 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) {
static void RecurseUhi(llst lst, int lv) { int lv1 = lv - 1; if (lv == dl) { // check if on last stage of permutation
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 ((usum = acu[lv1]) > ulim) if ((urt = (ulong)Sqrt(usum)) * urt == usum) sru.Add(usum); } // 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
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
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; }
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; }
Line 885: Line 884:
case 9: lst[2] = ((n >> 1) & 1) == 0 ? 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; }
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
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
RecurseUhi(lst, lv + 1); } } // Recursively call next level

// Recursive procedure to evaluate the unsigned lo permutations, shortcuts added to avoid generating many non-squares
// 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
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]) > ulim) if ((urt = (ulong)Sqrt(usum)) * urt == usum) sru.Add(usum); } // test accumulated sum, append to result if square
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
else foreach (int n in lst[lv]) { // set up next permutation
d[lv] = n; if (lv == 0) acu[0] = ppu[0] * (uint)n;
d[lv] = n; if (lv == 0) acu[0] = ppu[0] * (uint)n;
else acu[lv] = acu[lv] = n >= 0 ? acu[lv1] + ppu[lv] * (uint)n : acu[lv1] - ppu[lv] * (uint)-n; // update accumulated sum
else acu[lv] = acu[lv] = n >= 0 ? acu[lv1] + ppu[lv] * (uint)n : acu[lv1] - ppu[lv] * (uint)-n; // update accumulated sum
Line 900: Line 899:
case 1: lst[2] = (((n + 9) >> 1) & 1) == 0 ? evl : odl; break;
case 1: lst[2] = (((n + 9) >> 1) & 1) == 0 ? evl : odl; break;
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
case 5: lst[2] = n < 0 ? evl : odl; break; } break; }
RecurseUlo(lst, lv + 1); } } // Recursively call next level
RecurseUlo(lst, lv + 1); } } // Recursively call next level

// Returns unsigned Integer Square Root
// Returns unsigned Integer Square Root
static ulong ISR(ulong s) { return (ulong)Sqrt(s); }
static ulong ISR(ulong s) { return (ulong)Sqrt(s); }

// Recursively determines whether "r" is the reverse of "f"
// 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)); }
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)); }
Line 912: Line 911:
Results on the core i7-7700 @ 3.6Ghz.
Results on the core i7-7700 @ 3.6Ghz.
<pre style="height:64ex;overflow:scroll">nth forward rt.sum rt.dif digs block time total time
<pre style="height:64ex;overflow:scroll">nth forward rt.sum rt.dif digs block time total time
1 65 11 3 2: 00:00:00.0031497 00:00:00.0031498
1 65 11 3 2: 00:00:00.0030253 00:00:00.0030254
3: 00:00:00.0001015 00:00:00.0034161
3: 00:00:00.0000983 00:00:00.0032817
4: 00:00:00.0000978 00:00:00.0035969
4: 00:00:00.0000990 00:00:00.0034631
5: 00:00:00.0000954 00:00:00.0037755
5: 00:00:00.0000911 00:00:00.0036445
2 621770 836 738 6: 00:00:00.0022287 00:00:00.0060875
2 621770 836 738 6: 00:00:00.0021199 00:00:00.0058466
7: 00:00:00.0001597 00:00:00.0063308
7: 00:00:00.0001463 00:00:00.0060747
8: 00:00:00.0002527 00:00:00.0066623
8: 00:00:00.0002520 00:00:00.0064081
3 281089082 23708 330 9: 00:00:00.0022195 00:00:00.0089630
3 281089082 23708 330 9: 00:00:00.0011330 00:00:00.0076229
4 2022652202 63602 300
4 2022652202 63602 300
5 2042832002 63602 6360 10: 00:00:00.0047810 00:00:00.0138352
5 2042832002 63602 6360 10: 00:00:00.0041000 00:00:00.0118157
11: 00:00:00.0205794 00:00:00.0345061
11: 00:00:00.0192048 00:00:00.0311078
6 868591084757 1275175 333333
6 868591084757 1275175 333333
7 872546974178 1320616 32670
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 00:00:00.0560034 00:00:00.0906168
8 872568754178 1320616 33330 12: 00:00:00.0493361 00:00:00.0805451
9 6979302951885 3586209 1047717 13: 00:00:00.3805575 00:00:00.4712564
9 6979302951885 3586209 1047717 13: 00:00:00.3521252 00:00:00.4327577
10 20313693904202 6368252 269730
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
11 20313839704202 6368252 270270
Line 933: Line 932:
14 20333875702202 6368252 336330
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 00:00:01.0451909 00:00:01.5166639
16 40351893720200 6368252 6336336 14: 00:00:00.9007085 00:00:01.3336807
17 200142385731002 20006998 69300
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
18 204238494066002 20122102 1891560
Line 942: Line 941:
23 403058392434500 20211202 19940514
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 00:00:07.2425003 00:00:08.7592526
25 816984566129618 40421606 250800 15: 00:00:06.6980714 00:00:08.0318719
26 2078311262161202 64030648 7529850
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
27 2133786945766212 65272218 2666730
Line 957: Line 956:
38 8191376864400818 127950856 3366330
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 00:00:19.8636982 00:00:28.6230347
40 8650349867341457 127246955 33300333 16: 00:00:17.3843639 00:00:25.4163357
41 22542040692914522 212329862 333300
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 00:02:18.5172366 00:02:47.1403959
43 86965750494756968 417050956 33000 17: 00:02:07.9290721 00:02:33.3454971
44 225342456863243522 671330638 297000
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
45 225342458663243522 671330638 303000
Line 980: Line 979:
61 865721270017296468 1315452006 32071170
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18: 00:06:18.4782142 00:09:05.6187192
63 898907259301737498 1339270086 64576740 18: 00:05:33.0309642 00:08:06.3765495
64 2042401829204402402 2021001202 18915600
64 2042401829204402402 2021001202 18915600
65 2060303819041450202 2020110202 199405140
65 2060303819041450202 2020110202 199405140
Line 992: Line 991:
73 8197906905009010818 4046976144 133408770
73 8197906905009010818 4046976144 133408770
74 8200756128308135597 4019461925 495417087
74 8200756128308135597 4019461925 495417087
75 8320411466598809138 4079154376 36366330 19: 00:44:48.3196521 00:53:53.9384378</pre>
75 8320411466598809138 4079154376 36366330 19: 00:43:27.2101276 00:51:33.5869307</pre>


=={{header|D}}==
=={{header|D}}==
Retrieved from "https://rosettacode.org/wiki/Rare_numbers"