# Theoretically the most efficient compression algorithm

I remember in high school we did this thing where we were given a bunch of numbers in a row that had a pattern. We were asked to work out what the next number in the pattern would be. It was very easy stuff and they taught as a formula that i can't remember. Basically the patterns looked like this:

2 4 6 8 _


They formula had us work out the difference between the numbers (in this case it was 2) and then we had to exchange a variable into a formula. In this same formula was another variable that acted as the index, we exchanged the index (in this case 5) and work it out.

This is some easy stuff, so they made it just a tad harder by giving us a seemingly random bunch of numbers. But when you worked out the differences between the numbers, then a pattern emerged that looked like the above number pattern, like so:

5 7 11 17  _
\/\/ \ /\ /
2 4   6  _


In this case had another formula which made it convenient to to calculate the next number by exchanging some variables and the index.

Back then i thought that this concept could be the key to the most efficient compression algorithm ever. If you had a collection of numbers that always consisted of the same amount of numbers (say a collection of 10 numbers) and you could figure out a way to calculate a formula from that collection of numbers so that you could reconstruct it. So theoretically you'd be presented with a collection of numbers and you would calculate a formula based on this collection. This formula would have some variable where the index and the size of the collection would be two of them. Then you would exchange the first index into the formula and calculate it and just keep doing that until the index and the size of the original collection are the same and just like that you would have reconstructed the original collection.

I thought that something like that could be applied to a file, which is just a collection of numbers ranging from 0 to 255 and usually has a known size. A compression algorithm that works like this would just save the variables and the formula that was calculated for the file to a file and then when the file is "extracted", then it would just reconstruct the file using the formula and the variables.I am not a computer science expert, and i am definitely not a mathematician, but maybe someone here understands what i mean?

It fees like someone would have already thought of something like this and it is just extremely hard to implement in practice or just plain impossible.

So the question is, does something like this exist, or is something like this impossible?

• Kolmogorov complexity. Jan 6 at 16:40
• @YuvalFilmus ya beat me to it :) Just adding a link to wiki : en.wikipedia.org/wiki/Kolmogorov_complexity Jan 7 at 18:43
• – D.W.
Jan 7 at 22:14