From: cliff@watson.ibm.com (cliff)
Subject: Cliff Puzzle 17: Weird Recursive Sequence
Date: Fri, 06 Nov 1992 16:03:58 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: A

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. )                                           
                                                                                
                                                                                
Newsgroups: rec.puzzles