You are given 2 positive numbers,

`$m`

and`$n`

.Write a script to find out if the given two numbers are

Two Friendly.Two positive numbers, m and n are two friendly when \(\text{gcd }(m, n) = 2^p\) where \(p > 0\). The greatest common divisor (gcd) of a set of numbers is the largest positive number that divides all the numbers in the set without remainder.

```
Input: $m = 8, $n = 24
Output: 1
Reason: gcd(8,24) = 8 = 2^3
```

```
Input: $m = 26, $n = 39
Output: 0
Reason: gcd(26,39) = 13
```

```
Input: $m = 4, $n = 10
Output: 1
Reason: gcd(4,10) = 2 = 2^1
```

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.

Enter two positive integers, to check if they are two friendly:

First number: Second number:

First number: Second number:

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.

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.