10
1
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[1..i+1]
matches S[n-i..n]
exactly for all i
in order from 0
to n-1
. For example,
S = 01010
gives
[Y, N, Y, N, Y].
This is because 0
matches 0
, 01
does not match 10
, 010
matches 010
, 0101
does not match 1010
and finally 01010
matches itself.
Define f(n)
to be the number of distinct arrays of Y
s and N
s one gets when iterating over all 2^n
different possible bit strings S
of length n
.
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.
Task
For increasing n
starting at 1
, your code should output n, f(n)
.
Example answers
For 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
Scoring
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.
https://www.math.uni-bielefeld.de/~sillke/SEQUENCES/autocorrelation-range.c (linked from the OEIS page) run with -O3 can calculate up to 100 in <.02 seconds on my machine – vroomfondel – 2017-06-16T15:08:55.327
@rogaos Oh dear. I should delete the question but it already has an answer. – None – 2017-06-16T15:10:19.467
I think it's still a cool problem – but maybe up to 1000 instead? Or ask answers to golf a sufficiently fast program – vroomfondel – 2017-06-16T15:11:34.107
1@rogaos I just removed the hard limit completely. – None – 2017-06-16T15:19:23.530