We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea: Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number is 1/256. If I prime factorize each number though I get a stream of prime numbers where I can calculate the probabilty of encountering a specific prime number by looking at how often it appears in all prime factorizations of all 8-Bit numbers. Here's a couple of issues straight away:

  • 0 and 1 are special cases, they dont have a prime factorization per-se
  • the transform is not invertible, you'd have to use seperation symbols

One way to "solve" both issues is to include 1 as a prime number and encode a number x as a prime factorization of number (x + 1) which allows for 0 and 1 and still fits into 8-Bits because the largest 8-Bit prime is 251. The 1 at the beginning of each prime factorization also serves as a separation symbol.

Could I use this way to somehow ("efficiently") encode a random stream of data?


1 Answer 1


No. If it is a stream of random bytes, where each byte is independently and uniformly distributed, it cannot be compressed. It doesn't matter what method you're using. You're trying to do something analogous to inventing a perpetual motion device; we don't have to look at the detailed blueprint to know that it won't work.

  • $\begingroup$ In this particular case, I’d say a highly inefficient attempt at a Perpetuum mobile. Using this method to represent 8 bit values in less than 16 bit on average seems challenging to me. $\endgroup$
    – gnasher729
    Commented Jan 12, 2021 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.