# 2009th smallest number in base 10 whose binary representation contains even number of 1's

HMMT 2009 Problem 20 :

A positive integer is called Jubilant if the number of 1’s in its binary representation is even. For example, $$6=110_2$$ is a Jubilant number. What is the $$2009$$th smallest jubilant number?

There is 1 two digit Jubilant number
2 three digit Jubilant numbers
4 four digit Jubilant numbers

In genereal there are - 2n-2 n digit Jubilant numbers

So, (111111111111)₂ must be the 2047th jubilant number. Now to find the 2009th Jubliant number I'll have to write down all 38 Jubilant numbers in between, which seems to be a tedious task.

Is there a better approach to solve this question ?

• There are $64$ with digits $11111ddddddd$ which brings you back to $2048-64=1988$. Then $16$ with $1111100ddddd$ bringing you up to $1988+16=2004$. Commented Jun 17 at 9:07
• Either $2n$ or $2n+1$ has an even number of 1s, so the answer is either $2009×2$ or $2009×2+1$ Commented Jun 17 at 14:17
• @Empy2 Following your idea, the $n$th Jubilant number is $2n$ if $n$ is Jubilant and $2n+1$ otherwise. So, is $2009$ Jubilant or not? If it is, then the answer is $4018$. If not, then the answer is $4019$. Zero-indexing is not an issue, as $1$ is not Jubilant (in fact, $0$ would actually be the "$0$th Jubilant number"). Commented Jun 17 at 14:52
• This and other HMMT solutions of 2009: hmmt-archive.s3.amazonaws.com/tournaments/2009/feb/guts/… Commented Jun 17 at 15:03
• The usual term for "jubilant number" is "evil number". Non-jubilant numbers are then the odious numbers. Commented Jun 17 at 16:58

For any $$k$$, exactly one of $$2k$$ and $$2k+1$$ will be jubilant, because an even and the subsequent odd just differ in the rightmost bit (the even has a $$0$$ in the rightmost bit, the odd a $$1$$).

Note that $$1$$ is not jubilant. So from $$1$$ to $$2k+1$$, there will be exactly $$k$$ jubilant numbers.

This means that from $$1$$ to $$4019$$ there will be exactly $$2009$$ jubilants, with the $$2009$$th jubilant being $$4018$$ or $$4019$$. So then you just check which of these two numbers has an even number of $$1$$s in its binary expansion, to see which is the $$2009$$th jubilant number.

For positive integer $$n$$, exactly one of $$2n$$ and $$2n+1$$ is jubilant, since they differ only in the last bit. (An edge case need checking: 0 is jubilant, 1 is not. So the jubilant positive integers start with 2.)

So the 2009th jubilant number is either $$2009 \times 2 = 4018$$ or $$2009 \times 2 + 1 = 4019$$.

To figure out which it is, note that $$2009 = 2047 - 38 = (2^{11} - 1) - 38$$. I write it this way instead of as $$2^{11} - 39$$ - that way you can easily find the binary expansion without having to "borrow" in the subtraction. In particular $$11111111111_2 - 100110_2 = 11111011001_2$$. (You don't actually have to do the subtraction - $$2047$$ in binary has 11 ones, and subtracting $$38$$ turns off three of them, corresponding to $$32 + 4 + 2$$.)

Thus 2009 in binary has eight $$1$$s, so $$2009 \times 2 = 4018$$, also with eight $$1$$s, is jubilant.

• Well we hit it at just about the exact same time. :-) Commented Jun 17 at 14:56

You get other 12-digit Jubilant numbers by replacing two 1s (not the first one) with two 0s. There's one option for the last two digit, 2 for the last three, 6 for the last four and one additional for all of the last for, $$\binom{5}{2} = 10$$ for the last 5 and $$\binom{5}{4} = 5$$ additional ones for flipping four of the last five bits etc.

Leaving the first digits as they are and only changing the last 6 digits, this should give $$\sum_{k=1}^6 \binom{k}{2} + \sum_{k=4}^6 \binom{k}{4} + \binom{6}{6}$$.)

Edit: I first forgot that flipping four (and six etc.) bits is also relevant and updated the formulas above.

• But adding 2 zeros in the coefficients of 2^4 or higher will give us smaller numbers than adding 4 zeros in the coefficients of 2^0, 2^1, 2^2, 2^3. So the order of the number will mess up Commented Jun 17 at 9:05
• The order is from right to left, but I still messed up, see my edit. In any case, I now believe that @Empy2's idea in the comments is faster than my approach, at least for the particular case of 2009.
– Keba
Commented Jun 17 at 13:58