Problem A: Cantor Fractions II

In the late XIXth century the German mathematician George Cantor argued that the set of positive fractions $\mathbb{Q}^+$ is equipotent to the set of positive integers $\mathbb{N}$ , meaning that they are both infinite, but of the same class. To justify this, he exhibited a one-to-one mapping from $\mathbb{N}$ to $\mathbb{Q}^+$ .

To exhibit such a mapping, consider a traversal of the $\mathbb{N}\times\mathbb{N}$ plane that covers all the pairs:

$\includegraphics{mapping}$

The first pairs in this traversal are:

$\begin{displaymath}(1,1),\; (2,1),\; (1,2),\; (3,1),\; (2,2),\; (1,3),\; \cdots\end{displaymath}$

It is clear that this traversal will generate all pairs $(p,q)\in\mathbb{N}\times\mathbb{N}$ ; however, it will also generate several pairs that correspond to the same fraction

(for example: the first and fifth pairs in the example above). To obtain a one-to-one mapping it suffices to skip pairs corresponding to fractions that appeared previously. Thus our one-to-one mapping would be:

$\begin{displaymath}\underbrace{1/1,}_{\mbox{1st}}\; \underbrace{2/1,}_{\mbox{2nd... ...}_{\mbox{skipped}}\; \underbrace{1/3,}_{\mbox{5th}}\; \cdots \end{displaymath}$

Problem

Write a program that finds the -th Cantor fraction following the one-to-one mapping outlined above.

Input specification

The inputs consists of a positive integer number , with $1 \leq i\leq 100\,000$ .

Output specification

The output consists of the -th fraction, with numerator and denominator separated by a slash (/). The fraction should be presented in the simplest form, but always with a denominator (even if it is the unit).

Sample input

Sample output

1/3

ACM Programming Contest -- SWERC'2001 practice-session -- University of Porto, Portugal