Problem K
A Rational Sequence (Take 3)
A sequence of positive rational numbers is defined as follows:
An infinite full binary tree labeled by positive rational numbers is defined by:
-
The label of the root is
. -
The left child of label
is . -
The right child of label
is .
The top of the tree is shown in the following figure:
![\includegraphics[]{f1.png}](/problems/rationalsequence3/file/statement/en/img-0001.png)
The sequence is defined by doing a level order (breadth first) traversal of the tree (indicated by the light dashed line). So that:
Write a program to compute the
Input
The first line of input contains a single integer
Output
For each data set there is a single line of output. It
contains the data set number,
Sample Input 1 | Sample Output 1 |
---|---|
4 1 1 2 4 3 11 4 1431655765 |
1 1/1 2 1/3 3 5/2 4 2178309/1346269 |