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