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.

  • 3
    $\begingroup$ You'd have to be more specific as to what you're looking for in this equation, especially what you mean by "shortest possible". For example, for your example of n=6415607, I could just write 6415606+1. $\endgroup$
    – Sohom Paul
    Jul 5, 2019 at 15:07
  • 2
    $\begingroup$ Do you mean as few digits used as possible? $\endgroup$ Jul 5, 2019 at 15:36
  • 1
    $\begingroup$ What functions are allowed? Is it just addition, subtraction, division, multiplication, and exponentiation? $\endgroup$ Jul 5, 2019 at 15:55
  • 1
    $\begingroup$ Can you please edit your question to include the full list of operations that can be used? $\endgroup$ Jul 5, 2019 at 15:58
  • 1
    $\begingroup$ Your example of $1171350625$ is contrived. You clearly started with $185^4$ and computed it. Most numbers do not have a simpler representation. It is hard to prove that any given number does not, but there are not many significantly shorter strings to produce numbers. Suppose I give you $13472144758045575025758924749?$ What answer do you want? $\endgroup$ Jul 6, 2019 at 2:36

3 Answers 3


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.

  • $\begingroup$ Thanks for the answer, but what about the integers that it can be done with? If some of the equations cannot be compressed, that's fine as far as it works for the majority of the integers $\endgroup$
    – Un1
    Jul 5, 2019 at 16:21
  • $\begingroup$ I got that there's no such pre made function. But aren't there lot of tricks that can help us find those equations quickly? For example: n = 1282388557824 which ends with 4 (even) which means we can try using exponentiation operator with even bases, so we try 284 bases before we get to the 284 ^ 5 as the "possibly shortest" solution, or something like that? isn't math full of tricks like that which help you reduce the amount of brute-force? $\endgroup$
    – Un1
    Jul 5, 2019 at 16:30
  • $\begingroup$ @Un1 I think you ought to think hard about the implications of the third para of this answer. $\endgroup$ Jul 5, 2019 at 16:55
  • $\begingroup$ "as far as it works for the majority of the integers" turns out to be part of the story in the second paragraph, so there's really no hope for the general question. $\endgroup$ Jul 5, 2019 at 23:21
  • 1
    $\begingroup$ @Un1 One can make a correspondence between integers and strings, so the results about strings apply to integers as well. $\endgroup$ Jul 6, 2019 at 2:39

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.


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .