Peter
Peter Campbell Smith

Two are friendly and
Fibonacci combos

Weekly challenge 136 — 25 October 2021

Week 136: 25 Oct 2021

Task 1

Task — Two friendly

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 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.

Examples


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

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

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

Analysis

I did not submit a solution at the time, but have written this later.

Step 1 is to find the gcd of $m and $n. Of course there is a module that will do that, but simply looping down from the smaller of $m and $n and checking whether $m % 2 and $n % 2 are both zero will find it quickly even if the numbers are quite large.

Then I generated powers of 2 successively until one was >= $gcd; if it is equal then the gcd is a power of 2 and if not then it isn't.

Try it 

Try running the script with any input:



example: 32



example: 48

Script


#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-10-25
use utf8;     # Week 136 - task 1 - Two friendly
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

two_friendly(8, 24);
two_friendly(26, 39);
two_friendly(4, 10);
two_friendly(1, 1);
two_friendly(458752, 720896);
two_friendly(128, 128);

sub two_friendly {
    
    my ($m, $n, $gcd, $j, $p, $g);
    ($m, $n) = @_;
    
    # get gcd
    for ($gcd = $m > $n ? $n : $m; $gcd > 0; $gcd --) {
        last if ($m % $gcd == 0 and $n % $gcd == 0);
    }
    
    # check friendliness
    $g = 1;
    $p = 0;
    while ($g < $gcd) {
        $g = $g * 2;
        $p ++;
    }
    
    # show results
    say qq[\nInput:  \$m = $m, \$n = $n];
    say qq[Output: ] . ($g > $gcd ? qq[0 as gcd = $gcd] :
        qq[1 as gcd = $gcd = 2 ** $p]);
}

Output


Input:  $m = 8, $n = 24
Output: 1 as gcd = 8 = 2 ** 3

Input:  $m = 26, $n = 39
Output: 0 as gcd = 13

Input:  $m = 4, $n = 10
Output: 1 as gcd = 2 = 2 ** 1

Input:  $m = 1, $n = 1
Output: 1 as gcd = 1 = 2 ** 0

Input:  $m = 458752, $n = 720896
Output: 1 as gcd = 65536 = 2 ** 16

Input:  $m = 128, $n = 128
Output: 1 as gcd = 128 = 2 ** 7

 

Any content of this website which has been created by Peter Campbell Smith is in the public domain