Hide

Problem C
Common Factors

/problems/commonfactors/file/statement/en/img-0001.jpg
Photo by Bob Chao

Everyone likes to share things in common with other people.

Numbers are the same way! Numbers like it when they have a factor in common.

For example, 4 and 6 share a common factor of 2, which gives them something to talk about.

For a given integer n, we define a function, f(n), equal to the number of integers in the range [1,n] that share a common factor greater than 1 with n.

Furthermore, we can define a second function, g(n), which characterizes the fraction of numbers that like a given number as follows: g(n) = f(n)n

What we really want to know though, is, for any integer 2kn, what is the maximum value of g(k)?

Input

The input consists of a single integer n (2n1018), the value of n for the input case.

Output

For the provided test case, output the result as a fraction, in lowest terms, in the form p/q where the greatest common divisor of p and q is 1.

Sample Input 1 Sample Output 1
10
2/3
Sample Input 2 Sample Output 2
100
11/15
Hide

Please log in to submit a solution to this problem

Log in