主题
Search

整数复杂度

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
ComplexityNumber

整数 n 的复杂度 c_n 是使用 加法、乘法 和 括号 表示它所需的最少 1 的个数。例如，数字 1 到 10 可以最小化地表示为

1=1
(1)
2=1+1
(2)
3=1+1+1
(3)
4=(1+1)(1+1)
(4)
=1+1+1+1
(5)
5=(1+1)(1+1)+1
(6)
=1+1+1+1+1
(7)
6=(1+1)(1+1+1)
(8)
7=(1+1)(1+1+1)+1
(9)
8=(1+1)(1+1)(1+1)
(10)
9=(1+1+1)(1+1+1)
(11)
10=(1+1+1)(1+1+1)+1
(12)
=(1+1)(1+1+1+1+1),
(13)

因此，n=1, 2, ..., 的复杂度为 1, 2, 3, 4, 5, 5, 6, 6, 6, 7, 8, 7, 8, ... (OEIS A005245)。

复杂度为 n=1, 2, ... 的最小数字是 1, 2, 3, 4, 5, 7, 10, 11, 17, 22, 23, 41, ... (OEIS A005520)。

另请参阅

复杂度

使用 Wolfram|Alpha 探索

参考文献

Guy, R. K. "用 1 表示数字。" §F26 in 数论中未解决的问题，第 2 版。 纽约：施普林格出版社，第 263 页，1994 年。Guy, R. K. "一些可疑的简单序列。" 美国数学月刊 93, 186-190, 1986.Guy, R. K. "月度未解决问题，1969-1987。" 美国数学月刊 94, 961-970, 1987.Guy, R. K. "未解决的问题走向成熟。" 美国数学月刊 96, 903-909, 1989.Pegg, E. Jr. "数学游戏：整数复杂度。" 2004 年 2 月 12 日。 http://www.maa.org/editorial/mathgames/mathgames_04_12_04.html. Pegg, E. Jr. "整数复杂度。" http://library.wolfram.com/infocenter/MathSource/5175/.Rawsthorne, D. A. "需要多少个 1？" 斐波那契季刊 27, 14-17, 1989.Sloane, N. J. A. 序列 A005245/M0457 和 A005520/M0523 在 "整数序列在线百科全书" 中。Wolfram, S. 一种新科学。 伊利诺伊州香槟市：Wolfram Media, 第 916 页, 2002.

在 Wolfram|Alpha 上被引用

整数复杂度

请引用为

韦斯坦因，埃里克·W. "整数复杂度。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/IntegerComplexity.html

主题分类