3 ms·
> In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion. An interesting result. Do you have a link to the
by praptak 14y ago
> In the theoretical case he has almost a 255/256 of doing it he generates a string in a truly random fashion.
An interesting result. Do you have a link to the proof?
- Dylan16807 14y agoProof: There are k strings of bytelength n. There are k * 256 strings of bytelength n+1. k input strings can decompress to at most k output strings Therefore only k / (k * 256) of length n+1 strings can be compressed by a byte. The reason for 'almost' is the miniscule number of strings that will compress more than one bye.
- praptak 14y agoAh right, I totally missed the fact that compression by 1 bit doesn't beat the challenge!