给定一个整数,找到给出它的最小函数

Question

我有一个非常大的正整数(百万位).我需要用尽可能小的函数来表示它,这个数字是可变的,这意味着,我需要一个生成最小函数的算法来获得给定的数字.

示例:对于数字29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889,算法必须返回"9 ^ 99".它必须能够分析数字并始终返回表示数字的数学函数.示例编号21847450052839212624230656502990235142567050104912751880812823948662932355202必须返回"9 ^ 5 ^ 16 + 1".

Answer 1

听说过Kolmogorov的复杂性？

回答你的问题:除非你限制自己使用一些特定的功能,否则这是不可能的.

编辑:即使在你的例子中,你怎么知道最短的代表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实际上是9 ^ 5 ^ 16 + 1？即使在这种特定情况下,难道不是很难证明吗？

如果您将自己局限于某些功能集,则可以使用以下算法:

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

它保证会停止,因为在外循环的最后一次迭代(i = n)中,最终会得到一个包含输入逐字的字符串.

当然,这不是很有效.具体来说是O(b ⁿ),其中n是输入的长度,b是字母表的大小.

Answer 2

扩展@ ybungalobill的简洁回答,您的函数等效于计算任意字符串的Kolmogorov复杂度的函数.(如果将非常大的数字的每个数字视为字符,将数字视为字符序列,则等效性很明显.)

据对Kolmogorov复杂的维基百科页面中,K(s)给出了一个字符串的复杂功能s是不是一个可计算函数.(该页面包含证明.)

换句话说,您想要的算法根本不存在.