==> pickover/pickover.17.p <==
Title: Cliff Puzzle 17: Weird Recursive Sequence
From: cliff@watson.ibm.com
If you respond to this puzzle, if possible please send me your name,
address, affiliation, e-mail address, so I can properly credit you if
you provide unique information. PLEASE ALSO directly mail me a copy of
your response in addition to any responding you do in the newsgroup. I
will assume it is OK to describe your answer in any article or
publication I may write in the future, with attribution to you, unless
you state otherwise. Thanks, Cliff Pickover
* * *
Consider the simple yet weird recursive formula
a(n) = a(a(n-1)) + a(n-a(n-1))
The sequences starts with a(1) = 1, and a(2) = 1. The "future" values
at higher values of n depend on past values in intricate recursive ways.
Can you determined the third member of the sequence? At first, this may
seem a little complicated to evaluate, but you can being slowly, by
inserting values for n, as in the following:
a(3) = a(a(2)) + a(3-a(2))
a(3) = a(1) + a(3-1) =
a(3) = 1+1 = 2
Therefore, the 3rd value of the sequence a(3) is 2.
The sequence a(n) seems simple enough: 1, 1, 2, 2, 3, 4, 4, 4, 5, ...
Try computing a few additional numbers. Can you find any interesting
patterns? The prolific mathematician John H Conway presented this
recursive sequence at a recent talk entitled "Some Crazy Sequences." He
noticed that the value a(n)/n approaches 1/2 as the sequence grows and n
becomes larger. Can you find a value, N, above which the sequence the
value of a(n)/n is always within 0.05 of the value 1/2? (In other
words,
.eq vbar a(n)/n -1/2 vbar lt 0.05.
The bars indicate the absolute value.)
A difficult problem? you ask.
John Conway offered $10,000 to the person to find the s-m-a-l-l-e-s-t
such N. A month after Conway made the offer, Colin Mallows of AT&T
solved the $10,000 question: N = 3,173,375,556. Manfred Shroeder has
noted that the sequence is "replete with appealing self-similarities
that contain the clue to the problem's solution." Can you find any
self-similarities? As I write this, no-one on the planet has found a
value for the smallest N such that a(n)/n is always within 0.01 of the
value 1/2.
.eq (vbar a(n)/n -1/2 vbar lt 0.01. )