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

Question

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 always return a math function that represent the number. Example the number 21847450052839212624230656502990235142567050104912751880812823948662932355202 must return "9^5^16+1".

Answer 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.