Magic Sequences

This is a very popular constraint programming problem.

However, I like the following theorem from xnor on codegolf ):

---

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, 3: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.