4 ms·
No invertible function can map every non-negative integer to a lower or equal non-negative integer (no perfect compression), but you can have functions that com
by waldrews 2y ago
No invertible function can map every non-negative integer to a lower or equal non-negative integer (no perfect compression), but you can have functions that compress everything we care about at the cost of increasing the size of things we don't care about. So the recursive de-indexing strategy has to sometimes fail and increase the cost (once you account for storing the prefix).
- psychoslave 2y agoIs there some inductive proof of that? Or is that some conjuncture? Actually any resources related to that point could be fun to explore
- waldrews 2y agoIt's a classic application of the pigeonhole principle, the first on in this list: https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_applications https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...