for d = 1 to infinity do for n = 0 to d do if gcd(n,d) = 1 then print n/dwhere
gcd(n,d)
is the greatest common divisor of n and d.
For example, the start of the sequence looks like:
0/1, 1/1, 1/2, 1/3, 2/3, 1/4, 3/4, 1/5, 2/5, 3/5, 4/5, 1/6, 5/6, 1/7, ...
The input consists of a series of test cases. Each test case consists of a single integer 1 ≤ k ≤ 12,158,598,919. Input is terminated by 0; this case should not be processed.
For each test case, output the kth fraction
that would be printed by the program above in the format n/d
.
1 2 3 12158598919 0
0/1 1/1 1/2 199999/200000