Another variation on Conway's recursive sequence

详细信息	查看全文 | 推荐本文 |

• 作者：Grytczuk ; Jaroslaw
• 关键词：primary 05C38 ; 15A15 ; secondary 05A15 ; 15A18 ; Conway's recursive sequence ; Guided sparse substitution ; Pascal triangle ; Strange recurrence
• 刊名：Discrete Mathematics
• 出版年：2004
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：May 6, 2004
• 卷：282
• 期：1-3
• 页码：149-161
• 文件大小：283 K

摘要

We study a sequence defined by the strange recurrence formula A(n)=A(A(A(n−1)))+A(n−A(A(n−1))), with A(1)=A(2)=1. Like its father, the famous Conway sequence C(n)=C(C(n−1))+C(n−C(n−1)), C(1)=C(2)=1, A(n) conceals surprisingly rich combinatorial structure. For instance, we show that the associated binary string of first differences of A(n) can be factorized into segments forming successive diagonals of a Pascal-like triangle, defined by concatenation of words in a familiar recursive way. This combinatorial description can be used to explain many unexpected properties of the sequence such as shifting of Fibonacci numbers, expressed by the formula A(F_n+1)=F_n. Our approach is based on a special operation on words, called Guided Sparse Substitution which appeared earlier in the work of Andrasiu et al. (Theoret. Comput. Sci. 116 (1993) 339) on Cryptosystem Richelieu. This striking connection leads to new exciting generalizations and many open problems which are presented in the conclusion of the paper.