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

• Welcome to PPCG! This is a great challenge, but you need a winning criterion. For example, you could say that the winner is the shortest program. – Ypnypn May 14 '15 at 0:12
• Relevant: Self-descriptive number – Sp3000 May 14 '15 at 0:23
• Please don't change the winning criterion after answers have been posted. Also, this was much better as a code golf than as fastest code, at least in my opinion. – Alex A. May 14 '15 at 0:55
• @xnor you can start by generating the integer partitions of n and checking if they can be self-descriptive. – Martin Ender May 14 '15 at 1:36
• What's the smallest n>5 with a solution not of the form [n-4, 2, 1, ..., 0, 0, 1, 0, 0, 0]? I've looked up to n=20 and not found one, and wondering if I'm making an error. – xnor May 14 '15 at 2:43

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

• And the language is ...? – edc65 May 14 '15 at 7:55
• @edc65 It looks like python. But I'm not sure. – Ismael Miguel May 14 '15 at 8:10

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.

• @Ypnypn I've special-cased n=0. I'd missed that we're returning the result for a single n, not counting up n's. This gets me up to n=40. – xnor May 14 '15 at 4:17

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.

• FYI, the OP changed the winning criterion to fastest code. – Alex A. May 14 '15 at 0:55
• Regardless of the winning criterion, here's a 3 byte golf:  fqm/TdQT^UQQ – Jakube May 14 '15 at 7:11

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.