Rare numbers: Difference between revisions
→Quicker: slight speedup with added digital root consideration
m (unwanted '|' spotted & removed) |
(→Quicker: slight speedup with added digital root consideration) |
||
Line 721:
===Quicker===
Along the lines of the C++ version. Computing the possible squares for the sums and differences, then comparing them together and reporting the ones that have a proper forward, reverse result. To save computation time, some shortcuts have been taken to avoid generating many non-square numbers. <br/><br/>Update, added computation of digital root, which increased performance a few percentage points. Interestingly, the digital root is always zero for the ''difference list of squares'', so no advantage is given by tracking it. Only the ''sum list of squares'' benefits from calculating the digital root of the partial sum and using an abbreviated sequence for the last round of permutation.
<lang csharp>using static System.Math; // for Sqrt()
using System.Collections.Generic; // for List<>, .Count
Line 731:
{
#region vars
static int[] d
drar = new int[19], // digital root lookup 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
▲ hilo; // flag for sums/diffs
static long lim, // minimum limit for generated list of squares
sum, // calculated sum of terms (square candidate)
Line 767 ⟶ 768:
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
Line 785 ⟶ 791:
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
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
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
if (lv == dl - 2) lst[dl - 1] = odd ? chTen[dac[dl - 2]] : chAH[dac[dl - 2]]; // reduce last round according to dr calc
// 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]) > lim) 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
Line 793 ⟶ 816:
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
Recurselo(lst, lv + 1); } } // Recursively call next
▲ else 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; }
▲ Recurse(lst, lv + 1); } } // Recursively call next level
// Reveals whether combining two lists of squares can produce
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
Line 811 ⟶ 830:
// 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];
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
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; //
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, 0, lul, l2l).ToList(), listEm(hls, p[nd1], 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
Line 829 ⟶ 850:
}
#region 19
static ulong ulim, // unsigned minimum limit for generated list of squares
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
static void Reveal(List<ulong> lo, List<ulong> hi) {
List<string> s = new List<string>(); // create temp list of results
Line 842 ⟶ 867:
// Produces a list of unsigned candidate square numbers
static List<ulong> listEm(llst lst, ulong lmt, llst plu, llst pl2) {
d = new int[dl = lst.Count]; ulim = lmt; sru.Clear(); lu = plu; l2 = pl2; acu = new ulong[dl];
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
// 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 ((usum = acu[lv1]) > ulim) 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; 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
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
// Recursive procedure to evaluate the unsigned lo permutations, shortcuts added to avoid generating many non-squares
static void
if ((usum = acu[lv1]) > ulim) 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] = 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
RecurseUlo(lst, lv + 1); } } // Recursively call next
▲ else 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; }
▲ RecurseU(lst, lv + 1); } } // Recursively call next level
// Returns unsigned Integer Square Root
Line 873 ⟶ 912:
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
1 65 11 3 2: 00:00:00.
3: 00:00:00.
4: 00:00:00.
5: 00:00:00.
2 621770 836 738 6: 00:00:00.
7: 00:00:00.
8: 00:00:00.
3 281089082 23708 330 9: 00:00:00.
4 2022652202 63602 300
5 2042832002 63602 6360 10: 00:00:00.
11: 00:00:00.
6 868591084757 1275175 333333
7 872546974178 1320616 32670
8 872568754178 1320616 33330 12: 00:00:00.
9 6979302951885 3586209 1047717 13: 00:00:00.
10 20313693904202 6368252 269730
11 20313839704202 6368252 270270
Line 894 ⟶ 933:
14 20333875702202 6368252 336330
15 40313893704200 6368252 6330336
16 40351893720200 6368252 6336336 14: 00:00:01.
17 200142385731002 20006998 69300
18 204238494066002 20122102 1891560
Line 903 ⟶ 942:
23 403058392434500 20211202 19940514
24 441054594034340 22011022 19940514
25 816984566129618 40421606 250800 15: 00:00:07.
26 2078311262161202 64030648 7529850
27 2133786945766212 65272218 2666730
Line 918 ⟶ 957:
38 8191376864400818 127950856 3366330
39 8650327689541457 127246955 33299667
40 8650349867341457 127246955 33300333 16: 00:00:
41 22542040692914522 212329862 333300
42 67725910561765640 269040196 251135808
43 86965750494756968 417050956 33000 17: 00:02:
44 225342456863243522 671330638 297000
45 225342458663243522 671330638 303000
Line 941 ⟶ 980:
61 865721270017296468 1315452006 32071170
62 871975098681469178 1320582934 3303300
63 898907259301737498 1339270086 64576740 18: 00
64 2042401829204402402 2021001202 18915600
65 2060303819041450202 2020110202 199405140
Line 953 ⟶ 992:
73 8197906905009010818 4046976144 133408770
74 8200756128308135597 4019461925 495417087
75 8320411466598809138 4079154376 36366330 19: 00:
=={{header|D}}==
| |||