View Single Post
Old 2020-08-04, 14:11   #4
kruoli's Avatar
Sep 2017
Porta Westfalica, DE

3×5×43 Posts
Default Brute force probability analysis.

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.

Last fiddled with by kruoli on 2020-08-04 at 14:14 Reason: Minor clarifications.
kruoli is offline   Reply With Quote