Count the number of Hamming distance sequences The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Let P be a binary string of length n and T be a binary string of length 2n-1.  We can compute the n Hamming distances between P and every n-length substring of T in order from left to right and put them into an array (or list).

Example Hamming distance sequence

Let P = 101 and T = 01100. The sequence of Hamming distances you get from this pair is 2,2,1.

Task

For increasing n starting at n=1, consider all possible pairs of binary strings P of length n and T of length 2n-1.  There are 2**(n+2n-1) such pairs and hence that many sequences of Hamming distances.  However many of those sequences will be identical . The task is to find how many are distinct for each n.

Your code should output one number per value of n.

Score

Your score is  the highest n your code reaches on my machine in 5 minutes.   The timing is for the total running time, not the time just for that n.

Who wins

The person with the highest score wins. If two or more people end up with the same score then it is the first answer that wins.

Example answers

For n from 1 to 8 the optimal answers are 2, 9, 48, 297, 2040, 15425, 125232, 1070553.

Languages and libraries

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

My Machine The timings will be run on my 64-bit machine. This is a standard ubuntu install with 8GB RAM, AMD FX-8350 Eight-Core Processor and Radeon HD 4250.  This also means I need to be able to run your code.

Leading answers


11 in C++ by feersum. 25 seconds.
11 in C++ by Andrew Epstein.  176 seconds.
10 in Javascript by Neil. 54 seconds.
9 in Haskell by nimi. 4 minutes and 59 seconds.
8 in Javascript by fəˈnɛtɪk. 10 seconds.
Haskell, score 9

import Data.Bits
import Data.List
import qualified Data.IntSet as S

main = mapM_ (print . S.size . S.fromList . hd) [1..9]

hd :: Int -&gt; [Int]
hd n = [foldl' (\s e-&gt;s*m+e) 0 [popCount $ xor p (shiftR t i .&amp;. m)|i&lt;-[(0::Int)..n-1]] | let m=2^n-1,p&lt;-[(0::Int)..2^n-1],t&lt;-[(0::Int)..2^(2*n-1)-1]]


Compile with -O3. It takes 6min35s on my 6 year old laptop hardware to run up to n=9, so maybe it's under 5min on the reference hardware. 

&gt; time ./113785
2
9
48
297
2040
15425
125232
1070553
9530752

real  6m35.763s
user  6m27.690s
sys   0m5.025s