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

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Coprime Numbers”

  1. Zack said
    January 17, 2020 at 10:19 AM

    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
    January 18, 2020 at 8:55 AM

    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
    February 11, 2020 at 1:07 PM

    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.

Leave a comment