From: cliff@watson.ibm.com (cliff) 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 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. ) From: kubo@zariski.harvard.edu (Tal Kubo) In article <1992Nov06.160358.101157@watson.ibm.com> cliff@watson.ibm.com (cliff pickover) writes: >a(n) = a(a(n-1)) + a(n-a(n-1)) >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? >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. This is incorrect. Mallows did solve the problem, but his answer is not the number you list above. See his article in the January 1991 issue of American Mathematical Monthly. >Manfred Shroeder has noted that the sequence is "replete with appealing >self-similarities that contain the clue to the problem's solution." The sequence is connected with all of the following: variants of Pascal's triangle, the Gaussian distribution, combinatorial operations on finite sets, and Catalan numbers. Ravi Vakil and I have found a very simple characterization of a(n); as a corollary, we can state the exact asymptotic behavior, and have a simple algorithm to answer Conway's original problem, for any given upper bound. Anyone who would like to receive a copy of our paper (about 15 pages in AMSLaTex) should contact me by e-mail at the address below. By the way, did Schroeder make the above comment on Conway's sequence in his book on chaos and fractals? The sequence has rather smooth asymptotic behavior, and is anything but chaotic. >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. e Last n such that |a(n)/n - 1/2| > e ---- ---------------------------------------------------------- 1/20 1489 (found by Mallows in 1988) 1/30 758765 1/40 6083008742 (found by Mallows in 1988) 1/50 809308036481621 1/60 1684539346496977501739 1/70 55738373698123373661810220400 1/80 15088841875190938484828948428612052839 1/90 127565909103887972767169084026274554426122918035 1/100 8826608001127077619581589939550531021943059906967127007025 These values were found in a few minutes, using a Mathematica program running on a Sun 4. The program is about 15 lines long, and is available on request. -Tal Kubo kubo@math.harvard.edu or kubo@zariski.harvard.edu From: kubo@zariski.harvard.edu (Tal Kubo) In article clong@remus.rutgers.edu (Chris Long) writes: >In article <1992Nov06.160358.101157@watson.ibm.com>, Cliff Pickover writes: > >> 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. > >I recall reading somewhere that there was some question as to the >validity of Mallows's proof. Has it finally been accepted as correct? Where did you read that? I believe I am the only person who ever looked at the details of Mallows' method for determining the answer to Conway's question (they were not included in his published article). Therefore, I would be surprised if someone had claimed in print that Mallows' results were dubious, without bothering to check. In fact, his results are correct. Mallows' numerical results are as follows: the last n for which |a(n)/n - 1/2| > epsilon, is n=1489 for epsilon=1/20, and n = 6083008742 for epsilon=1/40. These values are reported in his article in the American Mathematical Monthly, January 1991, p. 5. His method of obtaining them is, strictly speaking, not a rigorous proof, since it relies on some assumptions about the behavior of the ratio a(n)/n. Also, he did not formalize his method into an algorithm; he only used it to find the above numbers. As a result of some work Ravi Vakil and I did on Conway's sequence, we have a simple and rapid algorithm to answer Conway's question for any given epsilon. (See the table of values in my previous posting on this thread). In particular, we can confirm Mallows' results. -Tal Kubo kubo@math.harvard.edu