wu :: forums
wu :: forums - Strange Recursion

Welcome, Guest. Please Login or Register.
Jan 20th, 2019, 3:21pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   medium
(Moderators: Eigenray, towr, SMQ, Icarus, ThudnBlunder, william wu, Grimbal)
   Strange Recursion
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Strange Recursion  (Read 5067 times)
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Strange Recursion  
« on: Oct 5th, 2003, 7:14am »
Quote Quote Modify Modify

Define F(n) thus:
 
F(n) = n - F(F(n-1)); F(0) = 0
 
What is F(100000000)?
 
IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13654
Re: Strange Recursion  
« Reply #1 on: Oct 5th, 2003, 10:17am »
Quote Quote Modify Modify

I get ::61803399::
 
It seems f(n)/n converges to a rather interesting number..
« Last Edit: Oct 5th, 2003, 10:29am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Strange Recursion  
« Reply #2 on: Oct 6th, 2003, 2:00am »
Quote Quote Modify Modify

I got the same answer as towr; and the same interesting number... Also, it has something to do with a very famous number sequence. I believe I can give a proof.
 
Very nice problem, THUDandBLUNDER!
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13654
Re: Strange Recursion  
« Reply #3 on: Oct 6th, 2003, 5:26am »
Quote Quote Modify Modify

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: You can use the Zeckendorf representation of the number
 
Of course you can get the answer even more easily by approximation, once you know what F(n)/n converges to.
« Last Edit: Oct 6th, 2003, 5:26am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Strange Recursion  
« Reply #4 on: Oct 6th, 2003, 11:22am »
Quote Quote Modify Modify

on Oct 6th, 2003, 5:26am, towr wrote:
hint:

Exactly! That's how I did it. In fact: 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.

 
on Oct 6th, 2003, 5:26am, towr wrote:
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).

I think, at least time should be logarithmic in n.
« Last Edit: Oct 6th, 2003, 11:22am by Barukh » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13654
Re: Strange Recursion  
« Reply #5 on: Oct 6th, 2003, 12:59pm »
Quote Quote Modify Modify

on Oct 6th, 2003, 11:22am, Barukh wrote:

I think, at least time should be logarithmic in n.
You have to create the whole table (up to some point), and look up the two values in each step.
 
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)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Strange Recursion  
« Reply #6 on: Oct 7th, 2003, 3:32am »
Quote Quote Modify Modify

on Oct 6th, 2003, 12:59pm, towr wrote:
Of course I'm open to suggestions if you can get a better performance than the linear algorithm..

Here's the version that does it in logarithmic time (and space) for a given number n:
Code:
int F(n)
{
  int f[2*log(n)];
 
  int F_n, i;
 
  f[0] = 0; f[1] = 1;
  for (i = 1; f[i] + f[i-1] < n; i++) f[i+1] = f[i-1] + f[i];
 
  for (F_n = 0; n; i--) if (n >= f[i]) { F_n += f[i-1]; n -= f[i]; i--; }
 
  return F_n;
}

on Oct 6th, 2003, 12:59pm, towr wrote:
(Not including the approxitive method that gives it in constant time, which isn't trivial to prove correct)

Again, I believe I've got the proof.
« Last Edit: Oct 11th, 2003, 5:31am by Barukh » IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13654
Re: Strange Recursion  
« Reply #7 on: Oct 7th, 2003, 5:34am »
Quote Quote Modify Modify

on Oct 7th, 2003, 3:32am, Barukh wrote:

Here's the version that does it in logarithmic time (and space) for a given number n:
Nice. I hadn't thought about implementing it that way. Even though that's how I solved it originally Tongue
 
Quote:
Again, I believe I've got the proof.
I believe you, but I'm sure it's not trivial Wink (well, not to me anyway)
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Strange Recursion  
« Reply #8 on: Oct 9th, 2003, 10:16am »
Quote Quote Modify Modify

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 .
IP Logged
Barukh
Uberpuzzler
*****






   


Gender: male
Posts: 2276
Re: Strange Recursion  
« Reply #9 on: Oct 11th, 2003, 6:18am »
Quote Quote Modify Modify

At last! Here's the proof.
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 its true upto k, then for every m > k, F(fk + fm) = fk-1 + fm-1, and according to 2):
F(fk + fm + fk-1 + fm-1) = F(fk+1 + fm+1) = fk + fm.

5. Generalize 4) to a sum of arbitrary number of fk's.

 Shocked
« Last Edit: Oct 11th, 2003, 6:22am by Barukh » IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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