Squarefree Is Only One Side Of the Story

Wherein we learn that hard or easy, sometimes there’s only one row to hoe

THE WEEKLY CHALLENGE – PERL & RAKU #159 — Task 2


Going from Giraud to Moebius, I twisted the strip; changed dimensions. I was the same and yet someone else. Moebius is the result of my duality.

Jean Giraud


Moebius Number

Submitted by: Mohammad S Anwar

You are given a positive number $n.

Write a script to generate the Moebius Number for the given number. Please refer to wikipedia page for more informations.

Example 1:
Input: $n = 5
Output: -1
Example 2:
Input: $n = 10
Output: 1
Example 3:
Input: $n = 20
Output: 0

ANALYSIS

Named after August Ferdinand Möbius, of monogonal strip fame, the Möbius function serves as a classifier for number factorization: whether a number is squarefree, and, if so, whether is has an odd or even number of prime factors.

The squarefree numbers, that we visited in PWC150, are numbers whose prime decompositions have no squared values, or powers of 2. This in turn leads to the conclusion that the list of prime factors can only contain unique values, as no factor is doubled and any factor repeated more than two times will also contains the second power within that higher exponent. What we are left with, then, is that the only remaining permissible exponent is 1.

The Möbius function is defined according to a collection of rules for all positive integers:

  • If a number is not squarefree it in given the Möbius number 0.
  • If the number is 1 it is given the Möbius number 1.
  • If the number is squarefree and greater than 1, is will have a list of distinct prime factors, and if this list has an even number of values the Möbius number is 1, and if odd the number -1. This can also be expressed as (-1), with n the number of prime factors.

So what do we do with this function?

Number throry, as a matter of course, is not traditionally known for its practical application — an observation made acknowledging a notable turnabout to that trend with the applicability of prime number theory to modern cryptographic techniques. However within the field of number theory the Möbius function is well explored and often encountered. Well, often enough at least.

Summing over divisors is something commonly studied in the discipline, and there the Möbius function is thus most often seen as a component of what is known as the Möbius inversion formula, which describes a multiplicative relationship between certain pairs of functions in this domain. The inversion function can be generalized into arbitrary abelian groups in group theory and partially-ordered sets in order theory.

One property of the Möbius function is that the meta-analytical function describing the average order of the Möbius function can be shown to be equivalent to the prime number theorum. From this proof we can infer that the average order is 0, meaning that there are equal numbers of squarefree numbers with even and odd numbers of factors as the scale tends towards infinity.

Which is an interesting observation, if you’re into that sort of thing.

METHOD

PERL 5 SOLUTION

To compute the Möbius function we’ll need a list of primes up to and possibly including the target value. From this we can start working upwards from 2 checking the squares of the primes for divisibility. As the squares grow quickly, this easily and quickly can filter any non-square free, or squareful, numbers, giving the output 0.

However when working upwards through our list of primes, we check them for divisibility themselves, only passing those that pass the test to be further tested for their squares. Doing it this way allows us to count the prime factors as we go. All of the primes are tested this way unless the number is not square free, which short-circuits the loop early.

After testing, then, we know the number of prime factors, and raise -1 to this power to compute the Möbius number.

A special case is made for the input value of 1.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

my $input = shift @ARGV ;
say moebius_function( $input ) if defined $input;

sub moebius_function ( $input ) {
    return 1 if $input == 1;    
    
    our @primes = (2,3);  ## shared with subroutine
    my  $count = 0;

    add_next_prime() while $primes[-1] <= $input;
    
    ## check squarefree
    for (@primes) {
        if ($input % $_ == 0) {
            return 0 if $input % $_ ** 2 == 0 ;
            $count++;
        }
    }

    ## return based on odd or even count
    return (-1)**$count;
    
    sub add_next_prime ( ) {
    ## adds the next prime to external sequence
        
        my $candidate = $primes[-1] ;
        CANDIDATE: while ( $candidate += 2 ) {
            my $sqrt_candidate = sqrt( $candidate );
            for my $test ( @primes ) {
                next CANDIDATE if $candidate % $test == 0;
                last if $test > $sqrt_candidate;
            }
            push @primes, $candidate;
            last;
        }
    }
}

Raku Solution

Rewriting in Raku always seems to streamline things so well. Here a single iteration filters out the distinct prime factors for the target value, which are then checked for divisibility by their squares. If we make it through, the Möbius number is calculated by raising -1 to the length of the prime factor list.

unit sub MAIN ( $num = 302 ) ;

sub moebius ($num) {
    my @primes = (2..$num).grep: { .is-prime && $num %% $_ };

    return 0 if @primes.grep: $num %% *² ;
    return (-1)**@primes.elems ;
}


The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s