Definitions and restrictions

Rare   numbers are positive integers    n    where:

    n    is expressed in base ten
    r    is the reverse of    n      (decimal digits)
    n    must be non-palindromic   (n ≠ r)
    (n+r)    is the   sum
    (n-r)    is the   difference   and must be positive
   the   sum   and the   difference   must be perfect squares


Task

   find and show the first   5   rare   numbers
   find and show the first   8   rare   numbers       (optional)
   find and show more   rare   numbers                (stretch goal)


Show all output here, on this page.



References

   an   OEIS   entry:   A035519          rare numbers.
   an   OEIS   entry:   A059755   odd rare numbers.
   planetmath entry:   rare numbers.     (some hints)
   author's  website:   rare numbers   by Shyam Sunder Gupta.     (lots of hints and some observations).


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(); }
}