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
5 and the period of
In more formal terms, the period of a string
S is the minimum
i > 0 so that
S[1,n-i] == S[i+1,n] (indexing from
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
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
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.
- 2 minutes and 21 seconds for n = 128 in C# by Peter Taylor
- 9 seconds for n = 32 in Rust by isaacg