Compatible Numbers

January 5, 2016

Two numbers are compatible if they have the same prime factors, though with possibly different multiplicities.

Your task is to write a program to determine if two numbers are compatible. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

2 Responses to “Compatible Numbers”

  1. Learning a new language (Perl6) – so thought I’d try and solve it in that … syntactically it is a bit terse

    sub compatible($a,$b) {
      return (2..sqrt($a <$b??$a!!$b))
        .grep(&is-prime).
        .first(sub a($i){$a%$i&&$b%%$i||$a%%$i&&$b%$i})
        .WHICH eq 'Nil'
    }
    

    Notes:
    * $a??$b!!$c is perl6’s ternary operator
    * $a%%$b returns true if $a is a multiple of $b
    * first returns the first entry for which the condition is true o/w returns an object of type “Nil” which is an empty list
    * WHICH returns the type of the object…

  2. Paul said

    In Python.

    def is_compatible(a, b):
        if a < 2 or b < 2:
            raise ValueError("a and b should be larger than 1")
    
        def reduce(a, g):
            while g != 1:
                a //= g
                g = gcd(g, a)
            return a
        gg = gcd(a, b)
        return 1 == reduce(a, gg) == reduce(b, gg)
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: