整數複雜度

在數論中， 一個整數的整數複雜度（英語：Integer complexity）是用最少數量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）

外部連結

• 計算整數複雜度的MATLAB代碼 （頁面存檔備份，存於互聯網檔案館）
• 解釋以上MATLAB代碼的原版文章
• 2019年更新的C與Python計算代碼