[Question]
  [
*This is a tips question for golfing in Python concerning the [Evil Numbers](http://golf.shinh.org/p.rb?Evil%20Numbers) question on [Anarchy Golf](http://golf.shinh.org/).* 
An number is [evil](https://en.wikipedia.org/wiki/Evil_number) 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](http://golf.shinh.org/p.rb?Evil%20Numbers#Python) 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.
[![Table of Python 2 scores](https://i.stack.imgur.com/JHpOc.png)](https://i.stack.imgur.com/JHpOc.png)
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](http://golf.shinh.org/p.rb?Evil%20Numbers), 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](/questions/tagged/kolmogorov-complexity "show questions tagged '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]
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!](https://tio.run/##K6gsycjPM/r/P8/WwDq1IjVZvaAoM69EIc86L85WIy8uT9tIU9VY38g6T9vWyFpdy8TA4P9/AA "Python 2 – 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!](https://tio.run/##K6gsycjPM/r/P8/WwDq1IjVZvaAoM69EIc86zzZP2yhOIy8OSGnqG6kaW6trmRgY/P8PAA "Python 2 – 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!](https://tio.run/##K6gsycjPM/r/P8/WwDq1IjVZvaAoM69EIc86zzZP2yhOVyMvDkhrqhpbq2uZGBj8/w8A "Python 2 – Try It Online")
[Answer]
## Getting 39 bytes
This is an explanation of how I got a 39-byte solution, which [Dennis and JonathanFrech](https://codegolf.stackexchange.com/a/144075/20260) 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](https://codegolf.stackexchange.com/a/144019/20260) 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](https://codegolf.stackexchange.com/a/144019/20260) with `bin(k).count('1')%2`, and then with [bit manipulation](https://codegolf.stackexchange.com/a/144027/20260). 
**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](https://graphics.stanford.edu/~seander/bithacks.html). 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!](https://tio.run/##K6gsycjPM/r/P9s2ydaAK7UiNVmpoCgzr0TBSCtbO8k6Kc5WI1vbMC5bU9XYOlvb1tBaScvEwOD/fwA "Python 2 – Try It Online")
We removed parens around `k+1` in `((k+1)^k)%3` because [Python precedence](http://www.mathcs.emory.edu/~valerie/courses/fall10/155/resources/op_precedence.html) 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!](https://tio.run/##K6gsycjPM/r/P8/WgCu1IjVZqaAoM69EIc86L85WI0/fSNswDkhqqhpb52nbGlkraZkYGPz/DwA "Python 2 – 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!](https://tio.run/##K6gsycjPM/r/P8/WgCu1IjVZqaAoM69EIc86L85WVyNP2yguT1PV2DpP29bIWknLxMDg/38A "Python 2 – 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!](https://tio.run/##K6gsycjPM/r/P8/WgCu1IjVZqaAoM69EIc86zzZP2yhOVwNE5mmqGlsraZkYGPz/DwA "Python 2 – Try It Online")
[Answer]
*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!](https://tio.run/##K6gsycjPM/r/Py2/SCFPITNPoSgxLz1Vw8LAQNOKSyEzrS4pM08jT1MvOb80r0RD3VBdU9XIqqAoM69EIe//fwA "Python 2 – 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 `n`th 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!](https://tio.run/##K6gsycjPM/r/Py2/SCFPITNPoSgxLz1Vw8TAQNOqoCgzr0TBSCtPOykzTyNPUy85vzSvREPdUF1TFagFAA "Python 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!](https://tio.run/##K6gsycjPM/r/P8/WwDq1IjVZqaAoM69EIU87KTNPI09TLzm/NK9EQ91QXVPVyDpP29bIWknLxMDg/38A "Python 2 – 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]
# llhuii’s Python 3 submission
Here are the Python 3 submissions for Evil Numbers at the time of writing:
[![enter image description here](https://i.stack.imgur.com/MbATO.png)](https://i.stack.imgur.com/MbATO.png)
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:
[![enter image description here](https://i.stack.imgur.com/YERuq.png)](https://i.stack.imgur.com/YERuq.png)
[Answer]
# 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](http://oeis.org/A001969)):
> 
> 
> ```
> 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!](https://tio.run/##FcMxCoAwDAXQu2SyZqlZPzmJODRS0CUWyaCnj/jgjTeOyyXTtaIpLQRTqoT@9J1CGxqrwVgD4z49pr@tvpXCDmcV0Cw18wM) (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](https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence#Direct_definition), 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]
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]
# 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!](https://tio.run/##K6gsycjPM/r/P8/WgCvT1pArLb9IIV4hM0/JwFDJikshMw4opoAmCBXFEIaJY0rAZbBIIeSwSSLJYpVGlseuAEUFDiVoioDcNIU8GwsDA6uCosy8EoVM7TwkyTxtW2CIAQA "Python 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]
## 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!](https://tio.run/##K6gsycjPM/r/P8/WwDq1IjVZqcg2T9/QLC5P1dDMuqAoM69Ew8CmSN8krkjVxMZYUzvPOk/b1shaScvEwOD/fwA "Python 2 – 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]
# 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]
# 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
```
[Answer]
# Idea: [A006068](https://oeis.org/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](https://tio.run/##K6gsycjPM/r/P7UsM6dYwVYhOlM7My5TIS2/SCFTITNPoSgxLz1Vw9TQSDOWC03QyEDTiksBCEB6gVqNtDK1kzLzNDI19ZLzS/NKNNQN1TVVjcBKCooy80rACov1MvNSUis0QGzN//8B), 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!](https://tio.run/##RY5BDoIwFET3nOIvwVUlrirlFK5JavyVRjOQ3xLr6asVIrOZzMtkMvM7jhPafGNHtkajK/oqmOPPX6N/Ml1k4ZUXIRj0ffhn7woyStNV2D72nsGAvRa6bhsVjouAUGU3CYE8SCzuXJ@UanQy5cZ5Fo9I7SENKecP "Python 2 – 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.
]