I read this article titled Extending Given Digits to make Primes or Perfect Powers by Sury B, which appeared in the Resonance periodical (October 2010, Indian Statistical Institute, Bangalore). In this question, we are concerned with constructing Perfect Powers by extending digits of a given number. Refer to the linked article for the procedure to follow to extend digits of a given number to create another number that is a perfect power. The main result is that every integer can be extended with more digits to construct a perfect power.
The big idea is to compress data using this technique and the outline is as follows:
The sequence of bytes that we want to compress can be treated as a large integer. Say we have such data encoded as a large integer $n$. We extend the digits of $n$ such that,
$10^kn + c = a^m$ for some $a, k, m, c \in Z$, where $c \equiv a^m \mod 10^k$.
Note that we are only interested in $n$. It can be recovered through integer division of $a^m$ by $10^k$ since $n = \lfloor a^m / 10^k \rfloor$
In order for this to be an effective data compression method, the number of bits to represent $k, a, m$ should be less than the number of bits needed to represent $n$. In order for this scheme to be effective in representing large integers up to a bound $b$, the average bits required should approach the theoretical Shannon Limit.
Questions
- Can we show that this scheme is effective (or prove that it isn't)?
Related
This MSE article is for perfect squares with specified starting digits. A square number can be represented with only half the bits (i.e., we can send $x$ instead of $x^2$)
Prove that for any given sequence of digits, there is a perfect square starting with that sequence
This MSE question (posed by me) is for perfect power values of polynomials that uses a slightly different technique to get a perfect power value
You can't compress data unless there is substantial redundancy in it. To compress $n$ digit numbers to fewer than $n$ digits, you need most of the numbers not to be possible. If you compress them just to $n-3$ digits, you have $1000$ times less messages you can send, so you can only encode one in $1000$ of the $n$ digit numbers. This is independent of the compression technique you use.
The reason compression works so well for text, even better for pictures, and better yet for video is that there are lots of texts that are not possible messages (or are extremely unlikely and we tolerate no compression for them). You choose a compression scheme that takes advantage of the redundancy in the data. For text, it is that certain letter combinations make words and most do not. For pictures, you have large areas that are almost the same color. For video you have the redundancy from pictures plus the fact that successive frames are almost the same. If you want to transmit a random $n$ digit number you can't do better than just transmit the $n$ digits.