📑 Table of Contents▼

在数论中， 一个整数的整数复杂度（英語：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. （英语）. 

外部連結

编辑

📚 Artikel Terkait di Wikipedia

卡普的二十一個NP-完全問題

布爾可滿足性問題（Satisfiability）：對於布爾邏輯內合取範式方程式的滿足性問題（一般直接叫做SAT） 0-1整數規劃（0-1 integer programming） 分團問題（Clique，參考獨立集） Set packing（Set packing） 最小顶点覆盖问题（Vertex

组合优化

doi:10.1016/j.omega.2015.01.006. （原始内容存档 (PDF)于2019-12-26）.  Beasley, J. E. Integer programming (lecture notes). [2022-10-16]. （原始内容存档于2022-10-16）.  Cook,

−2

Encyclopedia of Integer Sequences. OEIS Foundation.  Koiran, Pascal. Valiant’s model and the cost of computing integers. computational complexity (Springer)

P/NP问题

average-case complexity", p. 134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995. Tentative program for the workshop on "Complexity and Cryptography:

L符號

最早出現L符號的文獻為卡爾·帕梅朗斯所著的論文《一些整數分解演算法的分析與比較》（Analysis and comparison of some integer factoring algorithms）。在此論文中，L符號的參數只有 c {\displaystyle c} ，其中的 α {\displaystyle

Python

yields a result with the same sign as its second operand (or zero); …… The integer division and modulo operators are connected by the following identity:

圓周率

拉马努金-佐藤级数（英语：Ramanujan–Sato series）。 2006年，加拿大数学家西蒙·普勞夫利用PSLQ整数关系算法（英语：integer relation algorithm）按照以下模版生成了几條计算π的新公式： π k = ∑ n = 1 ∞ 1 n k ( a q n −

根基

Encyclopedia of Integer Sequences. OEIS Foundation.  Adleman, Leonard M.; McCurley, Kevin S. Open Problems in Number Theoretic Complexity, II. Algorithmic