How to generate the shortest possible equation that has exactly one solution for specified integer?

Question

I'm basically trying to create a function that converts a positive integer n into an equation that has exactly one solution which can be computed back into the n. So if n = 1282388557824 the function should convert it to n = 264 ^ 5 since it's the shortest (or at least one of the shortest) equation and has only 1 solution.

The function can use any mathematical operators that a computer can calculate.

How would we even go about finding the shortest possible equation (or one of the shortest) without a slow brute-force? Any smart tricks we can use? Let's say we have n = 6415607, then how can we quickly find that the shortest equation for it is (23 ^ 5) - (12 ^ 4) and not something short like 186 ^ 3? (it's not, it's just an example)

It's fine if some of the integers cannot be compressed into an equation.

There's 2 preferred conditions:

• The equation should be as short and as easy to compute as possible. For example, for n = 17 it should generate something like n = 2 ^ 4 + 1

• Computation speed should not grow exponentially with integer length, the function should generate the equation relatively quickly, regardless of the integer's length. Let's say, something like under 0.1 ms for a 10 digit long integer and under 1 sec for a 100,000 digit long integer.

It would be nice if you could write the answer in a form of a function written in any programming language. I understand the algorithms better this way, math language is often too hard for me.

Answer 1

The notion you seem to want is Kolmogorov complexity, which informally speaking measures the size of the shortest program or expression that produces a given string.

It is a fundamental result that not all strings have short descriptions. Some (most?) strings need descriptions at least as long as themselves, and so cannot be compressed.

Moreover, Kolmogorov complexity is not a computable function: there is no program which takes a string $s$ and outputs the length of the shortest description of $s$. Let alone find that shortest description.

Answer 2

Here is a relatively simple heuristic procedure which will give you a generally fairly "short" equation (although not usually the shortest possible) involving much smaller numbers for basically any integer, even very big ones like ones with around $100,000$ digits.

First, choose a relatively small maximum base you want to check up to, e.g., $f = 1000$. Next, I suggest you choose as the bases to work with all integers from $2$ up to $f$, except for any that are integer powers of $2$ or more (e.g., exclude $4 = 2^2$, $8 = 2^3$, $9 = 3^2$, $16 = 2^4$, $25 = 5^2$, $27 = 3^3$, $32 = 2^5$, $36 = 6^2$, etc.) as their nearest integral powers would've already been determined previously. Next, apply the following loop, starting with $r = n$, where $n$ is the original number, and with a flag indicating you're adding values.

Among the list of bases to use, determine the logarithm of $r$ for each base $b$, and then determine the nearest integer (call it $m$) to that logarithm (e.g., if the log is $213.478\ldots$, then $m = 213$, while if it's $213.561\ldots$, then $m = 214$). Note if the programming language you're using doesn't support arbitrary bases for logarithms but, instead, say just natural (i.e., base $e$) or base $10$, then as described at Changing the base, you can use the identity

$$\log_b a = \frac{\log_d(a)}{\log_d(b)} \tag{1}\label{eq1}$$

In your case, $d$ would be $e$ or $10$, $b$ would be the base and $a = r$. Next, set $g = r - b^m$ and $h = \left| g \right|$, then check & store details of the smallest $h$ found among all $b$ checked. For the $b$ and $m$ of this smallest $h$, you may wish to check if $m$ has any fairly small factors. If so, you may use any of them to potentially make the $b$ and $m$ combination "smaller" (e.g., if $b = 2$ and $m = 3126 = 2 \times 3 \times 521$, then you can use $b = 2^{2\times 3} = 2^6 = 64$ and $m = 521$ instead, if you consider this to be smaller). Next, toggle the sign flag if $g \lt 0$. Append the sign (i.e., add or subtract), $b$ and $m$ values to a list. If $h \lt 2$, you're done so exit the loop. If you wish to have your expression be limited to a certain maximum number of terms, you should add a check for this and exit this loop if this limit is reached. However, before exiting, if $h \gt 0$, then add its final set of values to your list. Otherwise, if continuing, set $r = h$ and repeat the loop from the start of this paragraph.

In the end, you can put together the values from the stored list to get $n$ as a relatively short (it will generally be much less than $\log_2 n - 1$ items) expression of the sum and differences of various powers, plus possibly $\pm 1$ at the end (or whatever is left if the loop was exited early). For quite short numbers, like for $10$ digits, the run time will be very minimal, although the load time will generally cause it to overall take longer than a very short period like $0.1$ ms you asked for. Even for numbers as large as $100,000$ digits, this will work fairly quickly on modern computers, likely well within the $1$ second limit you requested.

Answer 3

If we assume that the number $n$ to be represented is randomly chosen and large enough so that searching for 'nice' situations (like $264^5$, or more generally perfect powers that are fortuitously close to $n$) is not likely to be efficient, I would start by making a table of $k^k$ and identifying the values that bracket the chosen number, call them $k_i$ and $k_{i+1}$. Then express $n=c_i\cdot k_i^{k_i}\pm a_1$, choosing $c_i$ so as to minimize $|a_1|$. If $a_1$ is unacceptably large, treat it as another $n$, and generate $n=c_i\cdot k_i^{k_i}\pm (c_j\cdot k_j^{k_j}\pm a_2)$. This general approach should yield a relatively compact equation (but not necessarily the most compact) of arbitrarily chosen large numbers.