Perl Weekly Challenge 136: Two Friendly

First, we note that unless both numbers are even, they cannot be two-friendly. In order for a greatest common divisor to contain a factor of 2, but numbers need to have a factor of 2 — that is, both numbers need to be even.

If both numbers are even, we need to do two things: calculate the greatest common divisor, and determine whether a number is a power of 2.

Calculating the greatest common divisor is something we have done several times in previous weeks. So we will just copy its code.

For most languages, we use Stein's algorithm.

Here is Stein's algorithm in C:

long long gcd (long long u, long long v) {
    long long u_odd = u % 2;
    long long v_odd = v % 2;

    return u == v || !v     ? u
         :           !u     ? v
         : !u_odd && !v_odd ? gcd (u >> 1, v >> 1) << 1
         : !u_odd &&  v_odd ? gcd (u >> 1, v)
         :  u_odd && !v_odd ? gcd (u,      v >> 1)
         :  u     >   v     ? gcd (u - v,  v)
         :                    gcd (v - u,  u);
}

and here it is in Scheme:

(define (gcd u v)
    (define u_odd (= (modulo u 2) 1))
    (define v_odd (= (modulo v 2) 1))
    (cond ((= u v) u)
          ((= u 0) v)
          ((= v 0) u)
          ((and (not u_odd) (not v_odd)) (ash (gcd (ash u -1) (ash v -1)) 1))
          ((and (not u_odd)      v_odd)       (gcd (ash u -1)      v))
          ((and      u_odd  (not v_odd))      (gcd      u     (ash v -1)))
          ((> u v)                            (gcd (- u v) v))
          (else                               (gcd (- v u) u)))
)

A few languages don't have bit shifting operations. In those languages, we implemented a recursive version of Euclids algorithm.

As an example, we will show the implementation in Lua:

function gcd (a, b)
    if b >  a then return gcd (b, a) end
    if b == 0 then return a          end
                   return gcd (b, a % b)
end

To find out whether a number is a power of 2, we repeatedly divide that number by 2, until we cannot evenly the number by 2 again. If we end with the number being 1, the original was a power of 2. Otherwise, it is not.

We can generalize this, by using a method is_power_of_n, which takes two arguments, number and n, and which returns true if \(\text{number} = n^p\) for some non-negative integer p.

We define this function recursively:

• if number is less than 1, we return false.
• if number equals 1, we return true, as \(n^0 = 1\) for all \(n \neq 0\).
• if number % n is not 0, we return false, as we cannot evenly divide number by n.
• otherwise, we recurse calling is_power_of_n with number / n and n as arguments.

We also create a wrapper function is_power_of_2, which takes one argument number, and just calls is_power_of_n (number, 2).

Here is an example implementation in R:

is_power_of_n <- function (number, n) {
         if (number <  1)      {FALSE}
    else if (number == 1)      {TRUE}
    else if (number %% n != 0) {FALSE}
    else                       {is_power_of_n (number / n, n)}
}

is_power_of_2 <- function (number) {
    is_power_of_n (number, 2)
}

and an implementation in Tcl:

proc is_power_of_n {number n} {
    if {$number <  1} {return 0}
    if {$number == 1} {return 1}
    if {$number % $n} {return 0}
                       return [is_power_of_n [expr $number / $n] $n]
}

proc is_power_of_2 {number} {
    return [is_power_of_n $number 2]
}

What's rest is just a few lines of code which read in the data, checks that both numbers are even, calls the two functions we discussed above, and then prints the result. Note that if the greatest common divisor equals 1, this is a power of 2, but it's not a two friendly, so we check for that.

This is the Perl code tying it together:

while (<>) {
    my ($n, $m) = split;
    say (0), next if ($n % 2) || ($m % 2);
    my  $r = gcd $n, $m;
    say $r > 1 && is_power_of_2 ($r) ? 1 : 0
}

And here is how we do this in Lua:

for line in io . lines () do
    local _, _, n, m = line : find ("([0-9]+)%s+([0-9]+)")
    n = tonumber (n)
    m = tonumber (m)
    if n % 2 == 1 or m % 2 == 1 then
        print (0)
        goto continue
    end
    local r = gcd (n, m)
    if r > 1 and is_power_of_2 (r) then
        print (1)
    else
        print (0)
    end
    ::continue::
end

We have implementations in GNU AWK, Bash, bc, C, Go, Java, Lua, Node.js, Pascal, Perl, Python, R, Ruby, Scheme, and Tcl on GitHub.

A pair of numbers can only be two-friendly if both numbers are even. But the density of two-friendly numbers among pairs of even numbers is high, as shown in the plot below. In the plot below, for each pair of even numbers \(2 \leq m \leq n \leq 250\), we mark the pair if they are two-friendly.

Runtimes

We have compared the run times of the various implementations. We did this by creating a file with half a million pairs of random positive integers \(i, 1 \leq i < 2^{31}\). An average of several runs have been taken. We left out the results for Bash, as it took too long to run.

The C, Go, Java and Pascal implementations are compiled.