6 added 513 characters in body
source | link
using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11;13; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];

            // Symmetry exclusion: perm[0] < (n+1) / 2
            if (n > 1) excluded[0] = (1 << n) - (1 << ((n + 1) / 2));

            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            int n = perm.Length;
            if (off == perm.Lengthn)
            {
                count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length;n; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Lengthn - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1] < n - 1 - perm[0]
                if (off == 0 && perm.Lengthn > 1)
                {
                    nextExcluded[perm.LengthnextExcluded[n - 1] |= (1 << n) - (2 << (n - 1 - val));
                    nextExcluded[n - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;

            int cmp = 0;
            for (int i = 0, j = perm.Length - 1; i <= j; i++, j--)
            {
                cmp = perm.Length - 1 - perm[i] - perm[j];
                if (cmp != 0) break;
            }

            return 2;cmp > 0 ? 4 : cmp == 0 ? 2 : 0;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 21.12 seconds, and n=10 in 2413.46 seconds. n=11 is just over 42 minutes.

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1]
                if (off == 0 && perm.Length > 1)
                {
                    nextExcluded[perm.Length - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;
            return 2;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 2.1 seconds, and n=10 in 24.4 seconds. n=11 is just over 4 minutes.

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 13; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];

            // Symmetry exclusion: perm[0] < (n+1) / 2
            if (n > 1) excluded[0] = (1 << n) - (1 << ((n + 1) / 2));

            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            int n = perm.Length;
            if (off == n)
            {
                count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < n; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < n - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1] < n - 1 - perm[0]
                if (off == 0 && n > 1)
                {
                    nextExcluded[n - 1] |= (1 << n) - (2 << (n - 1 - val));
                    nextExcluded[n - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;

            int cmp = 0;
            for (int i = 0, j = perm.Length - 1; i <= j; i++, j--)
            {
                cmp = perm.Length - 1 - perm[i] - perm[j];
                if (cmp != 0) break;
            }

            return cmp > 0 ? 4 : cmp == 0 ? 2 : 0;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 1.2 seconds, and n=10 in 13.6 seconds. n=11 is just over 2 minutes.

5 First symmetry is simple enough
source | link
using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count++;count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1]
                if (off == 0 && perm.Length > 1)
                {
                    nextExcluded[perm.Length - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;
            return 2;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 32.31 seconds, and n=10 in 3824.04 seconds. n=11 is just over 4 minutes.

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count++;
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 3.3 seconds, and n=10 in 38.0 seconds.

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count += CountSymmetries(perm);
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                // Symmetry exclusion: perm[0] < perm[-1]
                if (off == 0 && perm.Length > 1)
                {
                    nextExcluded[perm.Length - 1] |= (2 << val) - 1;
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        private static int CountSymmetries(int[] perm)
        {
            if (perm.Length < 2) return 1;
            return 2;
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 2.1 seconds, and n=10 in 24.4 seconds. n=11 is just over 4 minutes.

4 deleted 33 characters in body
source | link
using System;
using System.Collections.Generic;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count++;
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    intvar maxpoints = 1new <<Point[off off;
+ 1];
                   for (intvar subsetdenoms = 1; subset < max; subset++)
                 new BigInteger[off + {1];
                       points[0] //= subsetnew givesPoint us{ dataX points= (x_soff, y_s)
                        var pointsY = newperm[off] List<Point>()};
                        var tmpdenoms[0] = subset | max;1;
                        for ExtendExclusions(int i = 0; tmp > 0; i++perm, tmp >>= 1)
                        {
                            if ((tmp & 1) ==off, 1)0, points.Add(new Point { X = i, Y =1, perm[i]denoms, }nextExcluded);
                        }

                        // Barycentric Lagrange interpolation
                        Rational[] weights = new Rational[points.Count];
                        for (int s = 0; s < points.Count; s++)
                        {
                            BigInteger denominator = 1;
                            for (int t = 0; t < points.Count; t++)
                            {
                                if CountValidPerms(t == s) continue;
                                denominator *= points[s].X - points[t].X;
                            }
                         ref count, perm, weights[s]off =+ new1, Rational(points[s].YnextUnused, denominatornextExcluded);
                }
        }

              private static void ExtendExclusions(int[] perm, int off, int idx, Point[] forpoints, (int target = off +numPoints, 1;BigInteger[] targetdenoms, <int[] excluded.Length; target++)
                        {
                            BigInteger prod = 1;
                            forif (int t = 0; t <idx points.Count;== t++off) prod *= target - points[t].X;return;

                            Rational sum = new// Rational(0,Subsets 1);without
                            for ExtendExclusions(int sperm, =off, 0;idx s+ <1, points.Count; s++) sum += new Rational(prod / (target - points[s].X), *numPoints, weights[s].Numdenoms, weights[s].Denomexcluded);

            // Just add this to the subset
          if  points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (sumBigInteger[])denoms.DenomClone();
 == 1 && sum.Num >= 0 && sum    // Update invariant: denoms[s] = prod_{t != s} points[s].NumX <- permpoints[t].Length)X
 nextExcluded[target] |= 1 <<        denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)sum.Num;
            {
              }  denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - }points[s].X;
            }
    }        numPoints++;

            for (int target = CountValidPermsoff + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (refint count,t perm,= off0; +t 1< numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, nextUnused1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, nextExcludeddenoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 43.03 seconds, and n=10 in 4738.70 seconds.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count++;
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1)
                {
                    int max = 1 << off;
                    for (int subset = 1; subset < max; subset++)
                    {
                        // subset gives us data points (x_s, y_s)
                        var points = new List<Point>();
                        var tmp = subset | max;
                        for (int i = 0; tmp > 0; i++, tmp >>= 1)
                        {
                            if ((tmp & 1) == 1) points.Add(new Point { X = i, Y = perm[i] });
                        }

                        // Barycentric Lagrange interpolation
                        Rational[] weights = new Rational[points.Count];
                        for (int s = 0; s < points.Count; s++)
                        {
                            BigInteger denominator = 1;
                            for (int t = 0; t < points.Count; t++)
                            {
                                if (t == s) continue;
                                denominator *= points[s].X - points[t].X;
                            }
                            weights[s] = new Rational(points[s].Y, denominator);
                        }

                        for (int target = off + 1; target < excluded.Length; target++)
                        {
                            BigInteger prod = 1;
                            for (int t = 0; t < points.Count; t++) prod *= target - points[t].X;

                            Rational sum = new Rational(0, 1);
                            for (int s = 0; s < points.Count; s++) sum += new Rational(prod / (target - points[s].X) * weights[s].Num, weights[s].Denom);

                            if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < perm.Length) nextExcluded[target] |= 1 << (int)sum.Num;
                        }
                    }
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 4.0 seconds, and n=10 in 47.7 seconds.

using System;
using System.Diagnostics;
using BigInteger = System.Int32;

namespace Sandbox
{
    class PPCG160382
    {
        public static void Main(params string[] args)
        {
            if (args.Length != 0)
            {
                foreach (var arg in args) Console.WriteLine(CountValidPerms(int.Parse(arg)));
            }
            else
            {
                int[] smallValues = new int[] { 1, 1, 2, 4, 18, 48 };
                for (int n = 0; n < smallValues.Length; n++)
                {
                    var observed = CountValidPerms(n);
                    var expected = smallValues[n];
                    Console.WriteLine(observed == expected ? $"{n}: Ok" : $"{n}: expected {expected}, observed {observed}, error {observed - expected}");
                }
                for (int n = smallValues.Length; n < 11; n++)
                {
                    Stopwatch sw = new Stopwatch();
                    sw.Start();
                    Console.WriteLine($"{n}: {CountValidPerms(n)} in {sw.ElapsedMilliseconds}ms");
                }
            }
        }

        private static long CountValidPerms(int n)
        {
            // We work on the basis of exclusion by extrapolation.
            var unused = (1 << n) - 1;
            var excluded = new int[n];
            int[] perm = new int[n];
            long count = 0;
            CountValidPerms(ref count, perm, 0, unused, excluded);
            return count;
        }

        private static void CountValidPerms(ref long count, int[] perm, int off, int unused, int[] excluded)
        {
            if (off == perm.Length)
            {
                count++;
                return;
            }

            // Quick-aborts
            var completelyExcluded = excluded[off];
            for (int i = off + 1; i < excluded.Length; i++)
            {
                if ((unused & ~excluded[i]) == 0) return;
                completelyExcluded &= excluded[i];
            }
            if ((unused & completelyExcluded) != 0) return;

            // Consider each unused non-excluded value as a candidate for perm[off]
            var candidates = unused & ~excluded[off];
            for (int val = 0; candidates > 0; val++, candidates >>= 1)
            {
                if ((candidates & 1) == 0) continue;

                perm[off] = val;

                var nextUnused = unused & ~(1 << val);

                var nextExcluded = (int[])excluded.Clone();
                // For each (non-trivial) subset of smaller indices, combine with off and extrapolate to off+1 ... excluded.Length-1
                if (off < excluded.Length - 1 && off > 0)
                {
                    var points = new Point[off + 1];
                    var denoms = new BigInteger[off + 1];
                    points[0] = new Point { X = off, Y = perm[off] };
                    denoms[0] = 1;
                    ExtendExclusions(perm, off, 0, points, 1, denoms, nextExcluded);
                }

                CountValidPerms(ref count, perm, off + 1, nextUnused, nextExcluded);
            }
        }

        private static void ExtendExclusions(int[] perm, int off, int idx, Point[] points, int numPoints, BigInteger[] denoms, int[] excluded)
        {
            if (idx == off) return;

            // Subsets without
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);

            // Just add this to the subset
            points[numPoints] = new Point { X = idx, Y = perm[idx] };
            denoms = (BigInteger[])denoms.Clone();
            // Update invariant: denoms[s] = prod_{t != s} points[s].X - points[t].X
            denoms[numPoints] = 1;
            for (int s = 0; s < numPoints; s++)
            {
                denoms[s] *= points[s].X - points[numPoints].X;
                denoms[numPoints] *= points[numPoints].X - points[s].X;
            }
            numPoints++;

            for (int target = off + 1; target < excluded.Length; target++)
            {
                BigInteger prod = 1;
                for (int t = 0; t < numPoints; t++) prod *= target - points[t].X;

                Rational sum = new Rational(0, 1);
                for (int s = 0; s < numPoints; s++) sum += new Rational(prod / (target - points[s].X) * points[s].Y, denoms[s]);

                if (sum.Denom == 1 && sum.Num >= 0 && sum.Num < excluded.Length) excluded[target] |= 1 << (int)sum.Num;
            }

            // Subsets with
            ExtendExclusions(perm, off, idx + 1, points, numPoints, denoms, excluded);
        }

        public struct Point
        {
            public int X;
            public int Y;
        }

        public struct Rational
        {
            public Rational(BigInteger num, BigInteger denom)
            {
                if (denom == 0) throw new ArgumentOutOfRangeException(nameof(denom));

                if (denom < 0) { num = -num; denom = -denom; }

                var g = _Gcd(num, denom);
                Num = num / g;
                Denom = denom / g;
            }

            private static BigInteger _Gcd(BigInteger a, BigInteger b)
            {
                if (a < 0) a = -a;
                if (b < 0) b = -b;
                while (a != 0)
                {
                    var tmp = b % a;
                    b = a;
                    a = tmp;
                }
                return b;
            }

            public BigInteger Num;
            public BigInteger Denom;

            public static Rational operator +(Rational a, Rational b) => new Rational(a.Num * b.Denom + a.Denom * b.Num, a.Denom * b.Denom);
        }
    }
}

Takes values of n as command-line arguments, or if run without arguments times itself up to n=10. Compiling as "Release" in VS 2017 and running on an Intel Core i7-6700 I calculate n=9 in 3.3 seconds, and n=10 in 38.0 seconds.

3 deleted 174 characters in body
source | link
2 Minor speed-up
source | link
1
source | link