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

User Rankings
Search for User
Add to Google delicious Add to del.icio.us

More ways to get Braingle...
rss

Braingle Time
9:11 am

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.

   
rec.puzzles
Newsgroup
FAQ
Hall of Fame
alt.brain.teasers
Newsgroup
FAQ
Categories : 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. )




Solution


Users in Chat : sciencesteven 

Online Now: 14 users and 527 guests

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

Custom Search





Sign In A Create a free account