Rare numbers: Difference between revisions
Added C# version, translated from the Go version
m (removed the forcing of the placement of the TOC (table of contents).) |
(Added C# version, translated from the Go version) |
||
Line 26:
:* author's website: [http://www.shyamsundergupta.com/rare.htm rare numbers] by Shyam Sunder Gupta. (lots of hints and some observations).
<br><br>
=={{header|C#}}==
{{trans|Go}}
Converted to unsigned longs in order to reach 19 digits.
<lang csharp>using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using UI = System.UInt64;
using LST = System.Collections.Generic.List<System.Collections.Generic.List<sbyte>>;
using Lst = System.Collections.Generic.List<sbyte>;
using DT = System.DateTime;
class Program {
const sbyte MxD = 19;
public struct term { public UI coeff; public sbyte a, b;
public term(UI c, int a_, int b_) { coeff = c; a = (sbyte)a_; b = (sbyte)b_; } }
static int[] digs; static List<UI> res; static sbyte count = 0;
static DT st; static List<List<term>> tLst; static List<LST> lists;
static Dictionary<int, LST> fml, dmd; static Lst dl, zl, el, ol, il;
static bool odd; static int nd, nd2; static LST ixs;
static int[] cnd, di; static LST dis; static UI Dif;
// converts digs array to the "difference"
static UI ToDif() { UI r = 0; for (int i = 0; i < digs.Length; i++)
r = r * 10 + (uint)digs[i]; return r; }
// converts digs array to the "sum"
static UI ToSum() { UI r = 0; for (int i = digs.Length - 1; i >= 0; i--)
r = r * 10 + (uint)digs[i]; return Dif + (r << 1); }
// determines if the nmbr is square or not
static bool IsSquare(UI nmbr) { if ((0x202021202030213 & (1 << (int)(nmbr & 63))) != 0)
{ UI r = (UI)Math.Sqrt((double)nmbr); return r * r == nmbr; } return false; }
// returns sequence of sbytes
static Lst Seq(sbyte from, int to, sbyte stp = 1) { Lst res = new Lst();
for (sbyte item = from; item <= to; item += stp) res.Add(item); return res; }
// Recursive closure to generate (n+r) candidates from (n-r) candidates
static void Fnpr(int lev) { if (lev == dis.Count) { digs[ixs[0][0]] = fml[cnd[0]][di[0]][0];
digs[ixs[0][1]] = fml[cnd[0]][di[0]][1]; int le = di.Length, i = 1;
if (odd) digs[nd >> 1] = di[--le]; foreach (sbyte d in di.Skip(1).Take(le - 1)) {
digs[ixs[i][0]] = dmd[cnd[i]][d][0]; digs[ixs[i][1]] = dmd[cnd[i++]][d][1]; }
if (!IsSquare(ToSum())) return; res.Add(ToDif()); WriteLine("{0,16:n0}{1,4} ({2:n0})",
(DT.Now - st).TotalMilliseconds, ++count, res.Last()); }
else foreach (var n in dis[lev]) { di[lev] = n; Fnpr(lev + 1); } }
// Recursive closure to generate (n-r) candidates with a given number of digits.
static void Fnmr (LST list, int lev) { if (lev == list.Count) { Dif = 0; sbyte i = 0;
foreach (var t in tLst[nd2]) { if (cnd[i] < 0) Dif -= t.coeff * (UI)(-cnd[i++]);
else Dif += t.coeff * (UI)cnd[i++]; } if (Dif <= 0 || !IsSquare(Dif)) return;
dis = new LST { Seq(0, fml[cnd[0]].Count - 1) };
foreach (int ii in cnd.Skip(1)) dis.Add(Seq(0, dmd[ii].Count - 1));
if (odd) dis.Add(il); di = new int[dis.Count]; Fnpr(0);
} else foreach(sbyte n in list[lev]) { cnd[lev] = n; Fnmr(list, lev + 1); } }
static void init() { UI pow = 1;
// terms of (n-r) expression for number of digits from 2 to maxDigits
tLst = new List<List<term>>(); foreach (int r in Seq(2, MxD)) {
List<term> terms = new List<term>(); pow *= 10; UI p1 = pow, p2 = 1;
for (int i1 = 0, i2 = r - 1; i1 < i2; i1++, i2--) {
terms.Add(new term(p1 - p2, i1, i2)); p1 /= 10; p2 *= 10; }
tLst.Add(terms); }
// map of first minus last digits for 'n' to pairs giving this value
fml = new Dictionary<int, LST> {
[0] = new LST { new Lst { 2, 2 }, new Lst { 8, 8 } },
[1] = new LST { new Lst { 6, 5 }, new Lst { 8, 7 } },
[4] = new LST { new Lst { 4, 0 } },
[6] = new LST { new Lst { 6, 0 }, new Lst { 8, 2 } } };
// map of other digit differences for 'n' to pairs giving this value
dmd = new Dictionary<int, LST>();
for (sbyte i = 0; i < 10; i++) for (sbyte j = 0, d = i; j < 10; j++, d--) {
if (dmd.ContainsKey(d)) dmd[d].Add(new Lst { i, j });
else dmd[d] = new LST { new Lst { i, j } }; }
dl = Seq(-9, 9); // all differences
zl = Seq( 0, 0); // zero differences only
el = Seq(-8, 8, 2); // even differences only
ol = Seq(-9, 9, 2); // odd differences only
il = Seq( 0, 9); lists = new List<LST>();
foreach (sbyte f in fml.Keys) lists.Add(new LST { new Lst { f } }); }
static void Main(string[] args) { init(); res = new List<UI>(); st = DT.Now; count = 0;
WriteLine("{0,5}{1,12}{2,4}{3,14}", "digs", "elapsed(ms)", "R/N", "Unordered Rare Numbers");
for (nd = 2, nd2 = 0, odd = false; nd <= MxD; nd++, nd2++, odd = !odd) { digs = new int[nd];
if (nd == 4) { lists[0].Add(zl); lists[1].Add(ol); lists[2].Add(el); lists[3].Add(ol); }
else if (tLst[nd2].Count > lists[0].Count) foreach (LST list in lists) list.Add(dl);
ixs = new LST();
foreach (term t in tLst[nd2]) ixs.Add(new Lst { t.a, t.b });
foreach (LST list in lists) { cnd = new int[list.Count]; Fnmr(list, 0); }
WriteLine(" {0,2} {1,10:n0}", nd, (DT.Now - st).TotalMilliseconds); }
res.Sort();
WriteLine("\nThe {0} rare numbers with up to {1} digits are:", res.Count, MxD);
count = 0; foreach (var rare in res) WriteLine("{0,2}:{1,27:n0}", ++count, rare);
if (System.Diagnostics.Debugger.IsAttached) ReadKey(); }
}</lang>
{{out}}
Results from a core i7-7700 @ 3.6Ghz. This C# version isn't as fast as the Go version using the same hardware. C# computes up to 17 digits in under 9 minutes (Go is about 6 minutes). The '''''long'''-to-'''ulong''''' conversion isn't causing the reduced performance, C# has more overhead as compared to Go. This C# version can easily be converted to use BigIntegers to go beyond 19 digits, but becomes around eight times slower. (ugh!)
<pre style="height:64ex;overflow:scroll"> digs elapsed(ms) R/N Unordered Rare Numbers
28 1 (65)
2 29
3 29
4 29
5 29
30 2 (621,770)
6 30
7 30
8 34
35 3 (281,089,082)
9 36
37 4 (2,022,652,202)
61 5 (2,042,832,002)
10 116
11 175
450 6 (872,546,974,178)
483 7 (872,568,754,178)
935 8 (868,591,084,757)
12 1,224
1,547 9 (6,979,302,951,885)
13 2,053
6,214 10 (20,313,693,904,202)
6,291 11 (20,313,839,704,202)
7,947 12 (20,331,657,922,202)
8,199 13 (20,331,875,722,202)
8,898 14 (20,333,875,702,202)
21,287 15 (40,313,893,704,200)
21,444 16 (40,351,893,720,200)
14 23,985
24,051 17 (200,142,385,731,002)
24,295 18 (221,462,345,754,122)
27,423 19 (816,984,566,129,618)
29,052 20 (245,518,996,076,442)
29,294 21 (204,238,494,066,002)
29,369 22 (248,359,494,187,442)
29,698 23 (244,062,891,224,042)
35,723 24 (403,058,392,434,500)
35,966 25 (441,054,594,034,340)
15 38,517
92,890 26 (2,133,786,945,766,212)
114,173 27 (2,135,568,943,984,212)
117,490 28 (8,191,154,686,620,818)
120,349 29 (8,191,156,864,620,818)
121,606 30 (2,135,764,587,964,212)
123,449 31 (2,135,786,765,764,212)
127,882 32 (8,191,376,864,400,818)
142,589 33 (2,078,311,262,161,202)
180,807 34 (8,052,956,026,592,517)
185,714 35 (8,052,956,206,592,517)
222,640 36 (8,650,327,689,541,457)
225,114 37 (8,650,349,867,341,457)
226,926 38 (6,157,577,986,646,405)
274,632 39 (4,135,786,945,764,210)
314,875 40 (6,889,765,708,183,410)
16 318,242
324,777 41 (86,965,750,494,756,968)
325,772 42 (22,542,040,692,914,522)
506,383 43 (67,725,910,561,765,640)
17 523,467
The 43 rare numbers with up to 17 digits are:
1: 65
2: 621,770
3: 281,089,082
4: 2,022,652,202
5: 2,042,832,002
6: 868,591,084,757
7: 872,546,974,178
8: 872,568,754,178
9: 6,979,302,951,885
10: 20,313,693,904,202
11: 20,313,839,704,202
12: 20,331,657,922,202
13: 20,331,875,722,202
14: 20,333,875,702,202
15: 40,313,893,704,200
16: 40,351,893,720,200
17: 200,142,385,731,002
18: 204,238,494,066,002
19: 221,462,345,754,122
20: 244,062,891,224,042
21: 245,518,996,076,442
22: 248,359,494,187,442
23: 403,058,392,434,500
24: 441,054,594,034,340
25: 816,984,566,129,618
26: 2,078,311,262,161,202
27: 2,133,786,945,766,212
28: 2,135,568,943,984,212
29: 2,135,764,587,964,212
30: 2,135,786,765,764,212
31: 4,135,786,945,764,210
32: 6,157,577,986,646,405
33: 6,889,765,708,183,410
34: 8,052,956,026,592,517
35: 8,052,956,206,592,517
36: 8,191,154,686,620,818
37: 8,191,156,864,620,818
38: 8,191,376,864,400,818
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457
41: 22,542,040,692,914,522
42: 67,725,910,561,765,640
43: 86,965,750,494,756,968</pre>
I will revise this output when it completes the 19 digit run.
=={{header|F_Sharp|F#}}==
| |||