Count arrays of periods The period of a string is the shortest non-zero shift so that the string matches itself, ignoring any parts that overhang. So for example, abcabcab has period 3. By convention we say that if there is no such shift then a string has period equal to its length. So the period of abcde is 5 and the period of a is 1.  

In more formal terms, the period of a string S is the minimum i &gt; 0 so that S[1,n-i] == S[i+1,n] (indexing from 1).

For a given string S of power of two length, we will compute the period of all its prefixes of power of two length.  For example, consider S = abcabcab.  The periods we will compute are:

'a', 1
'ab', 2
'abca', 3
'abcabcab', 3


We will in fact just output the array of periods, that is [1, 2, 3, 3].

For a given  positive power of two n, consider all possible binary strings S.   Recall that a binary string is simply a string of 1s and 0s so there are exactly 2^n such strings (that is 2 to the power n). For each one we can compute this array of periods.  


  The challenge is to write code that takes n (a power of two)  as input and computes how many distinct such arrays there are.


The answers for n = 1, 2, 4, 8, 16, 32, 64, 128 are:

1, 2, 6, 32, 320, 6025, 216854, 15128807


The full set of distinct period arrays for n = 4 is:

1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4


Score

I will run your code on my computer running Ubuntu for 10 minutes. Your score is the largest n for which your code terminates in that time. In the case of a tie, the answer that completes the joint largest n fastest wins. In  the case that there is a tie within 1 second on timings, the first answer posted wins.

Languages and libraries

You can use any available language and libraries you like. Please include a full explanation for how to run/compile your code in Linux if at all possible.`

Your code should actually compute the answers and not, for example, just output precomputed values.

Leading entries


2 minutes and 21 seconds for n = 128 in C# by Peter Taylor
9 seconds for n = 32 in Rust by isaacg
C#, n=128 in about 2:40

using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q &lt;= 1 &lt;&lt; (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q &gt; 1 &lt;&lt; idx || p + q - Gcd(p, q) &gt; 1 &lt;&lt; idx &amp;&amp; UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a &gt; 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 &lt;&lt; idx);
            for (int i = 0; i &lt;= idx; i++)
            {
                for (int j = 0; j + periods[i] &lt; Math.Min(2 &lt;&lt; i, 1 &lt;&lt; idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary&lt;int, long&gt; rev = new Dictionary&lt;int, long&gt;();
            for (int k = 0; k &lt; 1 &lt;&lt; idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k &lt; 1 &lt;&lt; idx; k++) rev[union.Find(k)] |= 1L &lt;&lt; k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet&lt;int&gt; onesIndex = new HashSet&lt;int&gt;();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i &lt; idx; i++)
            {
                if (periods[i] == 2 &lt;&lt; i) onesIndex.Add((2 &lt;&lt; i) - 1);
            }
            for (int j = 0; j &lt; idx - 1 &amp;&amp; periods[j] == 2 &lt;&lt; j; j++)
            {
                for (int i = j + 1; i &lt; idx; i++)
                {
                    if (periods[i] == 2 &lt;&lt; i)
                    {
                        for (int k = (1 &lt;&lt; j) + 1; k &lt;= 2 &lt;&lt; j; k++) onesIndex.Add((2 &lt;&lt; i) - k);
                    }
                }
            }

            for (int i = 1; i &lt; idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 &lt;&lt; i) - periods[i];
                long dmask = (1L &lt;&lt; d) - 1;
                if (((zeroes &gt;&gt; 1) &amp; (zeroes &gt;&gt; periods[i]) &amp; dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes &amp; ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i &lt;= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L &lt;&lt; (1 &lt;&lt; i)) - 1;
                for (int j = numFilteredMasks; j &lt; masks.Length; j++)
                {
                    if ((masks[j] &amp; filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L &lt;&lt; numFilteredMasks) - 1 - M;
                M = (1L &lt;&lt; numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set &amp; -set;
                    long r = set + c;
                    set = (((r ^ set) &gt;&gt; 2) / c) | (r &amp; M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j &lt; masks.Length; j++, assignment &gt;&gt;= 1) ones |= masks[j] &amp; -(assignment &amp; 1);
            for (int i = idx - 1; i &gt; 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 &lt;&lt; i, periods[i - 1]) &lt; periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p &lt;= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L &lt;&lt; (n - p)) - 1L;
                if ((arr &amp; mask) == ((arr &gt;&gt; p) &amp; mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k &lt; size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 &lt; root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}


Extending to n=256 would require switching to BigInteger for the masks, which probably kills the performance too much for n=128 to pass without new ideas, let alone n=256.

Under Linux, compile with mono-csc and execute with mono.

Basic explanation

I'm not going to do a line-by-line dissection, just an overview of the concepts.

As a rule of thumb, I'm happy to iterate through on the order of 250 elements in a brute-force combinatoric program. To get to n=128 it is therefore necessary to use an approach which doesn't analyse every bitstring. So rather than working forwards from bit strings to period sequences, I work backwards: given a period sequence, is there a bitstring which realises it? For n=2x there's an easy upper bound of 2x(x+1)/2 period sequences (vs 22x bitstrings).

Some of the arguments use the string periodicity lemma:


  Let p and q be two periods of a string of length n. If p + q &le; n + gcd(p, q) then gcd(p, q) is also a period of the string.


Wlog I will assume that all of the bitstrings under consideration start with 0.

Given a period sequence [p1 p2 ... pk] where pi is the period of the prefix of length 2i (p0 = 1 always), there are some easy observations about possible values of pk+1:


pk+1 &ge; pk since a period of a string S is also a period of any prefix of S.
pk+1 = pk is always a possible extension: just repeat the same primitive string for twice as many characters.
2k &lt; pk+1 &le; 2k+1 is always a possible extension. It suffices to show this for pk+1 = 2k+1 because an aperiodic string of length L can be extended to an aperiodic string of length L+1 by appending any letter which isn't its first letter.

Take a string Sx of length 2k whose period is pk and consider the string SxyS of length 2k+1. Clearly SxyS has a period 2k+1. Suppose its period q is smaller.

Then 2k+1 + q &le; 2k+1+1 &le; 2k+1 + gcd(2k+1, q) so by the periodicity lemma gcd(2k+1, q) is also a period of SxyS, and since the greatest divisor is less than or equal to its arguments and q is the smallest period, we require q to be a proper factor of 2k+1. Since its quotient cannot be 2, we have q &le; (2k+1)/3.

Now, since q &le; 2k is a period of SxyS it must be a period of Sx. But the period of Sx is pk. We have two cases:


gcd(pk, q) = pk, or equivalently pk divides exactly into q. 
pk + q &gt; 2k + gcd(pk, q) so that the periodicity lemma doesn't force a smaller period.


Consider first the second case. pk &gt; 2k + gcd(pk, q) - q &ge; 2k+1 - q &ge; 2k+1 - (2k+1)/3 &ge; 2q, contradicting the definition of pk as the period of Sx. Therefore we are forced into the conclusion that pk is a factor of q.

But since q is a period of Sx and pk is the period of Sx, the prefix of length q is just q/pk copies of the prefix of length pk, so we see that pk is also a period of SxyS.

Therefore the period of SxyS is either pk or 2k+1. But we have two options for y! At most one choice of y will give period pk, so at least one will give period 2k+1. QED.
The periodicity lemma allows us to reject some of the remaining possible extensions.
Any extension which hasn't passed a quick-accept or a quick-reject test needs to be tested constructively.


The construction of a bitstring given a period sequence is essentially a satisifiability problem, but it has a lot of structure. There are 2k - pk simple equality constraints implied by each prefix period, so I use a union set data structure to combine bits into independent clusters. This was enough to tackle n=64, but for n=128 it was necessary to go further. I employ two useful lines of argument:


If the prefix of length M is 01M-1 and the prefix of length L &gt; M has period L then the prefix of length L must end in 1M. This is most powerful precisely in the cases which would otherwise have most independent clusters, which is convenient.
If the prefix of length M is 0M and the prefix of length L &gt; M has period L - d with d &lt; M and ends in 0d then it must in fact end in 10d. This is most powerful at the opposite extreme, when the period sequence starts with a lot of ones.


If we don't get an immediate contradiction by forcing the cluster with the first bit (assumed to be zero) to be one then we brute force (with some micro-optimisations) over the possible values for the unforced clusters. Note that the order is in descending number of ones because if the ith bit is a one then the period cannot be i and we want to avoid periods which are shorter than the ones which are already enforced by the clustering. Going down increases the chances of finding a valid assignment early.