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

        riddles >> hard >> Evaluate f(1,000,000,000,000)
        
(Message started by: pcbouhid on Nov 18th, 2005, 9:02am)
Title: Evaluate f(1,000,000,000,000)
Post by pcbouhid on Nov 18th, 2005, 9:02am
If f(0) = 0,

and for n>0,  f(n) = n - f(f(n-1)),

what is the value of f(1,000,000,000,000)?
Title: Re: Evaluate f(1,000,000,000,000)
Post by JocK on Nov 18th, 2005, 9:49am
My first guess would be:

f(n) = [hide]round( phi *n + phi2/(2 + phi) ) with  round(..) denoting rounding to the nearest integer and phi = (-1+sqrt(5))/2,  the golden ratio)...[/hide]

but need to think a bit further (after all, a hard problem is unlikely to be solved within an hour...  :-/ )
Title: Re: Evaluate f(1,000,000,000,000)
Post by Barukh on Nov 18th, 2005, 12:23pm
I remember seeing it somewhere...

Aha! It's under Strange Recursion (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1065363259;start=0#0) thread.
Title: Re: Evaluate f(1,000,000,000,000)
Post by Deedlit on Nov 26th, 2005, 3:16pm

on 11/18/05 at 09:49:13, JocK wrote:
My first guess would be:

f(n) = [hide]round( phi *n + phi2/(2 + phi) ) with  round(..) denoting rounding to the nearest integer and phi = (-1+sqrt(5))/2,  the golden ratio)...[/hide]

but need to think a bit further (after all, a hard problem is unlikely to be solved within an hour...  :-/ )


It's actually simpler than that - it's just
[hide]f(n) = [phi (n + 1)], although I think the reciprical definition of phi is more common, in which case it's f(n) = [(n + 1) / phi][/hide]
Title: Re: Evaluate f(1,000,000,000,000)
Post by JocK on Nov 26th, 2005, 11:37pm
You're right, although for the answer it doesn't matter:

Round(618,033,988,750.041) = [618,033,988,750.513] = 618,033,988,750


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board