Brain Teasers
Brain Teasers Trivia Mentalrobics Games Community
Personal Links
Your Friends
More Community
Teaser Comments
Trivia Comments

User Rankings
Search for User
Add to Google delicious Add to

More ways to get Braingle...

Braingle Time
11:06 pm

Usenet Newsgroups : rec.puzzles Hall of Fame

The rec.puzzles Hall of Fame is a compilation of over 500 of the most popular puzzles that have been posted and discussed in the rec.puzzles newsgroup. In most cases a detailed solution has been provided.

Many of these puzzles also appear in Braingle's own collection.

Hall of Fame
Categories : pickover : pickover.17.p

Title: Cliff Puzzle 17: Weird Recursive Sequence

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


Users in Chat : HarryPutter, The_Spider 

Online Now: 4 users and 435 guests

Copyright © 1999-2014 | Updates | FAQ | RSS | Widgets | Links | Green | Subscribe | Contact | Privacy | Conditions | Advertise

Custom Search

Sign In A Create a free account