The task is to compute OEIS A005434 as quickly as possible.
Consider a binary string
S of length
n. Indexing from
1, we can determine if
S[n-i..n] exactly for all
i in order from
n-1. For example,
S = 01010
[Y, N, Y, N, Y].
This is because
01 does not match
0101 does not match
1010 and finally
01010 matches itself.
f(n) to be the number of distinct arrays of
Ns one gets when iterating over all
2^n different possible bit strings
S of length
The observant will notice this question is a simpler variant of another recent question of mine. However, I expect that clever tricks can make this much faster and easier.
n starting at
1, your code should output
n = 1..24, the correct answers are:
1, 2, 3, 4, 6, 8, 10, 13, 17, 21, 27, 30, 37, 47, 57, 62, 75, 87, 102, 116, 135, 155, 180, 194
Your code should iterate up from
n = 1 giving the answer for each
n in turn. I will time the entire run, killing it after two minutes.
Your score is the highest
n you get to in that time.
In the case of a tie, the first answer wins.
Where will my code be tested?
I will run your code under Virtualbox in a Lubuntu guest VM (on my Windows 7 host).
My laptop has 8GB of RAM and an Intel i7 5600U@2.6 GHz (Broadwell) CPU with 2 cores and 4 threads. The instruction set includes SSE4.2, AVX, AVX2, FMA3 and TSX.
Leading entries per language
- n = 599 in Rust bu Anders Kaseorg.
- n= 30 in C by Grimy. Parallel version gets to 32 when run natively in cygwin.