3
$\begingroup$

What is the sum (in base 10) of all the natural numbers less than 64 which have exactly three ones in their base 2 representation?

The numbers will have at most $6$ digits in their binary representation and let first digits can be $0$ , hence all numbers can be made six digit numbers. The number of numbers with exactly $3$ ones $= 6C3= 6·5·4 6 = 20$. Each number has $3$ ones and $3$ zeros. So totally out of $20·6$ digits $20·3$ one’s are there. So there are exactly $20*3/6$ = $10$ one's in each place.

I don't know how I can proceed for here!

$\endgroup$
2
$\begingroup$

A natural number less than $64$ with exactly three ones in it's binary representation, can be written as the sum of three distinct powers of $2$, and vice-versa.

So what we are essentially doing, is adding up all numbers, that are a sum of three distinct powers of $2$. We know that there are six powers of $2$ below $64$. We'll put a notation : $\{a,b,c\}$ stands for $2^a + 2^b + 2^c$, where $a,b,c$ are distinct and between $0$ and $5$, both included. Now, we are adding up all such possibilities, whose number you have correctly calculated.

The point is, how many times does $a$ appear in these combinations, where $a$ is between $0$ and $5$? Suppose $a$ appears in a combination, then the other two can be chosen in $\binom 52 =10$ ways. Hence, the number of combinations in which $a$ appears is $10$.

Since this happens for all $a$, the answer should be $10(2^0 + ... + 2^5) = 630$.

$\endgroup$
1
$\begingroup$

There are ${6\choose3}=20$ numbers in $[0..63]$ having exactly three ones in their binary representation, makes $60$ ones in total. These ones are uniformly distributed over the six places in the binary representation, so that each of them creates ${1\over6}(1+2+\ldots+32)$ "worth" on average. It follows that the sum of all these numbers is $60\cdot{1\over6}\cdot63=630$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.