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.
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.
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. ;)
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!
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. ^_^
Watch Live TV
· 2 years ago
Lost me on "binomial coefficients".
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.
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!
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."?
Adriana Lima
· 2 years 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.
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
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
Ankur
· 1 year ago
There is solution to PrimeBits + Super Pattern on site wwww.nerant.com
All Comments
Why would you ever post the solution? I guess you're not interested in a job at Facebook.
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.
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. ;)
Cheers!
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.
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!
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
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