3
$\begingroup$

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 ?

$\endgroup$
9
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Empy2
    Commented Jun 17 at 9:07
  • 3
    $\begingroup$ Either $2n$ or $2n+1$ has an even number of 1s, so the answer is either $2009×2$ or $2009×2+1$ $\endgroup$
    – Empy2
    Commented Jun 17 at 14:17
  • 1
    $\begingroup$ @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"). $\endgroup$ Commented Jun 17 at 14:52
  • 1
    $\begingroup$ This and other HMMT solutions of 2009: hmmt-archive.s3.amazonaws.com/tournaments/2009/feb/guts/… $\endgroup$
    – Soham Saha
    Commented Jun 17 at 15:03
  • 3
    $\begingroup$ The usual term for "jubilant number" is "evil number". Non-jubilant numbers are then the odious numbers. $\endgroup$ Commented Jun 17 at 16:58

3 Answers 3

16
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Well we hit it at just about the exact same time. :-) $\endgroup$
    – paw88789
    Commented Jun 17 at 14:56
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Aashita
    Commented Jun 17 at 9:05
  • $\begingroup$ 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. $\endgroup$
    – Keba
    Commented Jun 17 at 13:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .