==> 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. )