Hide
Problem F
Fractional Sequence
Consider the following increasing sequence, $S$, of rational numbers:
\[ 1,\; 2,\; 2\frac{1}{2},\; 3,\; 3\frac{1}{3},\; 3\frac{2}{3} ,\; 4,\; 4\frac{1}{4},\; 4\frac{1}{2},\; 4\frac{3}{4},\; 5,\; 5\frac{1}{5},\; 5\frac{2}{5},\; 5\frac{3}{5},\; 5\frac{4}{5},\; 6,\; \ldots . \]$S$ is composed of an infinite set of blocks, $N_1, N_2, N_3, \ldots $, where block $N_i$ is
\[ i,\; \; i+1/i,\; \; i+2/i,\; \; \ldots , \; \; i+(i-1)/i . \]So $S(1) = 1, S(2) = 2, S(3) = 2\frac{1}{2}$, etc. Write a program which takes as input an integer $n$ and outputs $S(n)$.
Input
Input is a single line containing an integer, $n$ ($1 \leq n \leq 4\cdot 10^9$).
Output
Output $S(n)$ as a single integer if the answer is a whole number. Otherwise, output the integer part, a single space and a proper fraction $a/b$ in lowest terms (i.e. $0 < a < b$ and $GCD(a,b) = 1$). See the sample outputs.
| Sample Input 1 | Sample Output 1 |
|---|---|
326 |
26 |
| Sample Input 2 | Sample Output 2 |
|---|---|
448 |
30 2/5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
4000000000 |
89443 19596/89443 |
