Coprime Numbers

January 17, 2020

This exercise comes from CodeForces:

Given two natural numbers lo < hi, find a triple (a, b, c) such that a is coprime to b, b is coprime to c, and a is not coprime to c, or indicate that no such triple exists. If there is more than one such triple, you may return any of them. Two numbers are coprime if their greatest common divisor is 1. Lo and hi will be less than 1018 and differ by no more than 50.

Your task is to find a triple satisfying the conditions above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

3 Responses to “Coprime Numbers”

  1. Zack said

    Although not stated, it is assumed that a, b, and c are within the [lo, hi] interval, otherwise the lo and hi parameters are irrelevant.

    Anyway, here is my take on it in Julia:

    Worst case scenario, this script is not optimal for performance as it has a O(n^3). However, given that the range we work with is no more than 50, it is an acceptable compromise.

    Have a nice weekend!

  2. matthew said

    As @praxis says, it’s easy to find a single triple that satisfies the given condition – to make things more interesting, let’s consider finding all such triples. This Python function generates an n x n boolean array, where n = hi-lo, indicating coprimality (0 for coprime, 1 for not coprime). Two numbers are not coprime if they have a common prime factor, in which case the common factor must be less than or equal to the difference of the two numbers, so we can just generate all primes p up to n and mark off all multiples of p as not being coprime:

    from sympy import sieve
    import numpy as np
    def triples(lo,hi):
        n = hi-lo
        a = np.identity(n,np.bool)
        primes = sieve.primerange(2,n)
        for p in primes:
            start = (lo+p-1)//p*p - lo
            for i in range(start,n,p):
                for j in range(start,i,p):
                    a[i,j] = a[j,i] = 1
        return a

    From the output array, its easy to read off all the triples, so for lo = 100, hi = 120:

  3. Richard A. O'Keefe said

    Consider lo=10 hi=11.
    Reading the specification, it appears that
    a=10 b=11 c=10 and
    a=11 b=10 c=11
    are solutions. Since b is coprime to a and c, it cannot be equal to either, but I can find nothing in the specification that forbids a=c.
    So whenever a, b > 1 and a, b are coprime, (a,b,a) is a solution.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: