整数复杂度

维基百科,自由的百科全书
跳到导航 跳到搜索

数论中, 一个整数整数复杂度是用最少数量1的算式來表達此整數,可以使用任何数量的 加法乘法与括号,最後算式中出現1的個數即為整数复杂度。

[编辑]

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

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

然而,采用7个1或更少没有办法表示它。 因此,其复杂度就是是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

外部連結[编辑]