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.
Programming Praxis 
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!
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 aFrom the output array, its easy to read off all the triples, so for lo = 100, hi = 120:
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.