View Single Post
Old 2020-08-04, 14:15   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×3×1,699 Posts
Default

Quote:
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 offline   Reply With Quote