Magic Sequences of length n

Question

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

Answer 1

Python, n≈10⁸

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>=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>=7

So, for n>=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>=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]>=3, and so l[l[0]]=1. Now, there's at least one 1, which means l[1]>=1, but if l[1]==1 that's another 1, so l[1]>=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.

Answer 2

Python 3, n≈40

def plausible_suffix(l,N):
    if sum(l)>N:
        return False

    pairs = [(N-1-i,l[i]) for i in range(len(l))]

    if sum(i*x for i,x in pairs)>N:
        return False

    num_remaining = N - len(l)

    for index, desired_count in pairs:
        count = l.count(index)
        more_needed = desired_count - count
        if more_needed<0: 
            return False
        num_remaining -= more_needed
        if num_remaining<0:
            return False
    return True

plausible_func = plausible_suffix

def generate_magic(N):
    l=[0]
    while l:
        extend = False
        if plausible_func(l,N):
            if len(l)==N:
                yield l[::-1]
            else:
                extend = True
        if extend:
            l.append(0)
        else:
            while l[-1]>=N-2:
                l.pop(-1)
                if not l:raise StopIteration
            l[-1]+=1

n=40 #test parameter

if n>0:
    for x in generate_magic(n):
        print(n,x)

Does a breadth-first search of possible lists, filling in entries from right to left, stopping the search at a suffix if it isn't plausible, which can happen if:

• The sum of the entries in the suffix exceeds n (the sum for the whole list must be n)
• The weighted sum of i*l[i] in the suffix exceeds n (the sum for the whole list must be n)
• Any number appears in the suffix more times that the suffix says it should
• The number of remaining unfilled spots is too small to account for all numbers that need to appear more times.

I had original tested prefixes left to right, but that went more slowly.

The outputs up to n=30 are:

4 [1, 2, 1, 0]
4 [2, 0, 2, 0]
5 [2, 1, 2, 0, 0]
7 [3, 2, 1, 1, 0, 0, 0]
8 [4, 2, 1, 0, 1, 0, 0, 0]
9 [5, 2, 1, 0, 0, 1, 0, 0, 0]
10 [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
11 [7, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0]
12 [8, 2, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0]
13 [9, 2, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
14 [10, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
15 [11, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
16 [12, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
17 [13, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
18 [14, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
19 [15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
20 [16, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
21 [17, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
22 [18, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
23 [19, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
24 [20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
25 [21, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
26 [22, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
27 [23, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
28 [24, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
29 [25, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
30 [26, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]

Except for the first three lists [1, 2, 1, 0], [2, 0, 2, 0], [2, 1, 2, 0, 0], there is exactly one list of each length n>6, and it has the form [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]. This pattern persists up to at least n=50. I suspect it holds forever, in which case it's trivial to output a huge number of these. Even if not, a mathematical understanding on the possible solutions would greatly speed up a search.

Answer 3

Pyth - 15 bytes

Uses brute force by all possible sequences of len n and then filters.

f.A.eq/TkYT^UQQ

Full explanation coming soon.

Try it here online.

Answer 4

K, 26 bytes

{f@&{x~(+/x=)'!#x}'f:!x#x}

Like Maltysen's approach, brute force. The heart of the program is a predicate which tests whether a given vector is "magic":

{x~(+/x=)'!#x}

Build an iota vector as long as the input vector (!#x), count the occurrences of each digit ((+/x=)') and compare the result with the input vector (x~). If there's a match, you have a magic sequence.

Unfortunately, this first stab seems to be pretty slow. Testing using Kona on my laptop it takes about 12 seconds to handle n=7. I need to give this a bit more thought.