Thread: Is this a puzzle? View Single Post
2020-08-04, 14:15   #5
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×3×1,699 Posts

Quote:
 Originally Posted by kruoli Hitting < 718K should have a probability around 1 in 2e7, so still achievable by brute force, hitting < 710K is much less likely with 1 in 8e76. Formula used (please correct me if my approach is not applicable): $p = \frac{\sum_{k=0}^{x}{\binom{\lceil log2(n) \rceil}{k}}}{n}$ $$p$$ is the probability. $$n$$ in the number we want to "depopulize". $$x$$ is the target popcount. If our target popcount would be greater than $$\lceil log2(n) \rceil$$, take the sum from $$x$$ to $$\lceil log2(n) \rceil$$. Since we are multiplying $$n$$ with another value to "depopulize" it, the final result number is getting larger. This is not displayed by this formula, but should not make a huge difference, since our value for multiplication is really small in comparison.
There appears to be a typo. Should the exceptional sum be taken from 0, not x?