Magic Sequences of length n A magic sequence is a sequence of non-negative integers x[0..n-1] such that there are exactly x[i] instances of i

For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence since there are 6 0's, 2 1’s, and so on.

Write a function which when given n, outputs all magic sequences of length n



The program that can produce the correct output for the highest value of n within 10 seconds win. (All programs are welcome, though)

For example, Alice's program can deal with upto n=15 within 10 seconds while Bob's can deal with upto n=20 within the same time. Bob wins.

Platform: Linux 2.7GHz @ 4 CPUs
Python, n≈108

def magic_sequences(n):
    if n==4:
        return (1, 2, 1, 0),(2, 0, 2, 0) 
    elif n==5:
        return (2, 1, 2, 0, 0),
    elif n&gt;=7:
        return (n-4,2,1)+(0,)*(n-7)+(1,0,0,0),
    else:
        return ()


This uses the fact, which I'll prove, that the only Magic sequences of length n are:


[1, 2, 1, 0] and  [2, 0, 2, 0] for n=4
[2, 1, 2, 0, 0] for n=5
[n-4, 2, 1, 0, 0, ..., 0, 0, 1, 0, 0, 0] for n&gt;=7


So, for n&gt;=7, one only needs to return a huge tuple. I can do this for up to roughly n=10^8 on my laptop, which is likely limited by memory; any more and it freezes up. (Thanks to trichoplax for the idea of using tuples rather than lists.) Or, if one can instead print a dictionary of nonzero entries, {0:n-4, 1:2, 2:1, (n-4):1}, one can do this for ginormous n.

I prove the uniqueness for n&gt;=7; the other ones can be checked by brute force or casework.

The sum of the entries of l is the total count of all numbers of the list, which is its length n. The list has l[0] zeroes, and so n-l[0] nonzero entries. But by definition l[0] must be nonzero or we get a contradiction, and each of the other nonzero entries is at least 1. This already accounts for a sum of l[0] + (n-l[0]-1)*1 = n-1 out of the overall sum of n. So not counting l[0], there can be at most one 2 and no entry bigger than 2. 

But that means the only nonzero entries are l[0], l[1], l[2], and l[l[0]], whose values are at most l[0] and a permutation of 1,1,2, which gives a maximum sum of l[0]+4. Since this sum is n, which is at least 7, we have l[0]&gt;=3, and so l[l[0]]=1. Now, there's at least one 1, which means l[1]&gt;=1, but if l[1]==1 that's another 1, so l[1]&gt;=2, which implies l[1] is the lone 2. This gives l[2]=1, and all the remaining entries are 0, so l[0]=n-4, which completes the solution.