|
||||||
Title: Strange Recursion Post by THUDandBLUNDER on Oct 5th, 2003, 7:14am Define F(n) thus: F(n) = n - F(F(n-1)); F(0) = 0 What is F(100000000)? |
||||||
Title: Re: Strange Recursion Post by towr on Oct 5th, 2003, 10:17am I get ::[hide]61803399[/hide]:: It seems f(n)/n converges to a rather interesting number.. |
||||||
Title: Re: Strange Recursion Post by Barukh on Oct 6th, 2003, 2:00am I got the same answer as towr; and the same interesting number... Also, it has something to do with [hide]a very famous number sequence[/hide]. I believe I can give a proof. Very nice problem, THUDandBLUNDER! |
||||||
Title: Re: Strange Recursion Post by towr on Oct 6th, 2003, 5:26am I have to be honest though, I looked up the sequence, and how to get the answer more easily. I had first tried mathematica, but it wanted to do it the hard way which took too long. And programming it more efficiently would take too much memory (even though it's then linear in both time and space, which isn't overall bad). hint: [hide]You can use the Zeckendorf representation of the number[/hide] (http://mathworld.wolfram.com/ZeckendorfRepresentation.html) Of course you can get the answer even more easily by approximation, once you know what F(n)/n converges to. |
||||||
Title: Re: Strange Recursion Post by Barukh on Oct 6th, 2003, 11:22am on 10/06/03 at 05:26:03, towr wrote:
Exactly! That's how I did it. In fact: [hide] if Z is the Zeckendorf Representation (ZR) of n, then the ZR of F(n) is Z shifted one position to the right. The steps of the proof are as follows: 1) F(n+1) - F(n) = 0 or 1. 2) If F(n) = k, then F(n+k) = n. [/hide] on 10/06/03 at 05:26:03, towr wrote:
I think, at least time should be logarithmic in n. |
||||||
Title: Re: Strange Recursion Post by towr on Oct 6th, 2003, 12:59pm on 10/06/03 at 11:22:17, Barukh wrote:
to create the table up to some n: int F[n] F[0] = 0; for(int i=1; i < n; i++) F[i] = i - F[F[i-1]; This is linear, the same number of operations in each step; which is much better than the recursive function: int f(int i) { if (!i) return 0; else return i - f(f(i-1)); } this is exponential, I think. The evaluation tree grows fast with i. (But I haven't done a proper analysis, suffice it to say it's much worse) Of course I'm open to suggestions if you can get a better performance than the linear algorithm.. (Not including the approxitive method that gives it in constant time, which isn't trivial to prove correct) |
||||||
Title: Re: Strange Recursion Post by Barukh on Oct 7th, 2003, 3:32am on 10/06/03 at 12:59:05, towr wrote:
Here's the version that does it in logarithmic time (and space) for a given number n: Code:
on 10/06/03 at 12:59:05, towr wrote:
Again, I believe I've got the proof. |
||||||
Title: Re: Strange Recursion Post by towr on Oct 7th, 2003, 5:34am on 10/07/03 at 03:32:18, Barukh wrote:
Quote:
|
||||||
Title: Re: Strange Recursion Post by Barukh on Oct 9th, 2003, 10:16am Oops... I've found a flaw in the proof I believed I had! So, currently I don't have a proof. I also corrected the code . |
||||||
Title: Re: Strange Recursion Post by Barukh on Oct 11th, 2003, 6:18am At last! Here's the proof. [hide]Denote fk the k-th Fibonacci number. Then the following statement answers the question: If n = fk + fm + … + fs is represented as a sum of distinct Fibonacci numbers, 2 [le] k < m < … < s, then F(n) = fk-1 + fm-1 + … + fs-1. The proof is comprised of a number of steps. 1) For every n > 0, F(n) – F(n-1) = 0, or F(n) – F(n-1) = 1. Use induction by n: a. F(1) – F(0) = 1. b. F(n+1) – F(n) = F(F(n-1)) - F(F(n)) + 1. Now, if F(n) = F(n-1), then F(n+1) – F(n) = 1; if F(n) = k = F(n-1) + 1, then F(n+1) – F(n) = F(k) – F(k+1) + 1 = 0 or 1. 2) For every n > 0, if F(n) = k, then F(n+k) = n. Again, use induction by n: a. F(1) = 1, and F(2) = 1. b. Let F(n+1) = k. According to 1), F(n) = k or k-1. If F(n) = k, then F(n+k) = n, and F(n+k+1) = n+k+1 – F(n) = n+1. If F(n) = k-1, then F(n+k-1) = n, so that F(n+k) = n+k – F(n) = n, and F(n+k+1) = n+k+1 – F(n) = n+1. 3) For every k [ge] 2, F(fk) = fk-1. This is proved using 2) and induction by k. 4) For every pair 2 [le] k < m, F(fk + fm) = fk-1 + fm-1. Use induction on k: a. For every m > 2, F(fm + f2) = F(fm + 1) = fm + 1 – F(fm-1) = fm + 1 - fm-2 = fm-1 + 1 = fm-1 + f1 (uses 3) two times). b. Assume it’s true upto k, then for every m > k, F(fk + fm) = fk-1 + fm-1, and according to 2): 5. Generalize 4) to a sum of arbitrary number of fk's.[/hide] :o |
||||||
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |