主题
Search

Hofstadter-Conway $10,000 序列

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

由 递归序列 定义的 递推关系

a(n)=a(a(n-1))+a(n-a(n-1))
(1)

其中 a(1)=a(2)=1。 前几个值为 1, 1, 2, 2, 3, 4, 4, 4, 5, 6, ... (OEIS A004001; Wolfram 2002, pp. 129-130, 序列 (c))。Conway (1988) 证明了 lim_(n->infty)a(n)/n=1/2 并悬赏 $10000 给发现值 n 的人，使得对于 |a(i)/i-1/2|<1/20 对于 i>n 成立。该奖金随后被 Mallows 领取，在调整为 Conway “预期”的奖金 $1000 (Schroeder 1991) 之后，他找到了 n=1489。

HofstadterConwaySequence

上图显示了 a(n)/n (左图) 和 a(n)-n/2 (右图)。 令人惊讶的是，a(n)-n/2 揭示了它自身由一系列越来越大的 batrachion Blancmange 函数版本组成。

a(n)/n 对于 n 形式 2^k 的 k=1, 2, .... 值，取值为 1/2。更一般地，

a(2^k)=2^(k-1)
(2)

并且

a(2n)<=2a(n).
(3)

Pickover (1995) 给出了 n 的类似值的表格，对应于不同的 |a(n)/n-1/2|<e 值。

HofstadterConway2

一个相关的混沌序列由 递推方程 给出

b(n)=b(b(n-1))+b(n-b(n-2)-1)
(4)

其中 b(1)=b(2)=1，这给出了序列 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 8, 8, 8, ... (OEIS A055748; Pinn 2000; Wolfram 2002, pp. 129-130, 序列 (g))。

另请参阅

Blancmange 函数, Hofstadter Q 序列, Mallows 序列

使用 Wolfram|Alpha 探索

参考文献

Bloom, D. M. "Newman-Conway Sequence." Solution to Problem 1459. Math. Mag. 68, 400-401, 1995.Conolly, B. W. "Meta-Fibonacci Sequences." 在 Fibonacci and Lucas Numbers, and the Golden Section (编 S. Vajda). New York: Halstead Press, pp. 127-138, 1989.Conway, J. "Some Crazy Sequences." Lecture at AT&T Bell Labs, July 15, 1988.Guy, R. K. "Three Sequences of Hofstadter." §E31 在 Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 231-232, 1994.Kubo, T. and Vakil, R. "On Conway's Recursive Sequence." Disc. Math. 152, 225-252, 1996.Mallows, C. L. "Conway's Challenge Sequence." Amer. Math. Monthly 98, 5-20, 1991.Pickover, C. A. "The Drums of Ulupu." 在 Mazes for the Mind: Computers and the Unexpected. New York: St. Martin's Press, 1993.Pickover, C. A. "The Crying of Fractal Batrachion 1489." Ch. 25 在 Keys to Infinity. New York: W. H. Freeman, pp. 183-191, 1995.Pickover, C. A. "The Crying of Fractal Batrachion 1489." Comput. & Graphics 19, 611-615, 1995. Reprinted in Chaos and Fractals, A Computer Graphical Journey: Ten Year Compilation of Advanced Research (编 C. A. Pickover). Amsterdam, Netherlands: Elsevier, pp. 127-131, 1998.Pinn, K. "A Chaotic Cousin of Conway's Recursive Sequence." Exp. Math. 9, 55-66, 2000.Schroeder, M. "John Horton Conway's 'Death Bet.' " Fractals, Chaos, Power Laws. New York: W. H. Freeman, pp. 57-59, 1991.Sloane, N. J. A. Sequences A004001/M0276 and A055748 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, pp. 129-130, 2002.

在 Wolfram|Alpha 中被引用

Hofstadter-Conway $10,000 序列

引用为

Weisstein, Eric W. "Hofstadter-Conway $10,000 序列。" 来自 MathWorld-- Wolfram Web 资源。 https://mathworld.net.cn/Hofstadter-Conway10000-DollarSequence.html

主题分类