Re: Bitcoin puzzle transaction ~32 BTC prize to who solves it
This trick might be very useful for improving a vanity search with a long prefix, without looking for a full match. You skipped a lot of ranges to land on this hash, right? 
You can implement hash comparison logic using unordered_map for fast lookups. Instead of comparing the entire 20-byte HASH160, you can compare only the first 8 bytes with unordered_map.
I meant something else: let's say we want a match on the first 58 bits of the hash.
This means checking 2**58 hashes, on average.
But instead of scanning linearly one key after the next, jump around according to mcdouglasx/bibilgin strategies (trade off precision with probabilities).
That's why I said it can be a good improvement to find vanity addresses faster, but since there are skipped ranges, other matching prefixes might get lost, there is no violation. But this is not something that a vanity search would ever care about. Only something that should worry someone who wants to solve a puzzle in an efficient matter (e.g. an exact match).
I still dont see how skipping is more efficient than scanning everything.
A certain density of X bits prefixes (what you call being lucky) in an arbitrary range has zero impact on the probability of finding something on the next key, or on 100m keys later.
You can think of it this way : since distribution is random, any key can be replaced by any other key. As a result changing the traversal order does not improve odds of success.