Evil numbers

A recent 6 kyu kata on Codewars proposed by Paul Robertson defines an evil number as a nonnegative number with an even number of 1’s in its binary representation. The following table shows all nonnegative numbers up to 12 and indicate which ones are evil numbers:

The kata asks for a function getEvil so that getEvil n returns the nth evil number. For example, getEvil 1 should return 0 and getEvil 5 should return 9.

Before reading on, try to solve this kata yourself. In any case, this simple-looking kata is sufficiently rich for illustrating a bit of Haskell programming and mathematical thinking that are useful for learners.

Parity function

We first develop a function isEvil that tells us whether or not a given nonnegative integer has an even number of 1’s in its binary representation.

For our first attempt, we will simply do the obvious: Convert the number to a string of binary digits, and then see if it has an even number of ones. We will make use of the function showIntAtBase from the Numeric module in base. This function has type

showIntAtBase :: Integral a => a -> (Int -> Char) -> a -> ShowS

The first argument is the target base. The second argument is a function that converts a digit into a character. For this, we use intToDigit from the Data.Char module since every digit in bsae 2 is either the integer 0 or the integer 1. The third argument is the number to be represented in the target base. The output is a function of type ShowS which, according to the documentation, prepends the output String to an existing String.

For instance, to obtain the binary string for 1234, we can do the following in the ghci REPL:

λ> import Numeric (showIntAtBase)
λ> import Data.Char (intToDigit)
λ> showIntAtBase 2 intToDigit 1234 ""
"10011010010"

Here is our first attempt at implementing isEvil:

λ> isEvil n = even $ length $ filter (== '1') $ showIntAtBase 2 intToDigit n ""
λ> take 6 $ filter isEvil [0..]
[0,3,5,6,9,10]

So far so good. But the function looks incredibly inefficient; converting a integer to a string is rather expensive.

We can be more direct by just ‘peeling off’ one digit at a time by obtain the quotient and remainder upon division by 2. For integer types with standard width, some sort of bit shift operation will do the job. But since we need to accommodate arbitrarily large integers, we use quotRem.

Here is our second attempt:

λ> :{
isEvil' 0 = True
isEvil' 1 = False
isEvil' n = let (q,r) = n `quotRem` 2 
            in (r == 1) /= isEvil' q
λ> :}
λ> take 6 $ filter isEvil' [0..]
[0,3,5,6,9,10]

This works as expected, which is a good sign. Armed with this, we can simply solve the kata as follows, right?

λ> getEvil n = let es = filter isEvil' [0..] in es !! (n-1)
λ> map getEvil [1..6]
[0,3,5,6,9,10]

Not so fast

Being a 6 kyu kata, there must be a twist. In this case, the input n can be as large as \(10^{100}\) in the tests! The above implementation of getEvil will certainly not be able to pass the tests within the given time limit.

The fact that the input can be so large gives us a hint: We cannot afford to generate the whole list of evil numbers up to n. In other words, we need some sort of formula that returns the nth evil number as directly as possible.

Let us look at the table and see if there is a pattern.

Aha! If we consider the numbers 0 to 11 one pair at a time, we see that exactly one number in each pair is an evil number. Is there a simple mathematical explanation for this observation?

In the pair of numbers \(2m\) and \(2m+1\), the binary representation of the former ends in a 0 since it is a multiple of 2. Hence, the binary representation of \(2m+1\) has one more 1 than the binary representation of \(2m\). Hence, if \(2m\) is an evil number, \(2m+1\) cannot be an evil number. And if \(2m\) is not an evil number, \(2m+1\) must be an evil number. So we can conclude that the nth evil number must be either 2*(n-1) or 2*n-1. All we need to do is to test if 2*(n-1) is an evil number. If it is, we return it. Otherwise, we return 2*n-1. The following implementation of getEvil passes all the tests:

getEvil :: Integer -> Integer
getEvil n = 
    if isEvil' t then t else t+1
  where
    t = 2 * (n-1)