question

Given a range of positive integer numbers [a,b], write a function that returns the count of integers which have a prime number of 1 bits set in their binary representation.

P.S. This was originally a Facebook programming puzzle.

P.S. This was originally a Facebook programming puzzle.

Look into combinatorics and how to apply that to binary representations.

There is already a thorough, very well-written explanation of the answer on Jesse Farmer's blog. I'll reveal the secret sauce below but be sure to read through the blog post for a more complete answer.

The seemingly obvious naive solution would iterate through each number, determine its binary representation, and then determine the number of primes present. This is can be made more efficient by exploring the properties of binary numbers.

Consider numbers represented by 6 binary bits. This means to satisfy the property of a prime number of 1 bits, there must be only 2, 3, or 5 '1' bits in the binary representation. Using combinatorics [(6C5) + (6C3) + (6C2)], it becomes clear there are 41 6-bit numbers with a prime count of 1's. We cant extend this idea to solve the question - again, a more thorough explanation is available at Jesse's blog.

Thoughts or alternate solution? Let us know in the comments below!

The seemingly obvious naive solution would iterate through each number, determine its binary representation, and then determine the number of primes present. This is can be made more efficient by exploring the properties of binary numbers.

Consider numbers represented by 6 binary bits. This means to satisfy the property of a prime number of 1 bits, there must be only 2, 3, or 5 '1' bits in the binary representation. Using combinatorics [(6C5) + (6C3) + (6C2)], it becomes clear there are 41 6-bit numbers with a prime count of 1's. We cant extend this idea to solve the question - again, a more thorough explanation is available at Jesse's blog.

Thoughts or alternate solution? Let us know in the comments below!