Welcome to Weekly Challenge #159.

159 is a Woodall Number, which is any natural number of the form Wn = n * 2n - 1.

I don’t normally explain my titles, but this time I feel it’s justified, as Task #2 is about Möbius numbers, introduced by mathematician August Ferdinand Möbius.

I, however, immediately thought about Jean Giraud, the artist who collaborated on such works as Alien, Tron, The Abyss, Space Jam and the unmade version of Dune from Alejandro Jodorowsy. His work appeared in a comics magazine called Métal Hurlant, which is published in America as Heavy Metal.

He is known by the pseudonym Mœbius, with a ligature instead of the umlaut. Close enough for a title, I think

TASK #1 › Farey Sequence

Submitted by: Mohammad S Anwar
You are given a positive number, $n.

Write a script to compute Farey Sequence of the order $n.

One of the examples of a Farey Sequence is that of 4.

0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1

The easiest thought is to take every denomerator (1 through 4) and then every numerator (0 through denominator), and list them in order, but then you’d see something like.

0/1, 0/1, 0/2, 0/2, 1/4, 1/3, 1/2, 2/3, 2/3, 3/4, 1/1, 2/2, 3/3, 4,4

To control this, I used eval. I almost never use eval because I am usually dealing with input that isn’t my own. I know I’m doing safe things, like avoiding zero in denominator, so this is fine.

Show Me The Code!

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };

use Carp;
use Getopt::Long;

my $n = 6;
GetOptions( 'number=i' => \$n, );
croak 'Out of range' if $n < 1;

farey($n);

sub farey ( $i ) {
    my %farey;
    for my $d ( 1 .. $i ) {
        for my $n ( 0 .. $d ) {
            my $k = eval( $n / $d );
            $farey{$k} = qq{$n/$d} unless defined $farey{$k};
        }
    }
    my $output = join ', ', map { $farey{$_} } sort { $a <=> $b } keys %farey;

    say <<"END";
Input:  \$n = $i
Output: $output.
END
}
$ ./ch-1.pl -n 4
Input:  $n = 4
Output: 0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1.

$ ./ch-1.pl -n 5
Input:  $n = 5
Output: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.

$ ./ch-1.pl -n 6
Input:  $n = 6
Output: 0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1.

$ ./ch-1.pl -n 7
Input:  $n = 7
Output: 0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1.

$ ./ch-1.pl -n 8
Input:  $n = 8
Output: 0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1.

TASK #2 › 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.

From Wikipedia:

For any positive integer n, define μ(n) as the sum of the primitive nth roots of unity. It has values in {−1, 0, 1} depending on the factorization of n into prime factors:

  • μ(n) = +1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n has a squared prime factor.

So, we need to find all the prime factors and determine if any of them are repeated, because that means you have a squared prime factor. From there, we determine if there’s an even number of prime factors. All fairly easy.

So I decided to throw a complication. The function is the Möbius function and is written as μ(n). I just had to use utf8 so I can have μ and ö in variable and function names.

Wikipedia puts the 1 through 50 and the corresponding value of μ(n) into five tables of ten numbers each, and my output follows that format, but of course it would be easy to copy the Getopt::Long part of Task #1 over to get specific digits.

(I mostly know μ because that is the term for the add9 chords that appear all over Steely Dan songs, but it was also part of the quality control of gene sequences in a previous job.)

Show Me The Code!

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw{ say postderef signatures state };
no warnings qw{ experimental };

use utf8;

for my $n ( 1 .. 50 ) {
    my  = möbius($n);
    print join " ", "  " , map { sprintf '%2d', $_ } $n, $μ;
    say '' if $n % 10 == 0;
}

sub möbius ($n) {
    my @primes = prime_factors($n);
    my %primes;

    # has squared prime factor
    map { $primes{$_}++ } @primes;
    for my $k ( keys %primes ) {
        return 0 if $primes{$k} > 1;
    }

    # square-free
    my $p = scalar @primes;
    return $p % 2 == 0 ? 1 : -1;
}

sub prime_factors( $n ) {
    my @primes;
    my $nn = $n;
    for my $i ( 2 .. $n ) {
        while ( $nn % $i == 0 ) {
            $nn = $nn / $i;
            push @primes, $i;
        }
    }
    return @primes;
}
$ ./ch-2.pl
    1  1    2 -1    3 -1    4  0    5 -1    6  1    7 -1    8  0    9  0   10  1
   11 -1   12  0   13 -1   14  1   15  1   16  0   17 -1   18  0   19 -1   20  0
   21  1   22  1   23 -1   24  0   25  0   26  1   27  0   28  0   29 -1   30 -1
   31 -1   32  0   33  1   34  1   35  1   36  0   37 -1   38  1   39  1   40  0
   41 -1   42 -1   43 -1   44  0   45  0   46  1   47 -1   48  0   49  0   50  0

If you have any questions or comments, I would be glad to hear it. Ask me on Twitter or make an issue on my blog repo.