RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved generating more sequences. (Note that this is open until 10 April 2022.)

Task 1: Farey Sequence

You are given a positive number, $n.

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

In other words, all the fractions from 0 to 1 with integral numerators and denominators up to $n, in increasing order of value, in reduced forms (so you list 1/2 but not 2/4).

Of course some people might use floating point numbers for this. But floating point is bad and wrong. So instead I work out the LCM for the series of denominators (2 up to n), using the code from #155, then store each fraction as a pair of numbers, keyed by (value × lcm), which will always be an integer.

In JavaScript:

function farey (n) {

Calculate the lcm, just once.

    let l=lcmseries(2,n)

Initialise the hash that'll hold the fractions, and the array that'll hold the keys for later sorting.

    let d=new Map()
    let s=[]

Iterate denominators from 1 to n.

    for (let i=1;i <= n;i++) {

Calculate the multiplier value for this denominator.

        let m=l/i

Iterate numerators from 0 to denominator.

        for (let j=0;j <= i;j++) {

The value of this fraction, multiplied by the lcm.

            let k=m*j

If we haven't already seen this value, stick it in the hash, as a two-element array. (This takes care of the reduced forms; if n=4, 2/4 produces a k value of 2, but we already got a 2 for 1/2.) Also push the key value onto its list.

            if (!d.has(k)) {
                d.set(k,[j,i])
                s.push(k)
            }
        }
    }

Sort the key list. (Some languages, like this one, prefer to sort in place; for others I don't need a separate key list, and I just sort the keys of the hash and output in that order.)

    s.sort(function(a,b) {
        return a-b;
    })

Then return the hash values in order of the sorted key list.

    return s.map(i => d.get(i))
}

Kotlin has a Pair class, and Raku has Rat for storing fractions without the hazards of floating point, but otherwise I just use two-element arrays.

Task 2: Moebius Number

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.

Which comes down to: looking through the list of prime factors, if there are any squares or higher powers, the result is 0; otherwise it's +1 if the number of prime factors is even, -1 if it's odd.

Now obviously I could take a short cut by exiting early from the prime factorisation algorithm, but primefactors is useful library code, so I'll lose a little efficiency by calculating them in full and then analysing the result. (I did make the improvement to this algorithm I mentioned back in 155.)

In Perl (reusing the standard genprimes of course):

sub primefactor {
  my $n=shift;
  my %f;
  my $m=$n;
  foreach my $p (@{genprimes(int(sqrt($n)))}) {
    while ($m % $p == 0) {
      $f{$p}++;
      $m=int($m/$p);
      if ($m == 1) {
        last;
      }
    }
  }
  if ($m > 1) {
    $f{$m}++;
  }
  return \%f;
}

Then the actual Möbius analysis is nearly trivial:

sub moebius {
  my $n=shift;
  my $z=0;
  foreach my $v (values %{primefactor($n)}) {
    if ($v>1) {
      return 0;
    }
    $z++;
  }
  if ($z % 2 == 0) {
    return 1;
  }
  return -1;
}

Full code on github.