Given a integer number, find the smallest function that given it

I have a very large positive integer number (million digits). I need represent it with the smallest possible function, this number is variable, it means, I need an algorithm that generates the smallest possible function to get the given number.

Example: For the number 29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889 the algorithm must return "9^99". It must be able to analyze numbers and开发者_如何学Python always return a math function that represent the number. Example the number 21847450052839212624230656502990235142567050104912751880812823948662932355202 must return "9^5^16+1".

---

Heard of Kolmogorov complexity?

To answer your question: unless you restrict yourself to some specific set of functions, it's impossible.

EDIT: Even in your example, how do you know that the shortest representation of 21​847​450​052​839​212​624​230​656​502​990​235​142​567​050​104​912​751​880​812​823​948​662​932​355​202 is actually 9^5^16+1? Isn't it a quite hard to prove even in this specific case?

If you restrict yourself to some set of functions then you can use the following algorithm:

For i = 1 to n
  enumerate all strings s of length i
    if s represents a valid expression according to rules chosen a priori, 
      and evaluates to the number in the input,
        return s

It is guaranteed to halt because on the last iteration of the outer loop (i = n) you will get eventually to a string contains the input verbatim.

Of course, this is not very efficient. Specifically O(bⁿ) where n is the length of the input and b is the size of the alphabet.

---

Expanding on @ybungalobill's terse answer, your function is equivalent to a function that computes the Kolmogorov complexity of an arbitrary string. (The equivalence is obvious if you treat each digit of your very large numbers as characters, and the numbers as sequences of characters.)

According to the Wikipedia page on Kolmogorov complexity, the K(s) function that gives the complexity of a string s is not a computable function. (The page includes a proof.)

In other words, the algorithm you want simply does not exist.

---

@BlueRaja - Danny Pflughoeft: yes, it is. I'm trying to create some compression that uses this algorithm, but by the way this is impossible.

That's because it's technically impossible to compress arbitrary data, for the same reason, but that doesn't stop us from doing it :)

There are much better ways of compressing data, however. Take a look at, for instance, LZ. It is so ubiquitous that you can almost certainly find a library to do the compression for you, regardless of what language you're writing in. DEFLATE is another popular one.

Hope that helps!

---

If you're not looking for optimality, just a reasonably good job, then there are a bunch of heuristics you can use. For example, try to decompose n using all of the following

n = a^k + b

for k = 2, 3, ..., log n, and pick the one with the smallest a + b, say. You can compute a and b using a = floor(n^(1/k)) and b = n-a^k. Then recurse on a and b.

Of course, this uses only exponentiation and addition to find a good compression. If you allow subtraction as well, use a=round(n^(1/k)) instead and let b be negative.

Allowing multiplication as well makes it quite a bit harder because you would probably need to factor n.