All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Infinite Binary Tree (Posted on 2013-04-11) Difficulty: 4 of 5

Let CW be an infinite binary tree where each node
has exactly two child nodes designated left and
right. If a node contains the fraction i/j, then
the left child node contains the fraction i/(i+j)
and the right child node contains the fraction
(i+j)/j. The root node contains the fraction 1/1.

If we did a breadth first search of CW, then we 
would encounter the fractions 

   1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...

in that order. If we designate this sequence as
{an}, then prove that it can be 
generated by the following formula:

   ak+1 = 1/(2⌊ak⌋ - ak + 1) 

where a1 = 1/1 and ⌊ak⌋ is the integer part of ak.

See The Solution Submitted by Bractals    
No Rating

Comments: ( You must be logged in to post comments.)
  Subject Author Date
There are no comments yet.
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information