Farey’s in a twist
Weekly challenge 159 — 4 April 2022
Week 159: 4 Apr 2022
You are given a positive number $n. Write a script to generate the Möbius Number for the given number. Please refer to the Wikipedia page for more information.
Example 1: Input: $n = 5 Output: -1 Example 2: Input: $n = 10 Output: 1 Example 3: Input: $n = 20 Output: 0
I saved some time by using Math::Prime::Util
to generate the prime factors, but good old Eratosthenes’ sieve
would have worked just as well.
My solution first determines the count of prime factors, and assigns a provisional +1 or -1 to the result and then checks that no two prime factors are identical, and if so changes the result to 0.
I’m not sure that I’ve ever used a non-ASCII character in a subroutine name before, but I was pleased to see that Perl coped.
#!/usr/bin/perl # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge use v5.26; # The Weekly Challenge - 2022-04-04 use utf8; # Week 159 - task 2 - Möbius function use warnings; # Peter Campbell Smith binmode STDOUT, ':utf8'; use Math::Prime::Util 'factor'; möbius_function(5); möbius_function(10); möbius_function(20); möbius_function(46); möbius_function(47); möbius_function(48); sub möbius_function { my ($n, @pfs, $m, $pf, $prev); $n = shift; # get ordered prime factors @pfs = factor($n); # assume not a square multiple $m = 1 - (@pfs & 1) * 2; # check assumption unshift @pfs, 0; $m = $pfs[$_] == $pfs[$_ - 1] ? 0 : $m for 1 .. @pfs - 1; say qq[\nInput: \$n = $n]; say qq[Output: μ(n) = $m]; }
Input: $n = 5 Output: μ(n) = -1 Input: $n = 10 Output: μ(n) = 1 Input: $n = 20 Output: μ(n) = 0 Input: $n = 46 Output: μ(n) = 1 Input: $n = 47 Output: μ(n) = -1 Input: $n = 48 Output: μ(n) = 0
Any content of this website which has been created by Peter Campbell Smith is in the public domain