# RogerBW's Blog

The Weekly Challenge 159: Farey and Moebius 07 April 2022

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

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.

You are given a positive number `\$n`.

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.