algorithm - 给定一个整数，找到给定它的最小函数

Question

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

示例:对于数字 29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889，算法必须返回“9^99”。它必须能够分析数字并始终返回表示数字的数学函数。例如，数字 21847450052839212624230656502990235142567050104912751880812823948662932355202 必须返回“9^5^16+1”。

Answer 1

听说过 Kolmogorov complexity ？

回答您的问题:除非您限制自己使用某些特定的功能集，否则这是不可能的。

编辑: 即使在您的示例中，您怎么知道 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 是字母表的大小。