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