Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.
9 Fixed error.
source | link

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

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

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.

8 added 8 characters in body
source | link

n≈10Python, 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, 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.

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

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

7 deleted 19 characters in body
source | link

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, 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. Consider the entry l[0]. The number of nonzero entries oflist has ll[0] iszeroes, 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, so 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.

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, 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. Consider the entry l[0]. The number of nonzero entries of l is n-l[0]. 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, 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.

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

6 added 77 characters in body
source | link
5 added 71 characters in body
source | link
4 added 54 characters in body
source | link
3 deleted 16 characters in body
source | link
2 deleted 17 characters in body
source | link
1
source | link