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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: