## Coprime Numbers

### January 17, 2020

I mostly don’t like programming exercise web sites (I admit that is unusual, given that I write one!) because they too often rely on some kind of trick (yes, I do that too!); if you know the trick, the task is easy, otherwise it is hard. This exercise has a trick:

Given any natural number x, it is certainly coprime to x + 1. Also, two even numbers are never coprime, because they share a factor of 2. Thus, if lo is even, lo, lo + 1, and lo + 2 form a suitable triple, and if lo is odd, lo + 1, lo + 2, and lo + 3 form a suitable triple. This solution fails only if hi is too close to lo:

```(define (f lo hi)
(cond ((and (even? lo) (< 1 (- hi lo)))
(list lo (+ lo 1) (+ lo 2)))
((and (odd? lo) (< 2 (- hi lo)))
(list (+ lo 1) (+ lo 2) (+ lo 3)))
(else "No solution")))```
```> (f 2 4)
(2 3 4)
> (f 10 11)
"No solution"
> (f 900000000000000009 900000000000000029)
(900000000000000010 900000000000000011 900000000000000012)```

You can run the program at https://ideone.com/mTUKai.

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.