Two are friendly and
Fibonacci combos
Weekly challenge 136 — 25 October 2021
Week 136: 25 Oct 2021
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.
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
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.
#!/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]); }
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