Monday, March 11, 2013

Facebook Prime Bits Programming Puzzle

We know that, Every Positive integer can be represented using binary. That is, a number can be written in base of 2 also. Like decimal numbers, which is based around powers of ten. For example, 215 is really 2*102 + 1*101 + 5*100. Binary numbers  involves using 2's rather than 10's as place values, so, e.g., 5 is written as 101 = 1*22 + 0*21 + 1*20.

Every integer therefore can be respresented as a string of zeroes and ones. Define P(x) to be true if the number of ones in the binary representation of x is prime and false otherwise. 

So, e.g., P(5) is true but P(4) is false. 

Our job is to implement the function uint64_t prime_bits(uint64_t a, uint64_t b); which returns the number of integers k, a = k = b such that P(k) is true. uint64_t is a way of designating 64-bit numbers in C/C++.

This has been asked in Facebook. And people wanting to get the solution can email me at I do not guarantee to reply to all the emails at once, but will cater to your requests in a batch that I look once every fortnight.


Best is to discuss here..

1 comment:

  1. Among one of the finest pieces on the web, awakening in its specificity.