14 comments

• 

  Hung

  2 years ago

  Jesse, I got as far as linking the problem to the binomial coefficients and drawing some correlations to Pascal's triangle. I got stuck at the part for coming up with an algorithm for all numbers, rather than for powers of 2.
  
  Why would you ever post the solution? I guess you're not interested in a job at Facebook.
  reply
• 

  Jesse

  2 years ago

  Hey Hung,
  
  Oh, yeah? Then did you not send anything to the Facebook?
  
  My intention is to solve all their interesting puzzles and post the solutions. Why? Well, why not? De l'audace, encore de l'audace, toujours de l'audace.
  reply
• 

  Hung

  2 years ago

  I sent the sub-optimal solution, then I checked their puzzle page again that changed and asked for a better than O(n) solution. Then I thought about it for a while and got to the point I described. I didn't send it because I knew I could do better; I just hadn't figured it out yet.
  
  Then I got busy with some of my other side projects since I got an email from Facebook saying they were finished finding Summer interns (that's what I was going for). Solving the solution, while fun, would not be efficient use of my time.
  
  I guess the point in asking about posting the solutions is that it sort of undermines the effectiveness of the puzzle as a recruitment device. Plus it takes the fun out of figuring it out for ones' self. And by fun, I mean stress. ;)
  reply
• 

  Jesse

  2 years ago

  To those reading this post: I was contacted by the puzzle-writer at Facebook and he asked kindly for me to at least obscure my solution. I'm leaving the explanation up but removing the actual implementation. If you're interested in the implementation you can contact me and convince me I should share it with you.
  
  Cheers!
  reply
• 

  Cassie

  2 years ago

  Well, someone looking to solve the puzzle on their own would hopefully look over this post. If they are reading beyond the title and perhaps first paragraph, it suggests that the "fun of figuring it out for ones' self" has worn out. ^_^
  reply
• 

  Watch Live TV

  2 years ago

  Lost me on "binomial coefficients".
  reply
• 

  Jesse

  2 years ago

  Formally the binomial coefficient, nCk, is the number of k-subsets of a set of size n. Put in laymans terms this means nCk is the number of ways you can select k balls from a bucket filled with n balls, assuming you don't care about order, i.e., you don't care if you pick the first, third, and fifth balls in that order, or the third, first, and then the fifth.
  
  Applying it to this problem, then, there are 6C2 6-bit numbers which have two bits set to one, 6C3 with three bits set to one, and 6C5 with five bits set to one. Since 1, 3, and 5 are the only primes less than 6 there are 6C2 + 6C3 + 6C5 6-bit numbers with a prime number of bits set to one.
  reply
• 

  Sam

  2 years ago

  Jesse.. my implementation was very similar.
  
  It took me awhile to figure out the pascal's triangle caveat, but once I figured it out it was pretty simple.
  
  My implementation generates the pascal array to the number of rows needed [number of significant bits]. I then 'condense' that array to create an array[x][y] that reads:
  
  For all numbers equal to and less than 2^[x], there are occurances of [y] bits set on.
  
  From there it was as simple as adding arrays, then cross referencing them against the 'arePrimes' array.
  
  This was a very enjoyable problem!
  reply
• 

  Matt

  2 years ago

  You wrote: "e.g., 5 is written as 101 = 1*2^2 + 0*10^1 + 1*10^0." Did you mean "e.g., 5 is written as 101 = 1*2^2 + 0*2^1 + 1*2^0."?
  reply
• 

  Daniel

  1 year ago

  I couldn't understand some parts of this article , but I guess I just need to check some more resources regarding this, because it sounds interesting.
  reply
• 

  Chris

  1 year ago

  I have posted a solver, give it a try and see if our answers match: http://www.ctmouton.com/projects/facebook/optim...
  reply
• 

  Andres

  1 year ago

  Jesse, great job! It's an interested puzzle..
  I got lost in the part of solving the problem for other numbers rather than powers of 2. Could you explain it better? Can you give me other examples? why "-1"? why starting from 2C(3-1)?
  Thanks
  reply
• 

  Jesse

  1 year ago

  Andres,
  
  For powers other than 2 you need to break it down into several contiguous ranges. You have one range more than there are ones in the binary representation of the original number.
  
  For example, if the number you're looking at is 10110 then the ranges are 00000-01111, 10000-10011, 10100-10101, and 10110. There are three ones and four ranges.
  
  Each range corresponds to fixing one of the bits, starting from the left-most (most significant) bit. So the first range has no fixed bits, the second has one, the third has two, etc.
  
  We subtract from our calculation the number of fixed bits. So, if the range we're looking at is 10000-10011 we're interested in numbers of the form 100xx. The only prime numbers that are suitable here are 2 and 3. That is, we can have at most three 1-bits.
  
  But there's already a fixed bit (that one on the far left side), so if there are three 1-bits then that means there must be two 1-bits in the xx section. Thus we get 2C(3-1), because we're choosing the number of combinations in the xx section such that there are three 1-bits for the whole string.
  
  Hope that helps,
  Jesse
  reply
• 

  Ankur

  12 months ago

  There is solution to PrimeBits + Super Pattern on site wwww.nerant.com
  reply