wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> An Interesting Recursion
        
(Message started by: ThudanBlunder on Nov 26^th, 2008, 9:30am)

Title: An Interesting Recursion
Post by ThudanBlunder on Nov 26^th, 2008, 9:30am

Consider the recursive formula a(n) = a(a(n-1)) + a(n - a(n-1))

1) What is a(3)?

2) When does a(n)/n equal 0.5?

3) What is the least value of n such that http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vert.gifa(n)/n - 0.5http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/vert.gif < 0.05 for all greater n?

Title: Re: An Interesting Recursion
Post by towr on Nov 26^th, 2008, 10:08am

For a(n)=0
1) 0
2) never,
3) doesn't exist

Title: Re: An Interesting Recursion
Post by SMQ on Nov 26^th, 2008, 10:12am

What's the base case for the recursion?

My first thoughts are that in order for the recursion to be evaluated straightforwardly, 0 < a(n) <= n. If a(n-1) <= 0 for some n, then n - a(n-1) >= n, and a(n - a(n-1)) is unknown; likewise if a(n-1) > n-1 for some n then a(a(n-1)) is unknown.

Moreover, assuming the field of integers, 0 < a(n) <= n implies a(1) = 1; but if a(1) = 1, than a(2) = 2 and a(n) = a(n-1) + a(1) = n for all positive integer n.

--SMQ

Title: Re: An Interesting Recursion
Post by ThudanBlunder on Nov 26^th, 2008, 10:14am

on 11/26/08 at 10:08:14, towr wrote:

For a(n)=0

Oh yes, a(1) = a(2) = 1

I always forget something. ::)

Title: Re: An Interesting Recursion
Post by towr on Nov 26^th, 2008, 10:28am

Ah, well, in that case.
1) [hide]2[/hide]
2) [hide]for any n=2^k[/hide]
3) no idea there

Title: Re: An Interesting Recursion
Post by ThudanBlunder on Dec 4^th, 2008, 4:09pm

Mathworld (http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html) has a page about this batrachion.