4 ms·

I always wondered if prime numbers can be used as the basis of a compression algorithm. Where you describe how to get your number, in relation to how it can be

I always wondered if prime numbers can be used as the basis of a compression algorithm. Where you describe how to get your number, in relation to how it can be factored using prime numbers. You cut up your data into chunks, and then find the prime factors of each chunk. Now you have a list of arithmetic descriptions to describe your data, and you can use Huffman to compress the descriptions. Of course, this would be computationally intensive, for both the compressor, and the extractor, but it may save on the payload size, to allow for efficient data transfer. And while we still use Huffman’s algorithm, I wonder if advanced aliens may have discovered this technique for data compression. This is more of a sci-fi fantasy algorithm, than anything actually mathematically sound.

Simon_says 7y ago
The prime factors of a number takes (about) the same amount of space to list as the number itself.
- saagarjha 7y ago
  Notably, even listing the ordinal index of the prime (e.g. that a number is the product of the first, fifth, and tenth primes) takes about the same amount of space as well due to the prime number theorem.
  - yholio 7y ago
    > the average gap between consecutive prime numbers among the first N integers is roughly log(N) So if you are compressing exceptionally large numbers, say, a whole video file, which is likely to contain very long factors, you could shave log2(log(N)) bits for each factor of length N. Seems like the most impractical compression algorithm imaginable.
- Normal_gaussian 7y ago
  I would assume the intent is to use the fact that most numbers use the same prime factors as the encoding advantage. As in, you're transforming a list of dissimilar numbers into a list of similar ones.
krajzeg 7y ago
Interesting idea, but factoring a number does not compress it - the number of digits (binary or otherwise) will stay roughly the same. You can see this using logarithms: a x b = c implies ln a + ln b = ln c. But ln x is proportional to the number of digits of x, so a and b have roughly the same length together as c.
tinus_hn 7y ago
There is no way around the fact that you need a number of bits to represent a number of different codes. All you can do is take less bits to represent the codes you want and more to represent those you don’t care about. Using weird representations does not change that. But Huffman coding works with that fact because it represents often-used codes using less bits.
FartyMcFarter 7y ago
If this were true, that would provide a way to seemingly compress any number (with the exception of prime numbers, though even those could be compressed by representing them as their index in the list of all prime numbers!). The problem is that there can't be a way to compress every number: there aren't enough N-1 bit numbers to compress N bit numbers into (since the former set is only half as big as the latter).
aruggirello 7y ago
The only way this might work is that you succeed in finding the GCD of a sequence of numbers: https://en.wikipedia.org/wiki/Greatest_common_divisor https://en.wikipedia.org/wiki/Greatest_common_divisor
- saagarjha 7y ago
  That would tend to 1 for any reasonably size sequence.
imglorp 7y ago
There ARE a number of messages that can be represented as a polynomial of prime powers, look up Godelization. More generally there are SOME very compact methods to write large numbers using functions, eg factorial and tetration: 12345! + 3^^3^^2 -1 would be huge. The problem is MOST numbers do not have compact representations so they'd be bigger. I do wonder about how effective it is to pad messages in-band to align with the nearest compact representation. Funny you should mention scifi because there's a story that got me interested in this topic [1] where some folks encode a large, important message into a compact algebraic expression like this. Turns out they're pissed at the recipients and the decimal expansion would be enormous so it would take them a while to decode it. 1. Fredrick Pohl, "Starburst", pp 56, 58, 59.

Simon_says 7y ago

The prime factors of a number takes (about) the same amount of space to list as the number itself.

saagarjha 7y ago
Notably, even listing the ordinal index of the prime (e.g. that a number is the product of the first, fifth, and tenth primes) takes about the same amount of space as well due to the prime number theorem.
- yholio 7y ago
  > the average gap between consecutive prime numbers among the first N integers is roughly log(N) So if you are compressing exceptionally large numbers, say, a whole video file, which is likely to contain very long factors, you could shave log2(log(N)) bits for each factor of length N. Seems like the most impractical compression algorithm imaginable.
Normal_gaussian 7y ago
I would assume the intent is to use the fact that most numbers use the same prime factors as the encoding advantage. As in, you're transforming a list of dissimilar numbers into a list of similar ones.

krajzeg 7y ago

Interesting idea, but factoring a number does not compress it - the number of digits (binary or otherwise) will stay roughly the same. You can see this using logarithms: a x b = c implies ln a + ln b = ln c. But ln x is proportional to the number of digits of x, so a and b have roughly the same length together as c.

tinus_hn 7y ago

There is no way around the fact that you need a number of bits to represent a number of different codes. All you can do is take less bits to represent the codes you want and more to represent those you don’t care about. Using weird representations does not change that. But Huffman coding works with that fact because it represents often-used codes using less bits.

FartyMcFarter 7y ago

If this were true, that would provide a way to seemingly compress any number (with the exception of prime numbers, though even those could be compressed by representing them as their index in the list of all prime numbers!). The problem is that there can't be a way to compress every number: there aren't enough N-1 bit numbers to compress N bit numbers into (since the former set is only half as big as the latter).

aruggirello 7y ago

The only way this might work is that you succeed in finding the GCD of a sequence of numbers: https://en.wikipedia.org/wiki/Greatest_common_divisor https://en.wikipedia.org/wiki/Greatest_common_divisor

saagarjha 7y ago
That would tend to 1 for any reasonably size sequence.

imglorp 7y ago

There ARE a number of messages that can be represented as a polynomial of prime powers, look up Godelization. More generally there are SOME very compact methods to write large numbers using functions, eg factorial and tetration: 12345! + 3^^3^^2 -1 would be huge. The problem is MOST numbers do not have compact representations so they'd be bigger. I do wonder about how effective it is to pad messages in-band to align with the nearest compact representation. Funny you should mention scifi because there's a story that got me interested in this topic [1] where some folks encode a large, important message into a compact algebraic expression like this. Turns out they're pissed at the recipients and the decimal expansion would be enormous so it would take them a while to decode it. 1. Fredrick Pohl, "Starburst", pp 56, 58, 59.