整数复杂度

数论中, 一个整数整数复杂度(英语:Integer complexity)是用最少数量1的算式来表达此整数[1],可以使用任何数量的 加法乘法与括号,最后算式中出现1的个数即为整数复杂度。

例如,整数11可以使用8个1表示:

11 = (1 + 1 + 1) × (1 + 1 + 1) + 1 + 1.

若是用7个1或是更少个数的1,无法表示7。 因此7的整数复杂度就是8。

整数1, 2, 3, ...的整数复杂度分别是

1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, 8, 8, 8, 9, 8, ... (OEIS数列 A005245

复杂度为1, 2, 3, ...的最小整数分别是

1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, 47, ... (OEIS数列A005520

参考

  1. ^ Weisstein, Eric W. (编). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 

外部链接