Usenet Newsgroups : rec.puzzles Hall of FameThe 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. 

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, email 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(n1)) + a(na(n1)) 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(3a(2)) a(3) = a(1) + a(31) = 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 smallest 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 selfsimilarities that contain the clue to the problem's solution." Can you find any selfsimilarities? As I write this, noone 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