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

Question

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

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

Answer 1

根据@ybungalobill的简洁答案展开，您的函数等价于计算任意字符串的Kolmogorov复杂度的函数。(如果您将非常大的数字的每个数字视为字符，并将这些数字视为字符序列，则等价性是显而易见的。)

根据维基百科关于Kolmogorov复杂度的页面，给出字符串s复杂度的K(s)函数是not a computable function。(该页面包含一个证明。)

换句话说，你想要的算法根本不存在。

Answer 2

@BlueRaja - Danny :是的。我正在尝试创建一些使用此算法的压缩，但顺便说一句，这是不可能的。

这是因为出于同样的原因，压缩任意数据在技术上是不可能的，但这并不能阻止我们这样做:)

然而，还有更好的压缩数据的方法。例如，让我们看看LZ。它是如此无处不在，以至于您几乎肯定可以找到一个库来为您做压缩，无论您是用什么语言编写的。DEFLATE是另一个流行的。

希望这能有所帮助！

Answer 3

如果你不是在寻找最优，只是想找一份相当不错的工作，那么你可以使用一些启发式方法。例如，尝试使用以下所有方法分解n

n = a^k + b

对于k = 2, 3, ..., log n，选择a + b最小的那个。您可以使用a = floor(n^(1/k))和b = n-a^k计算a和b。然后在a和b上递归。

当然，这只使用了求幂和加法来获得良好的压缩效果。如果您还允许减法，请改用a=round(n^(1/k))，并让b为负。

允许乘法也会让它变得相当困难，因为你可能需要考虑n。