Peter
Peter Campbell Smith

Farey’s in a twist

Weekly challenge 159 — 4 April 2022

Week 159: 4 Apr 2022

Task 2

Task — Möbius number

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.

Examples


Example 1:
Input: $n = 5
Output: -1

Example 2:
Input: $n = 10
Output: 1

Example 3:
Input: $n = 20
Output: 0

Analysis

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.

Try it 

Try running the script with any input:



example: 42

Script


#!/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];
}

Output


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