View Single Post
Old 2020-08-04, 14:15   #5
xilman's Avatar
May 2003
Down not across

2×3×52×73 Posts

Originally Posted by kruoli View Post
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?
xilman is online now   Reply With Quote