## 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.