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: https://pastebin.com/SRxh3pDT

    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:

    10101110101010111010
    01000000000000000000
    10101110101110101111
    00010000000000000000
    10101010101010101110
    10100100101110110101
    10101010101010101010
    00000001000000000000
    10101110101110101110
    00000000010000000000
    10101110101010111010
    00100100100100100100
    10101110101010101011
    00000000000001000000
    10101110101110101110
    10000100001000010000
    10101010101010101010
    00101100100100100100
    10101010101010101010
    00100100000010000001
    
  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:

WordPress.com Logo

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

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: