Count arrays that make unique sets This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals.

Consider an array A of length n. The array contains only positive integers.  For example A = (1,1,2,2).  Let us define f(A) as the set of sums of all the non-empty contiguous subarrays of A. In this case f(A) = {1,2,3,4,5,6}.  The steps to produce f(A)  are as follows:

The subarrays of A are (1), (1), (2), (2), (1,1), (1,2), (2,2), (1,1,2), (1,2,2), (1,1,2,2). Their respective sums are 1,1,2,2,2,3,4,4,5,6. The set you get from this list is therefore {1,2,3,4,5,6}.

We call an array A unique if there is no other array B of the same length such that f(A) = f(B), except for the array A reversed. As an example, f((1,2,3)) = f((3,2,1)) = {1,2,3,5,6} but there is no other array of length 3 that produces the same set of sums. 

We will only consider arrays where the elements are either a given integer s or s+1. E.g. if s=1 the arrays would only contain 1 and 2.

Task

The task, for a given n and s is to count the number of unique arrays of that length.  You can assume that s is between 1 and 9.

You should not count the reverse of an array as well as the array itself.

Examples

s = 1, the answer is always n+1.

s = 2, the answers counting from n = 1 up are: 

2,3,6,10,20,32,52,86


s = 8, the answers counting from n = 1 up are:

2,3,6,10,20,36,68,130


Score

For a given n, your code should output the answer for all values of s from 1 to 9. Your score is the highest value of n for which this completes in one minute.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

Leaderboard


n = 24 by Anders Kaseorg in Rust (34 seconds) 
n = 16 by Ourous in Clean (36 seconds)
n = 14 by JRowan in Common Lisp (49 seconds)
Rust, n ≈ 24

Requires nightly Rust for the convenient reverse_bits feature.  Compile with rustc -O unique.rs and run with (e.g.) ./unique 24.



#![feature(reverse_bits)]
use std::{collections::HashMap, env, mem, process};

type T = u32;
const BITS: u32 = mem::size_of::&lt;T&gt;() as u32 * 8;

fn main() {
    let args = env::args().collect::&lt;Vec&lt;_&gt;&gt;();
    assert!(args.len() == 2);
    let n: u32 = args[1].parse().unwrap();
    assert!(n &gt; 0);
    assert!(n &lt;= BITS);
    let mut unique = (2..=9).map(|_| HashMap::new()).collect::&lt;Vec&lt;_&gt;&gt;();
    let mut sums = vec![0 as T; n as usize];
    for a in 0 as T..=!0 &gt;&gt; (BITS - n) {
        if a &lt;= a.reverse_bits() &gt;&gt; (BITS - n) {
            for v in &amp;mut sums {
                *v = 0;
            }
            for i in 0..n {
                let mut bit = 1;
                for j in i..n {
                    bit &lt;&lt;= a &gt;&gt; j &amp; 1;
                    sums[(j - i) as usize] |= bit;
                }
            }
            for s in 2..=9 {
                let mut sums_s =
                    vec![0 as T; ((n + (n - 1) * s) / BITS + 1) as usize].into_boxed_slice();
                let mut pos = 0;
                let mut shift = 0;
                let mut lo = 0;
                let mut hi = 0;
                for &amp;v in &amp;sums {
                    lo |= v &lt;&lt; shift;
                    if BITS - shift &lt; n {
                        hi |= v &gt;&gt; (BITS - shift);
                    }
                    shift += s;
                    if shift &gt;= BITS {
                        shift -= BITS;
                        sums_s[pos] = lo;
                        pos += 1;
                        lo = hi;
                        hi = 0;
                    }
                }
                if lo != 0 || hi != 0 {
                    sums_s[pos] = lo;
                    pos += 1;
                    if hi != 0 {
                        sums_s[pos] = hi;
                    }
                }
                unique[s as usize - 2]
                    .entry(sums_s)
                    .and_modify(|u| *u = false)
                    .or_insert(true);
            }
        }
    }
    let mut counts = vec![n + 1];
    counts.extend(
        unique
            .iter()
            .map(|m| m.values().map(|&amp;u| u as T).sum::&lt;T&gt;())
            .collect::&lt;Vec&lt;_&gt;&gt;(),
    );
    println!("{:?}", counts);
    process::exit(0); // Avoid running destructors.
}