How on earth did llhuii output the Evil Numbers in 42 bytes of Python?

Question

This is a tips question for golfing in Python concerning the Evil Numbers question on Anarchy Golf.

An number is evil if its binary expansion has an even number of 1's. The challenge is to print the first 400 evil numbers 0,3,5,...,795,797,798, one per line.

The Python 2 submissions are led by llhuii with a 42-byte solution. The next best is 46 bytes by mitchs, followed by five 47-byte submissions. It seems llhuii has found something truly magical that has eluded many strong Python golfers for over 2 years. Saving 4 or 5 bytes is huge for such a short golf.

I'm still at 47 bytes. I'm hoping we can crack this puzzle as a community. If we get an answer jointly, I'd submit it under the names of everyone who contributed. An answer to this question can be a piece of code or a new idea or a piece of analysis. If you are llhuii, please don't spoil it for us yet.

Though submissions are not revealed because this problem is Endless, we're given some leads. The winning submission took 0.1699 seconds to run, much longer than any other, suggesting an inefficient method. From the byte statistics, of the 42 characters, 23 are alphanumeric [0-9A-Za-z] and 19 are ASCII symbols. This means there is no whitespace in llhuii's solution.

You can test your code on the problem page, choosing Python from the language dropdown or uploading a .py file. Note that:

• Python 2.7 is used
• Your code must be a full program that prints
• There's no input for this problem, like kolmogorov-complexity
• Your program just has to print the 400 values as given, even if it would break on larger values
• Programs have 2 seconds to run
• Programs may terminate with error
• You may use exec; the "exec is denied" refers to shell exec

Answer 1

This isn't the same solution as llhuii's, but it's also 42 bytes long.

n=0;exec'print n;n^=(n^n+2)%3/2;n+=2;'*400

Try it online!

Thanks to @JonathanFrech, we're now at 40 bytes.

n=0;exec'print n;n=n+2^(n^n+2)/2%3;'*400

Try it online!

There's another byte to be saved, for a total of 39.

n=0;exec'print n;n=n+2^-(n^n+2)%3;'*400

Try it online!

Answer 2

Getting 39 bytes

This is an explanation of how I got a 39-byte solution, which Dennis and JonathanFrech found separately as well. Or, rather, it explains how one could arrive at the answer in hindsight, in a way that's much nicer than my actual path to it, which was full of muddy reasoning and dead ends.

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

Writing this a bit less golfed and with more parens, this looks like:

n=0
for _ in range(400):
  print n
  n=(n+2)^(-((n+2)^n))%3

Bit parities

We start with an idea from my 47-byte solution to output all numbers of the form n=2*k+b where k counts up 0,1,...,399 and b is a parity bit that makes the overall number of 1's even.

Let's write par(x) for the bit parity of x, that is the xor (^) all of bits in x. This is 0 if there's an even number of 1-bits (number is evil), and 1 if there's an odd number of 1-bits. For n=2*k+b, we have par(n) = par(k)^b, so to achieve evil par(n)==0 we need b=par(k), i.e. the last bit of n to be the bit parity of the preceding bits.

My first efforts at golfing were on expressing the par(k), at first directly with bin(k).count('1')%2, and then with bit manipulation.

Parity updates

Still, there didn't seem to be a short expression. Instead, it helped to realize that there's more info to work with. Rather than just computing the bit parity of the current number,

k  ---->  par(k)

we can update the bit parity as we increment k to k+1.

k   ---->  par(k)
      |
      v
k+1 ---->  par(k+1)

That is, since we're counting up k=0,1,2,..., we merely need to maintain the current bit parity rather than calculating it from scratch each time. The bit parity update par(k+1)^par(k) is the parity of the number of bits flipped in going from k to k+1, that is par((k+1)^k).

par(k+1) ^ par(k) = par((k+1)^k)
par(k+1) = par(k) ^ par((k+1)^k)

Form of (k+1)^k

Now we need to compute par((k+1)^k). It might seem like we've gotten nowhere because computing bit parity is exactly the problem we're trying to solve. But, numbers expressed as (k+1)^k have the form 1,3,7,15,.., that is one below a power of 2, a fact often used in bit hacks. Let's see why that is.

When we increment k, the effect of the binary carries is to invert the last 0 and all 1's to its right, creating a new leading 0 if there were none. For example, take k=43=0b101011

      **
  101011  (43)
 +     1
  ------
= 101100  (44)

  101011  (43)
 ^101100  (44)
  ------
= 000111  (77)   

The columns causing a carry are marked with *. These have a 1 change to a 0 and pass on a carry bit of 1, which keeps propagating left until it hits a 0 in k, which changes to 1. Any bits further to the left are unaffected. So, when k^(k+1) checks which bit positions change k to k+1, it finds the positions of the rightmost 0 and the 1's to its right. That is, the changed bits form a suffix, so result is 0's followed by one or more 1's. Without the leading zeroes, there are binary numbers 1, 11, 111, 1111, ... that are one below a power of 2.

Computing par((k+1)^k)

Now that we understand that (k+1)^k is limited to 1,3,7,15,..., let's find a way to compute the bit parity of such numbers. Here, a useful fact is that 1,2,4,8,16,... alternate modulo 3 between 1 and 2, since 2==-1 mod 3 . So, taking 1,3,7,15,31,63... modulo 3 gives 1,0,1,0,1,0..., which are exactly their bit parities. Perfect!

So, we can do the update par(k+1) = par(k) ^ par((k+1)^k) as

par(k+1) = par(k) ^ ((k+1)^k)%3

Using b as the variable we're storing the parity in, this looks like

b^=((k+1)^k)%3

Writing the code

Putting this together in code, we start k and the parity bit b both at 0, then repeatedly print n=2*k+b and update b=b^((k+1)^k)%3 and k=k+1.

46 bytes

k=b=0
exec"print 2*k+b;b^=(k+1^k)%3;k+=1;"*400

Try it online!

We removed parens around k+1 in ((k+1)^k)%3 because Python precedence does the addition first anyway, weird as it looks.

Code improvements

We can do better though by working directly with a single variable n=2*k+b and performing the updates directly on it. Doing k+=1 corresponds to n+=2. And, updating b^=(k+1^k)%3 corresponds to n^=(k+1^k)%3. Here, k=n/2 before updating n.

44 bytes

n=0
exec"print n;n^=(n/2+1^n/2)%3;n+=2;"*400

Try it online!

We can shorten n/2+1^n/2 (remember this is (n/2+1)^n/2) by rewriting

n/2+1 ^ n/2
(n+2)/2 ^ n/2
(n+2 ^ n)/2    

Since /2 removes the last bit, it doesn't matter if we do it before or after xor-ing. So, we have n^=(n+2^n)/2%3. We can save another byte by noting that modulo 3, /2 is equivalent to *2 is equivalent to -, noting that n+2^n is even so the division is actual halving without flooring. This gives n^=-(n+2^n)%3

41 bytes

n=0
exec"print n;n^=-(n+2^n)%3;n+=2;"*400

Try it online!

Finally, we can combine the operations n^=c;n+=2 into n=(n+2)^c, where c is a bit. This works because ^c acts only on the last bit and +2 doesn't care about the last bit, so the operations commute. Again, precedence lets us omit parens and write n=n+2^c.

39 bytes

n=0
exec"print n;n=n+2^-(n+2^n)%3;"*400

Try it online!

Answer 3

This gives my (xnor's) 47-byte solution and the thinking that led me to it. Don't read this if you want to figure this out yourself.

A natural first idea is to iterate through the numbers 0 to 799, printing only those with an even number of 1's in binary.

52 bytes

for n in range(800):
 if~bin(n).count('1')%2:print n

Try it online!

Here, the ~ takes the bit complement so as to switch even<->odd in the count and give a truthy value only on even counts.

We can improve this method by generating all the values instead of filtering. Observe that the output values are the numbers 0 to 399, each with a bit appended to make the number of 1 bits even.

0 = 2*0 + 0
3 = 2*1 + 1
5 = 2*2 + 1
6 = 2*3 + 0
...

So, the nth number is either 2*n+b with either b=0 or b=1. The bit b can be found by counting 1's in the bits of n and taking the count modulo 2.

49 bytes

for n in range(400):print 2*n+bin(n).count('1')%2

Try it online!

We can cut the 2 bytes for 2* by iterating over 0,2,4,..., which doesn't chance the count of 1's. We can do this by using an exec loop that runs 400 times and increasing n by 2 each loop.

47 bytes

n=0;exec"print n+bin(n).count('1')%2;n+=2;"*400

Try it online!

And, that's my 47-byte solution. I suspect most if not all the other 47-byte solutions are the same.

Answer 4

llhuii’s Python 3 submission

Here are the Python 3 submissions for Evil Numbers at the time of writing:

llhuii probably ported their trick to Python 3, and came up with a solution that is

• 3 bytes longer than their Python 2 solution, and
• has 45 − (25 + 18) = 2 bytes of whitespace.

Porting xnor’s 47B to Python 3 literally, we get this 50B:

n=0;exec("print(n+bin(n).count('1')%2);n+=2;"*400)

I submitted it as ppcg(xnor). (It adds parentheses to exec and print, which are now functions.) It has different code stats from the other Python 3 answers, which all have some amount of whitespace in them. Interesting!

There’s a shorter way to rewrite it though (exec tends to lose its competitive edge in Python 3):

n=0
while n<800:print(n+bin(n).count('1')%2);n+=2

It’s 49 bytes. I submitted it as ppcg(xnor,alternative). This has two bytes of whitespace, just like llhui’s answer! This leads me to believe that llhuii’s Python 3 answer looks kinda like this (newline, then a while loop.) So llhuii probably used exec in Python 2 and while in Python 3, just like us; this explains the whitespace discrepancy.

---

Our 47B became a 49B in Python 3. What’s interesting, now, is that llhuii’s 42B didn’t become a 44B, it became a 45B! Something about llhuii’s solution takes one byte extra in Python 3. This could mean a variety of things.

• The first thing that comes to mind is division: maybe llhuii uses / in Python 2, which became // in Python 3. (If they’re counting in twos like us, then n/2 might be used to shift n back to the right by one bit?)

• The other thing that comes to mind is unary operators after print. Our print blah became print(blah) (1 byte extra), but if llhuii wrote something like print~-blah in Python 2, it’d become print(~-blah) in Python 3.

• Maybe there are other ideas. Please let me know.

Code statistics for all Py3 solutions, including mine now:

Answer 5

Other approaches

1) Using a formula for A001969

Rather than converting to binary, it might be possible to take advantage of the following formula (from OEIS):

a(1) = 0
for n > 1: a(n) = 3*n-3-a(n/2) if n is even
           a(n) = a((n+1)/2)+n-1 if n is odd

I'm very bad at golfing in Python, so I'm not even going to try. But here is a quick attempt in JS.

^{NB: I don't think it would be a valid JS submission as it's just filling an array without displaying it. And even so, it's 5 bytes longer than the current best JS solution (which is 45 bytes). But that's not the point here anyway.}

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

for(a=[n=0,3];n<199;)a.push(2*++n+a[n],6*n+3-a[n])

console.log(a.join`, `)

Hopefully it may give some inspiration.

Using an array is probably not a good idea because it needs to be initialized and updated. It might be more efficient (code size wise) to use a recursive function instead, which would explain why the winning solution is taking more time than the other ones.

2) Building the Thue-Morse sequence with substitutions

In theory, this code should work:

n=0;a="1";b="0";exec"t=a;a+=b;b+=t;print(int(b[n]))+n;n+=2;"*400

Try it online! (runnable version limited to 20 terms)

It computes the Thue-Morse sequence with consecutive substitutions and looks for the position of 1's (Evil Numbers) in the same loop.

But:

• It's far too long in its current form
• It quickly leads to a memory overflow

3) Building the Thue-Morse sequence with bitwise operations

Starting from Wikipedia's Direct Definition of the Thue-Morse sequence, I've come to this algorithm (switching back to JS ... sorry):

for(e=n=0;n<799;)(e^=!(((x=n++^n)^x/2)&170))||console.log(n)

where we keep track of the current evilness of the sequence in e and use 170 as a bitmask of odd bits in a byte.

Answer 6

Idea: Shorter bit parity

It takes many characters to do bin(n).count('1')%2 to compute the parity of the bit-count. Maybe an arithmetic way is shorter, especially given a limited bit length.

A cute same-length way is int(bin(n)[2:],3)%2, interpreting the binary value as base 3 (or any odd base). Unfortunately, 4 of the bytes are spend removing the 0b prefix. It also works to do int(bin(n)[2:])%9%2.

Another idea comes from combining bits using xor. If n has binary representation abcdefghi, then

n/16 = abcde
n%16 =  fghi

r = n/16 ^ n%16 has binary representation (a)(b^f)(c^g)(d^h)(e^i)

So, r=n/16^n%16 is evil if and only if n is evil. We can then repeat that as s=r/4^r%4, a value s in 0,1,2,3, of which 1 and 2 are not evil, checkable with 0<s<3.

52 bytes

n=0;exec"r=n/16^n%16;print(0<r/4^r%4<3)+n;n+=2;"*400

Try it online!

This turned out a good deal longer. There's many knobs to turn though of how to split the number, how to check the final number (maybe a bit-based lookup table). I suspect these can only go so far though.

Answer 7

Nested counters approach

I have an idea for a different approach, but I am not experienced enough in python golfing, so I'll leave it here for you guys to consider as another possible starting point for golfing.

The ungolfed idea:

n=0
i=1
for _ in"01":
 i^=1
 for _ in"01":
  i^=1
  for _ in"01":
   i^=1
   for _ in"01":
    i^=1
    for _ in"01":
     i^=1
     for _ in"01":
      i^=1
      for _ in"01":
       i^=1
       for _ in"01":
        i^=1
        for _ in"01":
          i^=1
          if n<800:print i+n
          n+=2

Try it online!

Nine levels nesting depth, all the loops are the same, so in my mind they should be built by exec"something"*9+"deepest stuff". In practice I don't know if it is possible to do something like this with a for cycle.

Things to consider for golfing:

• maybe there is some other possibility to cycle twice other than a for loop (I tried a quine-like approach with the string to be executed passed to itself as a formatting argument twice,but my head exploded).

• there could also be a better alternative to if n<800:, which is needed here because otherwise we would keep printing evil numbers up to 2^10

Answer 8

By construction, n+n^n is always evil, but my poor Python skills could only come up with a 61-byte solution:

for n in sorted(map(lambda n:n+n^n,range(512)))[:400]:print n

Thanks to @Peilonrayz for saving 5 bytes and @Mr.Xcoder for saving 1 byte:

for n in sorted(n^n*2for n in range(512))[:400]:print n

Answer 9

Idea: A006068 (“a(n) is Gray-coded into n”)

Neil’s idea of sorting all the 2n XOR n intrigued me, so I tried to find the indices behind this sort. I wrote this code, and it reveals that we can write something like this:

for n in range(400):x=a(n);print 2*x^x

Where a(n) is A006068(n). Try it online!

However, this assumes we have some short way to compute A006068. This is already 38 bytes, assuming we can calculate it in 4 bytes (the a(n) part). The real implementation (in the TIO header) is far longer than that. Not much hope for this I think.

Answer 10

Idea: Reduce over XOR

If you XOR all the bits of n together, it will be 0 for evil and 1 for non-evil. You can do this with a recursive function (which may have thus taken more time?), like so:

f=lambda n:f(n/2^n&1)if n>1else-~-n

This returns 1 for evil.

That's 35 bytes, and checks whether or not a number is evil. Unfortunately, filter is already 6 bytes so this wasn't the optimal solution verbatim but this idea can probably be golfed.

Answer 11

Substitution method : {1 -> {1, -1}, -1 -> {-1, 1}}

You can also make this substitution 10 times {1 -> {1, -1}, -1 -> {-1, 1}}, then flatten and check the positions of 1's

here is the mathematica code

(F = Flatten)@
Position[F@Nest[#/.{1->{1,-1},-1->{-1,1}}&,1,10],1][[;; 400]] - 1